A vocabulary optimized for its inference rule

Optimality is relative to the inference rule

Byte Pair Encoding builds a vocabulary with a greedy merge heuristic, repeatedly fusing the most frequent adjacent pair. A recent line of work (ToaST for split-tree inference, ConvexTok for shortest-path) replaces the heuristic with direct optimization: fix the inference rule first, then train the vocabulary to maximize compression under exactly that rule. Framed this way there is no best-compressing tokenizer in the abstract; optimality only means something relative to an inference rule. JOLT extends the approach to greedy left-to-right (GL2R) longest-match decoding, the simple, fast rule WordPiece uses: scan the input left to right, at each position emit the longest vocabulary token that matches. GL2R works well even on vocabularies trained by other methods, yet no vocabulary construction had been designed specifically for it.

The quantity at stake is tokenization cost: how many tokens a corpus becomes. It sets the effective context budget and scales inference cost, so a vocabulary-only improvement is attractive precisely because it costs nothing at inference time. The question JOLT answers is how much of that improvement exists and how to provably capture it.

Vocabulary selection as an integer program

Text is first split into pretokens (the regex word-ish units GPT-4o-style tokenizers use), and each unique pretoken p with corpus count c_p has a set of candidate segmentations s, each spending cost(p, s) tokens. Two families of binary variables decide everything jointly: x_t = 1 admits candidate token t into the vocabulary, and z_{p,s} = 1 selects segmentation s for pretoken p. The objective is the corpus-weighted token count.

minimize    Σ_p Σ_s  c_p · cost(p, s) · z_{p,s}

subject to  Σ_s z_{p,s} = 1            each pretoken picks one segmentation
            z_{p,s} ≤ x_t              for every token t used by s
            Σ_t x_t ≤ |V|              vocabulary budget
            x_b = 1                    all 256 byte tokens stay in
            z_{p,s} ≤ 1 − x_t          for every t that extends a non-final
                                       segment of s   (greedy consistency)
            x_t, z_{p,s} ∈ {0, 1}

Greedy-consistency constraints

Without the last constraint family, the program would pick each pretoken's cheapest segmentation the vocabulary allows: an optimal segmenter, which is a different inference rule from the GL2R encoder this vocabulary is being built for. Scores would be optimistic relative to greedy decoding, and the optimized token count would no longer equal the count realized at deployment - the exact property JOLT exists to guarantee.

So greedy behavior is made part of feasibility. For every non-final segment g of a candidate segmentation s, and every candidate token t that strictly extends g while still fitting inside the pretoken, the pair is forbidden: z_{p,s} ≤ 1 − x_t. If a longer match t were in the vocabulary, greedy longest-match would take it instead of g, so s could not be what the encoder produces. Any (vocabulary, segmentation) assignment that satisfies these constraints is precisely what the deployed encoder will do, which means the objective measures deployed cost rather than an idealized bound on it.

Solving it: LP relaxation and a certificate

The exact 0-1 program is far too large at useful scales, so we relax the binaries to [0, 1] and solve the LP to optimality with Gurobi. Rounding is contribution-based: tokens with x_t at (or numerically at) 1 are admitted outright, and remaining vocabulary slots are filled by ranking fractional candidates by how much objective weight their segmentations carry.

The LP optimum lower-bounds the cost any same-size vocabulary can achieve under greedy decoding, which turns rounding error into a measurable quantity: across settings, rounded vocabularies land within 0.008-0.176% of the LP bound. That is what near-optimal means here - a certificate against the relaxation, not a comparison against whichever baselines happened to be tried. The honest cost is solve time: the largest final-round LP (top 200k pretokens, 32k vocabulary) takes roughly 94 hours of wall clock. It is a train-once cost; inference is unchanged.

Results

Setup: MiniPile with a GPT-4o-style regex pretokenizer, optimizing over the top-N pretokens (N up to 400k, covering roughly 96-98% of corpus count mass), at vocabulary sizes 32k and 64k, against BPE, WordPiece, and UnigramLM baselines all evaluated under the same greedy longest-match decoding.

At 32k, JOLT produces up to 0.78% fewer tokens than BPE; at 64k the margin shrinks to about 0.3%, consistent with a larger vocabulary leaving less room to disagree over. The more interesting number comes from the bound itself: the LP shows BPE was already within 1-2% of optimal for this encoder, and JOLT captures 89.6-99.4% of the gap that remained. Sub-percent is not a modest fraction of the available win - it is most of what there was to win.

Limitations

• Evaluation is on MiniPile, predominantly English; transfer to languages without whitespace-delimited words is untested.
• Optimality is relative to the pretoken boundaries the regex pretokenizer induces, and only the top-N pretokens are optimized - the tail is priced by a conservative fallback rather than optimized.
• Segmentations above order 3 are priced conservatively rather than enumerated, so very long tokens are handled approximately.
• Evaluation is intrinsic (token counts); no downstream task results yet.

Why this framing

Casting the design choice as explicit constrained optimization is what makes a certificate possible at all: near-optimal becomes an algebraic statement instead of a benchmark comparison. And the bound cuts both ways. It quantifies what JOLT gains, and it caps what any compression-focused vocabulary construction can ever gain over BPE under this encoder - worth knowing before spending another compute budget chasing it.