ConvexTok: A New Method for Tokenizer Construction Based on Convex Optimization

This article introduces ConvexTok, a new method for constructing tokenizers using convex optimization instead of greedy algorithms. Compared to locally optimal algorithms like BPE and Unigram, ConvexTok formulates tokenizer construction as a linear programming problem, which can be proven to be close to the global optimum and achieves improvements in multiple metrics.

Tokenizers are an indispensable component in modern natural language processing (NLP) pipelines. They convert raw text into sequences of discrete symbols that models can process, directly affecting the model's learning efficiency, inference speed, and even final performance. The construction process is a complex combinatorial optimization problem that requires selecting subword units from large-scale corpora to form a vocabulary. Traditional methods often use heuristic greedy strategies for approximate solutions.

Current mainstream algorithms like BPE and Unigram are essentially greedy algorithms. They make locally optimal decisions at each iteration and lack a global perspective. For example, BPE repeatedly merges the most frequent character pairs, while Unigram iteratively deletes entries to optimize the probability model—both may miss better vocabulary configurations. As model scales expand, the bottleneck in tokenizer quality becomes increasingly prominent.

ConvexTok reformulates tokenizer construction as a linear programming problem. It uses convex relaxation techniques to transform the discrete combinatorial optimization problem into a convex optimization problem that can be solved efficiently. This method considers the mutual influence of all candidate subword units simultaneously, avoids local optima, and can obtain a lower bound through the dual problem, proving that the solution is close to the global optimum.

Experimental results show that ConvexTok outperforms BPE and Unigram baselines in the bits-per-byte (BpB) metric, with higher encoding efficiency. In downstream NLP benchmark tests, models trained using ConvexTok also achieved better performance, indicating that improvements in tokenizer quality can be transferred to downstream applications.

ConvexTok calculates a theoretical lower bound for vocabulary configuration through duality theory. Experiments show that for common vocabulary sizes, the gap between the solution and the global optimum is within 1%, filling the gap where traditional greedy algorithms cannot provide optimality guarantees.

ConvexTok has higher computational overhead than greedy algorithms, and its efficiency for ultra-large-scale corpora needs improvement. Currently, it mainly focuses on compression efficiency; multi-language support and domain-specific adaptation need to be explored. Future directions include developing efficient approximation algorithms, integrating domain knowledge, and exploring joint optimization with other NLP components.

ConvexTok represents an important shift from heuristic to optimization-driven tokenizer construction. It not only achieves empirical performance improvements but also provides quantifiable optimality guarantees, and is expected to become the standard methodology for next-generation tokenizer design.