BPE-knockout: Pruning Pre-existing BPE Tokenisers with Backwards-compatible Morphological Semi-supervision

Thomas Bauwens, Pieter DelobelleNAACL 2024 · DOI

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.

Original BPE merge graph showing hierarchical subword construction.

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).

BPE-knockout process: the 'ids' node is removed, and the graph is re-linked to maintain reachability.

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

BibTeX
@inproceedings{bauwens2024bpe,
  author = {Thomas Bauwens and Pieter Delobelle},
  title = {{BPE-knockout: Pruning Pre-existing BPE Tokenisers with Backwards-compatible Morphological Semi-supervision}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  doi = {10.18653/v1/2024.naacl-long.324},
}
Figure