TL;DR
This paper investigates whether the complex "merge lists" used in Byte-Pair Encoding (BPE) tokenization are truly necessary for language model performance during inference. They demonstrate that simpler, "merge-free" inference algorithms that focus solely on compressing text achieve comparable, and sometimes even better, results than standard BPE, while significantly reducing security vulnerabilities associated with merge lists.
What Problem Does This Paper Address?
Large language models (LLMs) rely on tokenizers to convert raw text into numerical representations. Byte-Pair Encoding (BPE) is a popular tokenization algorithm that uses a learned vocabulary and a "merge list" to iteratively combine subword units. While effective, this merge list has been identified as a security vulnerability: it can expose information about the tokenizer's training data, which is often correlated with the LLM's training data. This could potentially be exploited to infer sensitive information or to introduce "glitch tokens" that cause generation failures. The authors aim to determine if it's possible to achieve good LLM performance without relying on these merge lists during inference, thereby mitigating these security risks.
Methods
The paper explores two main categories of BPE inference algorithms:
- Targeted Deviations from Merge Lists: These involve intentionally corrupting the merge list by shuffling merge orders, deleting merges, or truncating the list. This is done to understand the impact of merge list integrity on performance.
- Non-Targeted Merge-List-Free Algorithms: These algorithms focus on compressing text using only the BPE vocabulary, without referencing the merge list. Two specific algorithms are investigated:
- Left-to-Right Greedy Encoding: This algorithm greedily selects the longest possible prefix of the input text that exists in the BPE vocabulary.
- Maximal Compression Encoding: This algorithm aims to find the combination of tokens from the vocabulary that results in the shortest possible representation of the input text.
The authors then evaluate the downstream performance of LLMs using these different tokenization schemes.
Datasets
The paper uses the following datasets for evaluation:
- Accuracy-based QA: MMLU (Massive Multitask Language Understanding) and ARC-Easy/Challenge.
- Machine Translation: WMT16 Czech-English and German-English test sets.
- Open-ended Generation: Prompts extracted from the first five sentences of scientific papers from the Semantic Scholar Open Research Corpus (S2ORC).
The experiments utilize the Qwen-2-7B-Instruct model.
Key Insights and Ideas
- Merge lists are a significant security vulnerability: The paper confirms that manipulating merge lists can indeed degrade LLM performance, highlighting their role in model behavior and the potential for malicious exploitation.
- Simpler is often better (or at least as good): The core finding is that "merge-free" inference algorithms, which discard the merge list and focus purely on compression, perform surprisingly well. They often match or even exceed the performance of the standard merge-list-dependent approach.
- Compression is key: The success of the merge-free algorithms suggests that the primary objective of BPE during training (compression) is what truly matters for downstream performance, rather than the specific order of merges used during inference.
- Robustness to corruption: While targeted corruption of merge lists significantly harms performance, the non-targeted compression-focused methods are robust and maintain performance, indicating that LLMs can adapt to different tokenizations as long as they are semantically meaningful and compressed.
Key Results
- Targeted merge list corruption: Significantly degrades LLM performance on machine translation and open-ended generation tasks, though less so on accuracy-based QA. Merge shuffle and character-level tokenization performed particularly poorly, suggesting that severe corruption negates the benefits of subword tokenization.
- Non-targeted merge-list-free algorithms:
- Left-to-Right Greedy Encoding: Maintained or improved performance on accuracy-based QA and open-ended generation. It showed only minor degradations on machine translation.
- Maximal Compression Encoding: Largely maintained the performance of the standard tokenizer across tasks, with minor degradations on machine translation.
- Edit distances: Merge-list-free algorithms produced smaller edit distances (differences in token sequences) compared to the standard tokenizer than targeted corruption schemes, indicating they are less disruptive.
Limitations and Future Work
- Generalizability: The authors acknowledge that their findings are based on specific LLMs and tasks, and it's unclear if these merge-free algorithms are universally optimal across all domains and languages, especially those with non-monotonic or non-left-to-right writing orders.
- Theoretical guarantees: While empirically supported, the theoretical underpinnings for why these merge-free algorithms work so well are not fully established.
- Other attacks: The paper notes that while merge-list-free tokenization addresses specific security vulnerabilities, it doesn't defend against all potential tokenization-based attacks, such as those exploiting "glitch tokens."
- Future work: The authors suggest exploring the theoretical reasons behind the robustness of compression-based algorithms and investigating their performance on low-resource languages or languages with different writing systems. They also plan to further explore the relationship between training and inference tokenization.
Summary updated