PaperlayerView exact revision on arXiv

Source-linked AI summary

Component-Weighted Centroid Search for Exact Incremental BPE

Harshit Verma, Rex Ying

arXiv:2609.40016v1cs.DScs.LG

TL;DR

Exact incremental BPE needs to preserve canonical tokenization state after every appended byte, but the prior centroid-search approach takes O(log^2 t) worst-case time. The paper weights ordered intervals by the recursive component they select, reducing worst-case updates to O(log t) while preserving exact tokens; a reachable family separates the two search schemes, whereas ordinary-vocabulary runs show no average-throughput gain.

  • Problem

    Exact incremental BPE must retain canonical tokenization state after every appended byte, and the existing centroid-search method has two logarithmic factors.

    Source: §1 · p. 1

  • Method

    The method weights each ordered interval by the size of the recursive component it selects, replacing only local search within the existing centroid framework.

    Source: §1 · p. 1, §2 · p. 2

  • Results

    Worst-case updates fall from O(log^2 t) to O(log t) with the same exact token, and a reachable family separates Θ(log^2 t) from Θ(log t) probes.

    Source: §2 · p. 2, §3 · p. 3, §5 · p. 4

  • Takeaways & Limitations

    The improvement provides worst-case protection rather than a general tokenizer speedup on ordinary vocabularies.

    Source: §5 · p. 4, §4 · p. 4

    The separation concerns the original count-balanced and proposed component-weighted CST searches, not every exact incremental BPE algorithm.

    Source: §5 · p. 4

Abstract

from arXiv · show

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 $\Theta(\log^2 t)$ probes on a reachable update, while the weighted search uses $\Theta(\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.

1 Introduction

Exact incremental BPE preserves tokenizer state after each appended byte, while the prior centroid-search framework incurs two logarithmic factors. The paper changes only local search, weighting intervals by the recursive component they select, and establishes both telescoping charges and a reachable bad case for count-balanced search.

1 Introduction

  • Exact incremental BPE retains state after every appended byte, unlike streaming interfaces that use bounded delay or repair session appends with widening and fallback.The section distinguishes this exact every-prefix framework from related streaming and repair approaches.Source: §1 · pp. 1–2
  • The prior centroid search has two logarithmic factors, with the second arising from balancing each local search by interval count.The existing method finds the longest canonical suffix and searches its suffix-successor tree using centroid decomposition.Source: §1 · p. 1
  • Weighting each interval by the size of its remaining recursive component charges local search to component-size drops, while leaving matching, validity intervals, and centroid decomposition unchanged.Large remaining subproblems are encountered early, and the resulting charges telescope.Source: §1 · p. 1
  • The paper establishes that local charges telescope even across gaps and failed searches, and that a bad count-balanced case arises in a normalized BPE dictionary on a reachable update.The construction is checked against an offline heap implementation.Source: §1 · p. 1

2 Component-weighted centroid search

Component-weighted centroid search performs ordered interval lookup according to the size of the recursive component selected. Its local ratio bounds telescope across centroid levels, yielding exact O(log t) updates while preserving BPE semantics.

2 Component-weighted centroid search

  • At a centroid with component size m, each downward interval is weighted by the size of the component it selects; disjoint children give total weight at most m − 1.Each recursive child has at most half the current component’s size.Source: §2 · p. 2
  • An alphabetic tree chooses pivots whose strict left and right sides each have at most half the current weight, preserving the ordered interval map, including gaps.Queries left of a pivot interval go left, queries at or beyond its right endpoint go right, and queries inside it return that interval.Source: §2 · p. 2
  • Successful interval lookup takes at most 1 + ⌈log2(W/wi)⌉ probes, while unsuccessful lookup takes at most 1 + ⌈log2 W⌉.An empty list fails in O(1) time; the local bounds follow from halving the remaining weight.Source: §2 · p. 2
  • Component-weighted CST search returns the same exact last token in O(log t) worst-case time per appended byte, or O(n log t) time over an n-byte stream.Successful-move charges telescope over component-size drops; a failed downward lookup is terminal, and validity tests and upward transitions cost O(1) per level.Source: §2 · p. 2
  • The weighted tree evaluates the same ordered intervals as before, so the substitution preserves exact BPE semantics.The automaton and history operations are unchanged.Source: §2 · p. 2

3 A reachable separation under BPE semantics

A normalized proper BPE family realizes a reachable update that follows recursively nested heavy components. On this family, count-balanced search takes Θ(log^2 t) probes, while component-weighted search takes Θ(log t).

3 A reachable separation under BPE semantics

  • For every k ≥ 1, a normalized proper BPE dictionary over a fixed byte alphabet has a reachable update with t = Θ(k2^k), where count-balanced search uses Θ(k^2) = Θ(log^2 t) probes and weighted search uses Θ(k) = Θ(log t).The CST follows recursively nested heavy components under the stated strict-half centroid convention.Source: §3 · p. 3
  • The recursive construction adds a new root with the previous tree as its heavy child and leaf children, making that heavy child exactly half the new tree’s size.Under the construction’s centroid convention, descent proceeds only into a child strictly larger than half the component.Source: §3 · p. 3
  • At each level, the validity intervals have many unit weights and one heavy weight at the extreme end, so count balancing spends Θ(j) probes while weighted search tests the heavy branch first.The ordered intervals are Uq−1 through Ub, with weights [1, …, 1, 2j−1].Source: §3 · p. 3
  • A reserved left-context merge makes the longest suffix invalid on the final append while leaving the next suffix valid, forcing descent through the heavy components.Delimiter-protected binary macros extend the executable byte-label construction to an unbounded fixed-alphabet family.Source: §3 · p. 3
  • For executable instances with t = 2^k, the pinned predecessor convention uses exactly k(k + 1)/2 + 1 probes versus k for the weighted tree.This exact count is implementation-specific; the asymptotic separation only requires the selected interval to remain extreme.Source: §3 · p. 3

4 Evaluation

Evaluation tests constructed worst-case examples and ordinary vocabularies using a shared exact incremental tokenizer implementation. Probe counts follow the predicted scaling on constructed examples, while ordinary-corpus queries are shallow and the weighted method is slower overall in the tested runs.

4 Evaluation

  • At t = 8192, component-weighted search reduces constructed-example probes from 92 to 13, while median final-update time changes from 10.18 µs to 9.73 µs.The probe trend matches the predicted quadratic-versus-linear dependence on k; interval search is only part of an update.Source: §4 · p. 4
  • On GPT-2, RoBERTa-base, and GPT-NeoX-20B across English and Rust code, queried degree never exceeds five, and weighted search reduces conditional p99 probes from five to two.Complete-update time is 0.3%–13.1% slower, so the paper claims no average-throughput improvement; retained memory rises from about 38.3–38.5 MB to 44.6–44.7 MB.Source: §4 · p. 4
  • Both methods return the same token after every corpus byte and pass 1,470 retained-state audits against offline BPE.The constructed examples use t = 16 through 8192; ordinary-vocabulary runs use one million bytes each of English and Rust code without model-specific pretokenization, normalization, or special-token handling.Source: §4 · pp. 3–4
  • A fixed-threshold hybrid can scan small lists and use weighted search only for larger lists, retaining the O(log t) worst-case bound while avoiding weighted-search overhead on sampled ordinary-corpus queries.This is proposed as a way to avoid overhead where the original search is already shallow.Source: §4 · p. 4

5 Scope and conclusion

Within Jiang and Gong’s exact every-prefix framework, component-weighted search reduces worst-case update time without changing the returned token. The improvement is worst-case protection, not a general tokenizer speedup.

5 Scope and conclusion

  • Large interval-list degrees did not occur in the six ordinary-corpus runs, so the separation is a worst-case guarantee rather than an average-speed result.The comparison concerns the original count-balanced and proposed component-weighted CST searches, not every exact incremental BPE algorithm.Source: §5 · p. 4
  • Executable examples are limited by packed implementation fields, while the fixed-alphabet construction provides an unbounded mathematical family.The construction’s scope is the comparison between the two CST searches.Source: §5 · p. 4
  • Worst-case update time falls from O(log^2 t) to O(log t) without changing the returned token.The result is scoped to Jiang and Gong’s exact every-prefix framework.Source: §5 · p. 4

A Formal model and weighted point location

The weighted point-location tree keeps the ordered interval map while balancing pivots by the recursive component sizes they select. Its search-depth bounds and telescoping charges support an O(log t) search cost across the CST traversal.

A Formal model and weighted point location

  • Under the inherited word-RAM model, each append returns the exact final canonical token and stores a token/backpointer chain from which the full sequence is recoverable.The complete sequence is not recopied after every prefix.Source: A Formal model and weighted point… · p. 6
  • For positive ordered weights, a pivot can leave at most half the total weight on either strict side; recursive construction preserves interval order and branches by the query’s position.Queries left of the pivot interval go left, queries at or beyond its right endpoint go right, and queries inside it return that interval.Source: A Formal model and weighted point… · p. 6
  • The weighted tree returns an interval exactly when the query lies in it, and returns failure for gaps between stored intervals.Ordered, disjoint intervals make the pivot comparisons safe at each recursive step.Source: A Formal model and weighted point… · p. 6
  • An interval of weight w_i in a list of total weight W has depth at most 1+⌈log2(W/w_i)⌉, while an unsuccessful search has depth at most 1+⌈log2 W⌉.The successful-search bound follows as recursive subtree weight halves on each descent.Source: A Formal model and weighted point… · p. 6
  • Component-size weights make successful-search log-ratio charges telescope; validity tests, upward moves, additive costs, and one terminal miss add O(log t).The weight of an interval selecting the next component is that component’s size, and successful downward transitions are a subset of the halving CST transitions.Source: A Formal model and weighted point… · p. 6
  • Prefix sums and recursive weighted-pivot selection build the tree in O(d log d) time and O(d) temporary space, with linear-size preorder storage.The prototype has a larger constant factor.Source: A Formal model and weighted point… · p. 7

B Reachable direct-byte construction

The direct-byte construction realizes a reachable heavy-component path in the centroid search tree using a normalized proper BPE dictionary. Its interval ordering makes count-balanced search costly while the weighted index selects the heavy interval at each level.

B Reachable direct-byte construction

  • The construction uses distinct adjacent byte pairs, a terminal byte, and reserved left context to build target suffixes and trigger the reachable update.The dictionary includes all bytes, required block tokens, target suffixes, and the context token.Source: B Reachable direct-byte construction · p. 7
  • Three priority phases build canonical blocks, add reserved context, and then create target suffixes.The blocks are canonical before context or target rules apply, and each target suffix U_p is canonical with parent U_π(p).Source: B Reachable direct-byte construction · pp. 7–8
  • The suffix-successor tree contains exactly U_0 through U_n−1 among canonical vocabulary tokens that are suffixes of S.The terminal byte occurs only at the end of S, while the reserved context byte does not occur in S.Source: B Reachable direct-byte construction · p. 8
  • At level j, intervals appear as U_q−1 through U_b, with unit weights except for the last, heavy interval of weight 2^j−1.The heavy interval is extreme in the ordered list, so count-balanced search needs Θ(j) probes while the weighted pivot selects it at the root.Source: B Reachable direct-byte construction · p. 8
  • On stream 255S, the final append invalidates U_0 through the context rule, leaving U_1 as the true last token and forcing descent through the heavy components.The raw-suffix match initializes the search at U_0; the untouched suffix beginning at position one canonically forms U_1.Source: B Reachable direct-byte construction · p. 8
  • The pinned count-balanced search uses k(k + 1)/2 + 1 probes, while the weighted index uses k.The final miss contributes two count-balanced probes; the weighted index reads one record per successful level and at the miss.Source: B Reachable direct-byte construction · p. 8

C Fixed-alphabet unbounded encoding

The fixed-alphabet encoding replaces raw byte labels with delimiter-protected binary macros. It preserves the direct construction's execution and turns its separation into a bound in terms of maximum token length.

C Fixed-alphabet unbounded encoding

  • Delimiter-protected macros prevent code-building tokens from crossing macro boundaries, so each macro becomes its unique token before simulated rules apply.The code alphabet is {0, 1, #, $, !, @}.Source: C Fixed-alphabet unbounded encoding · p. 9
  • The macro simulation reproduces the direct construction’s token-level execution and preserves normalized properness.The construction transfers canonical blocks and suffixes, interval order, and reachability.Source: C Fixed-alphabet unbounded encoding · p. 9
  • Because log t = Θ(k), the executable Θ(k^2)-versus-Θ(k) probe separation converts to the fixed-alphabet Θ(log^2 t)-versus-Θ(log t) statement of Proposition 1.Source: C Fixed-alphabet unbounded encoding · p. 9

D Implementation and evaluation details

The evaluation times corpus and final-update workloads and separately records interval probes and endpoint comparisons. It reports search-tail and construction/memory measurements, alongside a fixed-threshold hybrid.

D Implementation and evaluation details

  • Runs used an Apple M4/Rust release build and pinned Gutenberg/Rust inputs; probes count interval reads, while endpoint comparisons are separate.The generator checks canonicality, successor edges, suffix sets, interval and tree properties, the forced update, and offline BPE equality.Source: D Implementation and evaluation details · pp. 9–10
  • 92 and 14 endpoint comparisons occur on the t = 8192 update; p99 endpoint comparisons fall from five to four in every corpus.Table 1 reports search-conditional tails over one million updates.Source: Table 1 · p. 10, D Implementation and evaluation details · p. 10
  • Table 2 pairs count-balanced and component-weighted values; probes are conditional on interval search, while time measures the complete update.The table covers ordinary-vocabulary results over one million updates per row.Source: Table 2 · p. 10
  • Peak heap was 46.4–46.8 MB for binary and 52.7–53.0 MB for weighted.Table 3 compares separate-process initialization; memory is decimal MB.Source: D Implementation and evaluation details · p. 10, Table 3 · p. 10
  • All sampled public-vocabulary queries take the linear path in the fixed-threshold hybrid, which is an engineering option rather than an asymptotic contribution.A fixed threshold preserves the O(log t) theorem because each CST level pays only O(1) for the scan.Source: D Implementation and evaluation details · p. 10
Loading 2609.40016v1…