Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tokenisation Is NP-Complete

arxiv.org

Post reply on HN
Print view View original

21–26 of 26 posts

Re: Tokenisation Is NP-Complete

#21

Post by mcyc »

bnjmn wrote: post #19
mcyc wrote: post #14

Earlier quoted context omitted.

NB: Can't edit my original reply. Sorry actually I misread part of your comment in relation to the paper and confused δ and another parameter, K. To clarify, δ is the number of tokens in the tokenized corpus and K is the size of the vocabulary. So, if you are asking about why would they limit _K_, then my answer still applies (after swapping δ for K). But if you still mean "why do they pick some arbitrary δ as the li…

Thanks for these detailed replies! Now I really want to read your paper.

Thanks!

Our paper [1] is kind of a goofy adversarial thing where we thought "here's this cool metric, how can we break it?". The tokenizers we propose are definitely not tokenizers you should use in practice.

The original paper that proposes the metric is, imo, much more interesting theoretically [2].

[1]: https://aclanthology.org/2024.lrec-main.1469/

[2]: https://aclanthology.org/2023.acl-long.284/

Re: Tokenisation Is NP-Complete

#22

Post by [deleted] »

sureglymop wrote: post #17
bnjmn wrote: post #8

> We still do not know, for instance, what makes a good tokeniser (Gowda and May, 2020; Cognetta et al., 2024): which characteristics should its produced subwords `s` have to be a good starting point for language modelling? If we knew this, then we could define an objective function which we could evaluate tokenisers with. I don't see how the authors get past this true general statement from the first paragraph of th…

Can anyone explain to a layman like myself why it wouldn't be better if we just used bytes as tokens?

[deleted]

Re: Tokenisation Is NP-Complete

#23

Post by immibis »

bnjmn wrote: post #18
immibis wrote: post #15

Earlier quoted context omitted.

NP is a category of decision problems - problems with boolean answers. Saying that it's NP-complete to find the tokeniser that produces the fewest symbols is meaningless. You have to convert it to the form "is there a tokenizer that produces fewer than N symbols?" before it even makes sense to ask whether it's NP-complete.

I fully agree with your final statement, but needing to constrain the problem in an artificial way to prove it's NP-complete doesn't mean the constraint was justified or realistic, because then you've only proved the constrained version of the decision problem is NP-hard. There might be plenty of perfectly "good" tokenizers (whatever that ends up meaning) that can be found or generated without formulating their desig…

If it's NP-hard to even know whether the answer is bigger or smaller than a certain number, then it's obvious that in a non-formal way, finding the exact answer is at least as hard as NP-hard, whatever that means.

Re: Tokenisation Is NP-Complete

#24

Post by akoboldfrying »

terrabiped wrote: post #6
HeliumHydride wrote: post #3

Earlier quoted context omitted.

Longest common substring is linear time.

You may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence .

The post you responded to is merely giving evidence that the GP's overall claim "Any of these text problems where you're tying to optimize over a whole corpus is kind of not hard to see to be NP-complete" is sometimes not true in surprising ways -- Knuth conjectured that there was no linear time algorithm for longest common substring (but then suffix trees came along).

Re: Tokenisation Is NP-Complete

#25

Post by sureglymop »

mcyc wrote: post #20
sureglymop wrote: post #17

Earlier quoted context omitted.

Can anyone explain to a layman like myself why it wouldn't be better if we just used bytes as tokens?

It's two problems: 1) the sequence length increases too much. Idk what the average token length is for Llama, but imagine it's like 5+ bytes. Using individual bytes as tokens immediately makes the context 5x longer which is super bad for inference speed and memory requirements (since attention inference is quadratic in the length of the sequence). 2) individual bytes have essentially no meaning, so byte embeddings ar…

Thank you very much for the thorough reply! I highly appreciate it.

Re: Tokenisation Is NP-Complete

#26

Post by conartist6 »

cantpostcanceld wrote: post #13
bnjmn wrote: post #8

> We still do not know, for instance, what makes a good tokeniser (Gowda and May, 2020; Cognetta et al., 2024): which characteristics should its produced subwords `s` have to be a good starting point for language modelling? If we knew this, then we could define an objective function which we could evaluate tokenisers with. I don't see how the authors get past this true general statement from the first paragraph of th…

I don't know if this is related but I work on a project with a language parser and so a tokenizer and one issue we have is the parser/tokenier was not designed to work on incomplete code so it's not useful for auto complete. That property of how good the design is for helping write and debug (useful error messages) seems like yet another metric that could be used I also don't know if tokenizers can be divorced from p…

CSTML and BABLR are designed to close this gap completely for people in your position.

We invented a new kind of zero just so that you could write arbitrary parsers and deal with things that are missing

Post reply on HN