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

Nicklas NidhöggarXiv 2026 · arXiv

Byte-Pair Encoding (BPE) is the unsung hero of the Large Language Model (LLM) revolution. It’s the process that turns raw text into the "tokens" that models like GPT-4 and Llama 3 actually process. While we often treat tokenization as a static pre-processing step, it’s actually quite dynamic: changing a single character at the start of a document can theoretically change every single token that follows.

In this paper, Nicklas Nidhogg explores this "left ripple" effect. While previous research established how far changes propagate when you append text, Nidhogg provides the first comprehensive look at what happens when you prepend or edit text on the left.

TL;DR

This paper proves that the "left ripple" of BPE—how far a change at the start of a string propagates to the right—is efficiently decidable and computable for any dictionary. Surprisingly, it reveals that popular tokenizers like GPT-2 and Llama 3 have an "infinite" origin radius, meaning a single character change at the beginning could theoretically shift token boundaries across an infinitely long document.

What Problem Does This Paper Address?

The core challenge is incremental tokenization. If you are typing in a text editor or streaming text from an AI, you don’t want to re-tokenize the entire document every time a character is added. To avoid this, we need to know the "lookbehind" or "ripple" distance: how far can a local change propagate?

Previous work by Berglund and van der Merwe showed that adding text to the right has a strictly bounded effect. However, they left the "left ripple" (prepending text) as an open question, noting that it appeared to be infinite in some cases. Nidhogg’s paper fills this gap by defining how to measure this ripple, identifying which dictionaries cause it to be infinite, and providing efficient algorithms to compute these bounds.

Methods

The author introduces several formal tools to analyze BPE dynamics:

  • The Overlap Graph: A novel construction that uses a "spelling automaton" to track how two different tokenizations of the same suffix (one with a prefix added, one without) diverge. This graph allows the origin radius to be computed in polynomial time.
  • Origin Radius ($R_L$): This measures the furthest position in a string where a token's starting point (its "origin") changes due to a prepend.
  • Effective Self-Pair Criterion: For dictionaries following a standard "ordering condition" (where rules producing a token precede rules consuming it), Nidhogg identifies a simple rule: if a dictionary contains a rule that merges two identical tokens (like (t, t) -> tt), and that rule actually fires, the ripple radius is infinite.
  • Streaming Tokenizer: The paper describes a polynomial-time algorithm for a "zero-delay" tokenizer that emits tokens as soon as it's certain they won't be changed by any possible future text.

Datasets

The research evaluates these methods using:

  1. A Census of 484 small dictionaries to test the limits of BPE logic.
  2. Production Merge Tables: The actual tokenization dictionaries used by GPT-2, Llama 3, and OpenAI’s cl100k_base and o200k_base.

Key Insights and Ideas

  • LLM Tokenizers are "Infinite": The most striking finding is that almost all major production tokenizers have an infinite origin radius. For example, GPT-2’s ripple becomes infinite after its 42nd merge rule. Llama 3 and OpenAI’s newer tokenizers are infinite from the very first rule because they start by merging two spaces (" ").
  • The Self-Pair Trigger: The "aha moment" for the infinite ripple is the self-pair rule. If you have a rule to merge two spaces, and you prepend a space to a long string of spaces, every single token boundary in that string will shift.
  • Label Distance vs. Origin Ripple: The paper distinguishes between the origin (where tokens start) and the label (what the tokens are called). Even if the origin ripple is infinite (boundaries shift), the actual sequence of token labels might only change by a small amount (the "label distance").
  • Decidability: Despite the complexity of BPE, the question of whether a dictionary has a finite or infinite ripple is not just a guess—it is a mathematically "certified" property that can be checked quickly.
This table summarizes the main results, showing that properties like the origin radius and label measure boundedness are decidable in polynomial time for every dictionary.

Key Results

  • GPT-2 Analysis: The paper computes the exact "right lookahead" for GPT-2 as 119 symbols. This means that while the left ripple is infinite, the right ripple is quite short.
  • Quadratic Bounds: Under the standard ordering condition, the maximum "label distance" (how many tokens change) caused by a single edit is quadratic ($m^2$) relative to the number of rules $m$.
  • Efficiency: The proposed algorithms for deciding the origin radius and label distance run in polynomial time relative to the size of the dictionary.

Limitations and Future Work

  • Pre-tokenizer Modeling: Most production systems use a "pre-tokenizer" (like splitting by whitespace) before BPE. This paper treats the BPE dictionary in isolation. While pre-tokenizers naturally "reset" the ripple, the author notes that pre-tokenized pieces can still be arbitrarily long.
  • Computational Complexity: While the algorithms are polynomial in the size of the written-out dictionary, BPE tokens can grow exponentially in length relative to the number of rules. The author points to a "compact companion" paper that addresses costs for compressed dictionaries.
  • Leading Constants: While the label distance is proven to be $\Theta(m^2)$, the exact leading constant (currently bounded between $1/10$ and $1/2$) remains an open mathematical question.

Summary updated

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.
BibTeX
@misc{nidhogg2026left,
  author = {Nicklas Nidhögg},
  title = {{The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary}},
  year = {2026},
  eprint = {2611.13061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13061},
}
Figure