# Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 27 references that are in the map.
- First posted on arXiv 11 Oct 2024.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Yi: Open Foundation Models by 01.AI](https://mlsanity.com/paper/2403.04652/) (2024)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [Six Challenges for Neural Machine Translation](https://mlsanity.com/paper/1706.03872/) (2017)
- [Efficient Training of Language Models to Fill in the Middle](https://mlsanity.com/paper/2207.14255/) (2022)
- [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)
- [Knowledge Fusion of Large Language Models](https://mlsanity.com/paper/2401.10491/) (2024)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [Ensemble Learning for Heterogeneous Large Language Models with Deep Parallel Collaboration](https://mlsanity.com/paper/2404.12715/) (2024)
- [Getting the most out of your tokenizer for pre-training and domain adaptation](https://mlsanity.com/paper/2402.01035/) (2024)
- [Unpacking Tokenization: Evaluating Text Compression and its Correlation with Model Performance](https://mlsanity.com/paper/2403.06265/) (2024)
- [Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2306.16842/) (2023)
- [MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling](https://mlsanity.com/paper/2403.10691/) (2024)
- [How to Compute the Probability of a Word](https://mlsanity.com/paper/2406.14561/) (2024)
- [Toward a Theory of Tokenization in LLMs](https://mlsanity.com/paper/2404.08335/) (2024)
- [Token Alignment via Character Matching for Subword Completion](https://mlsanity.com/paper/2403.08688/) (2024)
- [CharED: Character-wise Ensemble Decoding for Large Language Models](https://mlsanity.com/paper/2407.11009/) (2024)

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

- [Dynamic Chunking for End-to-End Hierarchical Sequence Modeling](https://mlsanity.com/paper/2507.07955/) (2025)
- [Universal Cross-Tokenizer Distillation via Approximate Likelihood Matching](https://mlsanity.com/paper/2503.20083/) (2025)
- [Broken Tokens? Your Language Model can Secretly Handle Non-Canonical Tokenizations](https://mlsanity.com/paper/2506.19004/) (2025)
- [Causal Estimation of Tokenisation Bias](https://mlsanity.com/paper/2506.03149/) (2025)
- [Bolmo: Byteifying the Next Generation of Language Models](https://mlsanity.com/paper/2512.15586/) (2025)
- [Cross-Tokenizer LLM Distillation through a Byte-Level Interface](https://mlsanity.com/paper/2604.07466/) (2026)
- [Sampling from Your Language Model One Byte at a Time](https://mlsanity.com/paper/2506.14123/) (2025)
- [Cross-Tokenizer Likelihood Scoring Algorithms for Language Model Distillation](https://mlsanity.com/paper/2512.14954/) (2025)
- [OmniDraft: A Cross-vocabulary, Online Adaptive Drafter for On-device Speculative Decoding](https://mlsanity.com/paper/2507.02659/) (2025)
- [TokSuite: Measuring the Impact of Tokenizer Choice on Language Model Behavior](https://mlsanity.com/paper/2512.20757/) (2025)
- [AdaFuse: Adaptive Ensemble Decoding with Test-Time Scaling for LLMs](https://mlsanity.com/paper/2601.06022/) (2026)
- [Convergence and Divergence of Language Models under Different Random Seeds](https://mlsanity.com/paper/2509.26643/) (2025)
- [Ensembling Language Models with Sequential Monte Carlo](https://mlsanity.com/paper/2603.05432/) (2026)
- [Lossless Vocabulary Reduction for Auto-Regressive Language Models](https://mlsanity.com/paper/2510.08102/) (2025)
- [Rethinking LLM Ensembling from the Perspective of Mixture Models](https://mlsanity.com/paper/2605.00419/) (2026)

## Abstract (arXiv)

Tokenization is associated with many poorly understood shortcomings in language models (LMs), yet remains an important component for long sequence scaling purposes. This work studies how tokenization impacts model performance by analyzing and comparing the stochastic behavior of tokenized models with their byte-level, or token-free, counterparts. We discover that, even when the two models are statistically equivalent, their predictive distributions over the next byte can be substantially different, a phenomenon we term as ``tokenization bias''. To fully characterize this phenomenon, we introduce the Byte-Token Representation Lemma, a framework that establishes a mapping between the learned token distribution and its equivalent byte-level distribution. From this result, we develop a next-byte sampling algorithm that eliminates tokenization bias without requiring further training or optimization. In other words, this enables zero-shot conversion of tokenized LMs into statistically equivalent token-free ones. We demonstrate its broad applicability with two use cases: fill-in-the-middle (FIM) tasks and model ensembles. In FIM tasks where input prompts may terminate mid-token, leading to out-of-distribution tokenization, our method mitigates performance degradation and achieves 18% improvement in FIM coding benchmarks, while consistently outperforming the standard token healing fix. For model ensembles where each model employs a distinct vocabulary, our approach enables seamless integration, resulting in improved performance up to 3.7% over individual models across various standard baselines in reasoning, knowledge, and coding. Code is available at: https://github.com/facebookresearch/Exact-Byte-Level-Probabilities-from-Tokenized-LMs