Finding Optimal Tokenizers

Researchers have developed an algorithm using integer linear programming that can compute optimal tokenizers for language models, a problem previously considered theoretically intractable. However, the practical impact is limited since existing tokenizers (like byte-pair encoding) already achieve near-optimal compression within 1%, and optimal tokenizers on training data don't necessarily generalize better to unseen data. The work parallels solutions to the Traveling Salesman Problem and demonstrates that difficult optimization problems can sometimes be solved optimally in practice despite theoretical intractability.