Joint Optimization for Greedy Longest-match Tokenization

Imagine you are trying to pack a massive library of books into a single, tiny suitcase for a trip. You want to fit as much text as possible into a limited space, but you can't just crush the pages into a ball; you need to organize them into neat, manageable chunks. In the world of artificial intelligence, this "suitcase" is the computer's memory, and the "chunks" are called tokens. AI models read text not as whole words, but as these smaller pieces. The way we chop up words matters a lot: if we cut them poorly, we use more space and the computer has to work harder to read them. For years, the standard way to cut these words has been a method called Byte Pair Encoding (BPE). Think of BPE like a very efficient, but slightly rigid, librarian who follows a strict rule: "Always glue the two most common pieces of text together first." It's a fast, greedy approach that has worked well, but it's essentially a heuristic—a good guess based on a simple rule, not a perfect mathematical solution.

Recently, scientists have started asking a big question: Is this librarian's "good guess" actually the best we can do? Or is there a smarter way to cut the words that fits even more text into the suitcase? This paper dives into that question by looking at a specific way AI reads text called "Greedy Longest-Match." Imagine reading a sentence and, at every step, grabbing the longest possible word you know before moving to the next letter. The authors wanted to see if they could design a vocabulary specifically for this reading style, rather than just hoping a general-purpose vocabulary would work. They built a new system called JOLT (Joint Optimization for Greedy Longest-match Tokenization). Instead of just gluing pieces together based on frequency, JOLT treats the whole problem like a giant, complex puzzle. It uses advanced math to figure out exactly which word pieces to keep and how to cut every single word in the training data so that, when the AI reads it using the "longest-match" rule, it uses the absolute minimum number of pieces possible.

The paper finds that while the old librarian (BPE) is actually quite good—already sitting within 1% to 2% of the theoretical best possible packing—the new system, JOLT, can squeeze out a little bit more space. By solving this mathematical puzzle, JOLT manages to close nearly all of the remaining gap between the old method and the perfect theoretical limit. In tests with different sizes of text data, JOLT reduced the number of tokens needed by up to 0.78% compared to the standard method. While that number sounds small, in the world of AI, saving even a fraction of a percent means the model can read more text, think faster, and cost less to run. The authors show that by aligning the vocabulary perfectly with the way the AI actually reads, we can recover almost all the "compression headroom" that was previously left on the table.

The Story of JOLT: Solving the Word Puzzle

To understand how JOLT works, let's imagine you are a master chef trying to create the perfect menu for a massive banquet. You have a huge list of ingredients (the text), and you need to chop them into specific sizes (tokens) to serve them to your guests (the AI). The catch is that your guests have a very specific eating habit: they always grab the biggest bite they can find that fits in their mouth before moving to the next bite. This is the "Greedy Longest-Match" rule.

For a long time, chefs (AI researchers) used a standard recipe called BPE. They would look at the ingredients and say, "Hey, 'th' and 'e' appear together a lot, let's glue them into 'the'." They kept doing this, gluing the most common pairs, until they had a menu of a certain size. It worked well, but it was a bit like building a house by just stacking bricks without checking if the walls were perfectly straight. It was a "greedy" approach—doing the easy, obvious thing first.

The authors of this paper realized that if you want the guests to eat efficiently, you shouldn't just build a menu based on what's common; you should build a menu based on how they eat. They created JOLT, which is like a super-smart chef who plans the entire menu at once, considering every single ingredient and every possible way to chop it, ensuring that the final result is perfectly optimized for the guests' "biggest bite" habit.

The Mathematical Puzzle
The core of JOLT is a massive math problem. The authors had to decide two things simultaneously:

1. Which ingredients to keep: Which word pieces should be in the final vocabulary?
2. How to chop the text: For every single word in the training data, which specific pieces should be used to build it?

The tricky part is that these two decisions are locked together. You can't decide to chop a word into "ta" and "ble" unless you have actually decided to keep "ta" and "ble" in your vocabulary. Furthermore, because the AI uses the "longest match" rule, you have to make sure that if you chop a word into "ta" and "ble," there isn't a longer piece like "table" in your vocabulary that would steal the show. If "table" exists, the AI will eat "table" whole, and your plan to serve "ta" and "ble" fails.

To solve this, the authors used a technique called "Integer Programming." Imagine a giant grid of switches. Some switches turn on a word (put it in the vocabulary), and others turn on a specific way of chopping a word. The goal is to flip the switches to get the lowest total number of pieces possible. However, solving this grid for a whole library of text is so huge that even the fastest computers would take forever.

The Smart Shortcut
So, the authors came up with a clever trick. Instead of trying to solve the whole puzzle at once, they started with a small, simple version. They only considered chopping words into one or two pieces. They solved the math problem, and if the computer said, "Hey, this word is too hard to chop with just these pieces, I need more options," they added more complex chopping options for just that word. They repeated this process, adding complexity only where needed, until the solution stabilized.

This approach allowed them to find a solution that is incredibly close to the perfect theoretical limit. They found that the standard BPE method was already doing a great job, sitting within 1% to 2% of the best possible result. But JOLT managed to close 89.6% to 99.4% of that remaining gap.

The Results
When they tested their new system on different amounts of data (from 100,000 to 400,000 words) and different vocabulary sizes (32,000 and 64,000 words), the results were clear. JOLT consistently used fewer tokens than the standard BPE method.

• With a vocabulary of 32,000 words, JOLT reduced the token count by up to 0.78% compared to the standard method.
• With a vocabulary of 64,000 words, the improvement was smaller but still present, reaching up to 0.31%.

The paper also checked how close their solution was to the absolute mathematical limit. They found that their final, rounded solution was within 0.008% to 0.176% of the theoretical best. This means the "rounding" process (turning the math solution into a real, usable vocabulary) didn't lose much efficiency. The small gains JOLT made over BPE weren't just a fluke; they were real, structural improvements.

Why This Matters
The authors also looked at other methods. They found that a popular method called WordPiece, which is designed for the same "longest match" reading style, actually performed worse than BPE when tested. This was because WordPiece was trained to maximize a different goal (predicting the next word) rather than minimizing the number of pieces. This proves that you can't just use a vocabulary designed for one purpose and expect it to work perfectly for another. You have to train the vocabulary specifically for the way the AI reads.

In summary, this paper shows that while the old "greedy" librarian (BPE) was doing a surprisingly good job, there is still a tiny bit of space left to squeeze out. By using a new, mathematically rigorous approach that aligns the vocabulary perfectly with the AI's reading style, JOLT recovers almost all of that lost space. It's a reminder that in the world of AI, even small improvements in efficiency can lead to faster, cheaper, and more capable models. The authors didn't just guess; they proved mathematically that their method gets us closer to the perfect packing job than ever before.