Objective vs. Search: 2×2 Experiment Shows Tokenizer Search Process Beats Objective Function

Forum topic · ✨步子哥 · 2026-09-17

Summary

A new arXiv paper (2609.19145) decomposes the two classic subword tokenization algorithms—BPE and UnigramLM—into two independent dimensions: the objective function (compression vs. log-likelihood) and the search procedure (bottom-up merging vs. top-down pruning). Using a 2×2 factorial design with two novel hybrids, BottomUpLL (bottom-up search + likelihood objective) and TopDownComp (top-down search + compression objective), the authors isolate each dimension's contribution across 4 corpora and 4 vocabulary sizes. Results show that search direction consistently matters: bottom-up methods achieve lower bits-per-byte regardless of objective, while the objective's effect is inconsistent and depends on vocabulary size. On the BLiMP grammaticality benchmark, no systematic effect was found for either dimension, suggesting grammar performance is decoupled from tokenizer choice. The findings challenge a decade of attributions in the BPE vs. UnigramLM debate and highlight factorial designs as an underused methodology in AI research, pointing to an overlooked tokenizer design space.

Original title: Objective vs. Search: Decomposing What Makes a Good Tokeniser Authors: Ahmet Can Yüce, et al. arXiv: 2609.19145

An Overlooked Question

Despite the proliferation of LLM architectures (MoE, linear attention, state-space models), tokenization has barely changed. Nearly all LLMs use BPE or UnigramLM, both treated as "solved" since 2015. The paper asks a simple question: what actually differs between BPE and UnigramLM?

The two algorithms differ simultaneously along two dimensions:

Objective function: BPE optimizes compression (greedy merges of frequent byte pairs); UnigramLM optimizes corpus log-likelihood via EM.
Search procedure: BPE is bottom-up (merging from a small vocabulary); UnigramLM is top-down (pruning from a large vocabulary).

Prior work conflates these dimensions—claims like "BPE is better for low-resource languages" were never decomposed.

A 2×2 Factorial Design

| | Bottom-up search | Top-down search | |--|---------------------|-------------------| | Compression objective | BPE (classic) | TopDownComp (new) | | Likelihood objective | BottomUpLL (new) | UnigramLM (classic) |

BottomUpLL: merges bottom-up like BPE, but picks the merge that maximizes log-likelihood gain rather than frequency.
TopDownComp: prunes top-down like UnigramLM, but removes the token least harmful to compression rather than to likelihood.

Holding one dimension fixed while varying the other cleanly attributes differences to objective or search.

Results: Search Dominates

Experiments covered 4 corpora × 4 vocabulary sizes, measuring bits-per-byte (BPB) and BLiMP.

BPB: bottom-up search (BPE, BottomUpLL) consistently yields lower BPB than top-down (TopDownComp, UnigramLM) across all corpora and vocab sizes. The objective effect is inconsistent: likelihood wins at large vocabularies, compression at small ones.

BLiMP: no consistent pattern—neither dimension has a statistically significant main effect; results are corpus-dependent.

Implications:

1. The old "BPE vs. UnigramLM" debate asked the wrong question—the difference lies in search, not objectives. 2. Grammar ability (BLiMP) appears decoupled from tokenizer choice.

Why Bottom-Up Wins

The authors offer an intuition: bottom-up search has "information memory"—each merge consolidates a real, frequent pattern into a dedicated token, producing a data-driven vocabulary. Top-down pruning "forgets" tokens without knowing their importance, yielding a hypothesis-driven vocabulary. This advantage is clear on BPB but disappears on BLiMP, showing tokenizer "quality" is multidimensional: optimal compression ≠ grammatical coverage.

Notably, BottomUpLL may be an overlooked third path—combining bottom-up compression advantages with likelihood semantics—though the authors stress this conclusion is exploratory.

Broader Lessons

1. The power of factorial thinking: many "X beats Y" claims conflate multiple dimensions—MoE vs. dense (sparsity vs. expert count?), RLHF vs. SFT (algorithm vs. preference data?), CoT vs. direct answers (reasoning vs. extra compute?). Each hides a 2×2 design space. 2. Search as an overlooked dimension: similar confusions exist in RL (objective vs. on/off-policy), optimizers (momentum vs. schedule), and architectures (attention vs. sequence modeling). 3. "Solved" problems are usually not solved: like recent papers revisiting foundational assumptions, this shows a neglected dimension can matter more than the assumed main one.

Honest Limitations

Few downstream tasks: only BPB and BLiMP—no machine translation, code generation, or long-context evaluation.
Limited corpus coverage: 4 corpora cannot support cross-lingual conclusions.
No BPE-dropout variants tested, which may shift the objective/search trade-off.
No analysis of token frequency distributions, which might explain the inconsistent BLiMP results.

Closing

The paper achieves something rare: a minimal 2×2 experiment that overturns a decade-old assumption. No new SOTA—just a revealed, overlooked dimension (search procedure) that matters more than the assumed main one. The newly completed design space—bottom-up search with new objectives, top-down search with new pruning strategies—may kickstart a new wave of tokenizer research.