💬 NLP

Faster Superword Tokenization

This paper introduces a significantly faster training algorithm for BoundlessBPE and SuperBPE tokenization methods by aggregating supermerge candidates by frequency and employing a two-phase formulation, achieving a 600x speedup over previous implementations while maintaining identical results.

Original authors: Craig W. Schmidt, Chris Tanner, Yuval Pinter

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Craig W. Schmidt, Chris Tanner, Yuval Pinter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot how to read and understand human language. To do this, you first have to break sentences down into smaller pieces called tokens. Think of tokens like Lego bricks: the robot doesn't see a whole sentence; it sees a string of bricks it has to snap together to understand the meaning.

For years, the standard way to make these bricks was an algorithm called BPE (Byte Pair Encoding). Here's the problem with the old way: it was very rigid. It had a rule that said, "You can only snap bricks together if they are already sitting next to each other in a pre-defined box."

The Problem: The "Box" Limitation

Imagine you have a sentence: "to be or not to be."
The old BPE algorithm first splits this into "pretokens" (the boxes): ["to", "be", "or", "not", "to", "be"].
Because of its rigid rules, it could combine to and be into a single brick called to be. But it could never combine to and be if there was a comma or a space in between that the algorithm decided was a hard wall. It was stuck treating words as isolated islands, even when they naturally flow together as phrases.

Two new methods, BoundlessBPE and SuperBPE, tried to fix this. They wanted to create "Superwords"—bricks that could span across those artificial walls to capture whole phrases like to be or not to be. This made the robot smarter and more efficient.

But there was a catch: These new methods were incredibly slow to train.

The Old Way: Training on 1GB of text took 59 seconds.
The New Way (Original): Training on the same 1GB took 4.7 days (over 100 hours).

It was like trying to build a skyscraper by hand-carrying every single brick from a quarry, one by one, instead of using a conveyor belt. The researchers realized the original code was trying to memorize the entire book in its head to find patterns, which is impossible for large datasets.

The Solution: The "Aggregation" Trick

The authors of this paper found a way to make the new "Superword" methods as fast as the old ones. They used a clever trick called Aggregation.

The Analogy: The Grocery Store Inventory
Imagine you are a store manager.

The Old Slow Way: Every time a customer buys a "to be" phrase, you walk to the back of the store, find the specific customer, check their receipt, and update a log. If you have a million customers, you are walking the aisles a million times.
The New Fast Way: You realize you don't need to look at individual customers. You just count: "How many times was 'to be' bought in total?" You write down: 'to be': 50,000.
The Result: Instead of processing a million individual transactions, you just process a list of 500 unique phrases and their total counts.

The authors showed that you can group these "Superword" candidates by how often they appear, just like regular words. This allowed them to stop memorizing the whole document and start working with a compact list of counts.

The Two-Phase Strategy

To make this work perfectly, they split the training process into two phases, like a two-step cooking recipe:

Phase 1 (The Basics): First, they train the robot using the standard, fast method to learn the most common words and how to break them down. This creates a solid foundation.
Phase 2 (The Super-Phrases): Then, they take the list of "Superword" candidates (phrases that span across the old boundaries) and see which ones are the most popular. They mix these in with the standard words to create the final, super-efficient vocabulary.

This approach is so efficient that they managed to speed up the training by 600 times.

Before: 4.7 days.
After: About 10 minutes (603 seconds).

Why This Matters

Speed: You can now train these advanced tokenizers on massive datasets in minutes instead of weeks.
Smarter Robots: By allowing the robot to see whole phrases as single units, it understands context better. It's the difference between seeing "to" and "be" as separate, and seeing "to be" as a single concept of existence.
Open Source: The authors didn't just write a paper; they built a free, fast tool (in both Python and a super-fast language called Rust) so anyone can use this technology immediately.

A Note on Non-English Languages

The paper also solved a tricky problem for languages like Chinese or Japanese, which don't use spaces between words.

The Issue: If you just chop these languages up by character, you might accidentally cut a character in half (like cutting a letter in half), creating "garbage" tokens that make no sense.
The Fix: They created a special rule that treats every single character as its own complete "pretoken" before starting. This ensures the robot never accidentally builds a brick out of half a character.

Summary

This paper is like upgrading a slow, manual assembly line to a high-speed automated factory. They took a brilliant but sluggish idea (Superwords), figured out how to count the parts efficiently (Aggregation), and split the work into two logical steps (Two-Phase). The result is a tokenizer that is 600 times faster, making it practical for the next generation of AI models to understand language more naturally and efficiently.

1. Problem Statement

Byte Pair Encoding (BPE) is the standard tokenization method for Large Language Models (LLMs). However, standard BPE is constrained by pre-tokenization boundaries (e.g., spaces, punctuation). It cannot merge tokens across these boundaries, limiting it to representing at most full words. This constraint prevents the formation of multi-word phrases (superwords), which can lead to suboptimal compression and token distributions.

Superword Tokenization algorithms, specifically BoundlessBPE and SuperBPE, were proposed to relax this constraint by allowing "supermerges" (combining adjacent pretokens into phrases). However, these algorithms suffered from prohibitive training speeds:

Original BoundlessBPE: Required ~4.7 CPU days to train on just 1GB of data.
Root Cause: Previous implementations stored full documents in memory to maintain context for potential supermerges. Because merge operations scale linearly with the number of pretoken occurrences, the lack of aggregation (counting unique pretoken sequences) made training computationally infeasible for large datasets.

2. Methodology

The authors propose a unified, high-speed framework that enables the training of BoundlessBPE and SuperBPE on large datasets by introducing pretoken aggregation and a two-phase training strategy.

A. Aggregation of Supermerge Candidates

Instead of storing full documents, the authors aggregate supermerge candidates (sequences of two or more consecutive pretokens eligible for merging) by frequency.

Eligibility: A pretoken is eligible for a supermerge only if it contains at least one Unicode letter (\p{L}) and is already tokenized as a single token.
Non-Space-Delimited Languages: For scripts like Chinese or Japanese (where spaces do not separate words), the authors introduce a script-specific pre-tokenization strategy.
- Documents are split into chunks containing a single script (e.g., Han, Latin).
- Each character is split into its own 3-byte pretoken.
- This prevents the formation of invalid UTF-8 tokens (partial bytes) and creates a sequence of single-character pretokens eligible for supermerging.
Optional Splitting: Longer candidate sequences can be greedily split into shorter, higher-frequency n-grams to further increase aggregation efficiency (though this was not used for the primary English results).

B. Two-Phase BoundlessBPE Algorithm

The authors reformulate BoundlessBPE into two distinct phases to decouple regular merges from supermerges, producing results identical to the original algorithm but with drastically reduced complexity.

Phase 1 (Regular BPE):
- Train a standard BPE model on aggregated pretokens up to the target vocabulary size $|V|$ .
- This establishes the set of "regular" merge rules and determines which pretokens are reduced to single tokens.
Phase 2 (Supermerge Selection):
- Uses the vocabulary from Phase 1 to identify eligible supermerge candidates.
- Algorithm 1: Iteratively compares the count of the best available supermerge candidate against the count of the next regular merge from Phase 1.
- If the supermerge count is strictly higher, the supermerge is applied; otherwise, the regular merge is applied.
- Key Insight: This process dynamically determines the split between regular merges ( $r$ ) and supermerges ( $s$ ), eliminating the need for SuperBPE's manual hyperparameter $s$ .

C. Inference Optimization

A significant optimization is introduced for the inference stage:

Vocabulary Lookup Shortcut: Before applying BPE rules, the system checks if a pretoken exists directly in the vocabulary. If it does, it is kept as a single token without further processing.
This avoids the naive approach of breaking pretokens into bytes and re-applying merge rules, which is computationally expensive.

3. Key Contributions

Aggregation Procedure: A method to aggregate supermerge candidates by frequency, removing the need to store full documents in memory.
Two-Phase Formulation: A reformulation of BoundlessBPE that is mathematically equivalent to the original but allows for the separation of regular and superword learning, enabling efficient aggregation.
Script-Specific Pre-tokenization: A strategy for non-space-delimited languages (e.g., CJK) that prevents invalid UTF-8 tokens and enables supermerging at the character level.
Open-Source Implementation: Release of both a reference Python implementation and a high-performance Rust implementation for BoundlessBPE and SuperBPE.
Inference Shortcut: A lookup-based optimization that significantly speeds up tokenization during inference.

4. Results

The authors evaluated the new implementation on the MiniPile dataset (up to 1M documents) with a vocabulary size of 131,072.

Training Speedup:
- BoundlessBPE: Reduced from 4.7 CPU days (original) to 603 seconds (new Rust implementation).
- SuperBPE: Reduced to 593 seconds.
- Magnitude: A >600x speedup compared to the original BoundlessBPE implementation.
Performance Comparison:
- The Rust implementation is significantly faster than Python (e.g., ~3x faster for training, ~2.9x faster for inference with the shortcut).
- The Inference Shortcut provides a 2.8x speedup in Python and 1.6x in Rust compared to standard BPE inference.
Scalability: Training time scales sublinearly with vocabulary size once the initial setup (pre-tokenization and counting) is complete.

5. Significance

Feasibility: This work removes the primary barrier to adopting superword tokenization (training time), making it practical to train these models on large-scale corpora (e.g., 10GB+ or full web-scale datasets).
Model Quality: Since the resulting models are mathematically identical to the original BoundlessBPE/SuperBPE, the known benefits (higher compression, better token distribution, improved downstream task accuracy) are preserved.
Accessibility: By providing open-source, fast implementations, the authors enable the broader research community to experiment with and deploy superword tokenization without needing custom, slow training pipelines.
Future Work: The authors note that while the current implementation is single-threaded, the architecture is compatible with parallelization, which could yield further speed improvements.

In summary, this paper transforms superword tokenization from a theoretical concept with impractical training costs into a viable, high-performance tool for modern LLM development.