CS Paper Radar

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

Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa

cs.DS ·submitted 2026-11-09 13:03 UTC · v1
theoryhot direction

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.81
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

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

cs.DS ·2026-11-05 ·Kundan Baliga, Aiden Xie, Aditya Byju
theory similarity 0.76
Abstract · 57 pages, 5 figures. Code, checkers and supplement: https://doi.org/10.5281/zenodo.24073514

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.

0.38

Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

cs.DS cs.CCcs.CL ·2026-11-10 ·Kundan Baliga, Aiden Xie, Aditya Byju
theoryhot direction similarity 0.68
Abstract · 34 pages, 11 figures. Code and certificates: https://doi.org/10.5281/zenodo.24023730

Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose $k$ merges that leave a string of length $n$ almost as short as possible; doing nothing is already within a factor $n$. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor $c\,n/\log n$, for some constant $c>0$, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that $k$ merges form a grammar with $k$ rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves $O(n/\log\log n)$, and no Karp reduction can prove hardness beyond order $n/\log n$ unless coNP $\subseteq$ NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on datasets with repeated strings.

0.65

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

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.66
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

Exact Algorithms and Complexity of the Smallest Grammar Problem

cs.DS ·2026-10-23 ·Xiangle Chen
theory similarity 0.65
Abstract · Revised version with a uniform alphabet-sensitive subexponential algorithm and quantitative transfers to SAT. Source package includes verifi…

The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, with size measured by the total right-hand-side length. For an input of length $n\ge2$ over at most $σ$ symbols, where $2\leσ\le n$, let $R=\log_σn$. We give a deterministic exact algorithm running in $n^{O(1)}2^{O(n\log\log n/(R\sqrt{\log n}))}$ time and polynomial space, with constants independent of $σ$. This gives time $2^{O(n\log\log n/(\log n)^{3/2})}$ for fixed alphabets and $2^{O(n\log\log n/\sqrt{\log n})}$ for arbitrary alphabets, up to polynomial factors. The algorithm combines pairwise disjoint representative occurrences of dictionary strings, a sparse interval certificate, and the Boolean tensor contraction theorem of OpenAI. It explicitly enforces dictionary membership, rule boundaries, and the grammar-size budget. Independently of that contraction theorem, disjoint representatives yield exact algorithms in $O^*(1.872258^n)$ time and $2^{O((n/R)\log(R+1))}$ time using $O(n)$ words of space. Anchor-based grammar projections establish binary NP-completeness and reductions with tunable alphabet size. We state their consequences as unconditional quantitative transfers from SGP algorithms to sparse SAT algorithms, and quantify the additional loss from sparsifying general formulas.

0.45

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

cs.DS cs.CCcs.CGcs.IT ·2026-11-03 ·L. Sunil Chandran, Rishikesh Gajjala
similarity 0.64
Abstract · 51 pages

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

0.23

Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space

cs.DS ·2026-10-28 ·Johannes Fischer, Dominik Köppl
similarity 0.62
Abstract

We revisit the output-sensitive enumeration of maximal closed substrings (MCSs). Given a string of length $n$ over an integer alphabet, let $k$ denote its number of MCS occurrences. We combine a right-to-left sweep on the string with range-successor queries to obtain all MCSs with two deterministic word-RAM bounds: for any fixed $\varepsilon>0$, we can report all MCSs in $O(n\sqrt{\log n}+k\log^\varepsilon n)$ time using $O(n)$ words of space, or in $O(n\sqrt{\log n}+k\log\log n)$ time using $O(n\log\log n)$ words. Both bounds include preprocessing and report occurrences by their endpoints. In particular, these algorithms improve the known $O(n\log n)$ worst-case time bound for sufficiently small output.

0.53