Metraipolis › archive › dc_e671cb062fa1

Component-Weighted Centroid Search for Exact Incremental BPE — arXiv:2609.40016

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.40016
License (as archived): CC0-1.0
Archived: 2026-10-07T13:47:50.465Z
SHA-256 of the archived text: 0aa3428e834478215b44cdb6f0feade8e959048c7bfe10cc4fb26a66eaa27bc9
Stable URL of this page: https://metraipolis.com/documento/dc_e671cb062fa1

How to cite

Component-Weighted Centroid Search for Exact Incremental BPE — arXiv:2609.40016 — arXiv (en), https://arxiv.org/abs/2609.40016 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e671cb062fa1 (Metraipolis archive dc_e671cb062fa1, sha256 0aa3428e834478215b44cdb6f0feade8e959048c7bfe10cc4fb26a66eaa27bc9)

BibTeX

@misc{dce671cb062fa1,
  title = {Component-Weighted Centroid Search for Exact Incremental BPE — arXiv:2609.40016},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40016},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e671cb062fa1; sha256 0aa3428e834478215b44cdb6f0feade8e959048c7bfe10cc4fb26a66eaa27bc9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40016. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LG).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.40016 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:18:10.686Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).