Introduction
Modern Large Language Models (LLMs) predominantly use Byte-Pair Encoding (BPE) for tokenization. While computationally efficient and data-driven, BPE is "linguistically blind." It prioritizes frequency over structure, often merging characters across morpheme boundaries. This results in subword units that lack semantic coherence, forcing models to learn fragmented representations. Furthermore, BPE creates "stepping stone" tokens that are rarely used in final tokenization, leading to vocabulary bloat.
The BPE-knockout Method
To address these issues, the authors propose BPE-knockout, a method to prune linguistically invalid merges from an existing BPE vocabulary.
The "Blame" Metric
The first step involves identifying "blameworthy" merges. Using a morphological reference (e.g., the CELEX database), the algorithm evaluates every merge in a corpus. A merge is "blamed" if it concatenates characters belonging to different morphemes. If a merge type is blamed in more than 50% of its occurrences, it is targeted for removal.
Graph Pruning and Byte-tuple Encoding (BTE)
Standard BPE is a binary merge process. Deleting a node in the middle of a merge sequence would normally break the chain. BPE-knockout treats the vocabulary as a directed acyclic graph (DAG). When a "blameworthy" node is removed, the algorithm re-links the graph, creating direct paths between the remaining components.
As shown in the figures, removing a node like ids requires re-routing the merges. This leads to Byte-tuple Encoding (BTE), where a single rule can merge three or more units simultaneously (e.g., A+B+C -> ABC).
Backwards Compatibility and Adaptation
A key advantage of BPE-knockout is its backwards compatibility. Since the underlying character sequences of the remaining tokens are unchanged, their original embeddings remain valid. This allows for "continued pre-training," where a model's tokenizer is "fixed" post-hoc, and the model is fine-tuned for a small fraction of the original training cost.
Evaluation and Results
The method was tested on English, Dutch, and German using the CELEX database and OSCAR corpus.
Morphological Adherence
BPE-knockout dramatically improves how well tokens align with morphemes. In English, the recall of morpheme boundaries increased from 4.0% with standard BPE to 59.2% with knockout.
Downstream Performance
The impact is most pronounced in token-level tasks. For Dutch RoBERTa models, BPE-knockout improved Named Entity Recognition (NER) F1 scores from 83.98 to 87.51. Crucially, an adapted model trained for only 5,000 additional batches outperformed a baseline BPE model trained for 30,000 batches on several tasks, demonstrating the efficiency of this structural refinement.
Conclusion
BPE-knockout offers a path to more linguistically sound tokenization without the prohibitive cost of training new models from scratch. By treating the vocabulary as a graph and pruning based on morphological "blame," researchers can salvage pre-trained models and improve their performance on complex linguistic tasks. Future work may explore iterative pruning and the integration of inflectional morphology.
Summary updated