The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary
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
| result | hypothesis | cost | statement |
|---|---|---|---|
| origin radius decided and computed, with certificates | every dictionary | polynomial | Theorem 3 |
| tail product of the token machine | every dictionary | polynomial in the machine | Corollary 1 |
| canonical adjacency, rationality | every dictionary | Theorem 2 | |
| right lookahead of symbols, subsequentiality | every dictionary | Theorem 4 | |
| streaming with zero delay | every dictionary | polynomial | Theorem 5 |
| pinned bytes | finite radius | Theorem 7 |
| verdict on the 484 proper dictionaries on two symbols, one to three rules | count |
|---|---|
| origin radius infinite | 370 |
| radius 1 | 2 |
| radius 2 | 30 |
| radius 3 | 40 |
| radius 4 | 32 |
| radius 5 | 8 |
| bound | one edit, | substitution | prepended symbol | statement |
|---|---|---|---|---|
| upper | Theorem 15 | |||
| upper | Theorem 17 | |||
| exact, no effective self-pair | Theorem 19 | |||
| lower | Theorem 16 , Proposition 16 | |||
| lower, | Proposition 17 | |||
| lower, | Theorem 20 |
| merges | measure |
|---|---|
| 4, 8, 12 | origin radius 1, 3, 3; mirrored constant 1, 2, 2 |
| 32 | origin radius 3; token machine of 131,245 states at a tail of 3 |
| 1 to 6 | origin radius 1 |
| to 41 | origin radius 3; mirrored constant 3 at 41 |
| 100 | infinite under 3 of 32 symbols, at most 6 under the rest |
| 200 | infinite under 6 of 53, at most 7 |
| table | merges | ordered prefix | rules | effective | least effective |
|---|---|---|---|---|---|
| GPT-2 | 50,000 | 50,000 | 244 | 244 | merge 41, |
| cl100k_base | 100,000 | 100,000 | 305 | 305 | merge 0, two spaces |
| o200k_base | 199,742 | 199,742 | 513 | 513 | merge 0, two spaces |
| Llama 3 (rank-derived) | 127,066 | 127,066 | 454 | 454 | merge 0, two spaces |
| merges | states | |||||
|---|---|---|---|---|---|---|
| 41 | 49 | 4 | 2 | 4 | 2 | 3 |
| 100 | 120 | 5 | 4 | 5 | 4 | 5 |
| 200 | 269 | 8 | 6 | 8 | 5 | 10 |
| 400 | 638 | 14 | 10 | 14 | 10 | 11 |
| 800 | 1,452 | 19 | 17 | 19 | 17 | 13 |
| 1,600 | 3,287 | 28 | 22 | 28 | 22 | 15 |
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| rules | states, median | states, max | tail-count bound | product nodes / states 2 , worst |
| 1 | 11.5 | 12 | 13 | 0.10 |
| 2 | 17.0 | 53 | 85 | |
| 3 | 62.5 | 276 | 781 |
| result and program | execution |
|---|---|
| Lemma 6 path_maximum.py | Executed, the maximum is the ripple on every nonempty input to length eight of every product of the census, of the 4 dictionaries of this section and of the two-rule dictionary , 612,780 inputs over 982 products, and on the 42,392 of them whose path ends at a terminal contribution the ripple is , with negative on 36,916. |
| Lemma 6 | Across those products, none of the 55,587 nodes whose two runs have the same suffixes, pending tokens and freeze points reaches a contribution. |
| the identity of the last tokens lemma_c_exact.py lemma_c_check.py | Executed, the identity holds on all 1,980,528 cases and on 2,000 seeded cases over 400 dictionaries, 169 of them failing the ordering condition. |
| Corollary 1 and Lemma 22 check_tail_product.py | Executed on 1,096 dictionaries, the census, the 4 dictionaries outside it and 608 that fail the ordering condition, its 2,447 verdicts and radii per prepended symbol equal those of the overlap graph of Section 7 , every one of the 748 positive finite radii is attained by an input of exactly that length, and each of the 1,016 certificates with its exit path has ripple equal to its length at every from zero to eight. |
| Corollary 1 and Lemma 22 | On the same dictionaries the quotient puts the 102,997 retained suffixes into 7,320 classes and the reachable pairs of the product fall from 195,958 to 12,967, with the same verdict and radius on all 2,447 and every attaining input and certificate replayed. |
| Corollary 1 and Lemma 22 | On all 1,431 finite radii both bounds hold and lie below , and the quotient’s lies below . |
| result and program | execution |
|---|---|
| Proposition 3 mirrored_census.py | On the two-rule dictionary the mirrored constant is 1 and the origin radius 2, both attained by prepending to . |
| Proposition 3 | Each dictionary yields one verdict per prepended symbol, so the census’s 484 dictionaries give 968 products. |
| Proposition 3 | On the 502 bounded verdicts among them, the computed constant equals the executed supremum over every input to length ten on every one. |
| Proposition 3 | The constant lies strictly below the origin radius on 182 of them, and on 84 of the 114 dictionaries bounded under both symbols. |
| Proposition 3 | Along every one of the 466 unbounded certificates, pumped one to five times, the mirrored quantity strictly deepens. |
| Proposition 3 | By execution as well as by the inequality, the two constants are infinite together. |
| result and program | execution |
|---|---|
| Lemma 9 general_canonical.py | Grouped by their tokenizers, the proper dictionaries of one to four rules on two symbols fall into 4,737 classes, and in each every dictionary has at least rules and symbols of operands and attains either minimum exactly when every one of its rules fires, as 6,934 of them do, at least one in every class. |
| Corollary 3 general_canonical.py | Every pair of classes, 11,217,216 of them, is told apart by a distinguishing word tokenized under the first member of each, the 4,289 pairs of classes with the same canonical words by the concatenation of a canonical pair of one class only and the rest by a canonical word of one class only, 99,069 tokenizations in all, while the members of a class agree with its first member on every concatenation of two of their canonical words, in 151,224 tests. |
| Corollary 3 | On 5,074 pairs of classes whose canonical words have at most five symbols, the 4,003 such pairs with the same canonical words and a seeded sample of the others, the candidates of least length are exactly the shortest words told apart by brute force, 7,833 in all, each of at most symbols and of exactly on 224 of the pairs, and where the canonical words agree each is two tokens under both, split at different places. |
| Corollary 3 | On and its reverse the canonical words are , , and for both, while is a canonical pair of the first only, and , tokenized by the first and by the second, tells them apart, and , tokenized and , is a shortest such word, of symbols. |
| Corollary 3 | On the family of the corollary at to and at , and 1,024, both dictionaries are ordered with the same canonical words, the longest of symbols, is tokenized as the corollary states, and the rules number exactly , at most , while a brute force over every word of at most symbols at to 5 finds it the only shortest word that the two tokenize differently. |
| Corollary 4 check_origin_graph.py direct_graph_check.py | Executed, the overlap graph returns the frozen product’s verdict and constants on all 968 census products, and the token machine’s and the mirrored constant’s on the same. |
| result and program | execution |
|---|---|
| Theorem 12 selfpair_census.py check_four_rules.py beyond_the_census.py | On the census the criterion, the overlap graph and the cycle of Theorem 1 agree on every dictionary, as the 370 of 484 with infinite radius are exactly the dictionaries with an effective self-pair. |
| Theorem 12 | 372 census dictionaries carry a rule , and the 2 whose rule is inactive are bounded at radius two. |
| Theorem 12 | Beyond the census the criterion agrees with the overlap graph on the 9,792 ordered ones of the 9,820 proper dictionaries of four rules on two symbols, 8,030 of all of them infinite, and, as an observation outside the theorem, on the 28 that are not ordered. |
| Theorem 12 | On three symbols it agrees on 600 ordered proper dictionaries of four to eight rules, and on 600 dictionaries of three to eight rules that satisfy clause (b) and fail clause (a). |
| Theorem 12 | The last class is the one the theorem’s hypothesis admits and the census does not contain. |
| Theorem 14 check_compact_witness.py | Executed on every finite ordered dictionary of one to four rules on two symbols, 1,904 of them, the attaining input cut at its ripple keeps both constants. |
| result and program | execution |
|---|---|
| Theorems 15 and 16 amplification.py label_bound.py check_fibonacci_bound.py | Executed, the family attains at to nine. |
| Theorems 15 and 16 | The two token sequences the proof names are asserted against Definition 1 , and the distance is taken from the full edit-distance table. |
| Theorems 15 and 16 | Between the two bounds the record is four tiers, one per rule count. |
| Theorems 15 and 16 | Every proper ordered dictionary of one, two and three rules on two symbols is run against every input to lengths twelve, thirteen and eleven and every single symbol edit of it, reaching 3, 5 and 7. |
| Theorems 15 and 16 | The three-rule dictionaries are run again against every run to sixty-four, reaching 7. |
| Theorems 15 and 16 | Every proper ordered one-symbol dictionary of four rules is run against every run to one hundred and twenty and every single edit that keeps its runs within that length, reaching 9. |
| result and program | execution |
|---|---|
| Theorem 18 check_label_graph.py check_edit_graph.py | Executed, the decision finds every product of the census bounded, 968 of them. |
| Theorem 18 | On every one the exact supremum equals the brute-force maximum over every input to length ten. |
| Theorem 18 | Every ordered table of every universe is bounded. |
| Theorem 18 | Among the fixtures on three symbols 6 products are unbounded, the two six-rule dictionaries and the source paper’s Example 2 among them, and 2 of 200 seeded tables. |
| Theorem 18 | Every certificate replays at pump counts to thirty-two with growing distance. |
| Theorem 18 | All 9,820 four-rule tables are bounded. |
Byte-Pair Encoding
Byte-Pair Encoding (BPE) builds subword vocabularies by repeatedly merging frequent adjacent units to represent text efficiently for language models.
See all 26 papers