← Publications

Tokenisation is NP-Complete

Philip Whittington, Gregor Bachmann, Tiago Pimentel
Annual Meeting of the Association for Computational Linguistics (ACL) · 2025 SAC highlights award

Read the paper

Find paper here

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).

@inproceedings{whittington-etal-2025-tokenisation,
    author = {
        Philip Whittington and
        Gregor Bachmann and
        Tiago Pimentel
    },
    booktitle = {Annual Meeting of the Association for Computational Linguistics (ACL)},
    title = {Tokenisation is NP-Complete},
    year = {2025},
    doi = {10.18653/v1/2025.acl-long.1365},
    url = {https://aclanthology.org/2025.acl-long.1365/},
    pages = {28133--28153},
}