acceptodds
Under review as a conference paper at ICLR 2027

Certifying The Near-Optimality Of Byte-Pair Encoding On Natural Language Corpora

17 views

Abstract

Language models operate on tokens, contiguous strings of bytes drawn from a finite token alphabet. The token alphabet is typically chosen so that a training corpus is represented with as few tokens as possible. Byte-pair encoding (BPE) is the most widely used procedure for inducing a token alphabet from data. It greedily merges tokens until a pre-determined vocabulary size is reached. The goal of this paper is to construct a scalable optimization algorithm that certifies how close to optimal a token alphabet, such as the one BPE learns, is on training corpora of realistic size. Our algorithm is based on dual decomposition, and it bounds the gap between standard tokenizers and the optimal token alphabet. To do so, we cast three previously proposed, declaratively specified tokenization objectives—direct vocabulary selection, optimal pair encoding, and optimal merge sequences—as integer linear programs (ILPs). For the first two formulations, dual decomposition allows us to exploit the fact that subproblems of the ILPs can be solved with dynamic programming. On ClimbMix—a common LM pretraining dataset—BPE's token count on held-out data is at most above the DVS optimum, with the gap shrinking to as vocabulary size increases, and BPE remains to faster. These results show that, under the evaluated constraints, BPE achieves near-optimal compression at substantially lower computational cost.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Tokenization, Language Models, BPE

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_9D78OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper computes optimality bounds for byte-pair encoding (BPE) vocabularies. Tests show small gaps under restricted conditions.

Critical strengths

The solver handles large corpora with less memory than the tested baseline. This makes certificate computation more practical.

Critical weaknesses

The held-out guarantee lacks a reported held-out lower bound. Tests also limit tokens to five bytes. They use Viterbi instead of BPE’s merge-order encoder. These choices limit the conclusion.

Questions for authors

Did you compute a held-out lower bound? Do the results hold with longer tokens and BPE’s merge-order encoder?

Reviewer_vsoQOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

In this paper the authors investigate the near-optimality of Byte-Pair Encoding (BPE), a widely used greedy tokenization algorithm, in minimizing the number of tokens required to represent natural language corpora under a fixed vocabulary budget. The authors consider three optimization formulations: Direct Vocabulary Selection (DVS), Optimal Pair Encoding (OPE), and Optimal Merge Sequences (OMS), which progressively impose additional constraints on vocabulary construction and tokenization. They formulate all three problems as integer linear programs (ILPs), establishing a hierarchy of optimal token counts.

The main contribution is a scalable optimization framework based on dual decomposition for DVS and OPE. By exploiting the separability of string segmentation through Viterbi dynamic programming and coordinating vocabulary selection using Lagrangian multipliers, the proposed approach computes lower bounds on the optimal token count and feasible upper bounds. This enables the authors to certify how close BPE is to the optimal vocabulary without solving the underlying combinatorial optimization problem exactly. The framework also incorporates an active-set strategy to improve memory efficiency and scalability.

The authors evaluate their approach on the ClimbMix corpus across vocabulary budgets ranging from 4,096 to 65,536 optional tokens. The results show that BPE's token count is at most 3.45% above the DVS optimum under the evaluated candidate restrictions, with the certified gap decreasing to 1.80% at the largest vocabulary budget. The proposed dual-decomposition methods also demonstrate substantially better memory scalability than a monolithic LP solver, although BPE remains 2.5–5.3 times faster. Additional experiments examine solver correctness on smaller instances, held-out compression performance, and the effect of vocabulary size. Overall, the paper provides theoretical and empirical evidence that BPE achieves near-optimal token-count compression under the studied conditions, while introducing a scalable framework for certifying tokenization quality.

Critical strengths

The authors discuss a well-motivated and important research question by investigating how close greedy BPE is to optimal tokenization. They present a unified mathematical framework, which formulates DVS, OPE, and OMS as ILPs and establishes their relationship through a hierarchy of optimal token counts. The theoretical analysis provides correctness guarantees for these formulations, while the proposed dual-decomposition algorithm exploits exact Viterbi-based segmentation and global vocabulary selection to compute valid optimality bounds. This combination of rigorous formulation and scalable optimization constitutes a substantive technical contribution.

The paper provides compelling empirical evidence supporting the practical value of its approach. It provides certificates quantifying the maximum possible improvement under the evaluated constraints, showing that BPE is within 3.45% of the DVS optimum, with the bound tightening to 1.80% at larger vocabulary sizes. The experiments also demonstrate substantial memory-efficiency improvements over monolithic LP optimization, enabled in part by the active-set strategy, while comparing runtime and solution quality against relevant baselines. These results make the theoretical contribution practically meaningful and offer useful insights into the effectiveness of greedy BPE.

Critical weaknesses

The experiments limit optional tokens to observed substrings of two to five bytes that occur at least twice, and the authors acknowledge that restricting candidate strings can change the optimum. Consequently, the reported bounds establish near-optimality only under the evaluated candidate restrictions, rather than for unrestricted vocabulary selection. This limits the scope of the paper's central conclusion that BPE is near-optimal on natural-language corpora.

The paper's main certification experiments evaluate token counts using minimum-token Viterbi segmentation for every vocabulary, including BPE's, rather than BPE's actual merge-order encoding. This isolates vocabulary quality but does not directly establish the same guarantee for the operational BPE tokenizer.

The main experiments focus on token-count minimization on ClimbMix under a specific pretokenization pipeline, without establishing that the results generalize across substantially different corpora (like, FineWeb-2) or languages. Also, the paper does not evaluate the downstream language model performance.

Questions for authors

The candidate-token space is restricted to substrings of two to five bytes that occur at least twice. Could the authors clarify how this restriction affects the near-optimality certificates and whether similar bounds hold when longer or less frequent tokens are included?

Do you expect the near-optimality findings to generalize beyond ClimbMix and the specific pretokenization pipeline?

Could the authors clarify whether the reported near-optimality guarantee also holds on held-out data, or only on the training corpus?

Reviewer_y1pKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper designs a scalable optimization algorithm to determine how close to optimal a learned token vocabulary is on a realistic training corpus. Here, an optimal alphabet will represent a corpus with as few tokens as possible. Establishing a lower bound on token counts can tell us how much improvement over BPE is possible on a given corpus. The authors approach this using three tokenization optimization problems from previous literature: direct vocabulary selection (DVS), optimal pair encoding (OPE), and optimal merge sequences (OMS). Each optimization problem allows different choices that influence the corpus token count that can be achieved. The authors cast DVS, OPE, and OMS into integer linear programming (ILP) problems and provide a dual decomposition for DVS and OPE that allow those problems to be solved efficiently with dynamic programming. On ClimbMix, the authors find that BPE's token count on held out data is at most 3.45% above the optimum they compute with DVS while being much faster. This indicates that BPE is near-optimal compression while being a much more practical tokenization algorithm.

Critical strengths

I think that this paper articulates an important problem: how much worse is BPE than the optimal tokenization algorithm at the same vocabulary size? More importantly, can this gap be computed efficiently on a large corpus? This can help inform tokenization research in many ways: for example, at a given vocabulary size, one characterize how much improvement is possible over BPE and whether exploring alternative algorithms is worthwhile.

The paper's technical contribution is impressive; the authors cast three previous optimization problems as ILPs and present an efficient method for calculating lower bounds on token counts over large pretraining corpora.

The introduction is well-written and does a good job of explaining the paper's contributions.

Critical weaknesses

While I found the intro to be well written, I found the rest of the paper to be extremely dense; descriptions of the notation were quite hard to follow in Section 2. The paper is also extremely hard to read for anyone not familiar with integer linear programs. A background section on that would have been appropriate. I believe sections 3 and 4 could benefit from some more intuitive explanations, such as introductory paragraphs that explain the sections at a high level, or more accessible explanations of concepts such as ILPs and dual decomposition.

In general, I often found myself having to re-read sentences over again in order to understand them because terms are sometimes not defined. For example, "multiplicities" is not well defined at line 145, and while I can assume it just means a token's frequency, the appearance of such undefined words influences the paper's readability.

Questions for authors

In Figure 4, can you explain your ideas/thoughts behind the differences in the bounds between vocabulary sizes? It would be great to give some explanation in addition to just reporting the pattern.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.