Tokenisation over Bounded Alphabets is Hard
Authors: Violeta Kastreva
Philip Whittington
Dennis Komm
Tiago Pimentel
Venue: ICLR 2026 Poster (2026)
Keywords: Tokenisation
tokenization
language modelling
compression
LLM
NLP
Primary area: foundation or frontier models, including LLMs
TL;DR: We prove that selecting a tokeniser which maximises a dataset's compression is NP-complete and does not admit a PTAS (unless P=NP), even when their inputs are defined on a binary alphabet.

Abstract: Recent works have shown that tokenisation is $\mathsf{NP}$-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets—an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode-characters. We close this gap by analysing tokenisation over bounded alphabets, considering two natural variants: bottom-up tokenisation and direct tokenisation, where we must, respectively, select a sequence of merge operations or a vocabulary whose application optimally compresses a dataset. We prove that even with binary alphabets, both variants are not only $\mathsf{NP}$-complete, but also $\mathsf{APX}$-hard and thus admit no polynomial-time approximation scheme (unless $\mathsf{P}=\mathsf{NP}$). We further show that direct tokenisation remains $\mathsf{NP}$-complete even when applied to unary alphabets. These results establish that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why current practical algorithms such as BPE and UnigramLM are heuristic, and point toward approximation algorithms being an important path going forward for tokenisation research.

Published conference paper at ICLR 2026
TOKENISATION OVER BOUNDED ALPHABETS IS HARD
Violeta Kastreva, f:1.2 f:112 Philip Whittington Dennis Komm, Tiago Pimentel'
'ETH Zürich, Soofa University "St. Kliment Ohridski"
busstrvvauui-ssofiabbe (ipaa//sooaaaigggiiiiiiiiitiiiii (philip.whittngtonn, dennis.komm, tiago.pimemtel@@@nneethh...
ABSTRACT
Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to imputs with unboundedly large alphabets- an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode-characters. We close this gap by analysing tokenisation over bounded alphabets, considering natural variants: bottom- up tokenisation and direct tokenisation, where we must, respectively, select sequence of merge operations or vocabulary whose application optimally compresses a dataset. We prove that even with binary alphabets, both variants are not only NP-complete, but also APX-hard and thus admit no polynomial-tin approximation scheme (unless P = NP). We further show that direct tokenisation remains NP-complete even when applied to unary alphabets. These results establish that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why current practical algorithms such as BPE and UnigramLM are heuristic, and point toward approximation algorithms being an important path going forward for tokenisation research.
INTRODUCTION
Tokenisation is the first step in most natural language processing pipelines. Given a string of characters c, a tokeniser maps it to a sequence of subwords s. Language models then operate on these subword sequences rather than the raw characters. Despite its central role, however, we still lack a comprehensive understanding of tokenisation; e.g., which properties of the produced strings of subwords actually help downstream modelling. A common property to aim for is compression (Sennrich et al., 2016; Uzan et al., 2024; Zouhar et al., 2023b), as using shorter subword-strings to encode a dataset allows for more efficient training and inference-more data can be passed through the model with the same number of flops. While not a silver bullet (Schmidt et al., 2024; Ali et al., 2024), compression has been shown to correlate with downstream model performance (Gallé, 2019; Rust et al., 2021; Zouhar et al., 2023a; Goldman et al., 2024) and will be our work's 's focus.
practical concern follows immediately: once an objective (e.g., compression) is fixed, can an optimal tokeniser be found efficiently? Popular algorithms such as BPE and UnigramLM are greedy or heuristic and need not return an optimal tokeniser for the metries they are designed to optimise. Recent work has sharpened this picture, proving NP-completeness of finding optimal tokeniser under compression-sty
objective (Kozma and Voderholzer, 2024; Whittington et al., 2025; Lim al., 2025). These papers, however, assume tokenisation of strings over unboundedly large alphabets. Conversely, in practice the strings we care about are typically composed of Unicode-characters or bytes, thus using bounded alphabets. Whether is possible efficiently find optimal tokenisers over Unicode-strings (which have an alphabet size of roughly 170,000), byte-strings (with an alphabet size of 256), bit-strings (with alphabet size of 2) open questions of practical relevance.
In this paper, we first define the n-ary tokenisation problem:
the problem of finding an optimal tokeniser strings constrained to alphabets of size We examine this problem under two variants: direct and bottom-up tokenisation, where- given a dataset over an n-ary alphabet and a vocabulary size K-we must find the vocabulary (in direct tokenisation) or sequence of merges (in bottom-up tokenisation) which, when applied to the dataset, maximally compresses it. We prove that (i) both
" Eqqual contribution. Work was done during research internship ETH Zürich.

---

Published conference paper at ICLR 2026
direct and bottom-up binary tokenisation are APX-hard, i.c. they are not in the polynomial-ting approximation scheme (PTAS) class and thus cannot be approximated arbitrarily well in polynomial time (unless NP); and that (ii) for the direct case, even unary tokenisation NP-complete. Notably, unary and binary are the easiest of the π-ary tokenisation problems, and thus these hardness results also trivially extend to tokenisation problems with larger alphabets.
Our results thus indicate that the computational hardness of tokenisation is not an artifact of large alphabets or elaborate merge operations: it already appears under direct tokenisation over umary alpha- bets. This helps explain why practical algorithms (e.g.. BPE) rely approximations, and suggests that future work should focus on provably good approximate methods or on relaxations for this problem.
TOKENISATION
Our notation's 's colour-cnding (following Whittington et al., 2025)
Blue for raw data (i.e., characters с E >²);
Magenta tokeniser-specific data (i.e., subwords s S merges m MM))
Orange for functions (e.g., tok).
Let c E E* be' character-string composed of characters from an alphahet Σ; for notational convenience, we may write one such string as 01 Ojl- Character-strings compose the raw text data found, say, on the web, which make up the datasets on which language models are trained. We denote one such dataset by = {Cm] Jm Before feeding data to our models, however, we typically convert them to strings of subwords, which is the job of tokeniser.
Formally, a tokeniser can be defined as a tuple (S, detok, tok), composed of vocabulary, decoding and encoding function. A vocabulary S is finite set of subwords, each of which is non-empty span of characters; we thus write S C E+. A subword-string is then sequence s S and represents a character-string via the concatenation of its subwords' characters. We say that pair of character- and subword-strings are equivalent if
c
concat(s),
concat(s)
82 8|s]
(1)
where $2, $2.... 3/s1), each s, S is subword, and operator denotes string concatenation. Notably, 2 [ typically enforced to guarantee that every CE " can be represented by at least one subword-string S*, and say that vocabulary's size is |S| = | K. Second in the tuple above, decoding function is defined as detok: S* - Σ", and given a subword-string it outputs the character-strine string it represents. This function thus is simply defined as detok(s) del concat(s).
Finally, an encoding function tok: E > S* maps character- to subword-strine -ttrings while ensuring the equivalence 2 for tok(c). Several encoding functions may respect this constraint, as many subword-strings may be equivalent to a specific character-string. For instance, given S (a, ao, aaa), the string aaa could be tokenised as s = (aaa) or as (a, aa). We focus on two encoding functions in this paper, which we follow Whittington et al. (2025) in labelling as direct and bottom- up. The direct encoding function (tok,) only requires a vocabulary, which it applies optimally to encode character-string In turn, the bottom-up encoding function (tok;) takes merge sequence m (mi....., m) as input, which it applies order a character-string: each of these
merges my is composed of pair of subwords, which we represent as sk sk and we write mergem: : S* - S* to represent function which, given a subword-string, processes left-to-right sk
[1]
[2]
and replaces any consecutive occurrence of the pair s sk with a new token
[1] [
[new [I]
Defining M det S x S, we say m E M and m E : we formalise the encoding functions as
tokg[S](c)
def arg min |s). SES*
tok, [ok[mm(c)
mergem
(c)
mmm
s.t. c
where O represents function composition. A tokeniser is thus fully determined by vocabu- lary or merge-sequence; for the direct case we have tok tokk while for bottom-up have
We that E denotes the Kleene of 5 (i.e., U E.) and + denotes Kleene plus (i.c., - E.).
2

---

Published conference paper at ICLR 2026
det tok (ax0tokymm [m]. Importantly, the direct encoding function (toks(S) can be efficiently computed in O(Ic)) time using the methods from Schmidt et al. (2024).
2.1 OBJECTIVE FUNCTIONS AND THEIR OPTIMISATION
As described above, direct tokeniser is fully determined by vocabulary, while a bottom-up tokeniser is identified by a mergo-sequence. How to select a specific tokeniser, though? This is typically done via defining and a dataset (D), returns a value representing the cost of that particular choice. Choosing a tokeniser then "simply" requires optimising this objective: e.g., for direct tokenisation we must find Sopt arg minscx- @(toks [S], D) under the constraint that [S] |Σ| + K.
objective function @ which, given encoding function (tok)
Several objective functions exist. UnigramL.M (Kudo, 2018), for instance, selects vocabulary that optimises a dataset's 's unigram negative log-probability. Other work has proposed alternative measures, such as the frequency of the 5-th % least frequent token (Gowda and May. 2020), or the tokeniser's 's Rényi efficiency (Zouhar et al., 2023a). As mentioned above, we focus on compression in this paper. We do so following a battery of previous work which formally analyses tokenisers (Zouhar et al., 2023b; Kozma and Voderholzer, 2024; Whittington et al., 2025; Lim et al., 2025). Prior work has shown that a tokeniser's compression correlates with the downstream performance of language models trained on its output subword-strings (Gallé, 2019; Zouhar et al., 2023a). We note, however, that other recent work has criticised compression as the sole objective for tokenisation, showing that these two properties (compression and downstream performance) may have a more complex relationship than originally suspected (Ali et al., 2024; Schmidt et al., 2024).
There are two natural ways to define compression objective: compressed length, which measures the number of remaining symbols after a string is tokenised, and compression reduction, which measures how many symbols are reduced in the string by tokeniser. These are formalised as:
By(tok, D) det Σ CED [tok(c)
G (rokk, D) def
CED (Itok(e)) - Iel)
compressed length, size of remaining string
compression reduction, number of reduced symbols
where /tok(c) denotes the length of the subword- subword-scquence produced by the tokeniser for string c. While equivalent in how they rank tokenisers, this choice can make big difference when evaluating the quality of an approximation. When using minimisation objectives, such as Gg the approximation ratio of algorithm upper-bounds the ratio between the objective value achieved by the algorithm's solution and an optimal solution, being thus at least 1 by definition. A similar definition applies when using maximisation objectives, such as Gr, but the approximation ratio is inverted. We say we have p-approximation algorithm if, for every possible input, this ratio is bounded from above by p. If a dataset has 1,000 characters and would have 100 symbols optimally compressed. suboptimal tokeniser which instead reduces it to at most 200 symbols would have an approximation ratio of 2 under Ge but of 1.125 under G,. Notably, prior work has analysed both these measures. We argue here that compressed length is the more natural objective, as it directly relates to the throughput achieved by a language model processing the given text, being thus connected to the model's training and inference costs. A 2-approximation for G implies that language model using that tokeniser may take twice as long as optimal when processing the same text."
After deciding merge-sequence (m E _M*) which optimises it. Unfortunately, both these optimisation problems have infinite search spaces (respectively, P(I+) and M where P denotes the powerset operation), which begs the question: is there an efficient way to find these optima? Recent work has shown that, in general, this is not possible, proving compression-baseee tokenisation to be NP-complete; more specifically, Kozma and Voderholzer (2024) showed this for bottom-up tokenisation, Whittington al. (2025) for direct and bottom-up tokenisation, and Lim al. (2025) for direct tokenisation with candidate tokens. This means that, unless P = NP, there exists no polynomial mitooiill-imeeeeee algorithm to find compression-optimat tokenisers. Beyond that, using the G, objective function, Kozma and Voder- holzer (2024) showed that bottom-up tokenisation is not only NP-complete but also APX-hard, which implies that it is not in the polynomial-time approximation scheme (PTAS) complexity class (unless P P= NP). A problem is in the PTAS class if, for every constant & > 0, there exists a polynomial-timg
objective function, such as Gg, must select vocabulary (S C Σイ> or
Asssuming that language models cannot achieve sub-linear computational complexity on their input's 's length.
3

---

Published conference paper at ICLR 2026
algorithm (whose time complexity may depend on E), which solves it with an approximation ratio upper-bounded by 1 + Not being in PTAS thus implies that there is no polynomial-time algorithm which can approximate the optimal solution arbitrarily well. Notably, all of the above complexity proofs apply to tokenisation problems over alphabets of arbitrarily large size. We show that these results hold even if the alphabet size is bounded by a constant, which was left open by prior work.
2.2 NOTE ON DECISION VS. OPTIMISATION PROBLEMS
In this paper, we will discuss two broad types of tokenisation problems: decision and optimisation versions. A decision problem is typically framed as a true-false existence question: c.g., does a tokeniser (within a certain class Tx) exist which achieves minimum target compression ò on dataset DD Alternatively, an optimisation problem asks what is the optimal solution to a problem: e.g.. what is the optimal compression achieved by any tokeniser within TK this dataset? More formally:
decision:
min Ge(tok, D), tokE7K
optimisation: dopt = min Gr(tok, D) tokE
(4)
Typically, NP-hardness is discussed mainly property of decision problems, while hardness of approximation (and consequently, being contained PTAS or not) property of optimisation problems. There is, however, notion of equivalence between these classes of problems: if polynomial-time algorithm exists to solve a decision problem, it can usually be leveraged to also find an efficient algorithm for its associated optimisation problem, and vece-versa. Similarly, if no polynomial --me algorithm can solve an optimisation problem with an approximation ratio arbitrarily close (i.e., if the problem is not in PTAS), this implies that there must be some hardness-of- approximation constant & such that is NP-hard to distinguish between instances that admit a solution with cost x and those that admit solution with cost (1 e)...
Our paper will focus on showing three main results for the analysed tokenisation problems. First, we will show that these problems are NP-hard. This is done by proving that another NP-hard problem can be reduced to tokenisation: i.e., there exists a reduction function that receives an instance of this other problem and, in polynomial time, outputs an instance of the tokenisation problem with the same truth condition. Second, we will show that a large subset of these problems is APX-hard. This can be done by showing that another APX-hard problem can be L-reduced to tokenisation: i.e., heyond a reduction function, there also exists a reconstruction function that receives solution of the tokenisation problem (i.c., a tokeniser) and, in polynomial time, outputs a solution of this other APX-hard problem within a certain quality bound (see App. A for formal description).
Finally, we will also compute an explicit of relying on gap-preserving reductions. To this end, it will be useful to also define gap versions of the problems we discuss. Formally, we will define such gap versions similarly to their decision versions, but while providing two decision boundaries, i... (8 8+)) instead of simply 8. In minimisation gap problems, the task is then to decide whether their optimal value is at most 8+ or at least 8=, with value falls between these, any answer is acceptable. For tokenisation problems, for
constant & for these problems,
8+ 8~ if instance, we would require an algorithm which returns: (i) true, if 8+ > min 0y(tok, D), (ii) false, if 8 < minnooee (toto,, D), and (iii) anything, if neither condition holds.
3 TOKENISATION OVER BOUNDED ALPHABETS
We now move to the analysis of tokenisation over bounded alphabets. Let an n--ry alphabet be an alphabet of size |Σ| n. We define the tokenisation problem over such bounded alphabets as follows.
Definition 1. Let K be a vocabulary size and 'D be a dataset composed of character- strings from an n-ary alphabet []] For a given 8. the n-ary tokenisation decision problem requires deciding whether there exists a vocabulary Sopt C Σx+ (for direct tokenisation) or a merge-sequence Mapt. E M (for bottom-up tokenisation) which compresses DD at most symbols. The n--ary tokenisation optimisation problem is to find what the maximal such compression of D is. Defining Tk =x= [toke[S])
def S ScEt, | =>>++>} for direct tokenisation or T (toky I E MM |m| m K) for bottom-up:
min Be(tok, D) TO
8apt min Bx(tok, D) TOXETK
(5)
m-ary tokenisation decision problem
m--rry tukenisation optimisation problem
4

---

Published conference paper at ICLR 2026
We will more specifically call these the n-ary direct tokenisation problem and the n-ary bottom-up tokenisation problem when dealing with, respectively, direct and bottom-up tokenisers, writing Tok K,) and Tokk (D, K, for the functions which return the solution to their decision problems, and Tok3 2 (D, K) and Tok, () for functions which return the solution of their optimisation problems. Finally, we define the tokenisation gap problem as:
T if 8+ #+ min Ge(tok, D) elif 8 miinookT Be(tok, D) ? else
(D, K, (6 ,8)))
Notably, the n-ary tokenisation problems form clear hierarchy from easiest (n 1) hardest (n + 00), with unary tokenisation being the easiest such problem. In the next sections, we first prove that both binary direct and binary bottom-up tokenisation are APX-hard (in $4). We then prove that unary direct tokenisation is NP-complete (in $5).
Fact n-rr tokenisation is hard, all n'-ary tokenisation problems for n' > n are hard.
Proof. Let n,,' E with n' 2 n. Any instance of the n-ary tokenisation problem is a valid instance of the n' na-ary problem with the same solutions, allowing for trivial reduction between them. Thus, any proof of hardness for the n-ary tokenisation problem immediately applies to n' -ayy problems. O
4 BINARY TOKENISATION IS HARD TO DECIDE AND APPROXIMATE
In this section, we will prove NP-hardness and APX-hardness of the two binary tokenisation decision problems above, well as NP-hardness of their corresponding gap problems (for specific gaps). To this end, we will use reduction from the 3-occurrence maximum 2-satisfiability problem (3-0CC-MAX2SAT), which we define in $4.1. 1. We then move to proving the hardness of the binary direct and binary bottom-up tokenisation problems (in $4.2 and $4.3, respectively).
4.1 3 O-OCCURRENCE MAXIMUM 2- 2-SATISFIABILITY
Let X be Boolean variable assigned value E {F, т}, and let X (X be set of such vari- ables, with joint assignment X = { Further, let C {LL be set of clauses, 3 where each literal L, is either variable X, or its negation -X, We define 3-OCC-MAX2SA as follows.
Let X = {X be set of Boolean variables and C = {(L) V D be a set of clauses. Further, let each variable Xj occur in exactly three clauses. Given target 7 N, the 3-OCC-MAX2SAT decision problem requires deciding whether there exists assignment x {F, T) such that at least clauses are satisfied. The 3-OCC-MAX2SAN optimisation problem requires finding the maximum number of satisfiable clauses. Formally:
Definition 2.
7
Σ V [E(F.
7
Topt XE
3-00C-HAX25AT decision problem
3-00C-MAX2SAT optimisation problew
) to denote a function that, given instance of the 3-0CC-MAX2SAT decision problem, returns its solution. Similarly, we write 30M2S' (X, C) for function that returns Topt- The 3-OCC-MAX2SAT problem was proven to be APX-har by Berman and Karpinski (1999), with their result also implying that this problem is NP-hard.
We write 30M2S(X, C)
4.2 BINARY DIRECT TOKENISATION IS HARD TO DECIDE AND APPROXIMATE
In this section, we prove that the binary direct tokenisation problem is both hard to decide and to approximate beyond certain constant greater than 1. First, we will prove that the decision version NP-hard (in 14.2.1). Second, we will use this initial result to prove both that this problem's 'ss optimisation version is APX-hard and that a gap version of the problem is similarly NP-hard (in $4.2.2). This will complete our proof that this problem's 's optimisation version is hard to approximate arbitrarily well, while providing an explicit crrddess-of-approxiine
constant.
In some formalisations, 3-0CC-MAX2SAT allows clauses of size one. We work here, more specifically, with the 3-nccurrence maximum sxact-2-satisfabblliy variant of this problem, thus not allowing single-literal clauses.
5

---

Published conference paper at ICLR 2026
4.2.1 THE BINARY DIRECT TOKENISATION DECISION PROBLEM IS NP-HARD
We now prove NP-completeness of binary direct tokenisation, which requires two things: inclusion in NP and being NP-hard. Inclusion in NP follows from the general (unbounded) case, which was previously proven by Whittington et al. (2025). Proving NP-hardness requires a polynomial-time reduction from another NP-hard problem to this problem, which we will design in what follows.
Reduction 1. Consider an instance of the 3-OCC-MAX2SAI decision problem and the binary alphabet == = {0. 1). Now, for each variable xj, let x3 = 02) and x = 02i, i.e., these are character-strings formed of 0 repeated 2j 1 or 2j times. Then we build subdatasets:
D1 = [1x], x31, 1x), xfil1s x
D2 = =1x]1, 1xfil1 J) x xf' (8a)
D3 =
x f" D2 1
x (8b)
where L! and L3 are replaced by their respective variable characters as they appear in the i-th clause (i.e. L; is replaced by x if is equal to X, or by x3 if it equals -X Further, xf denotes that a set of strings should be repeated f times in the corresponding dataset. These multiplicities are
f" def 7, f #et 2(f" + 3) + = 21, and f def 2( + f" +3 + = 63. A full dataset is then formed by joining these subdatasets: D D1 D2,UDuUT0 JDDUDD, Finally, we set the number of allowed tokens to K = 5J and the larget compression to ā 4fJ + 33 + J + 31 - 329J + 31 - 7.
We write RI(X,C 7) to represent the D-2-TOK instance that is output by this reduction, represented by the tuple (D, KK 8). Notably, this reduction runs in polynomial time. By proving its correctness, thus, we prove that binary direct tokenisation is NP-hard. For this reduction to be correct, the given 3-OCC-MAX2SAT instance must be satisfiable if and only if its reduced tokenisation instance is as well, We now prove both directions of this iff clause.
i.e., 30M25(X =
Theorem 1. The binary direct tokenisation decision problem is NP-complete.
Proof sketch. This proof is done in two steps.
Forward step (3M22 c, = To,,(R((X,C,))), See a formal proof in Lemma 1 in App. B. Assuming an instance of 3-OCC-MAX2SAT is satisfied by assignment x² {xj) we build direct tokeniser with tokens 1x2, 11,, 1x 1, and with token 1x.1 if x = T, and 1xf1 otherwise. This tokeniser compresses D1 to 252.J, D2 to 63., D3 to 14J, and D4 to 3I - -y" tokens, where y" is the number of clauses satisfied by x Adding these compressed lengths together, find that they satisfy the direct tokenisation problem, as y* 2 7 by assumption.
Backward step (Tok) We first show that an optimal tokeniser for the D-2-TOK instance is always sat-compliant." it con- tains all tokens of the form 1x], xJ1, 1, 1xf, x and either 1x51 or 1xf1 for each j E (1.....J]} J]. We do this by showing that Dj guarantees that any optimal solution includes tokens 1x]. 1, 1xf, 1xf,,f11; D2 guarantees that any optimal solution further only includes tokens of the form 1x]1, 11ff111511 1x;1; and Ds guarantees that either token 1x.1 1 or 1x.1 exist for each E (J}. Then, show that if such a sat-compliant tokeniser reaches the desired compression, it must correspond to an assignment x² that satisfies the desired number of clauses.
r)) = 30M2S(X, 7)). See full proof in Lemma 2 in App. C.
4.2.2 BINARY DIRECT TOKENISATION IS HARD TO APPROXIMATE
We now prove that the binary direct tokenisation problem is not only NP-hard, but APX-hard, implying that this problem is not in PTAS (unless P = NP). Further, we also prove that its gap constant for this problem in the process.
version is NP-hard, computing a prrddess--o-approxximee
Theorem 2.
The binary direct lokenisation optimisation problem is APX-hard and cannot be approximated in polynomial time with an approximation ratio p < 1. 1.000002, unless = NP.
Proof sketch. This proof is done in two steps.
"This reduction is inspired by Whittington et al.'s (2025) reduction, which we update to (i) rely on binary, as opposed to unbounded, alphabets; (ii) use constant-sized f's, which allow us to prove approximation hardness. TThis concept is inspired by Kozma and Voderholzer's (2024) use of well-formed tokenisers.

---

Published conference paper at ICLR 2026
The optimisation problem is APX-hard. See a formal proof in Lemma in App. D. Our proof rests on an L--reduction from 3 3-OCC-MAX2SAT, which was shown to be APX-hard by Berman and Karpinski (1999). We again reduce from this problem D-2-TOK using Reduction To define a reconstruction function, consider two cases: a solution to D-2-TOK (i.e., tokeniser) will be either sat-compliant or not. Given a sat-compliant tokeniser, is easy to build a solution for 3-OCC-MAX2SAT with bounded quality. Given sat-noncompliant tokeniser, we first transform it into sat-compliant via quality-improvie transformations, we then use this sat-compliant tokeniser to build a solution for 3-OCC-MAX2SAT with bounded quality. This concludes this step of the proof.
The gap problem NP-hard. See a formal proof in Lemma 4 in App. E. As shown by Berman and Karpinski (1998; 1999), the 3-OCC-MAX2SAT gap problem is NP-hard for instances with / /= 201 6n clauses, 7 = (2011 + E) lower bound, and y+ = (2012 - e)n upper bound. We use Lemmas and prove reduction from this gap problem D-2-TOK's gap problem. Notably, our reduction sets = 329 +3/ - for both 7 and y+. Analysing the gap of the resulting tokenisation problem, we find that this problem thus NP-hard for gap 8 - of 1.000002.
While the constant above (i.e.. 1. 1.000002) is remarkably small, note that proof makes attempt to optimise this bound. Our lemma's 's main takeaway is that it is not possible to compute D-2-TOK with approximation ratios arbitrarily close to 1 in polynomial time. Other larger bounds likely exist and, in fact, it might even be possible that there no constant-facte approximation for D- 2-K at all. Note that whether D-2-TOK admits any polynomial-time constant-factor approximation algorithm (i.e., whether it lies in APX, meaning it would be APX-complete) remains an open problem.
4.3 BINARY BOTTOM-UP UP TOKENISATION IS HARD TO DECIDE AND APPROXIMATE
As for the direct case, our argument proceeds by first proving the hardness of the decision version, and then leveraging this result to show APX-hardness of the optimisation version as well as an explicit harddess-ofapprooiiatiin constant via the gap problem.
4.3.1 THE BINARY BOTTOM-UL UP TOKENISATION PROBLEM IS NP-COMPLETE
As before, reduction from 3-0CC-MAX2SAT prove NP-hardness.
Reduction 2. Consider an instance of the 3-0CC-MAX2SAT decision problem and the binary alphabet
Σ (0, 1). Again, for each variable Xj. let x] 0 and xf 022 Then we build subdatasets:
D, (11) u (x, 1x],
122
f
(9a)
D2 1x,
(9b)
D3 [IX]
(9c)
D. (113112111,11
f"
(9d)
1x
if T. =x,; 1 = -X if = L3 X
1x
D.=
1x21xx
if = -X,, 1 ~N
(9e)
1x]1x].11
if L. x;; L3 X2
The subdataset multiplicities are f def 4, fr def 2(2 +3) 23, = def 2(2 2 +3)+
115, and f 2(2 + 2 + 2 + 3) + = 575. We set the vocabulary size to K = 10J and the target compression length to 8 +6J
f4" +3I - +375
We write R2(X'C, 7, to represent the B-2-TOK instance (D, K, 8) constructed by this reduction. As before, this is a polynomial time reduction. We now prove the equivalence 30M2S(X C, <
Tok, (R2(X', C, 7)) which shows the reduction's correctness and thus that B-2-TOK is NP-hard.
Theorem 3. The binary bottom-up tokenisation decision problem is NP-complete.
Proof sketch. This proof is done in two steps.
Forward step (O = (R1 See full proof in Lemma 5 in App. F. Assume the 3-0CC-MAX2SAT instance admits assignment x {x13/= satisfying
7

---

Published a conference paper at ICLR 2026
at least Y clauses. We construct merge sequence m m_ o mg m3 o m1 my m,- where m m2, m4, mg are structural merges that appear in every valid tokeniser solution and ensure that all strings corresponding to single variables are properly compressed; and m3, ms are assignment-dependein merges, chosen according to x²: for each variable zj. we merge 1 @ 11, @ 1 x I, and 1xx 1, @ x otherwise. Applying m to the string subdatasets D1, 22, D3. D4 gives the fixed compressed length 5398J + 575. For the strings Ds. the construction ensures that each clause compresses 2 tokens if at least one of its two literals is true under x", and remains at 3 tokens otherwise. Since x satisfies at least 7 clauses, we obtain at most 31- - symbols. Compression thus satisfies the budget 6.
30M2S(X, C. See full proof in Lemma 6 in App. G. We consider sat-compliant direct tokenisers, which must contain all tokens of the form 11,x3, x 1x], x31, 1x9, x111,,11,, 11x; and must contain either 1x51, 1x511 1xf]1, 1xx51 for each j E {L.....J} J}. Again, an optimal direct tokeniser for the B-2-ToK-instance is always sat- compliant, which is enforced by datasets Dj to D4. We then show that if such a tokeniser achieves the desired compression, it must correspond to an assignment x which satisfies the desired number of clauses. To finish, we show that, for any instance generated by Reduction 2, sat-compliant direct tokeniser always corresponds bottom-up upp tokeniser with the same compression quality.
Backward step (Tok, (R2(X,, ()))
4.3.2 BINARY BOTTOM- UP TOKENISATION IS HARD TO APPROXIMATE
As for direct tokenisation, we now show the APX-hardness of binary bottom-up tokenisation, and compute an explicit ofaddess-of-approximaat
constant for it.
Theorem 4. The binary bottom-up tokenisation optimisation problem is APX-compeete and cannot be approximated in polynomial time with an approximation ratio p 1.0000001, unless P = NP. Proof sketch. This proof is done in two steps, and relies on a similar strategy to Theorem 2, but while replacing the vocabularies of direct tokenisers with merge sequences. Additionally, Kozma and Voder- holzer (2024) show that bottom-up tokenisation is contained in APX even for unbounded alphabets, which thus transfers the problems we study here. Combined, these results prove APX-completeness.
The optimisation problem is APX-hard. See full proof in Lemma 7 in App. H. As in the proof of APX-hardness of binary direct tokenisation, we perform an L-reduction from 3-OCC-MAX2SAT, reusing the instance map of Reduction 2. We define a reconstruction map which first converts any feasible merge sequence into sat-compliant one, and then decodes a Boolean assignment from this sat-compliant tokeniser with bounded quality. This completes the proof.
The gap problem NP-hard. See full proof in Lemma 8 in App. Similarly to the direct case, we show that no polynomial-tine algorithm can solve the binary bottom-up tokenisation gap problem with gap of 1. 1.0000001, unless
NP.
5 UNARY TOKENISATION IS HARD TO DECIDE
We now move on the unary tokenisation case. Here, we work with alphabets composed of single symbol, i.e., Σ {a}. As Σ' = {a" E N}. it follows that unary character-string strings E E' may only differ from one another their length. There exists thus an isomorphism (given by the function I.I and its inverse) between these character-strings and their string-lengths, & E N. A natural notation for such problems then to work directly with string-lengths. In this section, we will thus represent a character-string
Vn by its length & E N; a dataset D {Cm JMM by the lengths of its strings Dy = (C MM 1= where C. = a'' ; and a vocabulary S C > by a set of string-lengthh SN C N+. A subword-string is then sequence of such string-lengths, SN E St and we have:
dst) der = ssm
toke (S) def
arg min |sy], s.t., E = sum(sw) S
(10)
where we overload the functions detok and tok, to handle this unary- representation. Note that all these definitions are equivalent (up to an isomorphism) to the definitions in $3.
When posing either the optimisation or decision version of the unary tokenisation problems, we could thus work with either representation of our data (as strings or string-lengths) and the solutions must be the same. However, the complexity of algorithm is typically measured as function of the
8

---

Published conference paper at ICLR 2026
length of its input. If this input is a unary string, the input will be as long as this string's is length. If this input is number, however, this input's length behaves logarithmically on the value of the number itself (as this number would typically encoded a compact binary representation). When dealing with problems such as unary tokenisation, this introduces important subtlety: the problem's s complexity status may change depending on how we represent it (with strings or string-lengths). such a problem is NP-hard when either representation is given, it is called strongly NP-hard. If this problem is NP-hard only in its string-length representation, but not when represented using unary strings, it is weakly NP-hard. Note that the opposite case case-where problem is NP-hard only when representing the data as strings, but not strings-lengths-iis not possible, as strings have a larger size than their lengths. Importantly, Fact applies only strongly NP-hard unary problems; as the trivial identity we use in its proof would not be valid for unary problems with string-length representations. For unary tokenisation, the string representation (where strings are explicitly represented) is more natural, and we are thus interested in strong NP-hardness.
5.1 UNARY DIRECT TOKENISATION IS STRONGLY NP-COMPLETE
In this section, we prove that the unary direct tokenisation problem is strongly NP-complete. In App. J, we prove that the problem is in NP, even if the input is in string-length representation. To prove NP-hardness of unary direct tokenisation, we then design a polynomial-time reduction from the well-known NP-hard vertex cover problem (vertex-cover; Karp. 1972; Garey and Johnson, 1979). Let (V,E) represent a finite, simple, undirected graph with V = fvi...... fs} and & S { u') v, o' E V.U # v'). A set C V is vertex cover if, for every edge (u, E, we have that either v or vf is in C. Given a budget v E N, the vertex cover problem requires deciding whether a graph has vertex cover of at most dp vertices.
Definition 3. Given a graph (V,E) and a budget vp E N, the vertex cover decision problem asks whether there exists vertex cover C C with [C] S ab in this graph.
E, For convenience, we will write VC(V,,, E,,) v) for a function that returns T if its input is a satisfiable
instance of the vertex-cover decision problem, and otherwise. We now provide a polynomial-tine reduction from vertex-cover to D-1-TOK, which will prove D-1-TOK's NP-hardness.
Reduction 3. Consider an instance (V,E,) of vertex-cover and let def
+ where
= [V] and = (8). Now, let enc (u,) = + 2 + N2 and B N We construct three subdatasets from this graph as:
D1 -1a 10 Vy U (B),
where e, = enc(v;)
vertex-strings (I1a)
D2 {ats 1 EV
where Ej = enc enc(v;) ) + B
cover-strings (11b)
D3 Jah (03.uz EE), where "hs- enc enc(r;) + enc (vy) + edge-strings (11c)
Finally, merge these subdatasets to form a dataset D Di D2 UD3, and set K = and 8 = 3J + 21 + +1 vb.
As before, we complete our NP- NP-hardness proof by showing this to be valid reduction, i.e., that VC(V, & 1)) > Tok. (R3(), E, v)). Notably, our reduction outputs (in polynomial time, as all lengths are polynomially bounded in the size of the original instance) an instance of the unary direct
tokenisation problem in string form. As such, by proving the correctness of this reduction, we prove the strong NP- harhnesssss of D-O-
Theorem 5. The unary direct tokenisation decision problem is strongly NP-complete.
Proof sketch. This proof is done in two steps.
Forward step (VC(V, E) = To3( +))) See full proof in Lemma 10 in App. K. Suppose that the given instance of vertex-cover true, i.e., that VC(V, = T. Now, let C. C V be vertex cover which satisfies this instance. Then we can build tokeniser with vocabulary SK f 1 V) U {a {att | E C*). This tokeniser will encode: all strings in D, single symbol; & strings in D2 with a single symbol and others with 2: and all strings in D3 with two symbols (as, per our assumption, all edges have at least one vertex in C*). This means that the total
amount of tokens used is (J 1) (2J + 27 = 8. Therefore, Tok. (D, K, 5) T.
9

---

Published conference paper at ICLR 2026
Backward step (Tok) &, b) = VC(V, E &)).. See full proof in Lemma 11 in App. L. We prove this lemma in 4 steps. First, we show that all string-lengths in DN are unique. Second, we show that an optimal tokeniser's ss vocabulary must contain only full strings in Dx. Third, we show that an optimal tokeniser's vocabulary must include all strings in D1. Fourth, we show that if compression of is achieved, than the corresponding vertex tertee-coeee instance must be true. Notably, three of these steps rely the fact that can use N numerical base to prove the uniqueness of both: (i) individual atring-lengths, as well as (ii) their pairwise summed values.
Interestingly, the unary direct tokenisation problem is tightly related to the problem of choosing denominations for coin system. In fact, the application of the function tok,[Su](( is equivalent to the change-mane making problem; a problem shown to be (weakly) NP-hard by Lueker (1975) and classic example for dynamic programming. The unary direct tokenisation problem can thus be equivalently seen as general optimal denomination problem, Aitere-gived a set of common currency transactions- one must select optimal coin denominations for a currency; see Shallit (2003) for a discussion of this problem.
Corollary 1. The general optimal denomination decision problem is strongly NP-complete.
5.2 A VARIANT OF UNARY BOTTOM-UP TOKENISATION IS (AT LEAST) WEAKLY NP-HARD
While direct tokenisation over a unary alphabet is strongly NP-complete, our current picture of the complexity of its bottom-up counterpart is more nuanced. In bottom-up tokenisation, one must find a merge sequence m which is then applied (by tok- [m]][m][))) exhausttveel and in sequence, replacing all occurrences of each pair one a time. A variant of this problem-terne optimal pair encoding (OPE) tokenisation-relann
this requirement, using the merge sequence for a different purpose: to define a merge-extracted vocabulary Sm > U {s} o s2 m m, m7 ($1, The final tokenisation is then produced by optimally applying this vocabulary, which can be done using the direct encoding function (toks(Sml(c)) This approach thus ensures that a merge is used only if it contributes to the most efficient segmentation overall. Notably, this variation was used by Schmidt et al. (2024) and formally analysed by Kozma and Voderholzer (2024). Now, let the unary OPE tokenisation problem be defined similarly to the other n-ary tokenisation problems (in Definition 1), but while constraining the search space to the set of OPE tokenisers: Tk= [toke [Sttokk[mm)] [Sm] m E MM,, [m|, = K3. Having defined the decision problem, now establish its computational hardness.
Theorem 6. The unary optimal pair encoding decision problem is (at least) weakly NP-complete.
Proof sketch. The full proof can be found in App- N. Inclusion in NP follows from Kozma and Voderholzer (2024). The proof of NP-hardness is achieved via a polynomial-time reduction from the addition chain sequence decision problem (see App. M for a formal definition). which is known to be NP-complete when its input numbers are encoded in binary (Downey et al., 1981). The reduction reveals a natural connection between the two problems: finding the shortest addition chain for set of numbers is equivalent to a special case of unary optimal pair encoding where every string in the dataset must be compressed into single token.
6 CONCLUSION AND LIMITATIONS
We proved several hardness results on bottom-up and direct tokenisation with bounded alphabets, thus answering open questions posed by both Kozma and Voderholzer (2024) and Whittington et al. (2025). A number of open questions remain, however, in particular with respect to approximability. For instance, while we showed that the binary tokenisation optimisation problems are Aar-hard and thus cannot be approximated arbitrarily well (unless P = NP). it is unclear whether binary direct tokenisation admits any polynomial-tine in APX). With respect to decision problems, while we showed strong NP- harddness of unary direct tokenisation, we were so far only able to prove: (i) weak NP-hardness unary OPE tokenisation, and (ii) no hardness result for unary (standard) bottom-up tokenisation. Finally, the results of our work are limited in that we consider (i) compression as objective, and (ii) bottom-up and direct tokenisation only; the hardness of other objectives and variants remains open. Overall, however, our results show that tokenisation remains a hard problem, even when restricted to small (even binary or unary) alphabets. Future work should thus explore provably good approximation algorithms.
constant-factor approximation algorithm (i.e., whether lies
10

---

Published conference paper at ICLR 2026
ACKNOWLEDGMENTS
We would like to thank Giulia Lanzillotta, Weronika Ormaniec, Dimitri von Rütte, and Felix Sarnthein for their helpful feedback on the introduction. We are also grateful to Pietro Lesci, Amit Moryossef, and Marius Mosbach for their comments the manuscript, and to Thomas Hofmann for insightful discussions about the paper. We further thank Gregor Bachmann, Hans-Joachim Böckenhauer, Emanuel Skodinis, and Moritz Stocker for their contributions in the early stages of this work, and Stefan Gerdjikov for his valuable early input and discussions. The work of Tiago Pimentel was funded by the Data Analyties Lab at ETH Zürich. The work of Violeta Kastreva was partially supported by the European Nextonneennnntrtiionn))) project, through the National Recovery and Resilience Plan of the Republic of Bulgaria [Grant Project No. BG-RRP-2.004--02
REFERENCES
Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling. Katrin Klug, Jan Ebert, Niclas Doll, Jasper Buschhoff, Charvi Jain, Alexander Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Ortiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Stefan Kesselheim, and Nicolas Flores-Herr. 2024. Tokenizer choice for LLM training: Negligible or crucial? In Findings of the Association for Computational Linguistics: NAACL 2024, pages 3907-3924, Mexico City, Mexico, Association for Computational Linguistics.
Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccannee and Marco Protasi. 2012. Complexity and approximation: Combinatorial optimization problems and their approximabilityy properties. Springer Science & Business Media.
Piotr Berman and Marek Karpinski. 1998. On some tighter inapproximability results, further improvements. In Electronic Colloquium on Computational Complexity, volume 65.
Piotr Berman and Marek Karpinski. 1999. On some tighter inapproximability results (extended abstract). In Automata, Languages and Programming 26th International Colloquium, ICALP 1999. Proceedings, volume 1644 of Lecture Notes in Computer Science pages 200-209, Berlin, Heidelberg. Springer.
Peter Downey, Benton Leong, and Ravi Sethi. 1981. Computing sequences with addition chains. SIAM Journal Computing, 10(3):638-6A4 --66.
Matthias Gallé. 2019. Investigating the effectiveness of BPE:
The power of shorter sequences. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNIIP), pages 1375-1381, Hong Kong, China. Association for Computational Linguistics.
Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP- NP-Coompetenesss. W. H. Freeman, San Francisco.
Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. 2024. Unpacking tokenization: Evaluating text compression and its correlation with model performance. In Findings of the Association for Computational Linguistics: ACL 2024, pages 2274-2286. Bangkok, Thailand. Association for Computational Linguistics.
Thamme Gowda and Jonathan May. 2020. Finding the optimal vocabulary size for neural machine translation. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3955-3964, Online. Association for Computational Linguistics.
Richard M. Karp. 1972. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York.
László Kozma and Johannes Voderholzer. 2024. Theoretical analysis of byte-pair encoding. Preprint, arXiv:241 1.08671.
11

---

Published conference paper at ICLR 2026
Taku Kudo. 2018. Subword regularization: Improving neural network translation models with multiple subword candidates. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pages 66-75, Melbourne, Australia. Association for Computational Linguistics.
Jia Peng Lim, Davin Choo, and Hady W. Lauw. 2025. partition cover approach to tokenization. Preprint, arXiv:2501.066 .06246.
G.S. Lueker. 1975. Two NP-complete Problems Nonnegative Integer Programming. Technical report: Computer Science Laboratory. Univ.
Christos H. Papadimitriou and Mihalis Yannakakis. 1991. Optimization, approximation, and com- plexity classes. Journal of Computer and System Sciences, 43(3):425 440.
Phillip Rust, Jonas Pfeiffer, Ivan Vulié, Sebastian Ruder, and Iryna Gurevych. 2021. How good is your tokenizer? On the monolingual performance of multilingual language models. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Ith International Joint Conference Natural Language Processing (Volume 1: Long Papers), pages 3118-3135, Online, Association for Computational Linguistics.
Craig W. Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. 2024. Tokenization is more than compression. Proceedings of the 2024 Conference Empirical Methods in Natural Language Processing, pages 678-702, Miami, Florida, USA. Association for Computational Linguistics.
Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pages 1715-1725, Berlin, Germany. Association for Computational Linguistics.
Jeffrey Shallit. 2003. What this country needs is an 18c piece. In Math. Intelligencer 25(2).
Omri Uzan, Craig W. Schmidt, Chris Tanner, and Yuval Pinter. 2024. Greed is you need: An evaluation of tokenizer inference methods. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 813-822 Bangkok, Thailand. Association for Computational I. Linguistics.
Philip Whittington, Gregor Bachmann, and Tiago Pimentel. 2025. Tokenisation is NP-complete, In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), Vienna, Austria. Association for Computational Linguistics.
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. 2023a. Tokenization and the noiseless channel. In Proceedings of the 61 Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 5184-5207, Toronto, Canada. Association for Computational Linguistics.
Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. 2023b. A formal perspective on byte-pair encoding. In Findings of the Association for Computational Linguistics: ACL 2023, pages 598-614, Toronto, Canada, Association for Computational Linguistics.
12

---

Published conference paper at ICLR 2026
A PROVING APX-HARDNESS AND L-REDUCTIONS
APX is the class of optimisation problems that admit polynomial-time constant-factor approximation algorithms. problem is APX-hard if, under approximation-preeevvinn reductions, it is at least as hard to approximate as every problem in APX. To prove APX-hardness, standard polynomial-time reductions are insufficient because they do not guarantee the preservation of approximation ratios. Instead, we rely on L-reductions. An L-reduction is polynomial-ting reduction that relates optimal objective values and approximation errors by fixed constants, ensuring that any constant-factor approximation for the target problem implies a constant-factor approximation for the source problem (Papadimitriou and Yannakakis, 1991). L-reductions achieve this by relying on two polynomial-time functions. Given optimisation problems A and B, a reduction function receives an instance of reduced problem A and outputs an instance of the target problem B; in turn, a reconstruction function receives both an instance of problem A, and a solution to problem B, returning solution to problem A. Formally, we define L-reductions as follows:
Definition 4. Let A and B be optimization problems with objective-value functions & (.) and 6 (.))) and optimal values OPT (IA) and OPT (Ig)) for instances IA and Ig. We say that A L-reduces to B (denoted A St. B) if there exist polynomial time computable reduction and reconstruction functions J and g and constants or B > O such that for every instance LA of A:
(i) IB f[AA) is an instance of B whose optimal solution is upper-bounded by a times the optimum LA. Formally:
((EAA( (OPTA((A))
(12)
(ūi Given IB = ((IA) and any of its feasible solutions of Ln, SA = ([AA,88) is a solution of La and has a quality difference to the optimum bounded by sB 's quality:
[ - A S ()
OPT 8 B((AA))
(13)
L-reductions preserve APX-hardness; therefore, if A is APX-hard and A Sz B, then APX-hard (Papadimitriou and Yannakakis, 1991; Ausiello et al., 2012).
B PROOF OF FORWARD STEP OF THEOREM 1
Lemma 1. Ifa 3-0CC-MAX2SAT instance is satisfiable, then the D-2-TOK instance output by Reduc- tion 1 is also satisfiable. Formally: 30M2S(X,C,)) = (R1,
Proof. To prove this forward step of Theorem 1, we first establish that satisfiable 3-OCC-MAX2SAT instance guarantees the existence of binary direct tokeniser that meets the compression target. Assume a (X, C, 7) instance of the 3-OCC-MAX2SAT problem satisfiable, i.c., that 30M2S(X, Y) true. We must prove that, in this case, Tok3 (X, C, 7)) also true. Now, let x {x; 1 be any satisfying solution to the (X, 7) instance. We will denote the number of clauses satisfied by x. by 7", noting that y 2 by assumption. We can construct tokeniser from this solution as follows:
s s [x], { xJI, 1xJ, }
U
{IxJI if 23 -T else 1xf1]
(14)
j=1
Note that as required by our reduction this tokeniser has vocabulary size |S| K 5. tokens were added. Under this tokeniser, have:
= Σ + K, since
tok. [S](Di) (IxJ), (xJ1), (1x5), (x51) (length 1)
|isjsJ
x (15a)
toke (S](22) { (Ix]1), (1x5, 1)
(length 3)
if 5 =T
|1Sح5
x f (15b)
(1xf, 1), (1xF1)
(length 3)
else
[1x x)
(length 2)
if at =T
toke (Sko)))(D2)
|15
x f (15c)
(Ix}, 1xf1)
(length 2)
else
(IL) 1, 121)
(length 2)
if L =T
toko|8|(2))
(LL) 1
(length 2)
elif T
|1sis1
x1 (15d)
(LL). 1, 1
(length 3)
else
13

---

Published conference paper at ICLR 2026
where we override function toks [S] apply elementwise full dataset of character-strings. instead of to unique c. Consequently, we get the compressed lengths:
6x(tok, [S], D1) = 4J J [e[tok,[S], D3) = 2J f" 14
Gx(tok,[S), D2) =
(16a)
Ge(tok, = =31
(16b)
We have that each character-string in dataset D4 is compressed symbols if either L; or Lł are true, and otherwise is kept at 3 symbols; the y satisfied clauses in xt" will thus be compressed to 2 symbols and the unsatisfied clauses to Summing these values together. we get the compressed length of the entire dataset under this tokeniser: Gx(toks D) 329. + 31 y² Finally:
2 7
329J + + - S 329J 33 -2
(17)
This completes this proof.
C PROOF OF BACKWARD STEP OF THEOREM
Before starting lemma's proof, define few notions which will be useful throughout it. First, we define sat-compliant tokeniser to be any tokeniser which: (i) contains all tokens of the form 1x,, xf1, 1x3, x51 and (ii) contains either 1x.] or Ix₃1 for each j E ,I,...,J} J.. Otherwise, call the tokeniser sat-noncompliant Given the vocabulary of a cat-compla tokeniser, we can easily build an assignment 3-OCC-MAX2SAT instance with the following function:
g(S) = { where
2 = zj = F elif 1x
1xTE E
(18)
Further, we will define 101-string any character-string of the form 10*1, and as a 10101-string any character-string of the form 10+10+ (The 0+ notation stands for a sequence characters.) Considering the datasets output by Reduction 1, we know that there are no 101-strings in Dj. Further, we know that each unique 101 101-string appears datasets D2 and D3 exactly I' and f" times, respectively, and exactly 3 times in D1. (This is due to us working with the three-occurrences variant of MAX2SAT and to the fact that x] (20 and x (2..) We now prove the following lemma.
one or more
Lemma 2. If the D-2-TOK instance output by Reduction 1 is satisfiable, then the 3-0CC-MAX2SAT instance which generated it is as well. Formally: Tok? (R C,)) = C0,,
Proof. Assume this (D,K, K, instance of D-2-TOK-whene (D, K, 6) = R1 7) satisfiable, i.e. that Tok, (X, C, 7)) evaluates to true. We must prove that, in this case, 30M2S( C) also evaluates to true. Now, let Sopt be arbitrary optimal solution to (D, K,5), 8). We know, by definition, that:
(R1,,, =
(Se(tokn[Sopt). =
(19)
We can thus prove this lemma by showing the following implication:
(Be(toko[Sop)) D) D) 5) = 30M2S(X,C,))
(20)
We will proceed in four steps:
we prove that Sept must include all tokens of the form 1x], x[], 1x7, xx,;;
we prove that Sopt must, in addition to the tokens above, only include tokens of the form
1x]1, 1xf1;
we prove that Sept may only include, for each j. either token 1x]1 or Ixf1;
finally, we prove that, if (S((toks[Sppp] D) S 6). we can build variable assignment which satisfies this 3-OCC-MAX2SAT instance (X,C, C)
14

---

Published conference paper at ICLR 2026
3 show that Sppt must be the vocabulary of sat-compliant tokeniser; in step ④ we will then rely on the function (defined above in Eq. (18)) to convert this vocabulary into a satisfying assignment X app of the 3-OCC-MAX2SAT instance.
Note that, together, steps !
LemmaProofStep 1. (Step ①). 1xJ, x31, 1xf, xf1, Le.:
An optimal tokeniser must include all tokens of the form
[x] [x], xfI, 1x 13x } _ S
(21)
Proof. We prove this step by contradiction. Assume there exists optimal tokeniser with vocabulary Sx which does not include > 0 of the tokens above. Now, choose an arbitrary set t tokens in this vocabulary which not of the above form, and replace them with the missing tokens in this set. We denote this new tokeniser's vocabulary by Sy. Note that the strings in Di with these missing tokens represented with at least 2 symbols under Sx, but with single token under Sv, i.e.:
Be(tok, [Sx]. D1) 2 (4J + +)s,
Be(toko [s J. D1) = 4Jf
(22)
Further, note that under Sv, we have that strings in dataset D2 are compressed to most symbols, while strings in D3 and D4 are compressed to at most three symbols:
Vc D2: (e(toks[S)).)) 2, Vc E D3 UD1 (e <
(23)
To improve on this compressed length, Sx must, thus, compress strings in D2 to a single symbol, or strings in D3 and D4 to one two symbols. Notably, this only be done if the non-compliant tokens in Sx contain 101 -tr-sttings. This is because, to compress a string in D2 to a single symbol, the full character-string must become a token, and D2 only includes 101-strings. Moreover, under Sv. strings in D3 and D4 are already compressed to at most (1x]. 1, x)1). To further compress them, tokeniser Sx must include tokens which cross the "middle" of this character-string. which would make this tokens at least have a 101 prefix or suffix. We consider the best case scenario, which is if they are exactly 1tt-strings, as any longer string will be most as frequent as it.
As discussed above, however, each 101 101-string appears at most: f' times in D2, f times in D3, and 3 times in D4. This gives us a best case scenario- in which all the strings in which a new token appears are compressed to a single symbol-where. where:
& (e(tokg[Sv), D2 U D3 D4) Ge(toks [Sx], D2 UD3 U S t(ff 2(f" + +3)
(24)
As the difference in Eq. (22) is of at least tff tokens, we put these together:
Gr(toko[Sv] D) (ttkkss(x) (( + 2( + +3) tf
(25)
As /' + + 3), this difference is smaller than zero, implying that S, improves on Sx. This shows a contradiction, which completes our proof.
LemmaProofStep 2. (Step 2). An optimal tokeniser must include all tokens of the form 1xf.x 1, 1x3, x. I, and further only tokens of the form 1x,1, 1x iee:
xI,,
J=1 Sopt and Sopt c { [I]x 1x7, 2x,,, f=1
(26)
Proof. As before, we prove this step by contradiction. Given step 1. we know an optimal tokeniser includes all tokens 1x], x]1, 1x5. x 1. Now, assume there exists an optimal tokeniser with vocabulary Sx with t > 0 tokens which not of the form 1x]. x11, 1xf,x or 1x]11, 1x,11 note that these t tokens are nocomponcmll Choose an arbitrary set of t unused compliant tokens -ie. with form 1x, 1x5 1-to replace the non-compliant tokens with, forming new tokeniser's vocabulary Sz.
Both these vocabularies compress strings in D2 equally:
Gr(tok, Dz) 4JF, (e(toks(Ss),D:) 4Jf
(27)
For strings in D2: if the entire string is in the vocabulary, is encoded as a single token; otherwise, represented with two symbols. Under Sy, there are J tokens covering strings in D2. Under Sx, there are only (J 1) tokens covering strings in D2. This implies:
3 (5ttoks(Sx), D2) (3J + D)
Be(toko[S/} D2) = =3
(28)
15

---

Published conference paper at ICLR 2026
Finally, for strings in D3 and D4, a similar argument to the previous step applies: (i) only tokens containing 101 101-stnsngs can compress these datasets; (ii) each 101-string appears at most f" + 3 times in them; (iii) each 101-string will lead to at most two symbols being saved. As Sx differs from S, in t tokens, we get that it will improve on it by at most:
Ge(toks[S/), D3 U D4) (tokk [Sx], D3 D1) S 2 +3)
(29)
Summing together the compression on all datasets, we get that their difference is bounded by:
Gr(toks[S/),))
(totkko[Sx]] D) I 2f( + 3) -t
(30)
As f > 2( + +), this difference is smaller than zero, implying that S, improves on Sx. This shows a contradiction, which completes our proof.
LemmaProofStep 3. (Step 3 An optimal tokeniser must be sat-compliant: must contain all tokens of the form 1x], x]1, 1xf, x51 and it must contain either 1x]11 or 1x511 for each S S J.
Proof. As before, we prove this step by contradiction. Given step !. we know an optimal tokeniser includes all tokens 131, Ixf, x Further, given step 2 we know its other tokens all have form 1x51, 1x.1 1. Now, assume there exists an optimal tokeniser with vocabulary Sy which includes both 1xf1 1 and 1xf11 for t > 0 variables, and thus neither of those two for t 0 other variables. Then, define Sy as a vocabulary where the 1xf1 token of all / doubly assigned variables are replaced with the 1x]1 token of all non-assigned variables. Note that S, is sat-compliant. These two tokenisers achieve the same compression on D1 and D2:
Ge(toks D1 U D2) = fJ + 33 and Ge(toko [S>], UD) = 4J
(31)
The tokeniser with vocabulary Sy will then compress each string in D3 to 2 symbols, while Sx will compress the strings 1x] 1x]1xf1 with unassigned variables symbols. This will lead to a total compression of:
Gr(toks [Sx], D3) = (2J+ +t,,,,
(s()) f
(32)
Finally, the doubly assigned tokens of the form 1xf1 (which Sy does not contain) appear at most three times in D4 and will lead to at most one symbol being saved, leading to a bound:
Gy(toks [S,], - 3x(tok, [Sx], D4) < 3/
(33)
Putting these compressed lengths together, we get:
Br(tok, [S D) - (r(toks[Sx) D) s 31 - tf"
(34)
As /"> 3, this difference is smaller than zero, implying that S, improves on Sx. This shows contradiction, which completes our proof.
LemmaProofStep 4. (Step (4) If an optimal tokeniser achieves compressed length of at most 329J - 31 the original 3-OCC-MAX2SAT instance is satisfiable, i.e.:
(pppt D) < 329J +-1 +3I-7)
30M25(X,C,7)
(35)
Proof. Given steps 1 to 3) we know that an optimal tokeniser will be sat-compliant. We will now denote this optimal tokeniser's vocabulary by Sept and use Eq. (18) to extract a 3-OCC-MAX2SAT assignment x = gSSppt) which corresponds to this tokeniser's vocabulary. From the previous proof steps we see that any sat-compliant tokeniser achieves the following compressed length in D,, D2. and Dy:
(e(toko(Sope). D, D2 D2D)) 4Jf + 3J 22 329J
(36)
Now, note that a character-string 1 in D4 will be: compressed to two symbols at least one of the tokens 1L, 1 LL; exists, or compressed three symbols neither exists. Equivalently, a clause L.VL3 in 300CCMMA2SAA is: satisfied if either L! or L3 evaluates to true, or not satisfied if both evalu- ate to false. Given our construction of function g above, one of 3-OCC-MAX2SAT'S clauses will be satis- fied if and only if its corresponding string in D2 is compressed to two symbols. We can thus state that:
Σ 11 12) [[)=))))>
G (x(ttkk Da) = 31 ---
x+)
(37)
Given the construction of 329.J 31 - 7, we conclude that sat-compliant tokeniser which compresses the full dataset to at least that size can be mapped to a 3-OCC-MAX2SAT assignment which satisfies at least 7 clauses. This concludes the proof.
16

---

Published conference paper at ICLR 2026
D PROOF THAT BINARY DIRECT TOKENISATION IS APX-HARD (STEP 1 OF THEOREM 2)
We prove APX-hardness of D-2-TOK by providing an L-reduction (defined in Definition 4) from the APX-complete problem 3-OCC-MAX2SAT (Berman and Karpinski, 1999). For the reduction function Jo-2-Tok of the L-reduction, we do not introduce new transformation: directly reuse the reduction from Reduction 1. To complete the L-reduction, we additionally provide reconstruction function 9b-2-Tok that maps any feasible tokeniser for the D-2-TOK instance back to valid Boolean assignment for the original formula. We then verify these functions satisfy the L-reduction conditions for suitable constants and B. Notably, for given instance (X,C) and assignment {F, T) of the 3-OCC-MAX2SAT optimisation problem, we will denote its cost function as
6 (2 == 1
(38)
Now that the objective (cost) functions for both problems are fixed, prove APX-hardness. Lemma 3. The binary direct tokenisation problem is APX-hard.
Proof. We prove that D-2-TOK is APX-hard by constructing an L-reduction from the APX-complete problem 3 3-OCC-MAX2SAT. Let (X,C) C) be arbitrary instance of 3-0CC-MAX2SAT, To establish the L-reduction, we must define pair of polynomial-tine instances and solutions between the two problems, and find constants a and / such that the conditions in App. A are satisfied. We will prove this holds for = 444 and 3 1.
algorithms, fo-2-rok and 9o-2-1a6, that map
L-Reduction's Condition (i) is Satisfied. First, want prove that algorithm f0-2-Tok produces an instance (D, K) = (o- C) of D-2-TOK such that
Tok (fo-2-fooooooee (X),) S a 30M2S* (X,C).
(39)
We define fo-2-Tok using the polynomial time construction detailed in Reduction 1, Since this mapping formulated for the decision problem as R1 (X', 7) = (D, K, 5), we discard the target values from the function definition for the optimisation problem. Formally, we define fo-2-Tox ( where the dataset D and the token budget K 5J remain identical to the original construction.
(D, K),
As shown by Eqs. (36) and (37), the size of any dataset tokenised by sat-compliant tokeniser S, is linearly related to the number of satisfied clauses y by assignment x g(S)):
(r(tok,(S)) D) = -329. + +1
(40)
As there is one-to-one mapping between sat-compliant tokenisers, and assignments x it trivially follows that the optimal tokenisation size is Tok? 2.* (D, K) 329J 3/ 30M2S* (X, C).
By definition, each variable in X' appears exactly three times in C, and each clause contains two literals. This implies 3./ 27. Furthermore, there always exists (efficiently computable) assignment satisfying at least half the clauses, meaning that the problem is trivial for y < 5. We thus restrict our attention cases where 30M2S* (X' C) Tope 2 11, which constitute the interesting instances of 3-OCC-MAX2SAT Substituting J / into the optimality equation, we get:
Tok?" (fo-2-To (X, C)) Tok. 2. (D,
(41a)
2
329
1
31 - 30M2S
(41b)
667
-
10M0MM2 (X,C)
(41c)
3
1331
30M2S*
(41d)
3
Thus, the first condition of the L-reduction holds with 444.
17

---

Published conference paper at ICLR 2026
L-Reduction's Condition (ii) is Satisfied.
Second, let (D, fo-2-Tok (X, we want to prove that algorithm 9b-2-Tok maps any solution S of (D, K)) to solution x of (X' such that
M2s (x." C) 30M2S (X, C)L $ 3 [G,(tok,(S), D) Tok 2. (D, (D, K)1,
where (D,K) fo-2-Tox C) t = 92-2-ToX C) (42)
We define the polynomial-time algorithm 9b-2-ToK to map any valid D-2-TOK solution S of a mapped instance (D, K) back to 3-OCC-MAX2SAT assignment x. for (X,C). As established in Lemma (Steps 1-4), an arbitrary solution S may contain sat- sat-noncompliant tokens, which must be systemati- cally switched to compliant ones before extracting truth values.
Let S be any feasible solution to the mapped instance (D, K, RI(,,, 7). Note that, by the problem definition, these tokenisers have vocabulary size |S| = | + K. We then define:
S' = [x], x311, 1xf, xf1))=1
s" = 1x]]1, 1
(43)
Using Lemma 2, we construct in polynomial time vocabulary S, that is sat-compliant and satisfies Gx(tokg (S)1,D) S (e(toko(S)),0
(44)
The construction is as follows:
1. While there exists t E S' \ S, choose any u E S S' and set S + (8 u By Step O this replacement does not increase (ottoko[S]..0)
2. Let S Snon-comp
(S' 8"). Choose any set S Sasssing S S" S such that |Snssiing Spon- chon-comp1l and define: S + (S Snonnccopl) U S Sissing. By Step ② this replacement
does not increase (r(toks[S),
3. While there exist indices j * k such that {Ix]1, 1x]1] S and [Ix]1, 1x 0. choose any {1x]11 1xf1) and any E {ix]1, 1x,11, and set S +- (8) u By Step 3, this replacement does not increase ((tok,(S).2)
Let Sy be the final vocabulary. By construction, S' S S. S and for each j exactly one of 1x.1 or 1xf1 belongs to Sy: hence S, is sat-compliant, and the objective inequality follows from the three nonincreasing replacements. Further, this polynomial-time transformation guarantees that the total compressed length does not increase, ensuring Gr(toka [t]t D) < Gx(toko (S), D).
We can now use the algorithm g defined in Eq, (18) to extract the variable assignment x directly from the compliant tokens in Sy. Thus, we define 9b-2-ToK as the application of our extraction function to this sat-compliant vocabulary:
T = T J =
1x E S, elif 1x S
90-2-
- (x,)) where
(45)
From Eqs. (36) and (37), the objective value of the sat-compliant tokeniser S. has a linear relation to the value of assignment x":
Gy (S,], 329J + 31 - GM2s(x",C)
(46)
We can now prove our desired bound as:
@r(toke[S], D) Tok?" 2.* (D, K)
for K) So-z-ToK (XC,)
2 (t) Tok3 Tok2.t(,,K (D,K)
(47a)
(329J 31 - 6 ( (329- + 33 - 30MM25(XX,)) for X = 90-2-Tok ((,
(47b)
30M25*(X,C))) B (x2s(x*.C)
(47c)
Taking absolute values, reductions holds with | = 1. Since 3-OCC-MAX2SAT APX-complete, this L-reduction completes the proof that D-2-TOK is APX-hard.
the inequality in Eq. (42)-and thus the second condition for L-
18

---

Published conference paper at ICLR 2026
E PROOF THAT THE BINARY DIRECT TOKENISATION GAP PROBLEM IS NP-HARD (STEP 2 OF THEOREM 2)
Lemma 4. The binary direct tokenisation gap problem NP-hard.
Proof. For this proof, we rely on a result by Berman and Karpinski (1998; 1999) that, for specific instances of 3 3-OCC-MAX2SAT with 1 = 201 6n clauses, it is NP-hard distinguish whether at least (2012 - E)n or at most (2011 + E)n of these clauses are satisfiable, for any > O. We will denote this 3-0CC-MXX2SAT gap problem by 30M2S(X, C, (> ,t)),, with ? (2011 + s)n and y* (2012 E n. We can now prove NP-hardness of the binary direct tokenisation gap problem
by reducing 3 --OCC-MAX2SAT's gap problem to it. To this end, we rely on reduction identical to (1''', y), but where we define:
8 = 329. + 3/ Y
8+ -29./ + 31 -
(48)
329J + 37 201 1 + I
2012
329J 37-
2016
2016
Lemmas and 2 trivially show the validity of this reduction:
(,, () = Tok (0
(49)
which holds since 30M2S(X, C, = (D, K, K,O+) and the same for 7 and 6= It is
therefore ha-hard to distinguish whether dataset can be compressed to at most 329 2012
2016
symbols, if at least 329J+3I- 2011+ I symbols remain (with allowed vocabulary size K = 5.)).
Since each variable occurs exactly three times in 3-OCC-MAX2SAT, we have that 3 = 1. We now compute a lower bound on the best achievable compression ratio:
8
329.J + 31
2011+
2016
(50a)
8+
329J
+ 31
2012 -
2016
667
+033+33
2016
(50b)
667
6036-
2016
1338639
3e
(50c)
1338636 + 3e
446213 -
(50d)
446212 +
Thus, binary direct tokenisation cannot be approximated in polynomial time with an approximation ratio better than 446213 > 1.000002, unless P = NP.
146212
F PROOF OF FORWARD STEP OF THEOREM 3
We first need another lemma in preparation for the actual proof of this forward step. Note that Reduction 2 produces character-strings x). and xf. with form {0r 1 2J). which our tokeniser must compress. However, a merge-sequence m = 1' @ does not compress all these targets into a single symbol; character-string 0000, for instance, would be merged into (00, 00) by the first merge 0 in this sequence, and merge 03 0 would not be applied to it. Thus, we need to describe a more unwieldy merge sequence to achieve this with the same number of merges. We do so in App. F.I, where we show that exactly 2J merges are required to compress all these strings into a single symbol. With this, we now prove the forward step of Theorem 3 in the following lemma.
Lemma 5. I 3-OCC-MAX2SAT instance satisfiable, then the B-2-TOK instance output by Reduc- tion 2 is also satisfiable. Formally: 30M25(X,C,n) - Tok3 C))
Proof. Assume this (X, C,CC,)) 7) instance of the 3 3-OCC-MAX2SAT decision problem is satisfiable, i.e., that 30M2S(X, C, 7) is true. We must prove that in this case, Tok (RI (X,C,))) is also true. We
19

---

Published conference paper at ICLR 2026
define the following list of merges which, as shown in SubLemma compresses every target of type x] or x into single token:
mi (1 @ 1)
Of Ml 1(00' @ 0² ]]
DoRa JJ j=1 O [00 @ 0²)o
(51)
merges which compress each x3 and x/ single token
Note that the merge 1 @ is independent of the merges on O) and could thus be placed at any point in the sequence. We also define the following lists of merges, which will be included in any satisfying solution to the tokenisation problem:
m2 1 @ ) (x) @ 11)],
m4 = -f=111 @ 1). @ xx)]
(52a)
m O xf). (x) 1)]
(52b)
Now, let x² = {xj}ン=1 any satisfying solution to the 3-OCC-MAX2SAT instance CX,,,)). We define the following instance-specific merges:
Ó [ m3 m3= y=1
(1 (1@ x11 if 23 =T (LIx] 1)
(1x @1 ms ò [
(x (1xxfi)
if if =T
(53)
else
else
In words, we include merges I @ x 11 and 1x, if 23 is true, or 11x, @ and
1@
x3] if
is
false. We then create a merge sequence by concatenating these lists in order:
m1 m2 ma m4 mş m6
(54)
This gives us a total of m = K = 10. merges. Now we just need to count the symbols output by this solution check whether the bound satisfied.
By applying the merges m, each string in D will be compressed into a single symbol, obtaining:
By(tok, [m], D1) (1 + 8JJff
(55)
For each pair of strings 1x31 and 1xf1 in D2, one is compressed into single symbol while the other
only compressed two symbols the one with x is compressed into a single symbol a3 and the one with x otherwise. The same is true for each pair of strings 1x]11 and 11x51, also in D22-
We thus have that, for each variable X,, the strings in D2 will occupy a total of (1 2 1 1+ f) symbols, and:
Ge Se(tok, [m]. D2) = 6 Similarly, each string in D3 and D4 will be compressed into only symbols after this tokeniser is applied to it. We thus have:
(56)
Gr(toky [m]. D3) = J, (,(tok;[m) Da) =
(57)
Finally, we have the strings in D;- These strings are constructed such that they will be compressed
into 2 symbols if either L or Lł evaluates to and kept with symbols otherwise; see Tab. 1 for detailed simulation of why this is the case. We thus have:
L X, and x1 e 1)
or 1 -x, and (11xf Φ 1), 0 Em or L Xy and (1 (1xx @1) Em
By(tok, [tto, Dz) =
3 - 1
(58a)
1=1
or L3 = -Xy and (1Ix² @ (1
31 Σ
1x (L) v LT}
(58b)
31
(58c)
where, by construction, we have a merge in our sequence (e.g.. 1 x111 11x o 1) if and only if its value is in a satisfying assignment (e.g., 4; = Tor xj = F, respectively). Summing together the lengths in Eqs. (55) to (58), we get that:
(tok, [m], D) s 8 (1 8J)f + (6f +4f" + +4f") J +3 31-9
(59)
which concludes the proof.
20

---

Published conference paper at ICLR 2026
Anggeee
Credison
wodfen mggo)
tell Jouy my mmv0m
tols mnnee
tel: Jmu
(fac
(1421 -2.3
Oig
Baguuaaa
[Ctat: 3.45-1
(63,013000
Table 1: Performance of merges on strings in D5, adapted from Whittington et al. (2025). The dot symbol denotes the string not changing under the given merge.
F.1 PROOF THAT EXACTLY 2J MERGES OPTIMALLY COMPRESS THE 2J O STRINGS
SubLemma 1. Given character-strings {0$ j 2J), an optimal bottom-up tokeniser requires exactly 2J merges to encode all these strings into a single token. 6
Proof. We establish the result in two steps:
we prove that least 2J merges are required to reduce these strings single token;
we prove that 2. merges are sufficient to reduce these character-strings to single token.
Given these upper and lower bounds, conclude exactly 2. 1 merges required to reduce these character-strings to a single token. This completes the proof.
SeboosspPro 1. (Step D). Given character-strings (0) j < 2J}. an optimal bottom-up tokeniser requires least 2J 1 merges encode all these strings into single token.
Proof. The target contains 2. distinct values, of which is the base symbol 0. Whenever target becomes single token through a merge, that merge must combine exactly two tokens whose concatenation equals that specific target. Since all targets are distinct, this concatenation cannot simultaneously equal any other target. Hence, a single merge can complete at most one target. It follows that least 2. merges are required to reduce all targets to single tokens.
PaboaosePPoofSt 2. (Step 2) Given character-strings (0' | S S 2J), there exists an explicit merge sequence that reduces all these strings to single tokens in exactly 2J 1 merges.
Proof. For the matching upper bound, we will construct an explicit merge sequence, composed of two types of merges:
1. Binary stage. For each power of two up to J-ic., with j N such that 2 < J incrementally include binary merges as 02 0²².
2. Extension stage. For each power of two up to J-i.e, with j E N such that 2 < J- incrementally create non-binary merges by merging binary tokens 0 with non-binary ones
0 (with j' E N such that j' < 2/). These merges will thus be 0
These merges are combined as:
O llog J
j
[(0 0²))
lloga J1 ==1
O3'z1 10 o'))
(60)
binary mergos
merges
"Note the same is true for both optimal direct tokenisers, and optimal OPE tokenisers (defined in $5.2). As we will see in the proof, the smallest non-fully merged value always consists of only two symbols, such that the "rightmost" tiebreaker not necessary.
21

---

Published conference paper at ICLR 2026
Note that, as merges are created incrementally, token 0 always exists when merge 02 @02² is applied. Similarly, for j' < 2¹, both token 0² and 0* will exist when merge 0² @ of is applied. Finally, for J'.j" < 2 tokens 0' and 0 will both be created before any extension merge with left-side 0² is applied: thus, merge 0 @ 0 will never affect subword-string, (0 ,0'") or vice-versa. After these merges are applied, it is easy to see that each character-strinn {0r S j - 2 will be represented as single symbol. As the merge- sequence above contains 2. merges, this completes the proof.
G PROOF OF BACKWARD STEP OF THEOREM
We again start with defining some useful notions and redefine compliant tokenisers.
First, even though this section about bottom-up tokenisers, we define a term addressing direct tokenisers, meaning this definition describes tokenisers with tokens instead of merges. We will use this definition in our lemma to prove a fact about direct tokenisers, which we later generalise by showing that it applies to bottom-up tokenisers well. We define sat-compliant (direct) tokeniser to be any tokeniser which: (i) contains all tokens of the form 11, xJ. X 1x], x31, 1x x 1,11,x 11xf. and (ii) contains either 1x,1, 1x, 11 or 1xf11 11x;1 for each j E (1....,J}. Otherwise, we call the tokeniser sat-noncomillaatt. Again, given the vocabulary of a sat-compliant tokeniser, we can easily build an assignment to a 3-OCC-MAX2SA. instance with the same function as for direct tokenisation, defined in Eq. (18):
===T T if e elif LxfES
g(S) {zy})=ı where
(61)
==
We further adapt the definition of 101-strings to also include all character-strings of the form 110+1 and 10+11. 11. Considering the datasets output by Reduction 2, we know that there are no 101-strings in dataset D Further, we know that each unique 101-string appears in datasets D2. D3. and D4 exactly 2 2 and 2 times, respectively, and exactly 3 times in Ds (this is due to working with the orrrreoccursseees variant of MAX2SAT and to the fact that x = 02)-1 and x = 02)). We now prove the following lemma.
Lemma 6. If the B-2--OP TOK instance output by Reduction 2 is satisfiable, the 3-OCC-MAX2SAT instance which generated it is as well. Formally: (R2((,,,,))) = 30M2S(X,C,n).
Proof. Assume this B-2-TOK instance (D, K, (D, R2(X', C, 7) i satisfiable, i.e. that (R2 C)) evaluates to true. We must prove that, in this case, 30M2S C, also evaluates to true. Now, let Mopt be an arbitrary optimal solution to (D, K, 8). We know, by definition, that:
Tok (R2(X,,
(meptok/(oop.l D))
(62)
We can thus prove this lemma by showing the following implication:
( (Se(tokymmopl) D) < =6) = 30M25(x,C,7)
(63)
When comparing two bottom-up tokenisers, things quickly get messy, because we have to not only consider the merges, but also their order. For this reason, show that sat-compliant direct tokenisers can be transformed into bottom-up tokenisers without loss of compression quality. Thus, for the sat-compliant tokeniser, we can consider the direct tokeniser instead. The key idea for this to work that all target strings are hit via a sequence of merges such that each intermediate merge also hits a target (which has high multiplicity), such that this target must also be included tokeniser. We also compare to sat-noncompliant direct tokenisers, which are by definition at least as strong as nottom-up tokenisers; thus we can compute upper bounds on their performance.
token by direct
Let Sept again be the optimal direct tokeniser for (D, K, 8). We will proceed in six steps:
1 we prove that Sept must include
all
tokens of the form
11, x 1xJ, xJ1, 1xT, x11, x11, 11x5,
22

---

Published conference paper at ICLR 2026
we prove that Sop must, in addition the tokens above, only include tokens of the form 1x 1xf1, 1x1,,,
we prove that S Spt may only include, for each j. either token 1x or 1xf11, and either token
1 1xx]1 1 or 1xf11;
we prove that Sopt may only include, for each j. either tokens 11x31, 1x31 1xf1, 1xf11
we prove that for any sat-compliant Supt. there exists a merge sequence mopt with the same performance;
finally, we prove that if (mxpt) D) which satisfies this 3-OCC-MAX2SAT instance Cx)
S 6).. we can build variable assignment
Note that, together, Steps ! to 4 show that Sept must be the vocabulary of a sat sat-mopplian direct tokeniser; in Step 3 we show that we can convert any sat-compliant Sops to a merge sequence Mopt without losing compression, showing an equivalence between the two types of tokenisers for these reduced instances; and in Step (). we will then rely function g (defined above) to convert this merge sequence into a satisfying assignment X. = opSo for the instance (X, C.7)
LemmaProofSter 1. (Step 1). An optimal (direct) tokeniser must include all tokens of the form 11,x), x9. 1x]. x
1, 1xf, x 11,,, 11x3, i.e.:
11, 1x
1x
11x,
C S
(64)
j=1
Proof. We prove this step by contradiction. Assume there exists an optimal tokeniser with vocabulary Sx which does not include >> O of the tokens above. Now, remove i arbitrarily chosen tokens in this vocabulary which are not the form above, and replace them with the missing tokens this set. We denote this new tokeniser's vocabulary by S.. Note that the strings in D) with these missing tokens were represented with at least 2 symbols under Sx, but with a single token under Sy, i.e.:
Gz(tok, [Sx), 2 (8J + 1 t)S,
(e(toko[Sy), Di) = (8J + 1)S
(65)
Further, note that under Sy, we have that strings in dataset D: are compressed to at most two symbols, while strings in D3. D4, and D; are compressed at most three symbols:
Vc D2: (S S 2, Vc E D3 UD UDs : (e(toks(Sy),c) 3
(66)
To improve on this compressed length, Sx must, consequently, compress strings in D2 to a single symbol, strings in D3, D4, and D5 to the noncompliant tokens in Sx contain 101-strings.* & As discussed above, however, each 101-string appears, prefix or suffix, at most: 2 times in D2, 2 times in D3, 2 times in D4, and times in D5. This gives us a best case scenario in which all the strings in which new token appears are compressed single symbol where:
two symbols. As before, this can only be done if
Be(toko[S>], UD UDD UDD) D2 DDD2DD UDJUD.UD))
(67)
I =t(2f' + 2(2 28"h + 3))
As the difference in Eq. (65) is of at least if tokens, we put these together:
Cx(toks (x(toko(Sy), D) Gx(toko [Sx], S ((2 + 2(2/" + + + +3) -f
(68)
Since f> 2(2 + 2f" + 2f 2f 3). this difference is smaller than zero, implying that S, improves on Sx. This shows a contradiction, which completes our proof.
'This follows the same argument as in the proof of Lemma Note that the extension of 101-strings to include strings of the form 110*1 and 10 11 does not break the argument, as the substring has to appear as prefix or suffix to yield a saving. Thus, even though the strings of form 10+1 are included in the new strings, we do not have count those occurrences.
23

---

Published conference paper at ICLR 2026
LemmaProolStep 2. (Step 2). An optimal tokeniser must include all tokens of and further only tokens of the form
the form 11, x x, 1xj, xj1, 1xf, xf1,
1x 1x3 1, 1x 11x 1, i.e.:
11, 11, x 1xJ, x 1, 1xf, x311, 11x} / j=1 C Sopt and
(69)
1x51, 1xf1, 12,11,11111 11x51 }
Sapt C 11, 11,
1xj,
Proof. As before, we prove this step by contradiction. Given Step ! we know that an opti- mal tokeniser includes all tokens 11,x].x;, 1xf, x;1, 1xf,
Now, assume there exists an optimal tokeniser with vocabulary Sx with > 0 tokens which are not of the form 11,x).xx, 1x), x Lx xx11, 11x, or ,x 1x we will call these tokens non-compliant here. Choose an arbitrary set of t. unused compliant tokens-i.e. with form 1x51, 1xf11 11, 11x replace the non-compliant tokens with, forming a new tokeniser's vocabulary S,. Both these vocabularies compress strings in D1 equally:
(t)) (8J + 1)5,
Ge(toko[S<), Di) (8J+1)
(70)
For strings in D2: if the entire string is in the vocabulary, it is encoded as single token; else, it is represented with two symbols. Under Sy, there are 2J tokens covering strings in D2- Under Sx, there are only (2J - t) tokens covering strings in D2. This implies:
6 (Stkkk(Sx), D2) = (6J + +)',
(s = 6J
(71)
For strings in D3. D4, and Ds. an argument similar to the previous step applies: (i) only tokens containing 101-strings can compress these datasets; (ii) each 101-string appears, at most 2 + 2 + times in them; (iii) each 101-string will lead at most two symbols being saved. As Sy differs from Sy in & tokens, get that it will improve on it by at most:
prefix or suffix,
6g(tok, (tttok/[Ss].200 D3 U D2 U Ds) - By(toks [Sx], D3 U DA Ds) S 2t(f + 2f" +3)
(72)
Summing together the compression on all datasets, we get that their difference is bounded by:
G,(toks($y), D) (x(tokk [Sx), D) < 21 25" + +3) -ff As f' > 2(2f" + 2 + 3), this difference is smaller than zero, implying that S, improves on Sx- This shows contradiction, which completes our proof.
(73)
Li
LemmaProofStep 3. (Step 3 An optimal tokeniser must contain all tokens of the form 11.x,, xf. LxJ, x,,, Lx), x 11,,111,115, and further only tokens of the form 1x51115511 Ix]11, 11x51, and for each 1 I j S J, it must contain exactly one of 1x]1, 1x511 and exactly one of
Proof. As before, we prove this step by contradiction. Given Step D. we know an optimal tokeniser includes all tokens 11, 11,x], xf., 1x],, x, 1xf, 1xf,, x,,,, 1xx Further, given Step (2. we know its other tokens all have form 1x]1, 1x 1x311, 11xf1. Now, assume there exists an optimal tokeniser with vocabulary Sx which includes both tokens in pair 1x]1, 1x, or 11x]1, 1x for > 0 such pairs, and thus neither of those two for f. > 0 other such pairs. Then, define S as vocabulary where the 1x51 respectively 1xf11 token of all doubly assigned pairs are replaced with the 1x!1 respectively 11x]1 token of all uncovered pairs.
These two tokenisers achieve the same compression D1 and D2:
(x(toks[Sx), UD2) = (8J + +J Gr(toks[S UD2) = (8J + +1f +J
(74)
The tokeniser with vocabulary Sy will then compress each string in D3 to 2 symbols, while Sx will compress the strings of the form 1x] 1x]1xf1 or 1 1xf11x111 1 for which their respective pair 1x] 1x51 or 11x31, 1x51 11 is uncovered, to symbols. This will lead to a total compression of:
Ge(toko(Sx) Dz) (4J + +tf"",
Be(toksSS/) (S)), 4J
(75)
24

---

Published conference paper at ICLR 2026
Finally, the doubly assigned tokens (which S does not contain) appear at most fr times in D1 and three times in 5s and will lead to at most one symbol being saved, leading to bound:
[t/ D4 U Ds) - Gz(toks D4 DD) S t(f" +3)
(76)
Putting these compressed lengths together, we get:
B (y(tok,[Sy]
Go(toks [Sx], S t(5" +3) 11"
(77)
As f" p + 3, this difference is smaller than zero, implying that Sy improves on Sx. This shows a contradiction, which completes our proof.
m
LemmaProofStep 4. (Step ④). An optimal tokeniser must be sat-compliant: it must contain all tokens of the form 11, x,, xf. xx3,x]1, 1xf, x² 1, x3 11, 11x, and further only tokens of the
form 1x31, 1x 1x311, 11x31, and for each 1 S j S J, it must include either 1x) 1, 1x) 11 or 1xf1, 11x
Proof. As before, we prove this step by contradiction. Given Step ①. we know that an optimal tokeniser includes all tokens 11, x1,x 1x], x311, 1x5, xf,1, x3 11, 1ix Further, given Step 2 we know that its other tokens all have form 1x, 1xf,1 1x] 11, 1xx Finally, given Step 3 we know that it contains exactly one token for each pair 1x] 1, 1x51 and 1x]11, 11xI1.
Now, assume there exists an optimal tokeniser with vocabulary Sx which includes both tokens in a pair 1xf 1, 1x31 1 or 1x,11, such pairs. Then, define S, as a vocabulary where the 1xf11 respectively, 11x5) 1) token of all doubly assigned pairs are replaced with the 1x31 (respectively, 1x{11) token of all uncovered pairs. These two tokenisers achieve the same compression on 11, D2, and Dz:
for & such pairs, and thus neither of those two for > 0 other
Ge(toks D1 U U2 U D3) (8J 1)S + 6J + 4JJ" Gr(tok, [S,],
(78)
Dj U U D3) (8J 1)ʃ + 6J 4JJ"
(79)
The tokeniser with vocabulary S. will then compress each string in D4 to 2 symbols, while Sy will only compress the l strings of the form 1xf1x]] or 1xxf1x31, 1, for which the pair is uncovered, to symbols. This will lead to total compression of:
(t(tok((Sx] (a) Da) = (4J + t)f",
(s) = f."
(80)
Finally, the i doubly assigned tokens of the form 1xf1 or 11x (which Sy does not contain) appear, as a prefix or suffix, at most three times Dz. and will lead to at most one symbol being saved, leading to a bound:
Cx(toks [St]. D3) - (Sxtok//Sx),200 3t
(81)
Putting these compressed lengths together, we get:
By(tok, (o(tok.[Sy],22 D) Ge(toks [Sx], D) S 31- -
(82)
As f" 3, this difference is smaller than zero, implying that Sy improves on Sx. This shows contradiction, which completes our proof.
LemmaProofftep 5. (Step 2) A sat-compliant direct tokeniser can be transformed into bottom- up tokeniser without changing its performance. As any optimal direct tokeniser is sat-compliant, this implies:
Toke (R2(X,C,))
(83)
Proof. As every bottom-up tokeniser can be interpreted as a direct tokeniser with the same vocabulary size and possibly suboptimal application of its tokens, it holds that:
T C, c)) = Tok3 (R2(X, c))
(84)
This is to say, direct tokenisers always compress at least as well as bottom-up tokenisers, when allowed the same vocabulary size.
25

---

Published conference paper at ICLR 2026
Given a sat-compliant direct tokeniser, we first describe how transform into a bottom-up tokeniser. We always include merges:
mi @1 1) j=1 1og(2/-1)) [(0 00d)] O j=l O3 100 @ 00)],
(85a)
m2 = 01 C xx)), @ 11)],
(85b)
m4 10= o 1)) (xx]]
(85c)
m = O)=1((1 @ 5x) (x) o 1)]
(85d)
and additionally, depending on which tokens are included in the direct tokeniser's vocabulary S:
@ 1I) (1ix) @
if 1xf11 E
m3
(85c)
else
3=1
[lx] @1 (1)
ix eS
m5 = O
(851)
else
Note that since the tokeniser is sat-compliant, we have:
1xf11 + IxfLES
(86)
is easy to verify that the resulting bottom-up tokeniser has the same performance on datasets D1 to Da. For D,, Tab. 1 shows that each string which could be reduced two symbols by the direct tokeniser is also reduced to two symbols by the bottom-up tokeniser. Thus, we get:
Toke (R2(K, > TR2x(
(87)
which completes this proof.
LemmaProofStep 6. (Step (). If an optimal (direct) tokeniser achieves a compressed length of at most 5398.J + 575 31 y, the original 3-OCC-MAX2SAT instance satisfiable, i.e.:
( (ce(toks(Sopp)))) D) - 5398./ + 575 + 31 -7) = 30M2S(X,C,
(88)
Proof. Given Steps ! to 4) we know that an optimal tokeniser will be sat-compliant. We will now denote this optimal tokeniser's vocabulary by Sept and use Eq. (18) to extract a 3-0CC-MAX2SAT assignment x = (Spope) which corresponds to this tokeniser's vocabulary. From the previous proof steps, know that any sat-compliant tokeniser achieves the following compressed length in Dj, D2, D3, and D4:
(e(toko(Sapt) UUD.DDD = (8J+1) - 4J + 4J
(89a)
= (85 6 115 + 23 + 4 J)J 575
(89b)
5398./ 575
(89c)
Now, note that any target string in D3 will be: (i) compressed to two symbols either if L or L?
Xj and tokens 1xद1 I and 1x;11 exist or LŁ or Li -X, and tokens 1x,1 and 11x exist: or (ii) compressed to three symbols neither case is satisfied. Equivalently, a clause I.} T. in 3-OCC-MAX2SAT is: satisfied if either L! or Lł evaluates to true; or not satisfied if both evaluate to false. Given our construction of function g above, one of 3-OCC-MAX2SAT'S clauses will satisfied if and only if its corresponding string in D4 is compressed two symbols. We can thus state that:
([tooko(Sop), Ds) = 31 -1--')
--*)
Σ Fe (T. V [2] 7
(90)
Given the construction of 8 as 5398.J 575 31 7, conclude that sat-compliant tokeniser which compresses the full dataset to at most that size can be mapped a 3 3-0CC-MAX2SAT assignment which satisfies at least y clauses. This concludes the proof.
26

---

Published conference paper at ICLR 2026
H PROOF THAT BINARY BOTTOM-UP TOKENISATION IS APX-HARD (STEP) 1 OF THEOREM 4)
We prove APX-hardness of B-2-TOK by providing L-reduction (Definition 4) from the APX- complete problem 3-OCC-MAX2SAT (Berman and Karpinski, 1999). For the instance mapping fo-2-Tok. we reuse the construction of Reduction 2. To complete the L-reduction, we define a reconstruction mapping 9b-2-TOk that converts any feasible merge sequence (or induced tokeniser) for the B-2 B-2-TOK instance into Boolean assignment, and we relate objective gaps via the 3-OCC-MAX2SAT cost function defined in Eq. (38), which we repeat here for convenience:
(x) ==1
V
(91)
Lemma 7. The bottom-up binary tokenisation problem is APX-hard.
Proof. We prove that B-2-TOK is APX-hard by constructing an L-reduction from the APX-complete problem 3-OCC-MAX2SAT. Let (X', C) be an arbitrary instance of 3-OCC-MAX2SAT. To establish the L-reduction, we must define pair of polynomial-time algorithms, f6-2-rok and Ie-2-rok, that map instances and solutions between the two problems, and find constants a and [ such that the conditions in App. A are satisfied. Below, we prove these conditions hold for a = 7778 and B == 1.
L-Reduction''s Condition (i) is Satisfied. First, we want to prove that algorithm fa-2-Tok produces an instance (D, K) So-2-Tok (XX C) of B-2-TOK such that Tok? (fe-2-To
S a 30M2S' (X,C).
(92)
We define f8-2-Tok using the polynomial- construction detailed in Reduction 2. Since this mapping formulated for the decision problem as R2(X c) = (D, K, d), we adapt it for the optimisation setting by discarding the target values (i.e., 7 and 6) from the function definition. Formally, we thus define fe-2-Tok (X, C) = (D, K), where the dataset D = D, U D2 U D3 U U D3 and the token budget K = 10. remain identical to the original construction.
As shown by Eqs. (89) and (90) in the previous section, for any sam-compliant tokeniser, the size of the dataset tokenised with m, is linearly related to the number of satisfied clauses y* by the boolean assignment it corresponds to x = g(Sm,), where g is defined in Eq. (61):
(y(toky [m/], D) @z(tok, [S mm D)
by Lemma 6 Step
(93)
5398. 575 + 3/ - 7
by Lemma 6 Step 6
(94)
As an optimal tokeniser must be sat-compliant (by Lemma Step (-4), it follows that the compression it achieves is
Tok 2 (D, = 5398. + 575 + 31 - 30M2S*
(95)
By the definition of 3-0CC-MAX2SAT, each variable in X' appears exactly three times in the clauses C. and each clause contains exactly two literals; this implies 3J = 27. Furthermore, it is trivial to find an assignment that satisfies at least half the clauses. We now thus restrict ourselves to the non-trivial subset of instances with: 30M2S* (X, C) 2 I. We also note that we can always satisfy at least one clause: 3 C) 2 We can now manipulate the optimality equation to get:
Tok3 (D, 5398.J + 575 + 31 30M2S C,
(96a)
2
= 5398
+ 575 + 31 30M2S* (X),)
since J
(96b)
3
3
10805
574.57750 (x,c)
574
since 1 < 30M2S* (X, (96c)
3
21610
30M2S*
+ 574 SOM25((XC))
since I 230M2S (2, C) (96d)
3
221610
+ 574
30M2S (x,C)
(96e)
S 7778 30M2S*
30M2S*(X.C)
(96f)
Thus, the first condition of the L-reduction holds with 7778.
27

---

Published conference paper at ICLR 2026
L-Reduction's Condition (ii) is Satisfied. Second, let (D,K) = fs-2-Tox (X, C), we want to build
an algorithm 9B-2-TaK which maps any solution m of (D, K) to solution X3 of (X' C) such that
Mrs( C) - 30,2S0(X,.
S B [6.(tok- [m]; D) - Tok *0 (D, K)), where (D,K) = f8-2-Tok (X, (x,C). C).
(97)
X 9a-2-Tok (X, C), m)
We will now define the polynomial-time reconstruction algorithm 98-2-Tok to map any valid B-2-TOK solution- a merge sequence for the reduced 3 -AX22ATT instance (D, K) back to Boolean assignment X. with bounded quality.
First, remember that bottom-up solutions are specified by merges rather than explicit vocabulary. The first step in our construction will thus be to map these m to their induced token set Sm (the alphabet Σ together with every token created by merge in m). Notably, this transformation is cost-noninereasingg. i.c.;:
By(tok, [m], D) 2 (e(toks(Smm)
(98)
Notably, induced vocabulary may contain sat-noncompliant tokens. We now transform this vocabulary Sm into sat-compliant via the cost-nonincreasing replacement procedures of Lemma 6's
Steps ①-4. This will later allow us to extract Boolean assignments x with bounded quality from this sat- sat-compliant vocabulary. Before defining our cost nosinccnnnng transformations, however, we define the following vub-vocabularies:
S'
{ 11. x3, xf. 1x3, x 1xf, x311 j=1
(99a)
s" [x]] 1xf1, 1x3111 11x,11 ' f=1
(99b)
We can now apply the following cost-nonincreasing steps to make the vocabulary sat-compliant:
1. While there exists & E S' \ Sm. choose any u E Sm \ S' and set S. + (Sm \ fuf) U (t). By Step D. this replacement does not increase (eotk (8 m),
2. Let Span-coon coupl = Sm (S" Choose any set Saiveing S S such that |Snizinng = (Sen--oopp |, and set Sm + (Sm \ Snon-coappl U Snieeing. By Step 2), this replacement does not increase C (y (S,), D).
3. While there exist indices j + k such that (Ix]]1 1xf11} S Sm and {ix[1, ix[1)ns, choose any r E {1x]1, 1xf1) and any E {ixII, I, 1x. and set Sm + (Sm (t). By Step 3), this replacement does not increase 8 (S
4. While there exist indices j * k such that [1x]11, 11xf1) S Sm and {ixI11, 11x;1) n
S m 0. choose any r E {1x]11, 11xf1) and any E {ix[11, 11x and set Sm +
(Sm \ (r)) U [t}. By Step a this replacement does not increase (e(toko(Sml) D).
5. While there exist an index j such that {Ix]I, 11xf1] C Sm, Set + (Sm (11x51)) U { [Ix]11} Similarly, { {1xf1, 1, 1x] 11} c Sm. set Sm + (Sm (IxFI11) u {11xf1} 1]. By
Step ④ this replacement does not increase Gy [Sm]. D).
Now, let Sm/ be the vocabulary resulting from these transformations. By Lemma 6 (Steps ! 4), Sm/ is sat-compliant (for the bottom-up gadget), and thus for each it contains either [ixf1, 1x!11} or [1x|1, 11x Further, by this same Lemma, the cost of Sn/ smaller or equal to Sm. as each transformation is cost-nonin.raasing. We now define an algorithm 96-2-Tok which, given a merge-sequence m, transforms it into S Sn/ and then extracts the variable assignment x² from these sat-compliant tokens:
90-2-Tok ((X,C), m) g(Smm) {2y)/=1 where Ij T
if 1x]1 E Smd
(100)
Ij = F
elif 1xf 1 E Smd
28

---

Published conference paper at ICLR 2026
Finally, from Eq. (94), the cost of tokeniser with sat-compliant tokens Sm/ has a linear relationship with the cost of assignment x = g(Sm/):
@e(toks[Sm/]: = 5398.J + +75 + 31 M22s(x',
(101)
Now, with some simple operations:
Ge(tok, [m] D) Tok (D, K)
(102a)
2 Ge(toks [S], D) - (D,
tok, applies tokens optimally (102b)
2 [S[ttoks[Sm/]:
Tok, (D,
by Lemma 6 Steps !
(102c)
(5398J + 575 + 3/ M22((("
(102d)
(5398J 575 + 3/ (X,25"(X(C)
30M2S 6 M2s(x*"C)
(102e)
Taking absolute values, we get:
|30M2S* (XM22"(X,C))) 6 (t"" (t", S 1 [6x(tok:|m) D) Tok, (D, K)]
(103)
This confirms that the second condition holds with 1. Since 3-OCC-MAX2SAT is APX-complete, this L-reduction to B-2-TOK proves that B-2-TOK is APX-hard.
I PROOF THAT THE BINARY BOTTOM-UP TOKENISATION GAP PROBLEM IS -A-D (STEP OF THEOREM 4)
Lemma 8. The binary bottom-uy tokenisation gap problem is NP-hard.
Proof. For this proof, we again rely on the result by Berman and Karpinski (1998; 1999) that, for specific instances of 3-OCC-MAX2SAT with 2016n clauses, it NP-hard to distinguish whether at least (2012 e)n or at most (2011 + s)n of these clauses are satisfiable, for any & > 0. We will denote this 3-OCC-MAX2SAT gap problem by 30M2S(X,, C, (y", ")))) with (2011 + E) and y+ (2012 z).. We can now prove NP-hardness of the binary bottom-up tokenisation
gap problem by reducing 3-OCC-MAX2SAT's gap problem to it. To this end, we rely on reduction identical to R2(XX' C, 7), but where we define:
8 = 5398.J + 575 + 31 -
8+ = 5398.J + 575 + 31 - -
(104)
5398J 575 + 3/ 2011 +
= 5398J 575 + 33 2012
2016
2016
Lemmas 5 and 6 trivially show the validity of this reduction:
(, = (D, (8-,8)))
(105)
which holds since 30M2S(X.C, C,,+) - (D, k5o+) and the same for 7 and 8 It is most 5398.7 + 575 +3 201 symbols remain (with an allowed vocab- 2016
therefore NP-hard distinguish whether dataset be compressed
2012-6 symbols, or if at least 5398. + 575 + 3/
2016
ulary size K 10J). Since each variable occurs exactly three times in any 3-0CC-MAX2SAT instance,
we have that J = I. We now compute a lower bound on the best achievable compression ratio:
8
5398./ 575 + 31
2011+
2016
(106a)
8+
5398.J 575 + 31
2012
2016
10805.J + 575
6033
J
2016
(106b)
10805J + 575
6036 3z
2016
10805
6033+-3e*
2016
additive 575 omitted in e' for sufficiently large J (106c)
10805
6036-3e'
2016
7258949 g'
(106d)
7258948
We conclude that binary bottom-up tokenisation cannot be approximated in polynomial time with approximation ratio better than 7258949
7255048 1.0000001, unless P NP.
29

---

Published conference paper at ICLR 2026
J PROOF THAT UNARY DIRECT TOKENISATION IS IN NP
A decision problem is in the nondeterministic polynomial-time class (NP) if it can be verified in polynomial time the presence of certificate: a string designed verify that the current instance is a "yes"-instance, -instance, typically encoding an optimal solution to its search problem. When inputs are represented as strings, the following lemma follows trivially from the beboonndd-allphbbe case discussed by Whittington et al. (2025). Their proof, however, relies on the explicit computation of the direct tokenisation function:
toks [S](c) arg min |s|,
s.t. c-s
(107)
SES*
While we can efficiently compute this when inputs are given in string form, this is not known to be the case for the string-length representation. In this case, the optimal application of tokens corresponds to the change-making problem, which is itself weakly NP-hard, as shown by Lueker (1975). Thus, we include the optimal application of tokens a part of the certificate, in order to prove that this decision problem is still in NP when inputs are represented as string-lengths.
Lemma 9, The unary direct tokenisation decision problem is in NP.
Proof. We use as certificate a set of string-lengths composing the tokeniser's vocabulary SN, as well as a
1M where each Zm E SiS shows how many tokens of each length should be used to tokenise each string in the dataset Dr. Verifying this certificate then simply requires computing the sum of tokens used for each target.
If [Dnl < K, each l E Dr can be included as a token, and thus all entries in our dataset can be compressed into single token; consequently, the certificate can simply be empty and we verify the prob- lem's s satisfiability by checking whether 8 > [Drl holds. Assuming [Dvl > K-and therefore that K's value is polynomial in the input-we have that the certificate also has polynomial length, and that, in particular, the size of Z is bounded by [Dnl K log L maxx where L max is the maximum string-length in DR. Thus, all that is left is to compute the sum of and check whether Σxea sum(z) S ô.
K. PROOF OF FORWARD STEP OF THEOREM 5
Lemma 10. Ifa vertex-cover instance is satisfiable, then the D-1-TOK instance output by Reduc- tion 3 is also satisfiable. Formally: VC(V,, vp) = (R3(V,)
Proof. Suppose the given instance of vertex-cover is satisfiable. Then there exists a vertex cover C C V which uses & vertices. As consequence, we can choose as tokens those with the following lengths:
Sg (e, 1 (YU( 1 C*}
(108)
We have that every vertex-string in D2 is covered by single token, either of length Eg or B.
All sb cover-strings a in D2 which encode vertex that belongs to C* are also covered by single token. The remaining - &u cover-strings in D2 are covered by tokens, as for every target of length O enc (u;) + 3 there exist the tokens of length E enc enc(u,) and B = 3
As C* is vertex cover, we have that for every edge (uj, E E at least one of the vertices belongs to C*. It follows that for every edge-string of length ".3" = enc (v;) + +ncc(u)) + N in Dz. at least one of the tokens of length E enc(v,) + B or eye enc(vy.) + belongs Sy. Thus, all edge-strings are covered by two tokens.
We can now count the number of symbols used in each dataset: DD uses + 1 symbols; D2 uses 2. - se symbols; and Dy uses 2/ symbols. This gives us a total of 3J + 27 + - symbols. which satisfies this tokenisation instance. Thus, we have that Tok, (D, K, 8) = T.
L PROOF OF BACKWARD STEP OF THEOREM 5
Lemma 11. If the D-1-TOK instance output by Reduction 3 is satisfiable, then the vertex-cover instance which generated it is as well. Formally: (R3(,E, E)) = VC(V,E,
30

---

Published conference paper at ICLR 2026
Proof. Assume this instance (Dx, K, 6) of D-1-TOK--hert (Dx. K, R3(,, ()) - satisfi- able, i.e., that Tokg (R3(V, &, )) evaluates to true. We must prove that, in this case, VC(V, E, v) also evaluates to true. Now, let Sy be an arbitrary optimal solution to (DN, K,6). By construction, we have that K + sp and 3J + 21
v. We proceed in four steps:
We prove that all target strings in Dy are unique;
We prove that an optimal tokeniser must only include full target strings in its vocabulary; We prove that an optimal tokeniser will include all target strings in Dj in its vocabulary;
We prove that, if an optimal tokeniser achieves compression 6, then the instance of vertex-cover which was reduced to it satisfiable.
These steps first show that an optimal tokeniser must admit certain form (Steps ! 3) and that from this form (Step 4 ) we can deduce a valid vertex cover, which concludes the proof.
LemmaPPoofstep 1. (Step D). All strings in Dy are unique.
Proof. Now we show that all strings Dy are unique. These strings all have lengths:
la enc(()) B= NA, ty enc (Uj,) B, ey Gi enc(vv) + enc(Uja) + B
(109)
for 1 S j1.J2 S J and with (nc A Notably, our reduction defines N > J
and it will be useful to think about these lengths in base N. Let a number (a, b, c, d, e)N denote aN 6N3 + cN2 + dN' + e. For example, we can write:
ba,b,c,
1)N (a,0,0,0,1) 1)x (2a.b, 1,0)
(110)
We similarly write in this base:
4 (0. (0.0.f9-7..1))) (1,,000,00,) -1,00, G/ = (1,0, + +J)) 6, + +G, 02.0. b1
(11la)
(111b)
Two numbers are the same only if each "digit" this base system the same. Given this structure, we see that l,2 and B are all unique string-lengths Further, the string-lengths en are all different from one another. It is left to show that: (i) all string-lengths C% are different from all " and (ii) that string-lengths en .1. are different among themselves. Requirement (i) is proven by SubLemma 2, which shows that there is no set numbers J2. ja E for which ji = j2 + ja and of = j + 13. Requirement (ii) is proven by SubLemma 3, which shows that there is no set of numbers J2, J3. J1 E N for which j1 + j2 = ja + j1 and jf + j = j + j¹. It follows that all strings in DA are unique.
LemmaProofStep 2. (Step 2). optimal tokeniser must only include full character-strings in Di and compress all other strings to two symbols.
Proof. Note that, since all strings in Dr are unique, the best compression could possibly achieve would result from compressing K strings into a single symbol, and the remaining |Drel K to two symbols. As [Drl 2J 7 1, this (hypothetical) optimal compression would lead to:
Ge(Sopt, Dr) K + 2([ - K)
(1 12a)
= J #
+ 2(2 +
v)
(112b)
3.J 21 1
+5)
(112c)
As by assumption Tok, (R,3(V v)) evaluates to true, our tokeniser must achieve this compression, and is thus composed of K full strings Dr.. Further, must compress all other strings to at most two symbols.
LemmaProofStep 3. (Step 3.. An optimal tokeniser selects every vertex-string in D as a token.
31

---

Published conference paper at ICLR 2026
Proof. Suppose that some vertex-string of length Lj2 in D1 is not chosen as token. Then E must be the sum of two tokens. No tokens of cover- or vertex-strings (in datasets D2 and D2) can be used, since such tokens contain a summand B, which is significantly larger than lj. Hence, both summands would have to also be vertex-strings L/2 Cj. These string-lengths have values:
4- = (1,0, (L,0,
ls = (1, 12,,
la = (1, d3)))
(113)
Again, by SubLemma 2, it is impossible that 21 222 + Ezs- Thus, no target string in D1 can be covered by two other tokens; but, as argued in Step 2 the tokeniser may use at most two symbols per target. This concludes the proof that all character-strings in D1 must be included in the vocabulary Sg. Further, every cover and edge-string is larger than B, while all vertex-strings are significantly smaller than it; B thus cannot be written as two other tokens and must hence also be part of Sg. C
LemmaProofftep 4. (Step 4) an optimal tokeniser achieves compression then the original vertex-cover instance is satisfiable.
Proof. Step 3 shows that J J+1 1 tokens in any optimal tokeniser must correspond to the target strings in D1. Using only these tokens, every target in D2 needs two symbols, and every target in D3 needs three symbols. With Step 2). the remaining & tokens must correspond to target strings from D2 U DDz. We going to show that: token corresponding to edge target can only contribute itself; token corresponding to cover target can only contribute to itself and edge targets which include the vertex the cover consists of. Without loss of generality, let & with 0 S t S & of these remaining tokens be edge-strings (from D3) and let the remaining v - t be cover-strings (from D2).
We are now going to show that token from D3 can only improve the solution by reducing its target string to single token. Pick any of the selected edge tokens, having a length of J1 = (1, 0, Jf J. oî + J ji +j2)N. For this edge token to contribute to compressing target string, it must be combined with another token; let its length be la. such that their sum equals the length of one of the target strings already present in the dataset. Since El (n already contains summand B, the token la cannot contain B, as any target string length in the dataset is strictly less than 2B. As established in Step 2. tokens must correspond target string-lengths themselves. Since any non-vertex target string contains a summand B, the additional token &e must therefore be a vertex token, with length le (0, 0, _ Je je N. Now, assume that the edge token E" 54,.. ju combined with this vertex token E to compress an arbitrary target from one of the three datasets:
40 Sn + +l
(114a)
(0, (0.0, 2 2
jaNN (1, + + 2
+
+ + j2)N,
6 = ". + +
(114b)
= (1, 11
+ + 3 28 + + 12 + + j2)N
J. = 4 + +
(114c)
(1,0, + 1 + jo + +J)N = 01 + +
13.
+ 3
+
82. Ja + f1 + j2)N
The first case clearly cannot be satisfied, any vertex target has length strictly smaller than any edge target. Additionally, the two other cases cannot be satisfied per SubLemmas 4 and 5. In other words, this shows that edge-strings cannot contribute to any other target value.
We are now left with d t tokens formed of cover-strings. Recall that using only the tokens obtained from Step 3 every target in D: needs two symbols, and every target in D3 needs three symbols. Having the newly obtained tokens corresponding to a target from D2 we will show that they can only be applied optimally on: themselves, resulting in one symbol used; target strings from Dg. reducing the symbols to two. Any other application of these tokens would not yield a better compression, as improving compression only possible if the token obtained from D2 compresses target from D2 U D3 other than itself to single token. But Step I shows that all target strings are unique, meaning a token cannot reduce any target string apart from itself to single symbol.
Finally, these selected tokens must be used, in conjunction with vertex-strings, to compress all the remaining dlge-strings to two tokens. Note that only composing a cover and vertex-string can compress an edge-string to two symbols:
En + l/2 = (0, 10,0,11
1 + +2
17 12 11 +J2)N,
(1 (115a)
32

---

Published conference paper at ICLR 2026
(115b)
G + 82 = -1
(115c)
Additionally, an edge-string only be compressed by a cover- vertex-string subword which contains exactly the vertices that the edge consists of. Assume there exists another set of vertex- and cover-strings such that their tokens f,r lja can compress an edge-string consisting of different vertices 5 "Jas4" Then we have that:
Josi = +42 +
+ J8 ja +JNN 01, + 22 22 + j2)N
(116)
From SubLemma 3 it follows that this cannot be the case. This means that, for each edge-string of length E S1dd not in our tokeniser, we must have a subword (of length either e or ey which "covers" it to obtain our target compression. Consider thus, the subgraph (V,8") E"), where:
E' = E ((U U/2) E & 5 Sn}
(117)
There exists a vertex cover of size + t for this subgraph composed of vertices {uz E VIG Su Now, if we expand this set of vi vertices by picking one arbitrary vertex, Ui or U2us for each edge- string of length 31.22 in our vocabulary, we get cover C = {u, E V E UN)U(T) ey E SN} of size at most & for the original graph. Thus, it follows that VC(V, 1b) T.
L.1 PROOFS THAT LERING-LENGTHS IN REDUCTION 3 ARE UNIQUE
We now show the technical sublemmas used the previous proof.
SubLemma 2. For any N, there do not exist non-zero i, N such that:
i i+j=r,
2²
(118)
Proof. From (1+ -2 2ij + j² and the equations i + j = r and + =² we obtain:
,2 = 8 + 1² + 2ij 2² 2ij ij = 0,
(119)
contradicting i,j > O.
SubL.emma There do not exist two distinct pairs {i.j} * {a, b) of positive integers such that:
i+j=a- b,
1 + o² a² b²
(120)
Proof. Due to i + b, there is an integer such that: b レ
(121)
Then, replacing a and b with their corresponding expressions from Eq. (121), we obtain:
a² 12 (i2 + 1²) (i - s)² +j+ -2 - 2s² + 2s(j -i) i)
(122)
By the lemma statement a² + 62 = i2 + so 252 2 - i) = =0, i.c.:
s(++j-)) 0
(123)
Hence either = 0 or = i- If = 0, then a = i and b = j. If = i then a = =i- and j + (i j) In both cases, follows that {a. {i.j], contradicting distinctness.
SubLemma 4. For any N, there do not exist non-zero i, N such that:
itjtk=
+ =
$2 ²+ k2 --
(124)
Proof. Using (1+ ( h)2 22 12 2(1 + ik: + jkk) and the given equations:
2 マ= 2 2(j + ik jk) ij ik +
(125)
With i,j, > O, each product ij. ik, jı is positive, which yields a contradiction. Hence, no solution exists.
33

---

Published conference paper at ICLR 2026
SubLemma 5. r. N. There do not exist non-zero i, k such that:
2 + = p²,
+ k2 = 13 +1²
(126)
Proof. Letp1 =i P2 = -
, = 4 +/ and c1 = =i h. e2 = +j
6g ijk. From the first two equations:
př P2
(r+
(r² +p²) rp
6 = p.
62
(127)
2
2
Newton's identity for three variables gives:
P3 = c1p2 - e2P1 + 3e3
(128)
Substituting P1 pr = E2 = rp yields:
Ps = (r +r+ - p)
3e3 (r + p) + rp) + +33 = + 3e3
(129)
By the third equation in the lemma statement, P3 = T + +p"; hence 3e3 = 0 and so = ijk 0. contradicting i, O.
M DEFINITION OF THE ADDITION CHAIN PROBLEM
An addition chain is sequence of integers that provides an efficient way to "build" target set of numbers starting from 1.
Definition 5. Let t (t1,t2,.... tt be finite set of positive integer targets. An addition chain for t is a sequence of integers = (bo. bi.... bn) with the following properties:
1. The sequence starts with bo 1.
2. Every subsequent element b; is the sum of two preceding elements:
by b bj + bb: for some 0 S kkjjii
(130)
3. The sequence contains all targets: for every 13 there is some by b such that Lj by-
4. By convention, the length of the chain b R.
Definition 6. Let be a set of positive integers. Given maximum length C. the addition chain decision problem (Add-Chain) requires deciding whether there exists an addition chain for with length at most Ç. The addition chain optimisation problem is to find the minimal length for such an addition chain.
We denote by AddChain(t, () function which returns T if such a chain exists (meaning the Add-Chain instance is satisfied), and otherwise.
N PROOF THAT THE UNARY OPE DECISION PROBLEM IS (AT LEAST) WEAKLY NP-COMPLETE
Theorem 6. The unary optimal pair encoding decision problem is (at least) weakly NP-complete.
Proof. We write Tok (D, K, 5) for function which returns T its input corresponds to satisfiable instance of the OPE-1-TOK decision problem, and F otherwise. To prove weak NP-completeness,, we must show that the problem is NP and that is weakly NP-hard. Inclusion NP was already established by Kozma and Voderholzer (2024). We prove weak NP-hardness via reduction from the Add-Chain decision problem. First, we define this reduction.
Reduction 4. Given instance of Add-Chain consisting of a targets t = -ti,....tt tt} and a length limit Ç, we construct an instance of the OPE-1-TOK problem with the following parameters. The dataset D is the set unary strings corresponding to the targets: D = {a a²a ...... a'd), }; the merge budget is set to the addition chain length limit: K = Ç; and the token count threshold is set to the number of largets 8 = J.
34

---

Published conference paper at ICLR 2026
Note that setting the threshold 8 to the number of strings in the dataset implies that a valid solution must represent every string as a single token. The proof proceeds in two parts, showing both directions of the equivalence:
AddChain(t..) =
Tok (D, K)
(131)
Tokape(D, (D, We first show that solution to the Add-Chain problem implies a solution to the OPE-1-TOK problem. Assume there exists a valid addition chain b* (bo, 01,..., bR) of length R < for the target set t. By definition, for each element i, E b' (where r 2 1), there exist indices r', n" < r such that b = b, +b We construct a merge sequence m (m1..... ma) of length R where each merge is defined as m, = (a @ @al?", corresponding the predecessors of b, in the addition chain. The length of this merge sequence m is R & Ç. satisfying the merge budget K = Ç. By the iterative definition of the merge- merge-extracted vocabulary, the resulting vocabulary Sm (a0,++b,, m, E m) will contain a token at for every element b, in the addition chain b*. Since the addition chain b' contains all targets ij E t, the vocabulary Sm is guaranteed to contain a single token for each target string a E DD Consequently, the direct encoding function tok, (S,) ml can represent each string total token count is therefore:
Forward Step (AddChain(t,, ()
with exactly one token. The
Σ [tok((mm](c) = - (D]
(132)
EED
CED
By the construction used in reduction, [D] 6. The condition is met, thus proving the implication.
Back Step (Tokgeg (D, K,)) = AddChain(t, ())- Next, we show that a solution the 0PE-1-TOK problem implies a solution to the Add-Chain problem. Assume there exists merge sequence Mopt length R < ( that satisfies the 0PE-1-TOK decision problem. The condition is:
Σ [Sm) < 8
(133)
where, by the reduction's construction, we have ā = (D). Since the tokenisation of any string must contain at least one token, this sum is also hold with equality, which is only possible if every string is tokenised into exactly one token:
by [D]. Therefore, the inequality must
|tok, [Sm] = for all E
(134)
This implics that for every target t. E t, the corresponding string a' must exist as a single token in the merge-extracted vocabulary, i.e., a E Sm- Now, construct addition chain from S. as: S. from merges guarantees that b is a valid addition
= (e, afr E Sm). The construction chain." Since Sm contains all strings at, then must contain all targets tj E Further, was constructed from K < Ç merges. There is thus an addition chain for t of length at most Ç, which concludes the proof.
'If any subword produced by non-reachable merge exists in Sm. it should be pruned from b. A non- reachable merge is merge my (a'r' afr") whose pair of subwords a or' and af"" cannot be generated.
35


Reviews:
[{"review_id": "dyarkHKxRS", "reviewer": "Reviewer_jKLj", "summary": "The paper investigates the computational complexity of tokenisation when applied to inputs drawn from bounded alphabets, addressing a gap in earlier NP-completeness results that assumed alphabets of unbounded size. Tokenisation, a core component of natural language processing pipelines, converts character strings into subword sequences. Many tokenisation methods—such as Byte Pair Encoding (BPE) and Unigram Language Models—aim to compress data, thereby improving efficiency in model training and inference. While previous work had established that finding an optimally compressive tokeniser is NP-complete, those proofs relied on the unrealistic assumption of infinitely large alphabets.\n\nThe authors define and analyse two bounded-alphabet tokenisation problems: bottom-up tokenisation, where an optimal sequence of merge operations must be selected, and direct tokenisation, where the optimal vocabulary must be chosen directly. They demonstrate that even when the alphabet is extremely limited, the problems remain computationally intractable. Specifically, for binary alphabets (only two characters), both bottom-up and direct tokenisation are shown to be NP-complete and to lack any polynomial-time approximation scheme, unless P = NP. The authors also show that direct tokenisation remains NP-complete even for unary alphabets (containing a single symbol). Because unary and binary alphabets are the simplest cases, these hardness results automatically extend to all larger alphabets.\n\nThe findings imply that the difficulty of tokenisation does not stem from large alphabets or complex merge strategies, but from the inherent structure of the optimisation problem itself. Consequently, it is unlikely that any efficient algorithm can find or even closely approximate an optimal tokeniser under a compression objective.", "questions": "No question", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of the paper is that it closes a gap in earlier NP-completeness results, which assumed alphabets of unbounded size. The current paper shows that these hardness results hold even for small size alphabets.", "weaknesses": "The scope of the paper may be more suitable for a conference on computational complexity. On the other hand the results are about an important problem in natural language processing. Therefore it may fit a section dedicated to computational complexity results within natural language processing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DcZR9EDz5Y", "reviewer": "Reviewer_GzVs", "summary": "This paper investigates the tokenization problem, which is the first step in most NLP pipeline. The problem (somewhat involved to describe) is the following: Let $\\Sigma$ be a finite alphabet  and let $D = \\{c_1, c_2, \\dots, c_M\\}$ be a dataset of character strings \n$c_i \\in \\Sigma^{*}$. A *tokenizer* is a tuple $(S,dt,t)$ where $S$ is a *vocabulary* which is a finite set $S \\subset \\Sigma^{+}$ of nonempty substrings over $\\Sigma$. $dt$ (detokenizer) is a function from $S^{\\*}$ to $\\Sigma^{\\*}$ which is a string concatenation operator. The tokenizer encoder unction $t$ is a function from $\\Sigma^{\\*}$ to $S^{\\*}$ such that  for any $c \\in \\Sigma^{\\*}$, $c = \\mathrm{concat}(t(c))$.  Fix a natural encoding function (eg direct encoding) and a budget $K$. For a given vocabulary $S$ so that $|S| = K+|\\Sigma|$, the cost of $S$ is the minimum,  total number of tokens produced over all the dataset $D$ -- i.e., achieves maximal compression over $D$. The optimization problem is to find cost of the best-cost vocabulary of size $K+\\Sigma$.\n\nThe paper considers two types of encodings -- direct encoding and bottom-up encoding, which are used in practice and investigated in the literature. Prior work has shown that these optimization problems are NP-hard when the alphabet size is unbounded. The present work builds on this hardness result and  strengthen them in several ways. They show that in both cases, even if the alphabet is binary, these problems remain NP-complete. More interestingly to me, they show that even approximating the optimum value up to arbitrary accuracy (PTAS) is NP-hard. In other words, there exists a constant $\\varepsilon > 0$ such that no polynomial-time algorithm can approximate the optimum value within a factor of $(1+\\varepsilon)$ unless P=NP. The paper leaves open a very interesting theoretical question, is there a constant ratio approximation algorithm for this problem? Concretely, is there an approximation algorithm that finds a vocabulary whose cost is  almost twice the optimum?", "questions": "From a theoretical viewpoint, It will be very nice to see the exact constant beyond which one cannot approximate. You give a bound 1.000002, which is theoretically sufficient for the claim, but practically a 1.000002 approximation algorithm is very good.  Have you considered improving the constant? What is your insight as to the existence of constant factor approximation algorithm?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The computational problem studied in this paper is highly relevant, and, given the prior work, the demonstrated impossibility of approximation algorithms with arbitrary precision represents a significant theoretical contribution. The results provide valuable insights into the computational complexity of a fundamental step in modern AI and NLP models. The paper is clearly structured and written fairly well. While I did not verify all proofs in detail (as they are presented in the appendix), the claims appear sound and consistent with the constructions outlined in the main text. I also find the open question regarding the existence of a constant-factor approximation algorithm particularly intriguing—and I even suspect that the answer might turn out to be negative.", "weaknesses": "While theoretically it is an interesting paper, it appears like the practical tokenizers work very well and not clear whether these results will have any impact on the progress of modern NLP models. Another weakness I find is that it appears complicated than it needs to be to define the computational problems. Some notational use appears non-standard. For example while $tok$ is a function by definition, they also use it as a set and use notations such as $|tok|$ which, to my understanding is the cardinality of the vocabulary. I find such notional use a bit confusing. Another minor weakness is that, the paper is dense and proof-heavy with limited examples illustrating the reductions. Hence a small running example of the reduction would improve readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L7tPZ2nFW7", "reviewer": "Reviewer_bxh6", "summary": "The authors consider the problem of tokenization: given a database of words, how can one most efficiently tokenize the words? Tokenization is an important first step in most natural language processing pipelines, and finding the optimal tokenization is potentially useful to optimizing language model performance. Thus, it is important to understand how well we can hope to compute good tokenizations. Formally the authors consider two problems:\n\n1. Direct encoding: given a set of tokens, the tokenization of a database is the optimal splitting of the words in the database to minimize the number of tokens used. \n2. Bottom-up encoding: given a set of tokens, the tokenization of a database is represented by a set of merge operations. The tokenized database is obtained by sequentially applying the merge operations greedily to the database.\n\nFor both formulations of the tokenization function, the optimization problem asks to find the tokenization (i.e. the set of tokens in the former case, the merge operations in the second case) minimizing the number of tokens. Naturally, one can also consider approximations of this problem. The main result of this work establishes that unless P = NP, there is no PTAS for tokenization i.e. there exists a constant 1.00001 such that finding a 1.00001-approximation to the optimal tokenization is NP-hard. The proofs follow via reduction to a special case of the MAX-2-SAT problem. Whereas previous work obtained lower bound for unbounded alphabets, this work gives the first hardness result for bounded alphabets, and in fact gives a strong result ruling out polynomial algorithms for binary alphabets. Furthermore, they show that for (1) even unary tokenization is NP-complete.\n\nThe authors consider an interesting problem, and give strong results. The paper is well written and easy to follow. I therefore recommend accept.", "questions": "Minor Comments \n\nReference to Lemma 1 and 2 - I think better to reference Reduction 1 and Theorem 2\n\nMaybe good to state explicitly what all merge operations are in forward step of bottom-up tokenization proof.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper studies a practically motivated problem which is a key step in training natural language processing models. The result is strong and essentially resolves the question of tokenization with compression as an objective. The paper is well written, and the proofs are well motivated and easy to follow.", "weaknesses": "No clear weaknesses (see minor comments below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dcaP3uForJ", "reviewer": "Reviewer_Zs3e", "summary": "This paper addresses the computational complexity of bottom-up and direct tokenisation over bounded alphabet. The authors develop elaborate proofs to show that this problem is NP-complete even with alphabets consisting only of 2 characters. Also they show that there is no polynomial time approximation unless P=NP. The main optimization function is compression. The paper contains elaborate formal definitions of the problems addressed and provides elaborate technical details underlying the main results.", "questions": "How does this work fit under learning representation? \nThere are already heuristics to perform tokenisation which work very well in practice with no theoretical guarantees. How does this work impact the existing vast literature?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper presents rigorous proofs for tokenisation over bounded alphabets with compression as the optimization function.", "weaknesses": "In my opinion, this paper will not be of interest to the main ICLR community and is only of theoretical interest with no clear practical impact on learning or NLP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LrHzwtX8BU", "reviewer": "Reviewer_gmyW", "summary": "This paper explores the computational complexity of tokenisation when restricted to bounded alphabets, addressing a critical gap in prior research that focused on unbounded alphabets.\nThe authors analyze both direct and bottom-up tokenisation and demonstrate that these problems remain NP-complete even for binary and unary alphabets. Furthermore, they prove that neither admits a polynomial-time approximation scheme (PTAS) unless P = NP.\nThrough reductions from classic NP-hard problems (such as 3-OCC-MAX2SAT and Vertex Cover), the paper rigorously establishes the intractability of tokenisation even under practical, real-world constraints.", "questions": "Could the authors clarify whether their hardness results extend to probabilistic or heuristic tokenisation schemes commonly used in NLP (e.g., BPE variants with stochastic merges)?\n\nDo the reductions rely crucially on compression-based objectives, or might similar hardness results hold for alternative objectives like frequency balancing or entropy minimization?\n\nGiven the established hardness, do the authors foresee any provably efficient approximation algorithms for special cases (e.g., very small datasets or restricted merge operations)?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The connection drawn between tokenisation and classical NP-hard problems is conceptually elegant and insightful.\n\nThe paper tackles a relevant and previously unresolved problem, making a clear theoretical contribution to both computational complexity and NLP.\n\nThe authors thoughtfully discuss implications for practical tokenisation algorithms, encouraging further research on approximation and relaxation methods.", "weaknesses": "The discussion of approximation hardness constants (e.g., very tight lower bounds) could be expanded to give more intuition on their practical implications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)