Tokenisation is NP-Complete

Philip Whittington; Gregor Bachmann; Tiago Pimentel

doi:10.18653/v1/2025.acl-long.1365

Tokenisation is NP-Complete

Philip Whittington, Gregor Bachmann, Tiago Pimentel

Correct Metadata for

Important: The Anthology treat PDFs as authoritative. Please use this form only to correct data that is out of line with the PDF. See our corrections guidelines if you need to change the PDF.

Title Adjust the title. Retain tags such as <fixed-case>.

Authors Adjust author names and order to match the PDF.

Abstract Correct abstract if needed. Retain XML formatting tags such as <tex-math>.

Verification against PDF Ensure that the new title/authors match the snapshot below. (If there is no snapshot or it is too small, consult the PDF.)

Authors concatenated from the text boxes above:

ALL author names match the snapshot above—including middle initials, hyphens, and accents.

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

Anthology ID:: 2025.acl-long.1365
Volume:: Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Month:: July
Year:: 2025
Address:: Vienna, Austria
Editors:: Wanxiang Che, Joyce Nabende, Ekaterina Shutova, Mohammad Taher Pilehvar
Venue:: ACL
SIG:
Publisher:: Association for Computational Linguistics
Note:
Pages:: 28133–28153
Language:
URL:: https://aclanthology.org/2025.acl-long.1365/
DOI:: 10.18653/v1/2025.acl-long.1365
Bibkey:
Cite (ACL):: Philip Whittington, Gregor Bachmann, and Tiago Pimentel. 2025. Tokenisation is NP-Complete. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28133–28153, Vienna, Austria. Association for Computational Linguistics.
Cite (Informal):: Tokenisation is NP-Complete (Whittington et al., ACL 2025)
Copy Citation:
PDF:: https://aclanthology.org/2025.acl-long.1365.pdf

PDF Cite Search Fix data

Export citation

BibTeX
MODS XML
Endnote
Preformatted

@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",
    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 $\delta$ symbols by either finding a vocabulary directly ({\_}direct{\_} tokenisation), or selecting a sequence of merge operations ({\_}bottom-up{\_} tokenisation)."
}

Download as File

<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="whittington-etal-2025-tokenisation">
    <titleInfo>
        <title>Tokenisation is NP-Complete</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Philip</namePart>
        <namePart type="family">Whittington</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Gregor</namePart>
        <namePart type="family">Bachmann</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Tiago</namePart>
        <namePart type="family">Pimentel</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2025-07</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Wanxiang</namePart>
            <namePart type="family">Che</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Joyce</namePart>
            <namePart type="family">Nabende</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Ekaterina</namePart>
            <namePart type="family">Shutova</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Mohammad</namePart>
            <namePart type="given">Taher</namePart>
            <namePart type="family">Pilehvar</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Vienna, Austria</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
        <identifier type="isbn">979-8-89176-251-0</identifier>
    </relatedItem>
    <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).</abstract>
    <identifier type="citekey">whittington-etal-2025-tokenisation</identifier>
    <identifier type="doi">10.18653/v1/2025.acl-long.1365</identifier>
    <location>
        <url>https://aclanthology.org/2025.acl-long.1365/</url>
    </location>
    <part>
        <date>2025-07</date>
        <extent unit="page">
            <start>28133</start>
            <end>28153</end>
        </extent>
    </part>
</mods>
</modsCollection>

Download as File

%0 Conference Proceedings
%T Tokenisation is NP-Complete
%A Whittington, Philip
%A Bachmann, Gregor
%A Pimentel, Tiago
%Y Che, Wanxiang
%Y Nabende, Joyce
%Y Shutova, Ekaterina
%Y Pilehvar, Mohammad Taher
%S Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
%D 2025
%8 July
%I Association for Computational Linguistics
%C Vienna, Austria
%@ 979-8-89176-251-0
%F whittington-etal-2025-tokenisation
%X 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).
%R 10.18653/v1/2025.acl-long.1365
%U https://aclanthology.org/2025.acl-long.1365/
%U https://doi.org/10.18653/v1/2025.acl-long.1365
%P 28133-28153

Download as File

Markdown (Informal)

[Tokenisation is NP-Complete](https://aclanthology.org/2025.acl-long.1365/) (Whittington et al., ACL 2025)

Tokenisation is NP-Complete (Whittington et al., ACL 2025)

ACL

Philip Whittington, Gregor Bachmann, and Tiago Pimentel. 2025. Tokenisation is NP-Complete. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 28133–28153, Vienna, Austria. Association for Computational Linguistics.