---
title: "Tokenisation is NP-Complete — paper by Whittington et al. (2025)"
description: "Popular subword tokenisers such as BPE and UnigramLM rely on greedy or heuristic training. 38 references, cited by 4 papers here."
authors: ["Philip Whittington", "Gregor Bachmann", "Tiago Pimentel"]
year: 2025
venue: "Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)"
source: "https://aclanthology.org/2025.acl-long.1365/"
doi: "10.18653/v1/2025.acl-long.1365"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/whittington-2025-tokenisation-is-np-complete/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/whittington-2025-tokenisation-is-np-complete/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2025](https://md.research.elamur.ai/free/en/papers/2025/page/12/) / Tokenisation is NP-Complete

# Tokenisation is NP-Complete

**Authors:** Philip Whittington, Gregor Bachmann and [Tiago Pimentel](https://md.research.elamur.ai/free/en/authors/tiago-pimentel/) · **Year:** 2025 · **Venue:** [Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)](https://md.research.elamur.ai/free/en/venues/acl/) ([ACL 2025](https://md.research.elamur.ai/free/en/venues/acl/2025/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2025.acl-long.1365/) · [PDF](https://aclanthology.org/2025.acl-long.1365.pdf) · [DOI 10.18653/v1/2025.acl-long.1365](https://doi.org/10.18653/v1/2025.acl-long.1365) · [OpenAlex](https://openalex.org/W4412889868)

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

## Summary
Popular subword tokenisers such as BPE and UnigramLM rely on greedy or heuristic training. They are therefore not guaranteed to reach the best value of the objective they target. This paper asks whether an optimal tokeniser can be found efficiently when the objective is compression, meaning the tokenised dataset should be as short as possible.

The authors formalise two decision problems:
- **Direct tokenisation:** choose a vocabulary with K extra subwords, then encode each string with the fewest possible tokens.
- **Bottom-up tokenisation:** choose a sequence of K merges, applied left to right in the style of BPE.

In both cases, the question is whether the dataset can be shrunk to at most δ symbols. Using polynomial-time reductions from max-2-SAT, they prove both problems are NP-complete, and extend this to some variants, including datasets without repeated strings.

The practical message is that exact optimal tokenisers are unlikely to be computable efficiently. Research effort is better spent on approximation algorithms and on sharper analysis of methods like BPE.

## Key points
- Hardness is shown by reduction from max-2-SAT, whose NP-hardness was established by Garey et al. (1974).
- Compression is the objective (G(s) = −|s|). It is chosen because it correlates with downstream performance, efficiency and multilingual fairness, though not perfectly.
- Under compression, encoding text with a fixed vocabulary is efficient. The hard part is selecting the vocabulary or the merge sequence.
- Concurrent work by Kozma and Voderholzer (2024) shows APX-hardness of bottom-up tokenisation. Lim et al. (2025) cover a restricted direct variant with predefined candidate tokens.
- The proofs assume an unbounded alphabet, so the complexity for fixed alphabets (e.g., byte-level) remains open, as do objectives other than compression.

*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

- [ETH Zurich](https://md.research.elamur.ai/free/en/universities/eth-zurich/) — University, Zurich, Switzerland · 72 works · 5,176 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 · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

🧭 Topics (1): [✂️ Tokenization & segmentation](https://md.research.elamur.ai/free/en/topics/tokenization/) · 119 works

## Cite

Cite as: Philip Whittington, Gregor Bachmann and Tiago Pimentel. 2025. Tokenisation is NP-Complete. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

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

```bibtex
@inproceedings{whittington2025tokenisation,
  title = {{Tokenisation is NP-Complete}},
  author = {Philip Whittington, Gregor Bachmann and Tiago Pimentel},
  booktitle = {Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2025},
  doi = {10.18653/v1/2025.acl-long.1365},
  url = {https://doi.org/10.18653/v1/2025.acl-long.1365}
}
```

- [← previous The Landscape of Arabic Large Language Models (ALLMs): A New Era for Arabic Language Technology](https://md.research.elamur.ai/free/en/papers/al-khalifa-2025-landscape-arabic-large-language-models/)
- [next → Towards Developmentally Plausible Rewards: Communicative Success as a Learning Signal for Interactive Language Models](https://md.research.elamur.ai/free/en/papers/stopler-2025-towards-developmentally-plausible-rewards-communicative/)
- [↑ back to papers of 2025](https://md.research.elamur.ai/free/en/papers/2025/page/12/)

## References

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

1. Orevaoghene Ahia, Sachin Kumar, Hila Gonen, Jungo Kasai, David Mortensen, Noah Smith, and Yulia Tsvetkov. 2023. [Do all languages cost the same? Tokenization in the era of commercial language models](https://md.research.elamur.ai/free/en/papers/ahia-2023-do-all-languages-cost-same/). In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 9904…
2. Mehdi Ali, Michael Fromm, Klaudia Thellmann, Richard Rutmann, Max Lübbering, Johannes Leveling, Katrin Klug, Jan Ebert, Niclas Doll, Jasper Buschhoff, Charvi Jain, Alexander Weber, Lena Jurkschat, Hammam Abdelwahab, Chelsea John, Pedro Ortiz Suarez, Malte Ostendorff, Samuel Weinbach, Rafet Sifa, Ste… — [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://md.research.elamur.ai/free/en/papers/ali-2024-tokenizer-choice-llm-training-negligible/)
3. Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar Van Der Wal. 2023. Pythia: A suite for analyzing large language models across trainin… [find](https://scholar.google.com/scholar?q=Stella+Biderman%2C+Hailey+Schoelkopf%2C+Quentin+Anthony%2C+Herbie+Bradley%2C+Kyle+O%E2%80%99Brien%2C+Eric+Hallahan%2C+Mohammad+Aflah+Khan%2C+Shivanshu+Purohit%2C+USVSN+Sai+Prashanth%2C+Edward+Raff%2C+Aviya+Skowron%2C+Lintang+Sutaw)
4. M. Charikar, E. Lehman, Ding Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. 2005. The smallest grammar problem. IEEE Transactions on Information Theory, 51(7):2554–2576. [find](https://scholar.google.com/scholar?q=M%2E+Charikar%2C+E%2E+Lehman%2C+Ding+Liu%2C+R%2E+Panigrahy%2C+M%2E+Prabhakaran%2C+A%2E+Sahai%2C+and+A%2E+Shelat%2E+2005%2E+The+smallest+grammar+problem%2E+IEEE+Transactions+on+Information+Theory%2C+51%287%29%3A2554%E2%80%932576%2E)
5. Marco Cognetta, Vilém Zouhar, Sangwhan Moon, and Naoaki Okazaki. 2024. Two counterexamples to tokenization and the noiseless channel. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024), pages 16897–16906, Torin… [find](https://scholar.google.com/scholar?q=Marco+Cognetta%2C+Vil%C3%A9m+Zouhar%2C+Sangwhan+Moon%2C+and+Naoaki+Okazaki%2E+2024%2E+Two+counterexamples+to+tokenization+and+the+noiseless+channel%2E+In+Proceedings+of+the+2024+Joint+International+Conference+on+Compu)
6. Philip Gage. 1994. A new algorithm for data compression. C Users Journal, 12(2):23–38. [find](https://scholar.google.com/scholar?q=Philip+Gage%2E+1994%2E+A+new+algorithm+for+data+compression%2E+C+Users+Journal%2C+12%282%29%3A23%E2%80%9338%2E)
7. Matthias Gallé. 2019. Investigating the effectiveness of BPE: The power of shorter sequences. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 1375–1381, Hong Kong… [find](https://scholar.google.com/scholar?q=Matthias+Gall%C3%A9%2E+2019%2E+Investigating+the+effectiveness+of+BPE%3A+The+power+of+shorter+sequences%2E+In+Proceedings+of+the+2019+Conference+on+Empirical+Methods+in+Natural+Language+Processing+and+the+9th+Inte)
8. M. R. Garey, D. S. Johnson, and L. Stockmeyer. 1974. Some simplified NP-complete problems. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, page 47–63, New York, NY, USA. Association for Computing Machinery. [find](https://scholar.google.com/scholar?q=M%2E+R%2E+Garey%2C+D%2E+S%2E+Johnson%2C+and+L%2E+Stockmeyer%2E+1974%2E+Some+simplified+NP%2Dcomplete+problems%2E+In+Proceedings+of+the+Sixth+Annual+ACM+Symposium+on+Theory+of+Computing%2C+STOC+%E2%80%9974%2C+page+47%E2%80%9363%2C+New+York%2C+NY%2C+)
9. Pietro Lesci, Clara Meister, Thomas Hofmann, Andreas Vlachos, and Tiago Pimentel. 2025. Causal estimation of tokenisation bias. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Pietro+Lesci%2C+Clara+Meister%2C+Thomas+Hofmann%2C+Andreas+Vlachos%2C+and+Tiago+Pimentel%2E+2025%2E+Causal+estimation+of+tokenisation+bias%2E+In+Proceedings+of+the+63rd+Annual+Meeting+of+the+Association+for+Computa)
10. Renato Geh, Honghua Zhang, Kareem Ahmed, Benjie Wang, and Guy Van Den Broeck. 2024. Where is the signal in tokenization space? In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 3966–3979, Miami, Florida, USA. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Renato+Geh%2C+Honghua+Zhang%2C+Kareem+Ahmed%2C+Benjie+Wang%2C+and+Guy+Van+Den+Broeck%2E+2024%2E+Where+is+the+signal+in+tokenization+space%3F+In+Proceedings+of+the+2024+Conference+on+Empirical+Methods+in+Natural+Lan)
11. Mario Giulianelli, Luca Malagutti, Juan Luis Gastaldi, Brian DuSell, Tim Vieira, and Ryan Cotterell. 2024. [On the proper treatment of tokenization in psycholinguistics](https://md.research.elamur.ai/free/en/papers/giulianelli-2024-proper-treatment-tokenization-psycholinguistics/). In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Miami, Florida, USA. Association for Com…
12. Omer Goldman, Avi Caciularu, Matan Eyal, Kris Cao, Idan Szpektor, and Reut Tsarfaty. 2024. Unpacking tokenization: Evaluating text compression and its correlation with model performance. In Findings of the Association for Computational Linguistics: ACL 2024, pages 2274–2286, Bangkok, Thailand. Assoc… [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+2024%2E+Unpacking+tokenization%3A+Evaluating+text+compression+and+its+correlation+with+model+performance%2E+In+Findings+o)
13. Thamme Gowda and Jonathan May. 2020. [Finding the optimal vocabulary size for neural machine translation](https://md.research.elamur.ai/free/en/papers/gowda-2020-finding-optimal-vocabulary-size-neural/). In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3955–3964, Online. Association for Computational Linguistics.
14. Jia Peng Lim, Davin Choo, and Hady W. Lauw. 2025. A partition cover approach to tokenization. Preprint, arXiv:2501.06246. — [arXiv:2501.06246](https://arxiv.org/abs/2501.06246) [find](https://scholar.google.com/scholar?q=Jia+Peng+Lim%2C+Davin+Choo%2C+and+Hady+W%2E+Lauw%2E+2025%2E+A+partition+cover+approach+to+tokenization%2E+Preprint%2C+arXiv%3A2501%2E06246%2E+%E2%80%94+%5BarXiv%3A2501%2E06246%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2501%2E06246%29)
15. Alisa Liu, Jonathan Hayase, Valentin Hofmann, Sewoong Oh, Noah A. Smith, and Yejin Choi. 2025. SuperBPE: Space travel for language models. Preprint, arXiv:2503.13423. — [arXiv:2503.13423](https://arxiv.org/abs/2503.13423) [find](https://scholar.google.com/scholar?q=Alisa+Liu%2C+Jonathan+Hayase%2C+Valentin+Hofmann%2C+Sewoong+Oh%2C+Noah+A%2E+Smith%2C+and+Yejin+Choi%2E+2025%2E+SuperBPE%3A+Space+travel+for+language+models%2E+Preprint%2C+arXiv%3A2503%2E13423%2E+%E2%80%94+%5BarXiv%3A2503%2E13423%5D%28https%3A%2F%2Farxi)
16. Markus Lohrey. 2012. Algorithmics on SLP-compressed strings: A survey. Groups - Complexity -Cryptology, 4(2):241–299. [find](https://scholar.google.com/scholar?q=Markus+Lohrey%2E+2012%2E+Algorithmics+on+SLP%2Dcompressed+strings%3A+A+survey%2E+Groups+%2D+Complexity+%2DCryptology%2C+4%282%29%3A241%E2%80%93299%2E)
17. Matteo Muffo, Aldo Cocco, and Enrico Bertino. 2022. [Evaluating transformer language models on arithmetic operations using number decomposition](https://md.research.elamur.ai/free/en/papers/muffo-2023-evaluating-transformer-language-models-arithmetic/). In Proceedings of the Thirteenth Language Resources and Evaluation Conference, pages 291–297, Marseille, France. European Language Resources Association.
18. Rodrigo Nogueira, Zhiying Jiang, and Jimmy Lin. 2021. Investigating the limitations of transformers with simple arithmetic tasks. Preprint, arXiv:2102.13019. [find](https://scholar.google.com/scholar?q=Rodrigo+Nogueira%2C+Zhiying+Jiang%2C+and+Jimmy+Lin%2E+2021%2E+Investigating+the+limitations+of+transformers+with+simple+arithmetic+tasks%2E+Preprint%2C+arXiv%3A2102%2E13019%2E)
19. OpenAI. 2023. [GPT-4 technical report](https://md.research.elamur.ai/free/en/papers/openai-2023-gpt-4-technical-report/). arXiv:2303.08774.
20. Preprint, Dominik Kempa and Nicola Prezza. 2018. At the roots of dictionary compression: string attractors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 827–840, New York, NY, USA. Association for Computing Machinery. [find](https://scholar.google.com/scholar?q=Preprint%2C+Dominik+Kempa+and+Nicola+Prezza%2E+2018%2E+At+the+roots+of+dictionary+compression%3A+string+attractors%2E+In+Proceedings+of+the+50th+Annual+ACM+SIGACT+Symposium+on+Theory+of+Computing%2C+STOC+2018%2C+pa)
21. Artidoro Pagnoni, Ram Pasunuru, Pedro Rodriguez, John Nguyen, Benjamin Muller, Margaret Li, Chunting Zhou, Lili Yu, Jason Weston, Luke Zettlemoyer, Gargi Ghosh, Mike Lewis, Ari Holtzman, and Srinivasan Iyer. 2024. Byte latent transformer: Patches scale better than tokens. Preprint, arXiv:2412.09871. [find](https://scholar.google.com/scholar?q=Artidoro+Pagnoni%2C+Ram+Pasunuru%2C+Pedro+Rodriguez%2C+John+Nguyen%2C+Benjamin+Muller%2C+Margaret+Li%2C+Chunting+Zhou%2C+Lili+Yu%2C+Jason+Weston%2C+Luke+Zettlemoyer%2C+Gargi+Ghosh%2C+Mike+Lewis%2C+Ari+Holtzman%2C+and+Srinivasa)
22. J.C. Kieffer and En-Hui Yang. 2000. Grammar-based codes: a new class of universal lossless source codes. IEEE Transactions on Information Theory, 46(3):737–754. [find](https://scholar.google.com/scholar?q=J%2EC%2E+Kieffer+and+En%2DHui+Yang%2E+2000%2E+Grammar%2Dbased+codes%3A+a+new+class+of+universal+lossless+source+codes%2E+IEEE+Transactions+on+Information+Theory%2C+46%283%29%3A737%E2%80%93754%2E)
23. Aleksandar Petrov, Emanuele La Malfa, Philip Torr, and Adel Bibi. 2023. [Language model tokenizers introduce unfairness between languages](https://md.research.elamur.ai/free/en/papers/petrov-2023-language-model-tokenizers-introduce-unfairness/). In Thirty-seventh Conference on Neural Information Processing Systems.
24. Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. 2023. Toward a definitive compressibility measure for repetitive sequences. IEEE Transactions on Information Theory, 69(4):2074–2092. [find](https://scholar.google.com/scholar?q=Tomasz+Kociumaka%2C+Gonzalo+Navarro%2C+and+Nicola+Prezza%2E+2023%2E+Toward+a+definitive+compressibility+measure+for+repetitive+sequences%2E+IEEE+Transactions+on+Information+Theory%2C+69%284%29%3A2074%E2%80%932092%2E)
25. László Kozma and Johannes Voderholzer. 2024. Theoretical analysis of byte-pair encoding. Preprint, arXiv:2411.08671. — [arXiv:2411.08671](https://arxiv.org/abs/2411.08671) [find](https://scholar.google.com/scholar?q=L%C3%A1szl%C3%B3+Kozma+and+Johannes+Voderholzer%2E+2024%2E+Theoretical+analysis+of+byte%2Dpair+encoding%2E+Preprint%2C+arXiv%3A2411%2E08671%2E+%E2%80%94+%5BarXiv%3A2411%2E08671%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2411%2E08671%29)
26. Taku Kudo. 2018. Subword regularization: Improving neural network translation models with multiple Buu Phan, Marton Havasi, Matthew Muckley, and Karen Ullrich. 2024. Understanding and mitigating tokenization bias in language models. Preprint, arXiv:2406.16829. — [arXiv:2406.16829](https://arxiv.org/abs/2406.16829) [find](https://scholar.google.com/scholar?q=Taku+Kudo%2E+2018%2E+Subword+regularization%3A+Improving+neural+network+translation+models+with+multiple+Buu+Phan%2C+Marton+Havasi%2C+Matthew+Muckley%2C+and+Karen+Ullrich%2E+2024%2E+Understanding+and+mitigating+token)
27. Tiago Pimentel and Clara Meister. 2024. [How to compute the probability of a word](https://md.research.elamur.ai/free/en/papers/pimentel-2024-how-compute-probability-word/). In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, Miami, Florida, USA. Association for Computational Linguistics.
28. Phillip Rust, Jonas Pfeiffer, Ivan Vulić, Sebastian Ruder, and Iryna Gurevych. 2021. [How good is your tokenizer?](https://md.research.elamur.ai/free/en/papers/touvron-2023-llama-2-open-foundation-fine/) On the monolingual performance of multilingual language models. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Join…
29. Anton Schäfer, Thomas Hofmann, Imanol Schlag, and Tiago Pimentel. 2024. On the effect of (near) duplicate subwords in language modelling. In Findings of the Association for Computational Linguistics: ACL 2024, pages 9580–9597, Bangkok, Thailand. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Anton+Sch%C3%A4fer%2C+Thomas+Hofmann%2C+Imanol+Schlag%2C+and+Tiago+Pimentel%2E+2024%2E+On+the+effect+of+%28near%29+duplicate+subwords+in+language+modelling%2E+In+Findings+of+the+Association+for+Computational+Linguistics%3A+)
30. Lili Yu, Daniel Simig, Colin Flaherty, Armen Aghajanyan, Luke Zettlemoyer, and Mike Lewis. 2023. MEGABYTE: Predicting million-byte sequences with multiscale transformers. In Thirty-seventh Conference on Neural Information Processing Systems. [find](https://scholar.google.com/scholar?q=Lili+Yu%2C+Daniel+Simig%2C+Colin+Flaherty%2C+Armen+Aghajanyan%2C+Luke+Zettlemoyer%2C+and+Mike+Lewis%2E+2023%2E+MEGABYTE%3A+Predicting+million%2Dbyte+sequences+with+multiscale+transformers%2E+In+Thirty%2Dseventh+Conference+)
31. Craig W. Schmidt, Varshini Reddy, Haoran Zhang, Alec Alameddine, Omri Uzan, Yuval Pinter, and Chris Tanner. 2024. [Tokenization is more than compression](https://md.research.elamur.ai/free/en/papers/schmidt-2024-tokenization-is-more-than-compression/). In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 678–702, Miami, Florida, USA. Association for Comp…
32. Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Mrinmaya Sachan, and Ryan Cotterell. 2023a. Tokenization and the noiseless channel. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5184–5207, Toronto, Canada. Association for… [find](https://scholar.google.com/scholar?q=Vil%C3%A9m+Zouhar%2C+Clara+Meister%2C+Juan+Gastaldi%2C+Li+Du%2C+Mrinmaya+Sachan%2C+and+Ryan+Cotterell%2E+2023a%2E+Tokenization+and+the+noiseless+channel%2E+In+Proceedings+of+the+61st+Annual+Meeting+of+the+Association+for+)
33. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. [Neural machine translation of rare words with subword units](https://md.research.elamur.ai/free/en/papers/sennrich-2016-neural-machine-translation-rare-words/). In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1715–1725, Berlin, Germany. Association for Computational Lin…
34. Vilém Zouhar, Clara Meister, Juan Gastaldi, Li Du, Tim Vieira, Mrinmaya Sachan, and Ryan Cotterell. 2023b. A formal perspective on byte-pair encoding. In Findings of the Association for Computational Linguistics: ACL 2023, pages 598–614, Toronto, Canada. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Vil%C3%A9m+Zouhar%2C+Clara+Meister%2C+Juan+Gastaldi%2C+Li+Du%2C+Tim+Vieira%2C+Mrinmaya+Sachan%2C+and+Ryan+Cotterell%2E+2023b%2E+A+formal+perspective+on+byte%2Dpair+encoding%2E+In+Findings+of+the+Association+for+Computational+)
35. Aaditya K. Singh and DJ Strouse. 2024. [Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs](https://md.research.elamur.ai/free/en/papers/singh-2024-tokenization-counts-impact-tokenization-arithmetic/). Preprint, arXiv:2402.14903.
36. Chaofan Tao, Qian Liu, Longxu Dou, Niklas Muennighoff, Zhongwei Wan, Ping Luo, Min Lin, and Ngai Wong. 2024. [Scaling laws with vocabulary: Larger models deserve larger vocabularies](https://md.research.elamur.ai/free/en/papers/tao-2024-scaling-laws-vocabulary-larger-models/). In The Thirty-eighth Annual Conference on Neural Information Processing Systems.
37. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023a. [LLaMA: Open and efficient foundation language models](https://md.research.elamur.ai/free/en/papers/touvron-2023-llama-open-efficient-foundation-language/). Preprin…
38. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller,… [find](https://scholar.google.com/scholar?q=Hugo+Touvron%2C+Louis+Martin%2C+Kevin+Stone%2C+Peter+Albert%2C+Amjad+Almahairi%2C+Yasmine+Babaei%2C+Nikolay+Bashlykov%2C+Soumya+Batra%2C+Prajjwal+Bhargava%2C+Shruti+Bhosale%2C+Dan+Bikel%2C+Lukas+Blecher%2C+Cristian+Canton+Fe)

*Updated 31 October 2026*