Tokenization with Split Trees

2026-05-21 · Source: Computation and Language · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

Tokenization with Split Trees (ToaST) is a novel subword tokenization method that directly optimizes compression through a new recursive inference procedure. ToaST operates by greedily splitting each pretoken into a full binary tree using precomputed byte n-gram counts, independent of any vocabulary. Its inference mechanism recursively descends these split trees, emitting the first in-vocabulary node encountered on each path. Vocabulary selection is framed as an Integer Program (IP) to minimize total token count, with its Linear Programming (LP) relaxation yielding provably near-optimal vocabularies. Empirically, training time scales quadratically in the number of split trees. On English text, ToaST reduces token counts by over 11% compared to BPE, WordPiece, and UnigramLM at vocabulary sizes of 40,960 and above, thereby extending effective context length. It also improves Renyi efficiency by using common single-byte tokens less frequently. In experiments with 1.5B parameter language models, ToaST achieved the highest CORE score, outperforming baselines by 2.6% to 7.6% and scoring best on 13 of 22 individual tasks.

Key takeaway

For NLP Engineers developing large language models, especially those concerned with context length and inference efficiency, you should evaluate Tokenization with Split Trees (ToaST). Its ability to reduce token counts by over 11% compared to BPE and WordPiece directly translates to longer effective context windows and improved Renyi efficiency. Consider integrating ToaST to potentially enhance your model's CORE score and overall performance on diverse tasks, particularly for models with 1.5B parameters or more.

Key insights

ToaST tokenization optimizes compression and context length using recursive split trees and provably near-optimal IP-based vocabulary selection.

Principles

• Tokenization can directly optimize compression.
• Recursive inference on binary split trees is effective.
• Integer Programming yields near-optimal vocabularies.

Method

ToaST greedily splits pretokens into binary trees using byte n-gram counts. Vocabulary selection is an Integer Program minimizing token count, solved via LP relaxation. Inference recursively descends trees, emitting in-vocabulary nodes.

In practice

• Achieve >11% token count reduction on English.
• Extend language model effective context length.
• Improve Renyi efficiency in tokenization.

Topics

• Subword Tokenization
• ToaST
• Language Models
• Compression Algorithms
• Integer Programming
• Context Length Extension

Best for: AI Engineer, Research Scientist, AI Scientist, Machine Learning Engineer, NLP Engineer

Related on AIssential

• Modelling the Morphology of Verbal Paradigms: A Case Study in the Tokenization of Turkish and Hebrew — Tokenization strategy critically impacts Transformer models' ability to represent complex morphology, especially in non-concatenative languages.
• Text Preprocessing in NLP: Cleaning Text Before Machines Can Understand It — Text preprocessing cleans raw language data for machine learning models to improve accuracy and reduce computational load.
• BrahmicTokenizer-131K: An Indic-Capable Drop-In Replacement for o200k_base — BrahmicTokenizer-131K offers balanced, high-performance tokenization for Indic, English, EU, and code languages at a 131K vocabulary budget.
• A BART-based approach with hierarchical strategy for Vietnamese abstractive multi-document summarization — A hierarchical, BART-based approach for Vietnamese multi-document summarization uses "golden summaries" to guide document shortening, preventing information loss.
• A Calculus-Based Framework for Determining Vocabulary Size in End-to-End ASR — A calculus-based framework formally determines optimal vocabulary size for end-to-end ASR systems.
• Prefix Parsing is Just Parsing — Prefix parsing can be efficiently reduced to ordinary parsing via a grammar transformation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Computation and Language.