cs.FLNov 9, 2026

The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary

Authors: Nicklas Nidhögg

Organizations: Independent Researcher

Abstract

Berglund and van der Merwe formalized byte-pair encoding and bounded how far an appended string can change a tokenization, leaving the converse open: how far can a string prepended on the left change it, which dictionaries make that ripple infinite, and can it be computed efficiently when finite? We answer all three for every dictionary. The origin radius, how far a prepend can change covering spans, is decided with radius certificates by a product of two runs of the automaton that guesses the final tokens, in time polynomial in the dictionary written out, and it is infinite exactly when one periodic word has two canonical tilings with no common boundary. Under their ordering condition it is infinite exactly when some rule (t, t) finds its two copies adjacent at its own stage, and such a rule makes any dictionary infinite. A finite radius makes every window of a width read off the radii have a cut, and the radius is finite exactly when such cuts are dense. The token machine completes for every dictionary, and the tokenization is subsequential, extending what Berglund, Martens and van der Merwe proved for proper ones under one pass per rule. A streaming tokenizer emits after every symbol exactly the tokens that no continuation changes, in polynomial time, answering a question of Dalirrooyfard and Ye. Boundedness of the label measure, the edit distance of the token sequences, is decided for every dictionary in polynomial time as well, and under the ordering condition the largest distance one edit causes over dictionaries of m rules lies asymptotically between m^2/10 and m^2/2. GPT-2's merge table carries 244 effective self-pairs, so its origin radius is infinite from the forty-second merge on, and that of cl100k, o200k and Llama 3 from their first. Every measured number is its program's output, and what is not executed is named.

Figures & tables

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Theoretical Analysis of Byte-Pair Encoding

    Nov 13, 2024László Kozma, Johannes VoderholzerByte-Pair EncodingSubword Tokenization

  2. The Price of Token Boundaries: Compression Certificates and Prediction

    Sep 26, 2026Yuhao Du, Shunian ChenToken CompressionToken Efficiency

  3. Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

    Nov 5, 2026Kundan Baliga, Aiden Xie, Aditya ByjuByte-Pair EncodingLossless Data Compression