最適なトークナイザーの発見（15 分読了）

In this post, I will present an algorithm that was able to compute an optimal tokenizer in some

settings. This result is cool because optimal tokenization is theoretically intractable, but seems to be solvable in

practice. My finding is very similar to various results on the Traveling Salesman Problem (TSP), where

even difficult instances can be solved optimally using cutting-plane techniques.

I'll highlight that, while this result is cool, there are a few reasons that it isn't necessarily

*useful*. First, the existing state of the art was already somewhat close to optimal (often within

1%). Second, even if a tokenizer is optimal on the *training data*, it may not generalize as well

as other tokenizers when evaluated on held out test data. Finally, inefficient tokenizers are basically

fine: you can pay for the cost of a less efficient tokenizer by slightly increasing your vocabulary

size.

Despite the above caveats, I had a really fun time working on this project, and I hope others will be

interested in pushing the frontier of this problem as well.

Background: Tokenizers

Frontier LLMs are typically trained on sequences of integers known as *tokens*. Each token refers to

some sequence of bytes, and these byte sequences often correspond to common words. For example, in the

GPT-5 tokenizer, the token 290 corresponds to the bytes “ the”, and 6602 corresponds to

“ token”, so the text “ the token” can be encoded as the sequence [290, 6602].

The mapping from tokens to bytes, known as the “vocabulary”, is fixed before the LLM is even

trained. Typically, we try to find a vocabulary that compresses a slice of training data. In particular,

we would like to pick a vocabulary of a fixed size that minimizes the number of tokens required to encode

the data. The dominant technique for finding such a vocabulary is [byte-pair encoding

(BPE)](http://www.pennelynn.com/Documents/CUJ/HTML/94HTML/19940045.HTM), a decades-old greedy compression algorithm.

Tokenization as integer linear programming

In a recent paper, Tempus et al. connected

tokenization to integer linear programming. The basic idea of their approach is to represent the entire

dataset's tokenization as a set of integer variables.

In this formulation, there's a “color” variable for each possible vocabulary entry. In

particular, we create one color variable for every unique substring of the dataset. A color variable is 1

if the corresponding byte sequence is in the vocabulary, or 0 otherwise. We add a single constraint to

force the sum of color variables to equal the target vocabulary size.

A color corresponds to some sequence of bytes, but a given sequence of bytes may occur many times

throughout the dataset. For each occurrence of a color, there's a separate “edge” variable.

The edges work together to encode an actual tokenization of the dataset. If an edge is 1, then the

edge's corresponding token is used in this particular place. The objective of our linear program is to

minimize the sum of all the edge variables, i.e. the number of tokens used to encode our dataset.

For example, in the below picture, we tokenize the word “Queue” as the tokens [“Q”,

“ue”, “ue”]. We could alternatively have tokenized it as [“Qu”,

“e”, “ue”], but that is not the tokenization indicated by the current ILP

solution, since the edge variables for the initial “Qu” and “e” edges are 0.

We constrain the LP in two ways. First, we can't use a token if it's not in the vocabulary. To this end,

we constrain each edge variable to be less than or equal to its corresponding color variable. Second, we

want to make sure that we tokenize the dataset in exactly one valid way. To this end, we add flow

constraints: for each byte position in the dataset, we want the sum of edges flowing into this position

to be equal to the sum of edges flowing out of this position, with the exception of the boundaries. For

the first and last positions, we want the flow out or flow in to be 1. In an integer solution, you can

see flow constraints as asserting the following: *any point that an edge goes into must have an edge

going out of it, except the first and last positions*.

If all the variables were integral and constrained to [0, 1], then this linear program is enough to encode

the optimal tokenization. However, since we cannot solve arbitrary integer linear programs efficiently,

Tempus et al. relax the ILP to a continuous LP and solve this with a well-optimized solver.

The solution to the continuous LP is not generally integral. We can see an example of this below, where we

have two superimposed tokenizations of the word “Queue”: either we encode it as

[“Q”, “ue”, “ue”], or as [“Qu”, “e”,

“ue”]. The problem with this solution is that our color variables sum to 2.5, but we've

actually used four total colors, so we haven't actually found an optimal vocabulary of size 3. In

general, we might end up with many more non-zero color variables than the actual vocabulary size we are

targeting.

Tempus et al. propose to “round” the color variables in a few different ways, achieving an

integral but suboptimal solution to the ILP. The solution to the continuous LP gives a *lower bound*

on the optimal solution's token count, and the rounded tokenizer gives an upper bound.

One other caveat I should mention about this work: to make it tractable, we pretokenize the dataset (spit

it into words) and merge repeated words (with corresponding weights in the objective based on how many

times a word occurs). This drastically reduces the number of variables in the LP, but it does mean our

solution is only “near optimal” under the pretokenizer. Today, I won't try to remove this

restriction, but it would be an interesting direction for future work.

Cutting planes

I spent some time last year learning about the Traveling Salesman Problem (TSP), which can also be posed

as an ILP. We can often use cutting planes to solve this ILP:

first, we turn the ILP into a continuous LP, then add extra constraints until the optimal solution is

integral. The constraints must be provably “valid”–that is, never violated for actual

integer solutions. In theory, *any* ILP can be “turned into” a continuous LP with extra

constraints, but the magical extra constraints may be intractable to find. TSP solvers use a number of

heuristics to efficiently find such constraints in most practical cases. The authors of Corcorde (a TSP

solver) wrote an entire book about techniques for finding useful cuts.

After reading Tempus et al., I wondered if we could apply cutting planes to the tokenization ILP. The

method would work like this: first, solve the initial LP to get some lower and upper bound on the optimal

tokenization; then, keep adding valid cuts to the LP and re-solving it to make these bounds closer and

closer together–until they meet at the optimal solution.

It takes a lot of work and creativity to come up with “cut families” that might be useful for

an ILP, so instead of banging my head against this myself, I set Codex on the task. At first, it found

almost nothing–some of the cuts improved the LP bound a tiny bit, but most of the things it tried

were surface-level word heuristics.

Then I tried another approach: brute force. A “cut” is some constraint that is satisfied by

all integer solutions, but violated by the current fractional LP solution. We can find cuts by

constructing an auxiliary linear program with one constraint for each possible integer solution, and

optimizing it to maximize the violation of the fractional solution. We can't do this for the entire LP,

since the number of rows blows up exponentially, but we can do it for small interesting

“projections” of the LP. Codex proposed to look at all the variables in pairs or triplets of

words with common fractional colors.

The above technique found really good cuts that improved the rounded tokenizer and raised the lower bound.

However, this approach is really inefficient, since it involves solving (pretty large) auxiliary LPs for

a huge number of word pairs. The next trick was to have Codex look at the actual cuts we were finding.

By looking at the brute force cuts, Codex discovered several cut templates that can be found more

efficiently. The most effective family seems to be what Codex named “cycle constraints”. This

technique finds pairs of overlapping fractional edges in the current LP solution. For example, we might

find an overlapping (i.e. conflicting) pair of edges for colors A and B. We then find a few pairs that

share common colors, such as another pair for colors B and C and another for C and A. We can then create

a constraint out of the corresponding edge and color variables that is often violated by the continuous

LP solution but never violated by a valid integral solution.

Finding the cycle of conflicting pairs AB, BC, CA can be done with a neat trick: construct a graph where

the vertices are colors, and connect any pair of colors that overlap as fractional edges in the current

solution. After you have this graph, run DFS to find cycles in it. Codex implemented this all

autonomously, though I'm sure it's not an original trick.

Experimental setup

I was pretty hardware limited for this project, using only my Mac Studio and Mac mini. There aren't great

GPU-accelerated LP solvers for this hardware, so I mainly leaned on the HiGHS single-core simplex solver. Sadly, I found that this solver sometimes

stalls, especially for later iterations where we've applied a lot of (potentially degenerate) cuts.

To run experiments in a reasonable amount of time on this hardware, I studied single eBooks. I needed the

LPs to remain small enough to solve on the CPU, so I kept the pretokenization approach of Tempus et al.

Finally, I adopted some heuristics from Tempus et al. to make the LP smaller, such as dropping color

variables for substrings that appear less than 5 times. I also imposed a byte length limit on

colors–in this case 16 bytes. I found that this made a difference compared to an 8-byte limit,

where the optimal tokenization was slightly worse.

Results

I was able to find provably optimal tokenizers on at least a few toy problems. The one I am most proud of

is an optimal tokenizer of vocab size 512 for the book Pride and Prejudice. The algorithm converged in

about a dozen iterations, taking a bit over a day.

I tried increasing vocabulary size from 512 to 1024 on this same problem, and found that cycle constraints

weren't enough on their own to find an optimal solution. The lower bound continued to move significantly

after I added back other cut families, though my latest runs are still not finished. There are, without a

doubt, other cut families to be discovered here as well, and some may even be necessary to

solve the 1024-vocab problem.

Future work

At this point, the main bottleneck in my experiments is LP solve times. In many of my experiments, each

LP solve can take between hours and days. I've tried a few solvers (HiGHS, the solver in SCIP, and OR-Tools

PDLP), and all of them start to choke on my highly constrained LPs. My suspicion is that my cutting plane

approach is creating degenerate LPs, and this could be a potential area for improvement.

Generally, I'd love to see someone continue to scale up this work to larger corpora. I doubt that the cut

families I've explored are enough for harder problems, and there is surely a rich space of ideas to

explore.

I'd also love to see somebody remove the pretokenizer. This currently makes the LPs quite large, since we

don't get to merge repeated words. Removing the pretokenizer also eliminates the ability to use

word-based cut strategies. For example, some of my cut strategies enumerate all of the valid integer

solutions for each word, and then project these combinations into a subset of variables. These strategies

need to be completely reframed for a “single huge word” dataset.

Conclusion

This was a neat project, and it was fun to see Codex do an entire research loop with just a small bit of

guidance from me. I really hope to keep playing with it, but this is contingent on figuring out a

solution to the *slow LP* problem.

The incredibly hacky Codex implementation of this project is available on Github. For reference, the optimal

vocabulary for [Pride and

Prejudice](https://www.gutenberg.org/cache/epub/37431/pg37431.txt) that I found is here (note that the

vocab is actually 510, because the codebase reserves two special tokens).