pipette
ENEnglish

Component-Weighted Centroid Search for Exact Incremental BPE

Harshit Verma, Rex Ying

Preprint

En palabras de los autores

Exact incremental BPE maintains the canonical tokenization state after every appended byte. The recent algorithm of Jiang and Gong (2026) does this in worst-case time, where is the maximum canonical token length. Its centroid search visits components and can pay another 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 to size costs . These charges telescope, giving time per append and over an -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 probes on a reachable update, while the weighted search uses . 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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Accepted at AXIOM 2026, a NeurIPS 2026 Workshop. 10 pages