Objective vs. Search: Decomposing What Makes a Good Tokeniser

AI summary

Overview

Research area: Natural Language Processing — subword tokenisation and its effect on language model quality.

Technical level: Intermediate. The central idea (a 2×2 design space) is intuitive, but the paper includes formal proofs of merge-gain and deletion-cost formulas, which require comfort with information theory and probabilistic modelling.

Scope: The paper isolates which of two tokeniser design choices — the optimisation objective or the search procedure — actually drives downstream language modelling performance, by constructing the two missing algorithms needed for a fair comparison.

What This Paper Is About

Modern language models almost all use one of two tokenisers: BPE, which greedily merges characters to compress a corpus, or UnigramLM, which prunes tokens to maximise unigram log-likelihood. These two differ in two ways at once — what they optimise and how they search — so prior comparisons cannot say which difference causes the observed performance gaps. The paper builds the two missing algorithms that complete the 2×2 grid, then trains and evaluates language models with all four to attribute effects to the correct cause.

Key Contributions

1. A clean factorisation of tokeniser learning. The authors formalise a tokeniser learning algorithm as a pair of independent choices: an objective (corpus compression vs. unigram log-likelihood) and a search procedure (bottom-up merging vs. top-down pruning). They show that BPE and UnigramLM each confound the two axes.

2. Two new algorithms completing the design space. BottomUpLL mirrors BPE's greedy merge procedure but scores merges by log-likelihood gain; TopDownComp mirrors UnigramLM's pruning procedure but scores deletions by compression cost. Together with BPE and UnigramLM these fill all four cells.

3. Efficient scoring rules for both objectives. Lemma 1 gives BPE's standard "merge the most frequent pair" rule as an exact compression gain. Lemma 2 gives an exact, incrementally computable log-likelihood merge gain that makes BottomUpLL practical. Lemmas 3 and 4 give local-replacement approximations for top-down deletion costs under log-likelihood and compression respectively.

4. A controlled empirical study across settings. Language models are trained with tokenisers from all four algorithms, varying model size, vocabulary size, and domain (English-only vs. multilingual), and evaluated on bits-per-byte and on BLiMP grammaticality judgements.

Main Findings

• Search procedure dominates bits-per-byte, not the objective. Bottom-up tokenisers achieved lower bits-per-byte than their top-down counterparts in nearly every condition, holding the objective fixed: BPE beat TopDownComp, and BottomUpLL beat UnigramLM. The how of optimisation mattered more than the what.

• Grammaticality tells a different story. On BLiMP, neither the objective nor the search procedure separated the four tokenisers consistently. The BPB ranking did not transfer to this task.

• The objective matters at small vocabulary sizes. In small-vocabulary regimes, likelihood-based tokenisers outperformed compression-based ones, suggesting the objective is not irrelevant — just usually overshadowed.

• BottomUpLL behaves qualitatively differently from BPE. Analysis of its merge-gain formula shows it favours token pairs that co-occur more systematically than chance (a pointwise-mutual-information-like criterion), rather than merely the most frequent pair — connecting it to likelihood-guided merging ideas such as WordPiece.

• Bottom-up gains are exact; top-down costs are only approximate. Deleting a token under a top-down scheme can reshuffle the segmentation of unrelated strings, and under log-likelihood creates a circular dependency between counts, segmentation, and model parameters. The authors note this asymmetry is inherent to top-down search, not an implementation choice, and flag it as a limitation.

• Both axes matter. The overall conclusion is that neither objective nor search procedure alone explains tokeniser quality; each contributes depending on the regime.

Methodology in Plain English

The authors start by defining a tokeniser precisely as three things: a vocabulary, an encoder that segments text into tokens, and a decoder that reverses it losslessly. They then note that the ideal tokeniser — the one minimising either objective over all possible vocabularies — is computationally intractable (the compression variant is provably NP-hard), so every real algorithm is a heuristic. That heuristic has two separable parts: the objective function and the search strategy.

BPE takes the objective "produce as few tokens as possible" and the strategy "start from characters and greedily merge symbol pairs." UnigramLM takes "maximise unigram log-likelihood" and the strategy "start from a huge vocabulary and greedily prune tokens." To break the confound, the authors swap the halves: BottomUpLL keeps BPE's merge machinery but scores each candidate merge by how much it improves unigram log-likelihood; TopDownComp keeps UnigramLM's pruning machinery but scores each candidate deletion by how much it worsens compression.

A practical obstacle is that scoring every candidate by re-running the full objective is far too slow. The paper derives closed-form or approximation formulas so scores can be updated incrementally after each merge or deletion, keeping both new algorithms tractable. For bottom-up algorithms these formulas are exact; for top-down algorithms they rely on assuming only locally affected strings change segmentation, which is an approximation.

With four tokeniser-learning algorithms in hand, the authors train language models from scratch on identical data and hyperparameters, changing only the tokeniser. Evaluation uses bits-per-byte — an information-theoretic measure normalised per character so it is comparable across vocabularies — plus BLiMP, a suite of grammaticality minimal pairs. Experiments sweep vocabulary size, model size, and whether the training data is English-only or multilingual.

Why This Matters

Impact on research. Widely cited results — for example, that BPE-trained models outperform UnigramLM-trained ones — have been read as evidence that compression is the better objective. This paper shows that reading is wrong: the advantage comes mostly from the bottom-up search, not the compression objective. That reframes a common claim in the tokenisation literature and gives the field a cleaner experimental template for future algorithm comparisons.

Real-world applications:

• Multilingual and low-resource model design. Vocabulary allocation across languages is a persistent pain point; knowing whether to prioritise a better objective or a different search procedure directs limited engineering effort.
• Context-length and inference cost. Compression directly affects how many tokens a document becomes, and therefore how much text fits in a context window and how many forward passes a request costs.
• Domain-specific tokenisers. Code, legal text, and biomedical text all have distinctive subword structure; the 2×2 framework gives practitioners a principled menu rather than a two-way default choice.
• Small-vocabulary and on-device models. The finding that the objective matters most at small vocabularies is directly relevant to compact models where vocabulary size is constrained by memory.

Industry relevance. Tokenisers are chosen early and are expensive to change once a model is trained, since changing the vocabulary invalidates the embedding matrix. A clear answer about which design axis drives performance reduces the risk of locking in a suboptimal choice at the start of a multi-month training run.

Future Directions

• Resolving the BPB-versus-BLiMP tension. The two evaluations disagree, and it remains unclear which is the better proxy for what practitioners actually care about — perplexity-like compression, or downstream task quality. A broader battery of extrinsic evaluations would clarify this.
• Improving top-down search. Since bottom-up consistently wins and top-down costs are only approximated, an open question is whether better deletion-cost approximations — or exact ones — would close the gap and restore top-down methods' competitiveness.
• Moving beyond the 2×2 grid. The framework treats objective and search as binary choices, but there is room for hybrid objectives, alternative search strategies (e.g., non-greedy or beam-based), and tokenisers with constraints such as byte-level fallback or character coverage guarantees.
• Scaling the study. The results cover limited model sizes and one multilingual setting; whether the search-procedure dominance holds at frontier scale, across many language families and writing systems, is untested.

Target Audience

NLP researchers studying tokenisation, subword modelling, or language model pretraining pipelines will get the most from this paper, particularly those who cite or build on BPE-versus-UnigramLM comparisons. It is also valuable for machine learning engineers who must choose or train a tokeniser for a production model, and for graduate students looking for a clear worked example of how to identify and eliminate a confound in an empirical comparison.

Authors’ abstract

Two dominant tokenisation algorithms are used by modern language models: byte-pair encoding (BPE) and UnigramLM. These differ along two orthogonal axes: their optimisation objective (compression vs. log-likelihood) and their search procedure (bottom-up merging vs. top-down pruning). Existing comparisons confound these axes, making it unclear whether their observed differences stem from what is being optimised vs. how it is being optimised. We disentangle the two by introducing two new tokenisation algorithms that complete this 2x2 design space: BottomUpLL, a bottom-up likelihood-based tokeniser, and TopDownComp, a top-down compression-based tokeniser. We train language models with tokenisers produced by each algorithm, varying: model size, vocabulary sizes, and domain (English-only vs. multilingual). Evaluating models on bits-per-byte, we find that the search procedure -- not the objective -- is the dominant factor: bottom-up tokenisers consistently achieve lower bits-per-byte in most settings. Evaluating models on the BLiMP task, however, shows no consistent relationship between design choice and performance. Overall, our results disentangle the effect of tokeniser design choices on language modelling performance, offering concrete guidance for their more principled construction.