Original title: Objective vs. Search: Decomposing What Makes a Good Tokeniser Authors: Ahmet Can Yüce, et al. arXiv: 2609.19145
A Neglected Question
Despite a decade of LLM architecture evolution—MoE, linear attention, state space models—one component has barely changed: tokenization. Nearly all LLMs still use BPE (Byte Pair Encoding) or UnigramLM to split text into subword units, both treated as "solved problems" since 2015.
The paper's authors ask a deceptively simple question: what exactly differs between BPE and UnigramLM?
The two algorithms actually differ on two dimensions simultaneously:
- Objective function: BPE optimizes compression rate (greedily merging the most frequent byte pairs); UnigramLM optimizes corpus log-likelihood (via expectation-maximization)
- Search procedure: BPE is bottom-up (starting from a small vocabulary and merging); UnigramLM is top-down (starting from a large vocabulary and pruning)
- BottomUpLL: bottom-up search + likelihood objective. Like BPE, it merges from character level, but each merge is chosen by "which merge maximally increases corpus log-likelihood" rather than "which byte pair is most frequent."
- TopDownComp: top-down search + compression objective. Like UnigramLM, it prunes from a large vocabulary, but by "which token removal hurts compression least" rather than "which hurts likelihood least."
- "MoE beats dense"—sparsity, or number of experts?
- "RLHF beats SFT"—the RL algorithm, or the preference data?
- "Chain-of-thought beats direct answering"—the reasoning steps, or just more compute?
- RL algorithms: how much of actor-critic vs PPO comes from objectives (clipped vs full surrogate) vs. search (on-policy vs off-policy)?
- Optimizers: Adam vs SGD—momentum estimation, or learning rate scheduling?
- Architectures: Transformer vs Mamba—attention, or sequence modeling approach?
- Too few downstream tasks: only BPB and BLiMP; no machine translation, code generation, or long-context understanding
- Limited corpus coverage: 4 corpora cannot support cross-lingual conclusions
- Variants untested: BPE-dropout's stochastic merging may shift the trade-off
- No token distribution analysis: differences in token frequency distributions across algorithms—which might explain the inconsistent BLiMP results—were not examined
All prior research conflated these dimensions—claims like "BPE suits low-resource languages better" never isolated whether the objective or the search was responsible.
The 2x2 Factorial Design
The core contribution is a minimal factorial experiment:
| | Bottom-up search | Top-down search | |--|----------------------|---------------------| | Compression objective | BPE (classic) | TopDownComp (new) | | Likelihood objective | BottomUpLL (new) | UnigramLM (classic) |
The paper fills in the two missing corners:
Swapping the objective while holding search constant attributes differences to the objective; swapping search while holding objective constant attributes them to the search procedure.
Results: Search Crushes Objective
Experiments ran all 4 combinations on 4 corpora and 4 vocabulary sizes, measuring bits-per-byte (BPB, lower is better) and BLiMP (grammar judgment, higher is better).
BPB findings: bottom-up search (BPE, BottomUpLL) consistently achieves lower BPB than top-down search (TopDownComp, UnigramLM) across all corpora and vocabulary sizes. The objective's effect is inconsistent—likelihood wins at large vocabularies, compression at small ones.
BLiMP findings: no consistent pattern at all. Neither dimension shows a statistically significant main effect; results are corpus-dependent.
Two implications:
1. The old "BPE vs UnigramLM" debate asked the wrong question. The real difference lies in the search procedure, not the objective. A decade of attributing BPE's compression advantage to greedy merging may have been misplaced—bottom-up search itself is the key. 2. Grammar ability is decoupled from tokenizer choice. Tokenizer selection has no systematic effect on BLiMP, suggesting its impact on downstream grammar tasks has been exaggerated.
Why Bottom-Up Wins
The authors offer an intuition: bottom-up search has "information memory."
Bottom-up builds from characters, "solidifying" each frequent byte pair into a token—accumulating vocabulary tailored to patterns that actually occur in the corpus. Top-down starts from a large vocabulary and discards tokens—an act of "forgetting" where you don't know a discarded token's importance until it's gone.
Bottom-up vocabularies are "data-driven" (only frequent patterns survive); top-down vocabularies are "hypothesis-driven" (assume all possible tokens, then falsify one by one). Data-driven wins on compression—but not on grammar, suggesting tokenizer "quality" is multidimensional: good BPB does not mean good grammar coverage.
A Missed Design Space
The 2x2 reveals a design space neglected for ten years. All tokenizer improvements targeted the objective dimension—better compression goals, likelihood approximations, regularization. The search dimension was untouched.
The paper hints that bottom-up search + likelihood objective (BottomUpLL) may be an overlooked "third path": it combines bottom-up compression advantage with the probabilistic semantics of likelihood, achieving the lowest BPB at large vocabulary sizes. The authors honestly note this conclusion is exploratory—4 corpora and 4 vocabulary sizes cannot support strong claims; validation needs more languages and tokenizer-sensitive tasks like machine translation and code generation.
What This Means
1. The Power of Factorial Thinking
The most memorable lesson may be methodological: split one seemingly singular variable into two orthogonal dimensions, then use a 2x2 design to separate contributions. Many "X beats Y" conclusions conflate multiple dimensions:
Every "X beats Y" hides a 2x2 design space waiting to be decomposed.
2. Search Procedure as a Neglected Dimension
An algorithm's search procedure and objective function are independent dimensions but usually conflated. The same question echoes elsewhere:
3. "Solved Problems" Usually Aren't
Tokenization was considered solved for a decade; this paper found a neglected dimension hiding inside—and that dimension matters more than the assumed main one. It joins a wave of work re-examining foundational assumptions: TwinKV (attention weights ≠ causal contribution), MIST (necessity and sufficiency barely correlate), omission blindness (LLM judges can't detect missing content). "Solved" problems often weren't solved—just forgotten.
Honest Limitations
An Analogy: The Knife and the Sharpening
Think of the tokenizer as a kitchen knife and model training as chopping. For a decade we argued "which knife chops better"—the BPE brand or the UnigramLM brand. But the knives differ on two independent axes: the blade shape (objective) and the sharpening direction (search)—and the sharpening direction matters more. A well-sharpened dull blade can outperform a badly sharpened sharp one.
The deeper meaning: a tool's "quality" is multidimensional, but we usually compare on only one dimension.
Conclusion
This paper does something rare: a minimal 2x2 experiment overturns a decade-old assumption without proposing a new algorithm or chasing SOTA. It reveals a neglected dimension—the search procedure—and shows it matters more than the presumed main dimension. Not all progress comes from charging forward; sometimes it comes from looking back, un-conflating variables, and re-examining "solved problems."
The newly completed 2x2 design space may spark new tokenizer research: bottom-up search with new objectives, top-down search with new pruning strategies, or entirely different search paradigms. A decade-old "solved problem" may only now be starting to be truly understood.
---
Paper link: arxiv.org/abs/2609.19145