Search papers, labs, and topics across Lattice.
Tokenization with Split Trees (ToaST) is introduced, a novel subword tokenization method that directly optimizes compression by recursively splitting pretokens into binary trees based on byte n-gram counts. Vocabulary selection is formulated as an Integer Program, minimizing token count across split trees during inference, which recursively descends each tree and emits the first in-vocabulary node. Empirically, ToaST reduces token counts by over 11% compared to BPE, WordPiece, and UnigramLM and achieves state-of-the-art CORE scores when training 1.5B parameter language models.
Subword tokenization just got a whole lot more efficient: ToaST slashes token counts by 11% and boosts language model performance by up to 7.6% compared to standard methods.
We introduce Tokenization with Split Trees (ToaST), a subword tokenization method that directly optimizes compression under a new recursive inference procedure. ToaST greedily splits each pretoken into a full binary tree using precomputed byte n-gram counts, independent of any vocabulary. Given a vocabulary, inference recursively descends each split tree and emits the first in-vocabulary node reached on each path. Vocabulary selection is formulated as an Integer Program (IP) that minimizes the total token count over all split trees under this inference procedure. The Linear Programming (LP) relaxation is near-integral in practice, yielding provably near-optimal vocabularies, with training time empirically scaling quadratically in the number of split trees. On English text, ToaST reduces token counts by more than 11% compared to BPE, WordPiece, and UnigramLM at vocabulary sizes of 40,960 and above, reducing the number of inference tokens for models using this tokenizer, thus extending the effective context length. ToaST also uses common single-byte tokens less frequently than these baselines, leading to a substantial improvement in Renyi efficiency. In experiments training 1.5B parameter language models, ToaST achieves the highest CORE score, outperforming baselines by 2.6%--7.6%, with significance for two of three, and scoring best on 13 of 22 individual tasks.
MIT CSAIL