TL;DR
Large Language Models (LLMs) are surprisingly brittle when text is tokenized in valid but non-standard ways, leaving them highly vulnerable to adversarial exploits. This paper demonstrates that introducing stochastic tokenization—randomly varying how text is split into tokens during training—dramatically boosts model robustness against both random and adversarial perturbations at zero additional inference cost.
What Problem Does This Paper Address?
Before an LLM can process text, a tokenizer must break the raw string of characters down into pieces called tokens (often using algorithms like Byte Pair Encoding). Typically, this process is entirely deterministic: a single "canonical" sequence of tokens is generated for any given piece of text.
However, this mapping is rarely unique. A single string can often be broken down into multiple alternative, equally valid token sequences (known as non-canonical tokenizations). Because standard LLMs are only exposed to canonical tokenizations during training, they become incredibly fragile when encountering alternative token structures. Attackers can exploit this blind spot by crafting adversarial token sequences that completely break model alignment or degrade performance—all without changing a single character of the input text.
Methods
The authors explore training LLMs with stochastic tokenization, exposing models to alternative text segmentations while keeping the vocabulary fixed. They analyze an existing method called STOCHASTOK (which randomly splits tokens into pairs of smaller subtokens) and identify two major flaws: it has biased sampling (favoring certain split types) and incomplete support (it cannot generate all valid tokenizations).
To fix these issues, they introduce two new unbiased uniform sampling schemes:
- STOCHASTOK-UNI: A two-stage approach that retains STOCHASTOK's split-count distribution but samples the actual token segmentations uniformly, ensuring full support within those constraints.
- UNIFORM-K: This method uses a Multi-valued Decision Diagram (MDD) to sample marginally uniformly across the entire input sequence at a specific edit distance $k$, allowing splits to cross canonical token boundaries.
The authors systematically evaluate these methods across three distinct learning regimes: pre-training from scratch, supervised fine-tuning (SFT), and in-context learning (ICL).
Datasets
The authors evaluate their methods on a mix of token-sensitive tasks and general reasoning benchmarks:
- LANGUAGE GAME: A benchmark testing subword-level understanding (e.g., counting letters, identifying the shortest/longest word).
- CUTE: A dataset explicitly designed to evaluate the character-level understanding of tokens.
- General Benchmarks: Standard multiple-choice QA datasets including ARC-E, COPA, CSQA, Hellaswag, PIQA, and SocialIQA to test general reasoning capabilities under token perturbations.
Key Insights and Ideas
- The Fine-Tuning Vulnerability: While massive pre-training gives large models some inherent robustness, fine-tuning them on small, clean, curated datasets actually introduces severe tokenization vulnerabilities.
- Uniformity is Essential for Defense: Biased stochastic tokenization (like standard STOCHASTOK or BPE-Dropout) helps with random noise but falls short against worst-case adversarial attacks. True uniform sampling (like UNIFORM-K) provides a vastly superior defense because it covers a wider space of non-canonical variations.
- Embedding Space Smoothing: Why does this work? The authors mathematically and empirically prove that stochastic tokenization acts as a regularizer. It effectively "smooths" the model's embedding space, reducing its local sensitivity (Lipschitz constant) to token changes.
- A Free Lunch: Implementing stochastic tokenization during training preserves standard accuracy and incurs zero extra cost at inference time, since the model evaluates standard canonical text normally during deployment.
Key Results
- Brittleness of Standard Models: Evaluating a standard, canonically trained Llama-1b model on uniformly sampled non-canonical tokenizations slashes its accuracy by 29.8%.
- Defeating Adversarial Attacks: Under a greedy adversarial tokenization attack, a standard fine-tuned Llama-1b's performance catastrophically drops from 94% to just 6.1%. Fine-tuning with the authors' UNIFORM-K method mitigates this drop, maintaining an accuracy of 69.6%.
- Robustness to Random Noise: As test-time token perturbations increase, models fine-tuned with stochastic tokenization maintain stable, high accuracy, whereas canonically trained models degrade rapidly.
Limitations and Future Work
- Task Constraints: The evaluation is currently restricted to multiple-choice question-answering tasks. The authors note that extending this assessment to natural language generation (NLG) tasks is an essential next step.
- Optimization: While the theoretical analysis links tokenization to robustness bounds, more work is required to fully characterize and discover the absolute optimal design for a stochastic tokenization scheme.
Summary updated