arXiv preprint ·
GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quadratic-Time Barriers from Self-Referential SAT
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant
Constant-Factor Approximation Algorithms for Weighted Budgeted Multisensor Sweep Coverage
A Simple Discrete Newton Method for the Quickest Transshipment Problem
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.