Stochasticity in Tokenisation Improves Robustness

Sophie Steger, Rui Li, Sofiane Ennadir, Anya Sims, Arno Solin, Franz Pernkopf, Martin TrapparXiv 2026 · arXiv

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:

  1. 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.
  2. 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%.
Accuracy under canonical and adversarial tokenization for Llama-1b
  • 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.
Figure 1. Effect of stochastic tokenisation during testing. As the level of stochasticity increases (increasing number of splits), the accuracy of Llama-1b trained on LANGUAGE GAME with canonical tokenisation (CANON) sharply drops while the same model fine-tuned with stochastic tokenisation (STOK, STOK-UNI, or UNI-K) remains robust to perturbations during testing.

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

Abstract

The widespread adoption of large language models (LLMs) has increased concerns about their robustness. Vulnerabilities in perturbations of tokenisation of the input indicate that models trained with a deterministic canonical tokenisation can be brittle to adversarial attacks. Recent studies suggest that stochastic tokenisation can deliver internal representations that are less sensitive to perturbations. In this paper, we analyse how stochastic tokenisations affect robustness to adversarial attacks and random perturbations. We systematically study this over a range of learning regimes (pre-training, supervised fine-tuning, and in-context learning), data sets, and model architectures. We show that pre-training and fine-tuning with uniformly sampled stochastic tokenisations improve robustness to random and adversarial perturbations. Evaluating on uniformly sampled non-canonical tokenisations reduces the accuracy of a canonically trained Llama-1b model by 29.8%. We find that training with stochastic tokenisation preserves accuracy without increasing inference cost.
BibTeX
@misc{steger2026stochasticity,
  author = {Sophie Steger and Rui Li and Sofiane Ennadir and Anya Sims and Arno Solin and Franz Pernkopf and Martin Trapp},
  title = {{Stochasticity in Tokenisation Improves Robustness}},
  year = {2026},
  eprint = {2604.16037},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.16037},
}

Loading related content...

Figure