# Component-Weighted Centroid Search for Exact Incremental BPE

arXiv: https://arxiv.org/abs/2609.40016 · HTML: https://mlsanity.com/paper/2609.40016/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 9 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 4 of 4)

- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [TokTier: Exact Stateful CPU+GPU Tokenization for Agentic LLM Serving](https://mlsanity.com/paper/2607.29678/) (2026)
- [Incremental BPE Tokenization](https://mlsanity.com/paper/2605.30813/) (2026)

## Abstract (arXiv)

Exact incremental BPE maintains the canonical tokenization state after every appended byte. The recent algorithm of Jiang and Gong (2026) does this in O(log2 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(log2 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.