mlsanityData to 7 Oct 2026

Tokenisation via Convex Relaxations

arXiv 2605.22821 ↗First posted 21 May 2026cs.CL cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1% of optimal at common vocabulary sizes.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 17 of its 37 references that are in the map. First posted on arXiv 21 May 2026.

Builds on

17 of 37 references.

References · 17

  1. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  2. 2020Scaling Laws for Neural Language Modelscited by 6,411
  3. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,898
  4. 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,734
  5. 2018Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidatescited by 632
  6. 2023Tokenizer Choice For LLM Training: Negligible or Crucial?cited by 105
  7. 2025Nemotron-CLIMB: CLustering-based Iterative Data Mixture Bootstrapping for Language Model Pre-trainingcited by 62
  8. 2025SuperBPE: Space Travel for Language Modelscited by 58
  9. 2023A Formal Perspective on Byte-Pair Encodingcited by 35
  10. 2025Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barriercited by 31
  11. 2024BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Trainingcited by 30
  12. 2024Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removalcited by 16
5 more
  1. 2024Theoretical Analysis of Byte-Pair Encodingcited by 15
  2. 2024Two Counterexamples to Tokenization and the Noiseless Channelcited by 13
  3. 2024Tokenisation is NP-Completecited by 10
  4. 2025A Partition Cover Approach to Tokenizationcited by 5
  5. 2025Tokenisation over Bounded Alphabets is Hardcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026MinGram: A Minimalist Unigram Tokenizer with High Compression and Competitive Morphological Alignmentcited by 5
  2. 2026Joint Optimization for Greedy Longest-match Tokenizationcited by 1
  3. 2026Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruningcited by 0
  4. 2026The Price of Token Boundaries: Compression Certificates and Predictioncited by 0