💬 NLP

Tokenisation via Convex Relaxations

This paper introduces ConvexTok, a novel tokenization algorithm that formulates vocabulary construction as a linear program solvable via convex optimization, thereby outperforming traditional greedy methods in intrinsic metrics and language model efficiency while providing a certified bound on its proximity to optimality.

Original authors: Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Tempus, Philip Whittington, Craig W. Schmidt, Dennis Komm, Tiago Pimentel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Packing a Suitcase

Imagine you are trying to pack a massive library of books into a single suitcase (the computer's memory) to send it to a friend. To do this efficiently, you need a tokeniser.

In the world of AI, a tokeniser is like a set of custom stamps. Instead of sending every single letter of every book (which is slow and bulky), the tokeniser groups letters into "chunks" or "tokens" (like whole words or common phrases) and sends those instead. The goal is to make the suitcase as small as possible (high compression) while still being able to reconstruct the books perfectly when they arrive.

The Problem: The "Greedy" Packer

Currently, most AI models use a method called BPE (Byte-Pair Encoding). Think of BPE as a greedy packer.

How it works: The packer looks at the books, finds the two most common letters that appear next to each other (like "t" and "h"), glues them together into a new stamp ("th"), and repeats this process over and over.
The flaw: Because the packer only looks at the immediate next step (locally optimal), they might glue together two letters that seem helpful right now but end up creating a weird, inefficient shape later that doesn't fit well in the suitcase. They make a series of small, good decisions that lead to a bad overall result. They never step back to see the "big picture."

The Solution: The "Architect" Approach (ConvexTok)

The authors of this paper, Jan Tempus and colleagues, decided to stop using the greedy packer. Instead, they built an Architect.

They realized that finding the perfect way to pack the suitcase is a math problem so hard that computers usually give up on it (it's "NP-hard"). However, they found a clever trick: Convex Relaxation.

The Analogy: Imagine trying to find the lowest point in a mountain range to build a house. The greedy packer just walks downhill until they hit a small valley and stops there, thinking it's the bottom.
The Architect's Trick: The authors smoothed out the jagged mountains into a perfect, smooth bowl (a "convex" shape). In this smooth bowl, it is mathematically easy to find the absolute lowest point.
The Result: They solved this smooth, easy version of the problem using a tool called a Linear Program (LP). This gave them a "blueprint" for the perfect packing.

The Catch: From Blueprint to Reality

The blueprint they got from the smooth bowl had a problem: it suggested using "half-stamps." For example, it might say, "Use 0.7 of the 'th' stamp and 0.3 of the 'ing' stamp." You can't actually print a half-stamp.

To fix this, they invented three ways to round these numbers to whole stamps (like rounding 0.7 up to 1):

Deterministic (Det): Just pick the top $K$ stamps with the highest scores.
Biased (Bias): Pick stamps that are short and efficient, even if their score is slightly lower.
Integral (Int): Only pick stamps that the blueprint was 99% sure about.

What They Found (The Results)

The team tested their new ConvexTok method against the standard greedy BPE method. Here is what happened:

Better Packing: The ConvexTok suitcases were consistently smaller (better compression) than the BPE suitcases. This means the AI models could read the same amount of text using fewer "tokens."
The "Near-Perfect" Guarantee: One of the coolest things about their math is that it gives a "lower bound." Think of this as a certificate that says, "We know the perfect suitcase size is at least this small." They found that their ConvexTok suitcases were within 1% of that perfect theoretical size. In other words, they are almost as good as mathematically possible.
AI Performance: When they trained AI models using these new suitcases:
- The models were slightly better at understanding text (measured by "bits-per-byte").
- On complex reasoning tasks (like answering logic puzzles), the results were mixed. Sometimes ConvexTok was better, sometimes BPE was better, but ConvexTok was never significantly worse.
Stability: The greedy BPE method is very stable; if you give it slightly different books, it makes the same stamps. The new ConvexTok method is a bit more sensitive to the specific books it sees, meaning the stamps might change slightly if you change the training data.

Summary

The paper argues that we have been using a "greedy" method to teach AI how to read for too long. By using advanced math (convex optimization) to look at the entire problem at once, they created a new tokeniser called ConvexTok.

It's like switching from a person who blindly glues the most common letters together, to an architect who designs the entire suitcase layout at once. The result is a more efficient way to compress text, bringing us closer to the theoretical limit of how small we can make these AI "suitcases."

Technical Summary: Tokenisation via Convex Relaxations

Problem Statement

Tokenisation is a fundamental component of the Natural Language Processing (NLP) pipeline, converting byte-strings into token sequences for language models (LMs). While recent research suggests a correlation between tokenisation compression efficiency and downstream LM performance, finding an optimal tokeniser is an NP-hard problem. Current state-of-the-art methods, such as Byte-Pair Encoding (BPE) and Unigram, rely on greedy algorithms. These methods make locally optimal decisions (e.g., iteratively merging the most frequent token pairs) without considering the global optimality of the resulting vocabulary. Consequently, they may generate unnecessary intermediate tokens and fail to achieve maximum compression. The core challenge addressed by this paper is how to approximate a globally optimal tokeniser efficiently, moving beyond the limitations of greedy heuristics.

Methodology

The authors propose ConvexTok, a novel tokenisation algorithm that formulates the construction of a tokeniser as a linear program (LP) derived from a convex relaxation of an integer program (IP).

1. Graph Formulation

The problem is first recast as a shortest path problem on a directed acyclic graph (DAG):

Vertices: Represent positions between bytes in the dataset's byte-strings.
Edges:
- Byte-edges: Connect adjacent bytes (representing individual characters).
- Token-edges: Connect non-adjacent vertices, representing potential multi-byte tokens.
Colouring: Token-edges are coloured based on the specific byte-sequence they represent. A "colour" corresponds to a unique token.
Objective: Find a path from the start to the end of the graph that minimizes the total path length (compression) using a vocabulary of at most $K$ distinct colours (tokens).

2. Integer Programming (IP)

The graph problem is translated into an Integer Program. The authors define incidence matrices for free edges (byte-edges) and priced edges (token-edges), along with a colour-partition matrix. The optimization variables are binary vectors representing:

Which edges are used in the segmentation ( $f$ for free, $p$ for priced).
Which colours (tokens) are selected for the vocabulary ( $c$ ).
The objective is to minimize the total path length subject to flow constraints (ensuring a valid path) and a budget constraint (limiting the number of selected colours to $K$ ).

3. Convex Relaxation (LP)

Since solving the IP is NP-hard, the authors relax the discrete constraints ( $x \in \{0, 1\}$ ) to continuous intervals ( $x \in [0, 1]$ ). This transforms the problem into a Linear Program (LP), which can be solved efficiently using standard solvers (specifically, the PDLP method in NVIDIA CuOPT).

The Tokenisation Polytope: The solution space of this relaxed LP allows for "partial" tokens (fractional values), representing a convex combination of potential vocabularies.

4. Rounding Schemes

Since LMs require discrete vocabularies, the fractional LP solution must be discretised. The paper proposes and evaluates three rounding schemes:

Deterministic (Det): Selects the $K$ colours with the highest LP values.
Biased (Bias): Ranks colours by the ratio of their LP value to the token length ( $c / \text{length}(c)$ ), favoring shorter tokens when scores are comparable.
Integral-only (Int): Selects only those colours where the LP value is already near 1 (essentially "forced" by the relaxation), often resulting in a vocabulary smaller than the budget $K$ .

Key Contributions

Formulation: The paper provides the first formulation of tokeniser construction as a linear program via polyhedral techniques, explicitly linking tokenisation to shortest path problems on coloured graphs.
Algorithm (ConvexTok): It introduces a new algorithm that approximates a globally optimal tokeniser, avoiding the local optima inherent in greedy approaches like BPE.
Optimality Certification: The LP solution provides a provable lower bound on the compression achievable by any tokeniser on a given dataset. This allows researchers to certify how close a specific tokeniser (e.g., BPE or ConvexTok) is to the theoretical optimum.
Rounding Analysis: The paper systematically evaluates three distinct rounding strategies to convert fractional LP solutions into functional tokenisers.

Experimental Results

The authors evaluated ConvexTok against BPE across various vocabulary sizes (8k to 256k) using the ClimbMix400B dataset and GPT-style decoder-only transformers.

LP Solution Quality: As vocabulary size increases, the LP solution becomes increasingly integral (closer to 0 or 1), suggesting that at larger scales, the optimal token choices are less ambiguous.
Optimality Gap: The LP lower bound reveals that existing tokenisers are remarkably close to optimal. At common vocabulary sizes (128k, 256k), both BPE and ConvexTok variants are within 1% of the optimal compression bound.
Intrinsic Metrics:
- The Bias rounding scheme consistently outperformed BPE and other schemes on intrinsic metrics such as vocabulary utilisation, type-token ratio, and compression rate.
- BPE was found to be more stable than ConvexTok variants when retrained on different random subsets of data, likely due to its frequency-driven, local nature.
Language Modeling Performance:
- Bits-per-Byte (BpB): The Deterministic (Det) rounding scheme consistently achieved the best BpB scores, often outperforming BPE, particularly at larger vocabulary sizes.
- Downstream Tasks (CORE): Results on downstream benchmarks (reasoning, multiple choice, common sense) were mixed. While ConvexTok variants were competitive with BPE, they did not show a consistent, significant advantage across all tasks and model depths.
Stability: BPE demonstrated higher stability regarding training data sampling compared to ConvexTok, though the Integral-only rounding scheme showed higher stability than the other ConvexTok variants.

Significance and Claims

The paper claims that globally optimised tokenisation is a promising alternative to locally greedy merge-based methods. The primary significance lies in the ability to:

Solve Tokenisation Globally: Demonstrate that tokenisation can be approached via convex optimisation rather than greedy heuristics.
Certify Performance: Provide a rigorous lower bound to measure how far any tokeniser is from the theoretical optimum. The authors empirically found that at standard vocabulary sizes, current methods are already very close to this optimum (within 1%).
Improve Compression: Show that while BPE is already near-optimal, specific rounding schemes (like Bias) can yield slightly better intrinsic compression metrics.

The authors remain modest regarding downstream task improvements, noting that while BpB improved consistently, gains on downstream CORE tasks were less consistent. They conclude that while their method offers a theoretically superior framework and certifiable bounds, the practical gains over highly tuned greedy methods like BPE are incremental in the context of current large language model training.