Metraipolis › archive › dc_03dadd49ad4e

GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization — arXiv:2611.07346

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07346
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:20.628Z
SHA-256 of the archived text
63832411c534b9c04a2ef83ff8f162650446d80676019e008d348571de4d2048
Stable URL of this page
https://metraipolis.com/documento/dc_03dadd49ad4e

How to cite

GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization — arXiv:2611.07346 — arXiv (en), https://arxiv.org/abs/2611.07346 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_03dadd49ad4e (Metraipolis archive dc_03dadd49ad4e, sha256 63832411c534b9c04a2ef83ff8f162650446d80676019e008d348571de4d2048)
BibTeX
@misc{dc03dadd49ad4e,
  title = {GreedTok is a Constant-Factor Approximation for Partition-Cover Tokenization — arXiv:2611.07346},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07346},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_03dadd49ad4e; sha256 63832411c534b9c04a2ef83ff8f162650446d80676019e008d348571de4d2048},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07346. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.07346 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.628Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).