---
title: "Exact Byte-Level Probabilities from Tokenized Language Models"
description: "From it they build an inference-time sampler that turns an already trained tokenized model into an… 25 references, cited by 8 papers here."
authors: ["Buu Phan", "Brandon Amos", "Itai Gat", "Marton Havasi", "Matthew Muckley", "Karen Ullrich"]
year: 2024
venue: "arXiv:2410.09303"
source: "https://arxiv.org/abs/2410.09303"
doi: "10.48550/arxiv.2410.09303"
arxiv: "2410.09303"
licence: "CC BY-SA 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by-sa/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/phan-2024-exact-byte-level-probabilities-tokenized/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/phan-2024-exact-byte-level-probabilities-tokenized/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2024](https://md.research.elamur.ai/free/en/papers/2024/page/10/) / Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles

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

**Authors:** Buu Phan, Brandon Amos, [Itai Gat](https://md.research.elamur.ai/free/en/authors/itai-gat/), Marton Havasi, Matthew Muckley and Karen Ullrich · **Year:** 2024 · **Venue:** arXiv:2410.09303 · **Licence:** [CC BY-SA 4.0 (arXiv)](http://creativecommons.org/licenses/by-sa/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2410.09303) · [PDF](https://arxiv.org/pdf/2410.09303) · [DOI 10.48550/arxiv.2410.09303](https://doi.org/10.48550/arxiv.2410.09303) · [arXiv 2410.09303](https://arxiv.org/abs/2410.09303) · [OpenAlex](https://openalex.org/W4403564552)

**Citations:** 0 citations (OpenAlex, 2026-10-14) · 8 in our library, of the 149,439 papers whose bibliographies we read

## Summary
Subword-tokenized language models behave oddly when a prompt stops in the middle of a token: some continuations become practically impossible to generate. The authors show that every tokenized LM (using BPE or MPE tokenizers) has a byte-level twin that assigns the same probability to every complete sequence. Even so, the two can disagree sharply on the next byte after a given prompt. They call this mismatch "tokenization bias" and analyze it in closed form on Markov chains. Their Byte-Token Representation Lemma maps token-level distributions to exact byte-level ones. From it they build an inference-time sampler that turns an already trained tokenized model into an equivalent token-free one, with no retraining and constant overhead in model calls. They test it in two settings. The first is fill-in-the-middle (FIM) code completion, where prompts often end mid-token. The second is ensembling LMs with different vocabularies, which becomes possible once all predictions are expressed over bytes. The approach improves FIM coding results by 18% and lifts ensembles by up to 3.7%, which is relevant for code assistants and for combining heterogeneous LLMs.

## Key points
- **Tokenization bias defined:** a tokenized model and its statistically equivalent byte-level process can still give different next-byte probabilities for the same prompt.
- **Correction method:** the Byte-Token Representation Lemma yields zero-shot next-byte sampling for any tokenized LM. It needs no extra training and costs O(1) in model runs.
- **FIM results:** an 18% gain on FIM coding benchmarks, with consistent wins over token healing. CodeLlama-7b examples on RandomSpanInfilling/HumanEval show cases such as "odd_colla…" and "is_palindr…" that only byte-level prediction completes correctly.
- **Ensembles:** models with different vocabularies are combined in byte space, gaining up to 3.7% over individual models on reasoning, knowledge and coding baselines.
- **Authors and code:** work by University of Toronto and Meta AI; code is released at github.com/facebookresearch/Exact-Byte-Level-Probabilities-from-Tokenized-LMs.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Meta](https://md.research.elamur.ai/free/en/companies/meta/) — Company, Menlo Park, United States · 183 works · 228,558 citations
- [University of Toronto](https://md.research.elamur.ai/free/en/universities/university-of-toronto/) — University, Toronto, Canada · 96 works · 142,007 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🗄️ Information Systems](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) · 1,437 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,320 works

## Cite

Cite as: Buu Phan, Brandon Amos, Itai Gat, Marton Havasi, Matthew Muckley and Karen Ullrich. 2024. Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles. arXiv:2410.09303.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{phan2024exact,
  title = {{Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles}},
  author = {Buu Phan, Brandon Amos, Itai Gat, Marton Havasi, Matthew Muckley and Karen Ullrich},
  year = {2024},
  doi = {10.48550/arxiv.2410.09303},
  eprint = {2410.09303},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2410.09303}
}
```

- [← previous Bilingual Rhetorical Structure Parsing with Large Parallel Annotations](https://md.research.elamur.ai/free/en/papers/chistova-2024-bilingual-rhetorical-structure-parsing-large/)
- [next → GUMsley: Evaluating Entity Salience in Summarization for 12 English Genres](https://md.research.elamur.ai/free/en/papers/lin-2024-gumsley-evaluating-entity-salience-summarization/)
- [↑ back to papers of 2024](https://md.research.elamur.ai/free/en/papers/2024/page/10/)

## References

25 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Ben Athiwaratkun, Shiqi Wang, Mingyue Shang, Yuchen Tian, Zijian Wang, Sujan Kumar Gonugondla, Sanjay Krishna Gouda, Rob Kwiatowski, Ramesh Nallapati, and Bing Xiang. Token alignment via character matching for subword completion. arXiv preprint arXiv:2403.08688, 2024. [find](https://scholar.google.com/scholar?q=Ben+Athiwaratkun%2C+Shiqi+Wang%2C+Mingyue+Shang%2C+Yuchen+Tian%2C+Zijian+Wang%2C+Sujan+Kumar+Gonugondla%2C+Sanjay+Krishna+Gouda%2C+Rob+Kwiatowski%2C+Ramesh+Nallapati%2C+and+Bing+Xiang%2E+Token+alignment+via+character+mat)
2. Mohammad Bavarian, Heewoo Jun, Nikolas Tezak, John Schulman, Christine McLeavey, Jerry Tworek, and Mark Chen. [Efficient training of language models to fill in the middle](https://md.research.elamur.ai/free/en/papers/bavarian-2022-efficient-training-language-models-fill/). arXiv preprint arXiv:2207.14255, 2022.
3. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. [Language models are few-shot learners](https://md.research.elamur.ai/free/en/papers/brown-2020-language-models-few-shot-learners/). Advances in neural information processing systems, 33:1877–1901, 2020.
4. Gautier Dagan, Gabriele Synnaeve, and Baptiste Rozière. [Getting the most out of your tokenizer for pre-training and domain adaptation](https://md.research.elamur.ai/free/en/papers/dagan-2024-getting-most-out-tokenizer-pre/). arXiv preprint arXiv:2402.01035, 2024.
5. Paul Duetting, Vahab Mirrokni, Renato Paes Leme, Haifeng Xu, and Song Zuo. Mechanism design for large language models. In Proceedings of the ACM on Web Conference 2024, pp. 144–155, 2024. [find](https://scholar.google.com/scholar?q=Paul+Duetting%2C+Vahab+Mirrokni%2C+Renato+Paes+Leme%2C+Haifeng+Xu%2C+and+Song+Zuo%2E+Mechanism+design+for+large+language+models%2E+In+Proceedings+of+the+ACM+on+Web+Conference+2024%2C+pp%2E+144%E2%80%93155%2C+2024%2E)
6. L Gao, J Tow, B Abbasi, S Biderman, S Black, A DiPofi, C Foster, L Golding, J Hsu, A Le Noac’h, et al. A framework for few-shot language model evaluation, 12 2023. URL [https://zenodo.org/records/10256836](https://zenodo.org/records/10256836), 7, 2023. [↗](https://zenodo.org/records/10256836)
7. Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. Unpacking tokenization: Evaluating text compression and its correlation with model performance. arXiv preprint arXiv:2403.06265, 2024. [find](https://scholar.google.com/scholar?q=Omer+Goldman%2C+Avi+Caciularu%2C+Matan+Eyal%2C+Kris+Cao%2C+Idan+Szpektor%2C+and+Reut+Tsarfaty%2E+Unpacking+tokenization%3A+Evaluating+text+compression+and+its+correlation+with+model+performance%2E+arXiv+preprint+arXi)
8. Kevin Gu, Eva Tuecke, Dmitriy Katz, Raya Horesh, David Alvarez-Melis, and Mikhail Yurochkin. Chared: Character-wise ensemble decoding for large language models. arXiv preprint arXiv:2407.11009, 2024. guidance ai. Guidance ai, 2023. URL [https://github.com/guidance-ai/guidance](https://github.com/guidance-ai/guidance). GitHub repository. — [arXiv:2407.11009](https://arxiv.org/abs/2407.11009) [↗](https://github.com/guidance-ai/guidance)
9. Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009. [find](https://scholar.google.com/scholar?q=Trevor+Hastie%2C+Robert+Tibshirani%2C+Jerome+H+Friedman%2C+and+Jerome+H+Friedman%2E+The+elements+of+statistical+learning%3A+data+mining%2C+inference%2C+and+prediction%2C+volume+2%2E+Springer%2C+2009%2E)
10. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. [The curious case of neural text degeneration](https://md.research.elamur.ai/free/en/papers/holtzman-2019-curious-case-neural-text-degeneration/), 2020. URL https://arxiv.org/abs/1904.09751. [↗](https://arxiv.org/abs/1904.09751)
11. Yichong Huang, Xiaocheng Feng, Baohang Li, Yang Xiang, Hui Wang, Bing Qin, and Ting Liu. Enabling ensemble learning for heterogeneous large language models with deep parallel collaboration. arXiv preprint arXiv:2404.12715, 2024. — [arXiv:2404.12715](https://arxiv.org/abs/2404.12715) [find](https://scholar.google.com/scholar?q=Yichong+Huang%2C+Xiaocheng+Feng%2C+Baohang+Li%2C+Yang+Xiang%2C+Hui+Wang%2C+Bing+Qin%2C+and+Ting+Liu%2E+Enabling+ensemble+learning+for+heterogeneous+large+language+models+with+deep+parallel+collaboration%2E+arXiv+prep)
12. Albert Q. Jiang et al. Mistral 7b, 2023a. URL https://arxiv.org/abs/2310.06825. [↗](https://arxiv.org/abs/2310.06825)
13. Dongfu Jiang, Xiang Ren, and Bill Yuchen Lin. [Llm-blender: Ensembling large language models with pairwise ranking and generative fusion](https://md.research.elamur.ai/free/en/papers/jiang-2023-llm-blender-ensembling-large-language/). arXiv preprint arXiv:2306.02561, 2023b.
14. Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. In Thang Luong, Alexandra Birch, Graham Neubig, and Andrew Finch (eds.), Proceedings of the First Workshop on Neural Machine Translation, pp. 28–39, Vancouver, August 2017. Association for Computational Linguistics. do… [find](https://scholar.google.com/scholar?q=Philipp+Koehn+and+Rebecca+Knowles%2E+Six+challenges+for+neural+machine+translation%2E+In+Thang+Luong%2C+Alexandra+Birch%2C+Graham+Neubig%2C+and+Andrew+Finch+%28eds%2E%29%2C+Proceedings+of+the+First+Workshop+on+Neural+M)
15. Tomasz Limisiewicz, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettlemoyer. [Myte: Morphology-driven byte encoding for better and fairer multilingual language modeling](https://md.research.elamur.ai/free/en/papers/limisiewicz-2024-myte-morphology-driven-byte-encoding/). arXiv preprint arXiv:2403.10691, 2024.
16. Tiago Pimentel and Clara Meister. [How to compute the probability of a word](https://md.research.elamur.ai/free/en/papers/pimentel-2024-how-compute-probability-word/). arXiv preprint arXiv:2406.14561, 2024.
17. Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. [Bpe-dropout: Simple and effective subword regularization](https://md.research.elamur.ai/free/en/papers/provilkov-2020-bpe-dropout-simple-effective-subword/). In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2020.
18. Nived Rajaraman, Jiantao Jiao, and Kannan Ramchandran. Toward a theory of tokenization in llms. arXiv preprint arXiv:2404.08335, 2024. — [arXiv:2404.08335](https://arxiv.org/abs/2404.08335) [find](https://scholar.google.com/scholar?q=Nived+Rajaraman%2C+Jiantao+Jiao%2C+and+Kannan+Ramchandran%2E+Toward+a+theory+of+tokenization+in+llms%2E+arXiv+preprint+arXiv%3A2404%2E08335%2C+2024%2E+%E2%80%94+%5BarXiv%3A2404%2E08335%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2404%2E08335%29)
19. Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. [Code llama: Open foundation models for code](https://md.research.elamur.ai/free/en/papers/roziere-2024-code-llama-open-foundation-models/). arXiv preprint arXiv:2308.12950, 2023.
20. Felix Stahlberg and Bill Byrne. [On NMT search errors and model errors: Cat got your tongue?](https://md.research.elamur.ai/free/en/papers/stahlberg-2019-nmt-search-errors-model-errors/) In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural La…
21. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. [Llama: Open and efficient foundation language models](https://md.research.elamur.ai/free/en/papers/touvron-2023-llama-open-efficient-foundation-language/). arXiv preprint arXiv:2302.13971, 2023.
22. Fanqi Wan, Xinting Huang, Deng Cai, Xiaojun Quan, Wei Bi, and Shuming Shi. Knowledge fusion of large language models. arXiv preprint arXiv:2401.10491, 2024. [find](https://scholar.google.com/scholar?q=Fanqi+Wan%2C+Xinting+Huang%2C+Deng+Cai%2C+Xiaojun+Quan%2C+Wei+Bi%2C+and+Shuming+Shi%2E+Knowledge+fusion+of+large+language+models%2E+arXiv+preprint+arXiv%3A2401%2E10491%2C+2024%2E)
23. Alex Young, Bei Chen, Chao Li, Chengen Huang, Ge Zhang, Guanwei Zhang, Heng Li, Jiangcheng Zhu, Jianqun Chen, Jing Chang, et al. Yi: Open foundation models by 01. ai. arXiv preprint arXiv:2403.[04652, 2024](https://md.research.elamur.ai/free/en/papers/ai-2024-yi-open-foundation-models-01/).
24. Lili Yu, Dániel Simig, Colin Flaherty, Armen Aghajanyan, Luke Zettlemoyer, and Mike Lewis. Megabyte: Predicting million-byte sequences with multiscale transformers. Advances in Neural Information Processing Systems, 36, 2024. [find](https://scholar.google.com/scholar?q=Lili+Yu%2C+Da%CC%81niel+Simig%2C+Colin+Flaherty%2C+Armen+Aghajanyan%2C+Luke+Zettlemoyer%2C+and+Mike+Lewis%2E+Megabyte%3A+Predicting+million%2Dbyte+sequences+with+multiscale+transformers%2E+Advances+in+Neural+Information+Pro)
25. Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. Tokenization and the noiseless channel. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5184–5207, 2023. [find](https://scholar.google.com/scholar?q=Vile%CC%81m+Zouhar%2C+Clara+Meister%2C+Juan+Gastaldi%2C+Li+Du%2C+Mrinmaya+Sachan%2C+and+Ryan+Cotterell%2E+Tokenization+and+the+noiseless+channel%2E+In+Proceedings+of+the+61st+Annual+Meeting+of+the+Association+for+Comput)

*Updated 31 October 2026*