Reproduction: Incremental BPE Tokenization
Jiang & Gong, ICML 2026 (OpenReview ZbWgrDzCQo · arXiv 2605.30813) — independent Python reimplementation, evidence-first, every number from a committed protocol-compliant run
Claim 1 · Monotonic Path Property
Reproduced (empirically)
Zero violations across exhaustive candidate×history cross-products, per-byte upward-closure checks, 200 random dictionaries, and real 50k-vocab corpus runs.
Claim 2 · Algorithm design
Partially reproduced
Composition verified end-to-end at real scale. Missing §5.3 / §6.2 mechanisms: their absence measured (tail latency linear in depth; eager 34× vs paper's ~10%).
Claim 3 · 3.13× drop-in speedup
Equivalence reproduced · speedup untestable
Token-for-token identical to HF tokenizers over the paper's English corpus recipe. The speedup sits behind a measured 52× Python-vs-Rust constant — pre-declared scope limit.
Claim 4 · Pathological robustness
Reproduced (era-appropriate baseline)
Ours flat (slope 0.99); tiktoken 0.8.0 quadratic (2.04–2.08, incl. CL100K). Finding: current tiktoken fixed the quadratic upstream (1.14–1.16).
0.987ours, log-log slope, real vocab ('a'*n)
2.041tiktoken 0.8.0 on CL100K (quadratic)
114,399tokens, zero divergences vs HF tokenizers
5.7×our Python beats old Rust tiktoken @200 kB pathological
44 / 2,126tests / subtests, green in CI