ACL 2025long0 citations
Tokenisation is NP-Complete
Philip Whittington, Gregor Bachmann, Tiago Pimentel
Abstract
In this work, we prove the NP-completeness of two variants of tokenisation, defined here as the problem of compressing a dataset to at most 𝛿 symbols by either finding a vocabulary directly (_direct_ tokenisation), or selecting a sequence of merge operations (_bottom-up_ tokenisation).
BibTeX
@inproceedings{whittington-etal-2025-tokenisation,
title = "Tokenisation is {NP}-Complete",
author = "Whittington, Philip and
Bachmann, Gregor and
Pimentel, Tiago",
editor = "Che, Wanxiang and
Nabende, Joyce and
Shutova, Ekaterina and
Pilehvar, Mohammad Taher",
booktitle = "Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)",
month = jul,
year = "2025",
address = "Vienna, Austria",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2025.acl-long.1365/",
doi = "10.18653/v1/2025.acl-long.1365",
pages = "28133--28153",
ISBN = "979-8-89176-251-0"
}