Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression

Kundan Baliga; Aiden Xie; Aditya Byju

cs.DSNov 5, 2026

Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression

Authors: Kundan Baliga, Aiden Xie, Aditya Byju

Organizations: University of Illinois Urbana-Champaign · Georgia Institute of Technology

Abstract

Byte-Pair Encoding (BPE) builds a tokeniser by repeatedly merging a most frequent adjacent pair of symbols; its utility is the total reduction in string length achieved by $k$ merges. It was known that this greedy rule achieves at least a third of the optimal reduction. We prove that it always achieves at least 0.361 of the optimal reduction in string length, for every string, every budget and every tie-breaking rule; this is the first improvement of the bound one third. We also explain why one third was a barrier: the pair-packing relaxation behind it is tight, so a better bound must use more of the optimum's structure. When greedy destroys three of the optimum's merge points at once, one of them can usually be moved next door, because all copies of a rule of the optimum look alike; the remaining cases are paid for later. Along the way we determine the worst-case ratio for two merges exactly, bound it for three, and isolate a single inequality that would settle the problem.

Figures & tables

Panel of Figure 1 — Figure 1: The optimum’s forest on the word xabz for the rules $Q_{1}=(\texttt{x},\texttt{a})$ , $Q_{2}=(\texttt{b},\texttt{z})$ , $Q_{3}=(Q_{1},Q_{2})$ . Each node sits above its junction, the gap that its replacement glues. The dashed box is a greedy merge of ab , which glues gap $2$ and makes all three junctions non-intact. The junction pair of a rule is the pair of letters on the two sides of its junction; for $Q_{3}$ it is $(\texttt{a},\texttt{b})$ , the last letter of $u_{3}$ and the first letter of $w_{3}$ .

Panel of Figure 2 — Figure 2: Paying for a triple event. Greedy merges ab (dashed box) where the optimum has nodes at all three gaps. (a) If the center’s left child has length at least two, the center is moved to the gap left of greedy’s token; its new pair $(\texttt{x},[\texttt{ab}])$ is the same in every copy of the rule. (b) If the center is the optimum’s own merge of ab , its parent, of label $\hat{r}$ , sits at a neighbouring gap and is destroyed; a ghost marks that gap, and its pair is fixed by $\hat{r}$ .

term	meaning	defined in
affected gaps	the gaps $\gamma_{L}-1$ , $\gamma$ , $\gamma_{R}$ whose neighbouring tokens a replacement changes	Section 4
scan-order attribution	an object affected by several replacements of one step is charged to the leftmost	Section 4.2
intact, moved, live node	a node of $F$ at its own intact junction; a node relocated once, next to the token that absorbed its junction; either of these	Section 4.2
ghost	a placeholder left at the gap of a destroyed parent node	Section 4.2
ghost class	the pair (parent label, side) of a ghost; it fixes the ghost’s type	Section 4.2
kill / destroy	what a replacement does to a live node / to a ghost at one of its affected gaps	Section 4.2

Table 1: Glossary of the bookkeeping in Section 4 .

Panel of Figure 3 — Figure 3: A failure and its image. The center at $\gamma$ is of class JR, but a later replacement $R^{\prime\prime}$ of the same step glues the next pair, so the gap $\gamma+1$ is not free for the move. Because the node at $\gamma+1$ was already killed by the triple, $R^{\prime\prime}$ finds that gap empty. The gap $\gamma+1$ determines the center, so distinct failures have distinct images.

kind of replacement	$\kappa$	$\delta$	creates	effect on live nodes
original triple, JL or JR, saved	$3$	$0$	a moved node	$-3+1$
original triple, JR, failure	$3$	$0$	nothing	$-3$ ; its image has $\kappa+\delta\leq 2$
original triple, class A	$3$	$0$	a ghost	$-3$
triple that is not original	$3$	$0$	nothing	$-3$ , at least one of them moved
image of a failure	$\leq 2$	$\leq 2-\kappa$	nothing	$-\kappa$
any other replacement	$\leq 2$	$\leq 3-\kappa$	nothing	$-\kappa$

Table 2: Charging for one replacement

R

. In the proof of Lemma 3 , bound (a) charges

R

with

2+[\kappa=3]

and bound (b) with

3-\delta-[R\text{ is an image}]

Panel of Figure 4 — Figure 4: The instance of Section 4.4 . Small numbers are positions; gap $z$ lies between positions $z$ and $z+1$ , and each node sits above its junction. Greedy’s first merge ab (dashed boxes) makes three replacements. $R_{1}$ is an original triple of class JR whose save fails, because $R_{2}$ glues gap $4$ ; $R_{2}$ is its image. $R_{3}$ is a class-A triple: its center $Q_{1}$ has two single-letter children, its parent $Q_{2}$ sits at gap $10=\gamma+1$ , and a ghost is left there. Greedy’s second merge $([\texttt{ab}],\texttt{y})$ glues gap $10$ , hits the ghost, and empties the group $C_{Q_{2},\text{right}}$ for good.

step	merge (count)	glues	affected	removes	$\kappa$	$\delta$	$h$	kind	creates	$\Lambda$
$1$	$(\texttt{a},\texttt{b})$ ( $g_{1}=3$ )	$2$	$1,2,3$	$Q_{5},Q_{4},Q_{3}$	$3$	$0$	$1$	JR, failure	—	$3$
		$4$	$3,4,5$	$Q_{1},Q_{2}$	$2$	$0$	$1$	image $R^{\prime\prime}$	—	$2$
		$9$	$8,9,10$	$Q_{3},Q_{1},Q_{2}$	$3$	$0$	$1$	class A	ghost at $10$	$\frac{5}{2}$
$s_{1}=\texttt{x}\,[\texttt{ab}]\,[\texttt{ab}]\,\texttt{y}\,\texttt{\|}\,\texttt{b}\,[\texttt{ab}]\,\texttt{y}$ ; objects: one ghost, class $(Q_{2},\text{right})$ , gap $10$ , type $([\texttt{ab}],\texttt{y})$ ; $g_{2}=\mu(s_{1})=2$
$2$	$([\texttt{ab}],\texttt{y})$ ( $g_{2}=2$ )	$5$	$3,5,6$	—	$0$	$0$	$0$	other	—	$0$
		$10$	$8,10$	ghost	$0$	$1$	$1$	other (hit)	—	$\frac{1}{2}$

Table 3: The run of Section 4.4 . For each replacement: the glued gap, its affected gaps, the objects it removes (intact nodes by label, or a ghost),

\kappa

\delta

, the hit indicator

h

, its kind ( Table 2 ), what it creates, and

\Lambda=\kappa_{I}+\frac{1}{2}(\kappa_{M}+\delta)-\frac{1}{2}\beta

( Lemma 5 ).

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: A component of $r=3$ linked elements of $S$ (boxes) with three interior $Z$ -tokens and a left end token, marked $\triangleleft$ (the ab formed with the preceding letter a ); there is no right end token because the component is followed by $\texttt{x}\neq\texttt{b}$ . In $s_{1}$ the component’s $Z$ -tokens form a run of length $r+[\triangleleft]+[\triangleright]=4$ .

$a$	$b$	$\nu$	$\bar{P}_{2}(b)$	$\bar{P}_{3}^{\text{{ng}}}(a)$	$\frac{2}{5}(1-\bar{q})\geq$
$0.000$	$0.052$	$0.602$	$0.18032$	$0.53640$	$0.361311$
$0.052$	$0.102$	$0.623$	$0.18031$	$0.54233$	$0.361323$
$0.102$	$0.148$	$0.642$	$0.18054$	$0.54749$	$0.361300$
$0.148$	$0.190$	$0.661$	$0.17948$	$0.55402$	$0.361308$
$0.190$	$0.225$	$0.677$	$0.17838$	$0.55918$	$0.361328$
$0.225$	$0.254$	$0.691$	$0.17677$	$0.56446$	$0.361307$

Appendix

Table 4: Lower bounds on the large-

k

value of the no-ghost schedule. On

\alpha\in[a,b]

the switch fraction is

\nu

, and

\frac{2}{5}(1-\bar{q})

is a lower bound for the value, with

\bar{q}

computed from the two displayed products. Generated by hand_table.py (Appendix B ), which repeats every row in exact rational arithmetic.

Byte-Pair Encoding

Byte-Pair Encoding (BPE) builds subword vocabularies by repeatedly merging frequent adjacent units to represent text efficiently for language models.

See all 23 papers

Nov 13, 2024

Theoretical Analysis of Byte-Pair Encoding

Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between

1/3

and

(1-e^{-2})/2 \approx 0.4324

. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.

László Kozma, Johannes Voderholzer

Institut für Informatik, Freie Universität Berlin, Germany

Byte-Pair Encoding Subword Tokenization Approximation Algorithms

Ask PDF

Sep 20, 2026

MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization

Byte-Pair Encoding (BPE) constructs subword vocabularies through greedy pair merging, but conventional BPE requires the number of merges or target vocabulary size to be specified externally. Significance-Gain Pair Encoding (SG-BPE) replaces frequency-only selection with a statistical criterion based on how strongly an observed pair exceeds its expected co-occurrence under an independence model. This paper introduces MDL-Calibrated Significance-Gain Pair Encoding (MDL-SG), a three-stage procedure separating discovery, replication, and utility. Candidate pairs are ranked by Significance-Gain on a discovery partition, tested for replication on a separate partition using an exact one-sided hypergeometric test with per-iteration Benjamini-Hochberg correction, and then evaluated on a utility partition using a Minimum Description Length (MDL) criterion. Merging stops automatically when no replicated candidate yields positive held-out MDL gain. On WikiText-103, MDL-SG stops at 209, 433, and 847 merges for 120K, 250K, and 500K-character tokenizer-training samples, respectively. At 500K characters, it selects a stored vocabulary of 1,017 tokens without prescribing the vocabulary size in advance. In a compute-matched TinyGPT experiment with identical 2,024,448-parameter models and 500 optimizer updates per language model, MDL-SG achieves validation/test BPC of 3.2612/3.2436, compared with test BPC of 3.2894 for SG-BPE and 3.3493 for frequency BPE. Frequency BPE achieves stronger raw compression, while MDL-SG achieves lower BPC, showing that compression-oriented merge selection and language-model utility need not coincide.

Azam Nouri

Department of Science, Technology & Mathematics, Lincoln University, MO, USA

Subword Tokenization Byte-Pair Encoding

Ask PDF

Sep 7, 2026

Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning

Byte Pair Encoding (BPE) constructs vocabularies through greedy pair merging, but the resulting merge order does not necessarily allocate a fixed model-visible vocabulary optimally for compression. We propose Dynamic-Programming-Guided Hierarchical BPE (DH-BPE), a vocabulary-construction method that combines token exposure under exact minimum-token segmentation with the hierarchical dependencies induced by BPE training. Starting from a modestly overshot BPE candidate vocabulary, DH-BPE uses dynamic programming to measure candidate utility and applies exposure-guided, dependency-aware pruning to select a fixed-size model-visible vocabulary. We compare DH-BPE against Standard BPE and recent vocabulary-optimization baselines, including Pruned BPE, MinGram, and MinGram-PP, in primary evaluations at 12K and 16K target vocabulary sizes, with an additional 18K evaluation against MinGram only. Across the primary 12K and 16K comparisons, DH-BPE consistently improves aggregate compression over Standard BPE, Pruned BPE, and MinGram under a shared exact minimum-token DP encoder. MinGram-PP achieves stronger aggregate compression in the primary comparisons, but DH-BPE outperforms it at overshoot factors f = 2.0 and f = 3.0 in cross-corpus evaluation; at 12K, MinGram-PP reverses this ordering only with the substantially larger candidate pools at f = 4.0 and f = 5.0. Qualitative analysis further shows that DH-BPE balances later, more complete BPE merges with reusable subword components, providing a practical approach to improving vocabulary allocation under a fixed model-visible vocabulary budget.

Kenny Shao

Subword Tokenization Byte-Pair Encoding

Ask PDF

Abstract

Byte-Pair Encoding

Explore similar work

Theoretical Analysis of Byte-Pair Encoding

MDL-Calibrated Significance-Gain Pair Encoding: Replication-Aware Automatic Stopping for Subword Tokenization

Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning