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:
- A Census of 484 small dictionaries to test the limits of BPE logic.
- 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.
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