Joint Optimization for Greedy Longest-match Tokenization

Recent work shows that subword vocabularies can be trained to directly optimize compression for a specific inference rule, rather than relying on a greedy merge heuristic like Byte Pair Encoding (BPE). For example, ToaST targets split-tree inference and ConvexTok targets shortest-path inference. We extend this approach to greedy left-to-right (GL2R) longest-match decoding, the fast and widely used inference rule of WordPiece. We introduce Joint Optimization for Greedy Longest-match Tokenization (JOLT), which formulates GL2R vocabulary learning as an integer program (IP) over vocabulary-selection and segmentation-choice variables. The key ingredient is a set of greedy-consistency constraints that force each pretoken's segmentation to match exactly what GL2R produces under the selected vocabulary, making the optimized token count equal to the count realized at deployment. To solve the IP at scale, we use a linear program (LP) relaxation that escalates only unresolved pretokens to higher-order segmentations. The relaxation is near-integral: rounded solutions fall within $0.008$--$0.176\%$ of the LP lower bound, certifying near-optimal GL2R compression on the training scope. The same bound reveals that BPE already sits within $1$--$2\%$ of the LP lower bound on the training scope, confirming the heuristic is near-optimal for GL2R inference; JOLT closes $89.6$--$99.4\%$ of this gap. On held-out validation across four training scopes ($N \in \{100\text{k}, 200\text{k}, 300\text{k}, 400\text{k}\}$) and two vocabulary sizes ($|V| \in \{32\text{k}, 64\text{k}\}$), JOLT yields up to $0.78\%$ fewer tokens than BPE, with gains growing with scope. Together, these results show that most of the compression headroom between BPE and the LP lower bound can be recovered through inference-aligned vocabulary optimization.