Component-Weighted Centroid Search for Exact Incremental BPE

arXiv:2609.40016v1 Announce Type: cross 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(nlog 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.

Source: arXiv cs.LG | 2026-10-01