# Where is the signal in tokenization space?

arXiv: https://arxiv.org/abs/2408.08541 · HTML: https://mlsanity.com/paper/2408.08541/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 16 Aug 2024.

## Builds on (most cited first, 13 of 13)

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates](https://mlsanity.com/paper/1804.10959/) (2018)
- [Language Model Tokenizers Introduce Unfairness Between Languages](https://mlsanity.com/paper/2305.15425/) (2023)
- [BPE-Dropout: Simple and Effective Subword Regularization](https://mlsanity.com/paper/1910.13267/) (2019)
- [MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers](https://mlsanity.com/paper/2305.07185/) (2023)
- [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://mlsanity.com/paper/2402.14903/) (2024)
- [You should evaluate your language model on marginal likelihood over tokenisations](https://mlsanity.com/paper/2109.02550/) (2021)
- [Should you marginalize over possible tokenizations?](https://mlsanity.com/paper/2306.17757/) (2023)
- [Tokenization Matters: Navigating Data-Scarce Tokenization for Gender Inclusive Language Technologies](https://mlsanity.com/paper/2312.11779/) (2023)
- [Neural Lattice Language Models](https://mlsanity.com/paper/1803.05071/) (2018)

## Built on by (most cited first, 21 of 21)

- [Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations](https://mlsanity.com/paper/2506.19004/) (2025)
- [On the Proper Treatment of Tokenization in Psycholinguistics](https://mlsanity.com/paper/2410.02691/) (2024)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [Controllable Generation via Locally Constrained Resampling](https://mlsanity.com/paper/2410.13111/) (2024)
- [Adversarial Tokenization](https://mlsanity.com/paper/2503.02174/) (2025)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [Restructuring Tractable Probabilistic Circuits](https://mlsanity.com/paper/2411.12256/) (2024)
- [Sampling from Your Language Model One Byte at a Time](https://mlsanity.com/paper/2506.14123/) (2025)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [Transducing Language Models](https://mlsanity.com/paper/2603.05193/) (2026)
- [Auditing Pay-Per-Token in Large Language Models](https://mlsanity.com/paper/2510.05181/) (2025)
- [When to Ensemble: Identifying Token-Level Points for Stable and Fast LLM Ensembling](https://mlsanity.com/paper/2510.15346/) (2025)
- [Proxy Compression for Language Modeling](https://mlsanity.com/paper/2602.04289/) (2026)
- [Large Language Model Meets Constraint Propagation](https://mlsanity.com/paper/2505.24012/) (2025)
- [Language Models are not Equally Robust to Non-Canonical Tokenization across Languages](https://mlsanity.com/paper/2607.26831/) (2026)
- [Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models](https://mlsanity.com/paper/2508.06621/) (2025)
- [Entropy-Aligned Decoding of LMs for Better Writing and Reasoning](https://mlsanity.com/paper/2601.01714/) (2026)
- [Stochasticity in Tokenisation Improves Robustness](https://mlsanity.com/paper/2604.16037/) (2026)
- [Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service](https://mlsanity.com/paper/2506.06446/) (2025)
- [SurgiQ: A Large-Scale Multi-Domain Benchmark for Evaluating Surgical Understanding in Large Language Models](https://mlsanity.com/paper/2606.08071/) (2026)
- [Subliminal Prompting Beyond Static Geometry: Causal Depth and Multi-Token Confounds](https://mlsanity.com/paper/2609.19149/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are typically shipped with tokenizers that deterministically encode text into so-called canonical token sequences, to which the LLMs assign probability values. One common assumption is that the probability of a piece of text is the probability of its canonical token sequence. However, the tokenization of a string is not unique: e.g., the Llama2 tokenizer encodes Tokens as [Tok,ens], but [Tok,en,s] also represents the same text. In this paper, we study non-canonical tokenizations. We prove that, given a string, it is computationally hard to find the most likely tokenization for an autoregressive LLM, as well as to compute the marginal probability over all possible tokenizations. We then show how the marginal is, in most cases, indistinguishable from the canonical probability. Surprisingly, we then empirically demonstrate the existence of a significant amount of signal hidden within tokenization space. Notably, by simply aggregating the probabilities of non-canonical tokenizations, we achieve improvements across a range of LLM evaluation benchmarks for a variety of architectures, including transformers and state space models.