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

Aditya Byju; Aiden Xie; Kundan Baliga

REVIEW

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

Kundan Baliga, Aiden Xie, Aditya Byju

Data Structures and Algorithms · Submitted 5 Nov 2026

Pith's verdict: Resolves the open constant-factor question for greedy tokenization with clever techniques and honest bounds.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.07346 (version 2)

Pith IDC5DPIBEA, Pith's permanent record of this paper and its review

CitationAditya Byju, Aiden Xie, Kundan Baliga. "GreedTok Is a 0.3287-Approximation for Tokenization, Within 3% of the Best Possible Constant." arXiv:2611.07346 (2026). https://pith.science/paper/C5DPIBEA

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

This paper does what it says: it proves GreedTok is a constant-factor approximation for the partition-cover objective, and it does it cleanly. The shift lemma and the window charging argument are the real contributions — they handle the non-submodularity and the fact that a commit can kill optimal occurrences. The lower bound 0.2752 is the first constant for this algorithm, and the upper bounds (0.5256, 0.5380) show the analysis isn't wildly loose. The hardness result, though tiny, is also the first for this objective.

What I like most: the proof is self-contained, the model is clearly mapped to the released code, and the computational checks (window distributions up to L=1500, exhaustive small-instance enumeration) back up the analytic parts. The authors are honest about where the analysis loses (Section 7), that the worst-case ratio might be above 1/2, and that the hardness bound is weak. They also note that a different scan order would break the guarantee, and that the encoder's re-encoding can differ from the committed state — both real limitations that they flag.

Soft spots? The lower-bound proof requires (α,β)-good window distributions, which are verified by computation for L≤1500 and by an analytic construction for larger L. The analytic construction uses a specific family of distributions; it's plausible but not machine-checked for all L. I'd trust it because the continuum limit matches the LP bound and the monotonicity holds. The hardness result at 1−1/31580 is more a placeholder — it shows APX-hardness but is far from tight. That's fine for a first result.

Who this is for: anyone working on tokenizer theory, greedy approximation, or combinatorial optimization on strings. The techniques (shift lemma, window charging) may be useful for related problems.

Recommendation: send to a serious venue. The paper deserves a thorough referee; I expect it will be accepted with minor revisions (maybe a bit more clarity on the analytic window construction, but the appendices are thorough). I'd cite it.

Referee report

Minor objections (6)

[Abstract] The fraction (7−ln 2)/12 ≈ 0.5256 appears to be mis-parenthesized; it should be written as (7−ln 2)/12 or possibly 7/12 − (ln 2)/12. The approximation given is correct, but the expression with the right parenthesis placed after 12 is misleading. Consider rewriting as (7−ln 2)/12 for clarity.
[§4.3, Lemma 12] The text states that the linear program solves for window distributions with rational weights (denominator 10^{12}). It would be helpful to mention that the LP is solved per length L and that the rounding to 10^{-12} is a conservative rounding that preserves the bounds. The current phrasing is clear but could be expanded slightly.
[§5, Table 1] The table lists budgets 72 and 96 with worst-tie ratios 19/36, but the text says the root-cut instances at k=72,96 have ratios 19/36. The footnote † says the full tie tree was not explored; it might be worth noting that 19/36 is an upper bound for those budgets (as it is the value of one specific greedy run, all picks being maximizers). The current notation is clear but could be made explicit.
[Appendix E, Table 2] The table of computational checks is very thorough. One minor point: the row for Corollary 7 mentions 1,780,818,426 checks on short words; the unit 'checks' is slightly ambiguous. Clarifying that these are pairwise checks for score increases would help a reader understand the scale of verification.
[§D, Fidelity to the released implementation] The description of the lazy loop in Algorithm 1 of the original paper is discussed. The authors note a typo in lines 16–18 and interpret it as the accepted token; this is reasonable. They could add a citation to the specific line numbers from the original paper for traceability.
[§6, Theorem 20] The inapproximability constant 31579/31580 is very close to 1. The authors note that this is not optimized. It might be helpful to state explicitly that the hardness reduction is from Max-2SAT and the gap is derived from the Berman–Karpinski result, and that the constant could likely be improved by a more careful analysis. This is already implicit but could be made explicit.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

GreedTok guarantees a constant factor of at least 0.2752 of the optimal tokenization on every corpus.

The reading

The paper proves that GreedTok, a greedy algorithm for building a tokenizer vocabulary under the partition-cover objective, is a constant-factor approximation. The main result is a lower bound of 0.2752 on the worst-case ratio of GreedTok to the optimal solution for any corpus and any budget k, with optimality for k=1. This is significant because the objective function is neither submodular nor supermodular, so standard greedy analyses fail. The proof introduces a shift lemma for overlapping occurrences and a charging argument based on random substrings (windows) of optimal tokens, using window distributions certified by exact computation or closed-form formulas. The paper also provides an upper bound of approximately 0.5256 via adversarial instances and proves APX-hardness for the optimization problem.

What carries the argument

The central mechanism is the shift lemma (Lemma 4), which states that if two occurrences p and q of an unchosen string x overlap by a shift δ, then a pair inside p is covered if and only if the corresponding pair inside q is covered at the same time, and consequently their gains are equal. This allows the algorithm to skip overlapping occurrences without loss, and it lets the analysis charge skipped occurrences to their blockers. The other key machinery is the concept of (α, β)-good window distributions (Definition 8), which are sub-probability distributions over substrings of a token of length L such that the expected length of the window is at least α(L−1) and each boundary or interior offset contributes at most β to the expected loss when invalidating windows. The existence of such distributions for every L is verified computationally for L ≤ 1500 and analytically for larger L using a quadratic construction (Lemma 13).

Extended reading notes

Core claim

The paper establishes that GreedTok achieves at least 0.2752 times the optimal partition-cover value on any corpus and for any vocabulary budget k. This bound holds for any tie-breaking and for both the exact greedy loop and the lazy priority-queue version of the algorithm. The proof relies on a shift lemma: if two overlapping occurrences of a not-yet-chosen token are valid, they have the same gain, so GreedTok's left-to-right scan loses nothing when an occurrence is skipped due to overlap. This lemma enables a per-occurrence charging argument where a random window (substring) of an optimal token is shown to contribute expected gain at least α per optimal pair, while covered pairs cost at most β per occurrence. Solving the recurrence gives the constant factor. The best window distributions are obtained by solving a linear program for short tokens and an explicit quadratic family for long tokens, yielding α ≈ 0.563 and β = 7/4 as a good trade-off; using an envelope of several (α, β) pairs improves the final constant to 0.2752.

Load-bearing premise

The lower bound proof requires the existence of an (α,β)-good window distribution D_L for every token length L ≥ 2; the authors verify this computationally up to L = 1500 and provide an analytic construction for larger L, but the analytic construction assumes a specific quadratic parameterization and that β > 1 + 1/√2.

Editorial extensions

If this is right

For any corpus and any budget k, a practitioner can rely on GreedTok achieving at least 27.52% of the optimal partition-cover value, and this guarantee is independent of the tie-breaking rule.
The shift lemma provides a general tool for analyzing greedy algorithms where overlapping occurrences of the same candidate can be compared, potentially applicable to other sequence covering problems.
The lower bound of 0.2752 combined with the upper bound of about 0.5256 shows that the worst-case ratio of GreedTok lies in a range roughly [0.275, 0.526], leaving an open factor of nearly 2.
The APX-hardness proof (Theorem 20) shows that no polynomial-time algorithm can approximate the problem within 1 − 1/31580 ≈ 0.999968 unless P=NP, establishing a strong inapproximability result for the first time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The shift lemma might be extended to analyze other greedy algorithms that build vocabularies or segmentations where occurrences of the same string can overlap, such as in phrase-based machine translation or DNA motif discovery.
The quadratic window distribution family (Lemma 13) suggests a general method for constructing distributions that balance coverage and interference, which could be reused in other charging arguments for monotone submodular-like functions.
The gap between the lower bound 0.2752 and the best upper bound 0.5256 indicates that GreedTok's true worst-case ratio may be closer to 0.5, motivating the search for either an improved lower bound or a tighter upper bound via a different instance family.
The paper's computational verification (window certificates for L up to 1500, exact enumeration for small instances) sets a high standard of empirical support, and the same methodology could be applied to verify other combinatorial guarantees.

Original abstract

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

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-06: 1 request, 6,581 input tokens.

What the abstract itself states, as probabilities: claims first 0.85 · states limitation 0.83 · human participants 0.02 · controlled comparison 0.10 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.65 · mentions code or data availability 0.12.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

GreedTok (Lim, Tan, Choo and Lauw, NeurIPS 2025) builds a tokenizer vocabulary greedily for the partition-cover objective: choose $k$ tokens so as to maximize the number of adjacent character pairs merged when the corpus is segmented optimally. The objective is neither submodular nor supermodular, so the classical $1-1/e$ analysis does not apply, and a worst-case guarantee was left open. We prove that GreedTok is a constant-factor approximation: on every corpus and for every budget $k$ it achieves at least $0.2752$ of the optimum, and it is optimal for $k=1$. The bound holds for both the exact greedy loop and the lazy priority-queue loop of the published algorithm and its code. The key ingredient is a shift lemma: if two occurrences of a not-yet-chosen token overlap and both are still usable, they offer exactly the same gain, so GreedTok's left-to-right scoring loses nothing when occurrences collide. A per-occurrence charging argument, with window distributions certified in exact arithmetic or given in closed form, completes the proof. In the other direction, we construct corpora on which GreedTok, with adversarial tie-breaking, achieves at most a fraction of the optimum tending to $(7-\ln 2)/12\approx0.5256$ (below $0.5380$ when every greedy choice is unique). Finally, we show that the objective is NP-hard to approximate within $1-1/31580$, to our knowledge the first inapproximability result for it.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	GreedTok (Lim, Tan, Choo and Lauw, NeurIPS 2025) builds a tokenizer vocabulary greedily for the partition-cover objective: choose $k$ tokens so as to maximize the number of adjacent character pairs merged when the corpus is segmented optimally.	background 0.45	0.25	0.05	asserted 1.00
s1	The objective is neither submodular nor supermodular, so the classical $1-1/e$ analysis does not apply, and a worst-case guarantee was left open.	gap 0.98	0.18	0.03	asserted 1.00
s2	We prove that GreedTok is a constant-factor approximation: on every corpus and for every budget $k$ it achieves at least $0.2752$ of the optimum, and it is optimal for $k=1$.	result 0.94	0.94	0.92	asserted 1.00
s3	The bound holds for both the exact greedy loop and the lazy priority-queue loop of the published algorithm and its code.	result 0.81	0.82	0.09	asserted 1.00
s4	The key ingredient is a shift lemma: if two occurrences of a not-yet-chosen token overlap and both are still usable, they offer exactly the same gain, so GreedTok's left-to-right scoring loses nothing when occurrences collide.	method 0.70	0.89	0.04	asserted 1.00
s5	A per-occurrence charging argument, with window distributions certified in exact arithmetic or given in closed form, completes the proof.	method 0.97	0.92	0.04	asserted 0.99
s6	In the other direction, we construct corpora on which GreedTok, with adversarial tie-breaking, achieves at most a fraction of the optimum tending to $(7-\ln 2)/12\approx0.5256$ (below $0.5380$ when every greedy choice is unique).	result 0.96	0.94	0.06	asserted 1.00
s7	Finally, we show that the objective is NP-hard to approximate within $1-1/31580$, to our knowledge the first inapproximability result for it.	result 0.83	0.94	0.08	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** The running example w = abababab. Shaded boxes are committed occurrences; a filled dot marks a covered pair, an open dot an uncovered one. (a) Committing ba covers pairs 2, 4, 6. Pair 4 is the shared boundary of the two disjoint occurrences of abab, so both become invalid; so does [2, 6). (b) After committing ab, the overlapping occurrences p = [0, 4) and q = [2, 6) of abab are both valid. Shifting by δ = 2 maps the interior pairs 1, 2, 3 of p to the interior pairs 3, 4, 5 of q (arrows), and covered pairs map to covered pairs. So p and q have the same gain (Lemma 4). skipped [2, 6).…

**Figure 2.** The two kinds of words for optimal token

Figures reproduced from arXiv:2611.07346 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.