# Tokenisation via Convex Relaxations

arXiv: https://arxiv.org/abs/2605.22821 · HTML: https://mlsanity.com/paper/2605.22821/

## Key facts

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

## Builds on (most cited first, 17 of 17)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Nemotron-CLIMB: CLustering-based Iterative Data Mixture Bootstrapping for Language Model Pre-training](https://mlsanity.com/paper/2504.13161/) (2025)
- [SuperBPE: Space Travel for Language Models](https://mlsanity.com/paper/2503.13423/) (2025)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier](https://mlsanity.com/paper/2504.00178/) (2025)
- [BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training](https://mlsanity.com/paper/2409.04599/) (2024)
- [Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removal](https://mlsanity.com/paper/2404.17808/) (2024)
- [Theoretical Analysis of Byte-Pair Encoding](https://mlsanity.com/paper/2411.08671/) (2024)
- [Two Counterexamples to Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2402.14614/) (2024)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [A Partition Cover Approach to Tokenization](https://mlsanity.com/paper/2501.06246/) (2025)
- [Tokenisation over Bounded Alphabets is Hard](https://mlsanity.com/paper/2511.15709/) (2025)

## Built on by (most cited first, 4 of 4)

- [MinGram: A Minimalist Unigram Tokenizer with High Compression and Competitive Morphological Alignment](https://mlsanity.com/paper/2606.27019/) (2026)
- [Joint Optimization for Greedy Longest-match Tokenization](https://mlsanity.com/paper/2607.23362/) (2026)
- [Dynamic-Programming-Guided Hierarchical BPE and Empirical Analysis of Vocabulary Pruning](https://mlsanity.com/paper/2609.06898/) (2026)
- [The Price of Token Boundaries: Compression Certificates and Prediction](https://mlsanity.com/paper/2609.35869/) (2026)

## 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.