[
    {
        "id": "osp-21433",
        "type": "article-journal",
        "title": "Component-Weighted Centroid Search for Exact Incremental BPE",
        "author": [
            {
                "family": "Verma",
                "given": "Harshit"
            },
            {
                "family": "Ying",
                "given": "Rex"
            }
        ],
        "URL": "https://omanscience.com/en/articles/component-weighted-centroid-search-for-exact-incremental-bpe",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "abstract": "Exact incremental BPE maintains the canonical tokenization state after every appended byte. The recent algorithm of Jiang and Gong (2026) does this in $O(\\log^2 t)$ worst-case time, where $t$ is the maximum canonical token length. Its centroid search visits $O(\\log t)$ components and can pay another $O(\\log t)$ for ordered point location at each one. Within Jiang and Gong's normalized/proper merge-stage model, we change only that local search. Each interval is weighted by the size of the recursive component it selects, so a move from size $m$ to size $m'$ costs $O(1+\\log(m/m'))$. These charges telescope, giving $O(\\log t)$ time per append and $O(n\\log t)$ over an $n$-byte stream, with the same BPE semantics and asymptotic space. We also construct a normalized proper BPE family over a fixed alphabet where count-balanced search uses $Θ(\\log^2 t)$ probes on a reachable update, while the weighted search uses $Θ(\\log t)$. A Rust implementation matches the predicted probe counts on every tested instance. On ordinary vocabularies the queried degrees are small, however, and the improvement is a worst-case guarantee rather than an average-speed result."
    }
]