Tokenisation is NP-Complete
2024/12/19 by Philip Whittington, Gregor Bachmann, Whittington, Philip +3 · 8 voices · 5 citations
#cs.DS #cs.CL #cs.FL
paper · pdf · doi:10.48550/arxiv.2412.15210
Abstract
In this work, we prove the NP-completeness of two variants of tokenisation, defined 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).
Cited by
Discussions
- BPE is a greedy method to find a tokeniser which maximises compression! Why don't we try to find properly optimal tokenisers instead? Well, it seems this is a pretty difficult—in fact, NP-complete—pro [bsky, 45 points, 1 comments]
- Tokenisation Is NP-Complete https://arxiv.org/abs/2412.15210 (https://news.ycombinator.com/item?id=42488853) [bsky, 0 points, 0 comments]
- Hmmm... 🤔 Tokenisation is NP-Complete [PDF] arxiv.org/pdf/2412.15210 #compsci #paper [bsky, 0 points, 0 comments]
- Tokenisation Is NP-Complete [bsky, 0 points, 0 comments]
- Tokenisation Is NP-Complete https://arxiv.org/abs/2412.15210 (https://news.ycombinator.com/item?id=42488853) [bsky, 0 points, 0 comments]
- Tokenisation Is NP-Complete https://arxiv.org/abs/2412.15210 [comments] [57 points] [bsky, 0 points, 0 comments]
- Tokenisation Is NP-Complete (arxiv.org) Main Link | Discussion [bsky, 0 points, 0 comments]
- Tokenisation Is NP-Complete https://arxiv.org/abs/2412.15210 https://news.ycombinator.com/item?id=42488853 [bsky, 0 points, 0 comments]
Related