CS Paper Radar

GreedTok Is a 0.3287-Approximation for Tokenization, Within 3% of the Best Possible Constant

Kundan Baliga, Aiden Xie, Aditya Byju

cs.DS ·submitted 2026-11-05 02:36 UTC · v2
theory

Abstract

A tokenizer's vocabulary is chosen once and used on every input, so it matters how much compression a greedy vocabulary can lose. GreedTok (Lim et al., 2025) picks $k$ tokens one at a time, each time the string that saves the most tokens; its worst-case ratio was open. We prove that GreedTok saves at least 0.3287 of the optimal number of tokens saved, on every corpus and budget, while junction corpora show that no constant above 0.3387 is possible. The lower-bound proof is written out in full and uses no computer certificates. Its key idea is to track the order of greedy's choices: given that order, the pattern greedy leaves inside an optimal token depends on two numbers, and an induction peels off one chosen string at a time; without the order, a needed inequality fails for a 20-character token. Over 256 symbols, GreedTok's ratio exceeds 0.33861 for every $k\ge 104{,}910$, and over $k^c$ symbols with $c<1/2$ it is at least 0.4386 in the limit. We also show that the objective is APX-hard: it has no PTAS unless P = NP.

Comment
57 pages, 5 figures. Code, checkers and supplement: https://doi.org/10.5281/zenodo.24073514

Closest papers

Nearest neighbours by meaning across the whole index.

How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness

cs.DS ·2026-11-09 ·Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa
theoryhot direction similarity 0.76
Abstract

Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved \citep{kastreva2026}. We rule out every polynomial-time $M^{1-\varepsilon}$ approximation, for fixed $\varepsilon>0$, unless $\mathrm{P}=\mathrm{NP}$, even on distinct equal-length strings with $K=m-1$. Here $M$ is the total input length and $m$ is the number of input strings. We complement this lower bound with a deterministic polynomial-time $O(M/\log M)$ approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets \citep{baliga2026}; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in $2^{O(n\log\log n/\log n)}\poly(I)$ time, where $n$ is the total length of the distinct input strings and $I$ is the input encoding length. Finally, we resolve two unary merge-model hardness questions left by the bounded-alphabet study \citep{kastreva2026}: standard unary bottom-up tokenisation is APX-hard, and unary optimal pair encoding is strongly NP-complete, strengthening the previously known weak hardness.

0.23

Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses

cs.DS cs.CL ·2026-11-05 ·Kundan Baliga, Aiden Xie, Aditya Byju
theory similarity 0.71
Abstract · 40 pages, 7 figures. Restructured: the results on the re-typing inequality for short tokens moved to a companion paper; the compressed-lengt…

Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against the best $k$ merges? Kozma and Voderholzer proved that greedy achieves at least one third of the optimal shortening; the best known upper bound is $(1-e^{-2})/2\approx 0.432$. We show that one third is a barrier for packing-based analyses, which see the optimum only through a pair packing, and we prove that greedy achieves at least $0.391$ of the optimum on every input, with any tie-breaking. The key idea is rule determinism: all copies of a rule of the optimum spell the same letters, so when one greedy replacement destroys three of the optimum's merge points, half a unit can be refunded on each side. A weaker bound, $0.374$, has a short proof that needs no computer; $0.391$ adds a certificate in exact arithmetic. We also show that the worst-case ratio is exactly $3/4$ for two merges and at most $7/12$ for three.

0.53

Tokenization: Hardness and Bicriteria Approximation Algorithms

cs.DS cs.AIcs.CC ·2026-11-11 ·Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran
theory similarity 0.67
Abstract

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

0.18

The Price of Token Boundaries: Compression Certificates and Prediction

cs.AI cs.CL ·2026-09-26 ·Yuhao Du, Shunian Chen
theory similarity 0.66
Abstract

Pre-tokenisation restricts which text fragments can become prediction units, but its compression cost is obscured when tokenisers are compared only under the same boundaries. We measure this cost by bounding the minimum token count from both sides, with and without a regular-expression boundary rule. Nonnegative prices on token occurrences yield a lower bound through shortest paths and vocabulary-budget selection; maximising over all prices recovers the linear programming relaxation, and an independent integer checker certifies the reported values. On English Wikipedia, boundaries increase the optimal token count by 28.3--36.8\%. Byte pair encoding lies 2.1\% above the constrained lower bound, but 10.9\% above the unrestricted bound. Compression and prediction favour different dictionaries: at 85M non-embedding parameters and matched training-token budgets, unrestricted fitting yields higher mean held-out bits per byte under a common unrestricted decoder in all 12 languages in the paired study and 11 of 12 under independent tuning and evaluation. To study intermediate boundary policies, we introduce boundary licences, which limit the vocabulary entries permitted to cross cuts and admit the same form of certificate. On separate English and Chinese fitting corpora, licensing 10\% of the vocabulary budget recovers 85.2\% and 100.0\% of the achieved token-count reduction from removing all cuts. These results quantify the compression cost of boundaries while separating it from the prediction quality of the resulting token units.

0.08

A Non-constant Lower Bound for Grammar-Based Compression with Greedy

cs.DS cs.FL ·2026-09-10 ·Danny Hucke
theory similarity 0.59
Abstract

We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

0.25

A Multi-Word Tokenizer for 204 Languages That Needs Fewer Tokens Than GPT-4o's, Including on English

cs.CL cs.AI ·2026-11-09 ·Johin Johny Arimbur, Ankur Ashit Ghosh, Shervin Sam
hot direction similarity 0.57
Abstract

Languages of India need 1.6 to 14 times as many tokens as English on GPT-4o's tokenizer for the same content, which makes them more expensive and slower to serve. We train tokenizers from scratch on human-written text in about 200 languages. Havon v3 is a byte-level BPE tokenizer with 262,144 tokens and a pre-tokenizer that keeps combining marks with their letters and chunks scripts written without spaces. On FLORES-200 devtest it needs fewer tokens than GPT-4o's o200k_base on all 25 languages of India (median 0.74 of GPT-4o's count) and on 172 of 204 languages, but 7% more on English. Havon v4 adds a second, multi-word training stage (SuperBPE) to v3. At exactly GPT-4o's vocabulary size of 200,019 tokens, v4 needs 6.1% fewer tokens than GPT-4o on English and fewer on 161 of 204 languages and all 25 languages of India (median 0.74); at the same size, v3 needs 9.4% more on English and wins on 133. With 262,144 tokens, v4 needs 9.6% fewer tokens on English and fewer on 182 of 204 languages, and with 524,288 tokens it needs fewer on 203 of 204. The gains are largest for English, Hindi and the Romance languages; scripts without spaces, such as Khmer, Burmese and Tibetan, gain little and lose subword merges. Havon v5 replaces v4's Python-only code sample with permissively licensed code in 15 languages: on code it needs 1.03 to 1.22 times GPT-4o's tokens, against 1.11 to 1.29 for v4, while keeping all 25 languages of India (median 0.74, all significant under a sentence-level bootstrap) and English (0.94). These are compression results only: we have not yet evaluated a model trained with v4 or v5.

0.42

Optimal Single-History Tokenization Disambiguation for Provably Secure Linguistic Steganography

cs.CL cs.CR ·2026-11-12 ·Feng Jiang
theory similarity 0.57
Abstract · 19 pages, 4 figures

Provably secure linguistic steganography assumes that the receiver recovers the sender's tokens, but a text channel delivers only text, and ambiguous tokenizations break extraction. Existing fixes change the distribution, synchronize whole pools of tokens at a capacity that collapses with large vocabularies, or track several token histories. We prove that if extraction is exact and error-free across full-support language models, a single-history receiver is confined to a prefix-free candidate set at every step -- even if it reads the entire future text and the sender constrains later steps -- and must therefore give up the stop entropy, the entropy of deciding whether each prefix token ends there. Fixing these stop decisions on the prefix forest with shared randomness yields coin projection: a closed-form scheme that attains the bound, works with any distribution coder in one model call per token, preserves ordinary sampling, and refines SyncPool for every key. Across English, Chinese and Japanese, ambiguous text is rare (at most 11 in 1,000 tokens), yet the stop entropy at word and morpheme prefixes takes 7.2-9.0% of the entropy at every step; SyncPool's further loss comes from space and single-byte UTF-8 hubs that merge subtrees while carrying almost no stop uncertainty. Coin projection keeps 91-93% of the string entropy for the coder at every vocabulary size; with the full vocabulary, it turns 2.16-6.85 times as much entropy into message bits as SyncPool and recovers every completed message.

0.19

Objective vs. Search: Decomposing What Makes a Good Tokeniser

cs.CL cs.AI ·2026-09-16 ·Ahmetcan Yavuz, Clara Meister, Tiago Pimentel
top venuecode/data similarity 0.57
Abstract · Accepted at EMNLP 2026. 20 pages, 4 figures, 10 tables. Code: https://github.com/Ahmetcanyvz/comp-vs-like

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.

0.68