Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models

2025/08/08 by Tomohiro Sawada, Sawada, Tomohiro, Kartik Goyal +1
Computer Science · Decision Sciences · #Computation and Language (cs.CL) #Data Quality and Management #FOS: Computer and information sciences #Natural Language Processing Techniques #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2508.06621

openalex publication_date 2025/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Standard Byte-Pair Encoding (BPE) tokenization compresses text by pairing a learned token vocabulary with a detailed merge list. Recent work has shown that this merge list exposes a potential attack surface for extracting information about language model's training data. In this paper, we explore the downstream impact of BPE inference algorithms that do not rely on this merge list at all, and hence differ from the encoding process during BPE training. To address this question, we investigate two broad classes of BPE inference schemes that differ from BPE application during training: a) targeted deviation from merge-lists including random merge orders, and various corruptions of merge list involving deletion/truncation, and b) non-targeted BPE inference algorithms that do not depend on the merge list but focus on compressing the text either greedily or exactly. Extensive experiments across diverse language modeling tasks like accuracy-based QA benchmarks, machine translation, and open-ended generation reveal that while targeted deviation from the merge lists exhibits significant degradation in language model performance, the non-targeted merge-list-free inference algorithms result in minimal impact on downstream performance that is often much smaller than expected. These findings pave way for simpler and potentially more privacy-preserving tokenization schemes that do not catastrophically compromise model performance.

Citations

• Language Models over Canonical Byte-Pair Encodings
• Forking Paths in Neural Text Generation
• From Language Models over Tokens to Language Models over Characters
• From Tokens to Words: On the Inner Lexicon of LLMs
• Where is the signal in tokenization space?
• Data Mixture Inference: What do BPE Tokenizers Reveal about their Training Data?
• The Foundations of Tokenization: Statistical and Computational Concerns
• Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance
• Greed is All You Need: An Evaluation of Tokenizer Inference Methods
• Coercing LLMs to do and reveal (almost) anything
• Unnatural Error Correction: GPT-4 Can Almost Perfectly Handle Unnatural Scrambled Text
• Analyzing Cognitive Plausibility of Subword Tokenization
• A Formal Perspective on Byte-Pair Encoding
• What changes when you randomly choose BPE merge operations? Not much
• Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP
• COMET: A Neural Framework for MT Evaluation
• Measuring Massive Multitask Language Understanding
• Byte Pair Encoding is Suboptimal for Language Model Pretraining
• BPE-Dropout: Simple and Effective Subword Regularization
• SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing
• Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge
• Neural Machine Translation of Rare Words with Subword Units
• You should evaluate your language model on marginal likelihood over tokenisations

Related

• Data Mixture Inference: What do BPE Tokenizers Reveal about their Training Data?
• What changes when you randomly choose BPE merge operations? Not much
• Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization
• Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance
• BPE Gets Picky: Efficient Vocabulary Refinement During Tokenizer Training