Elamur Research⌕
☰
home / papers / 2024 / 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

Paper · 2024 · Buu Phan, Brandon Amos, Itai Gat et al.

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

🏢MetaMenlo Park · United States183 works · 228,558 citations🎓University of TorontoToronto · Canada96 works · 142,007 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 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. DOI 10.48550/arxiv.2410.09303 · arXiv 2410.09303

@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}
}

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
  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. 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. 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. 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
  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, 7, 2023. ↗
  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
  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. GitHub repository. — [arXiv:2407.11009](https://arxiv.org/abs/2407.11009) ↗
  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
  10. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration, 2020. URL 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
  12. Albert Q. Jiang et al. Mistral 7b, 2023a. URL 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. 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
  15. Tomasz Limisiewicz, Terra Blevins, Hila Gonen, Orevaoghene Ahia, and Luke Zettlemoyer. Myte: Morphology-driven byte encoding for better and fairer multilingual language modeling. arXiv preprint arXiv:2403.10691, 2024.
  16. Tiago Pimentel and Clara Meister. How to compute the probability of a word. arXiv preprint arXiv:2406.14561, 2024.
  17. Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. Bpe-dropout: Simple and effective subword regularization. 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
  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. arXiv preprint arXiv:2308.12950, 2023.
  20. Felix Stahlberg and Bill Byrne. On NMT search errors and model errors: Cat got your tongue? 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. 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
  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.
  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
  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

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/phan-2024-exact-byte-level-probabilities-tokenized/