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

Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

ndingwall.github.io

Post reply on HN
Print view View original

31–40 of 40 posts

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#31

Post by cschmidt »

anonymoushn wrote: post #27
yuvalpinter wrote: post #26

Earlier quoted context omitted.

A few years ago we released SaGe, which is a contextual tokenizer, meaning that it builds a vocab that's fit for an LM use case because tokens are selected to appear within as clear a context set as possible in a corpus. https://github.com/MeLeLBGU/SaGe It does better than both BPE and UnigramLM in several benchmarks. https://aclanthology.org/2024.acl-short.73/

Cool, I can have a look. By the way, I've filed a PR against the pathpiece repository correcting an error in the docs. I have read this paper before, and now that I have looked more closely I am a bit disappointed that the precise method of construction of the large initial vocabularies used for vocabulary learners that begin with large initial vocabularies in the experiment is not specified. I also notice that the s…

Co-author of the PathPiece paper here.

With regard to weighting the n-grams by length*frequency, I'm not sure it is clear that that would be better. The SentencePiece unigram model does it that way (as I mentioned in another comment), and hence, unigram produces longer tokens on average. It is generally considered that this is a bit of an issue with unigram. Not that there is particular evidence either way, as with many things in tokenization.

Why do you think 2^18 initial n-grams is too few? That's 5.3 times more than the largest vocab we train.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#32

Post by cschmidt »

anonymoushn wrote: post #27
yuvalpinter wrote: post #26

Earlier quoted context omitted.

A few years ago we released SaGe, which is a contextual tokenizer, meaning that it builds a vocab that's fit for an LM use case because tokens are selected to appear within as clear a context set as possible in a corpus. https://github.com/MeLeLBGU/SaGe It does better than both BPE and UnigramLM in several benchmarks. https://aclanthology.org/2024.acl-short.73/

Cool, I can have a look. By the way, I've filed a PR against the pathpiece repository correcting an error in the docs. I have read this paper before, and now that I have looked more closely I am a bit disappointed that the precise method of construction of the large initial vocabularies used for vocabulary learners that begin with large initial vocabularies in the experiment is not specified. I also notice that the s…

Regarding $O(n L^2)$ vs $O(n L)$, that was because we somewhat sloppily tend to use the term 'tokenization' for both training a tokenizer vocab, and for tokenizing a given document. In the paper, we tried to always call the latter one segmentation or inference. The former is $O(n L^2)$ per iteration, while the latter $O(n L)$. I'll update the README to be more explicit about this.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#33

Post by anonymoushn »

cschmidt wrote: post #32
anonymoushn wrote: post #27

Earlier quoted context omitted.

Cool, I can have a look. By the way, I've filed a PR against the pathpiece repository correcting an error in the docs. I have read this paper before, and now that I have looked more closely I am a bit disappointed that the precise method of construction of the large initial vocabularies used for vocabulary learners that begin with large initial vocabularies in the experiment is not specified. I also notice that the s…

Regarding $O(n L^2)$ vs $O(n L)$, that was because we somewhat sloppily tend to use the term 'tokenization' for both training a tokenizer vocab, and for tokenizing a given document. In the paper, we tried to always call the latter one segmentation or inference. The former is $O(n L^2)$ per iteration, while the latter $O(n L)$. I'll update the README to be more explicit about this.

No, the segmentation algorithm you have implemented has runtime O(N*L^2). In particular, if you want to do a hash table lookup using a string key, that takes time proportional to the length of the string, not constant time.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#34

Post by anonymoushn »

cschmidt wrote: post #31
anonymoushn wrote: post #27

Earlier quoted context omitted.

Cool, I can have a look. By the way, I've filed a PR against the pathpiece repository correcting an error in the docs. I have read this paper before, and now that I have looked more closely I am a bit disappointed that the precise method of construction of the large initial vocabularies used for vocabulary learners that begin with large initial vocabularies in the experiment is not specified. I also notice that the s…

Co-author of the PathPiece paper here. With regard to weighting the n-grams by length*frequency, I'm not sure it is clear that that would be better. The SentencePiece unigram model does it that way (as I mentioned in another comment), and hence, unigram produces longer tokens on average. It is generally considered that this is a bit of an issue with unigram. Not that there is particular evidence either way, as with m…

I think that the ideal number of initial n-grams would be large enough that adding additional initial n-grams has no effect on the output, because I expect to not be very good at tuning two different knobs.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#35

Post by woodson »

yuvalpinter wrote: post #25
YossarianFrPrez wrote: post #20

Earlier quoted context omitted.

This is a cool paper! Basically, prior to feeding text to the tokenizer people have split the text on whitespaces. But whitespaces aren't exactly meaningful separators. By getting rid of this restriction as the tokenizer is 'learning', some of the tokens end up being 'by the way' or 'in the the long run.' The researchers find that this makes the model much more efficient.

This can also be done within the tokenization framework, see our work here: https://arxiv.org/abs/2504.00178

How does this differ from SuperBPE, which seems to pursue a similar goal? https://arxiv.org/abs/2503.13423

Looks like parallel invention. (I’m not associated with the paper or its authors.)

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#36

Post by anonymoushn »

woodson wrote: post #35
yuvalpinter wrote: post #25

Earlier quoted context omitted.

This can also be done within the tokenization framework, see our work here: https://arxiv.org/abs/2504.00178

How does this differ from SuperBPE, which seems to pursue a similar goal? https://arxiv.org/abs/2503.13423 Looks like parallel invention. (I’m not associated with the paper or its authors.)

In SuperBPE, a fixed number of tokens are learned, and then the constraints of pretokenization are removed entirely, and then the remainder of the target vocab size is learned.

In Boundless BPE, no schedule must be chosen, because there is not any point at which the constraints of pretokenization are removed entirely. Instead, at any point in the learning process, merges between adjacent pretokens are permitted if the pretokens are each represented by a single token. There are some additional details about how the authors incorporate Picky BPE, which I will not try to repeat because I would probably get them wrong.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#37

Post by mcyc »

cschmidt wrote: post #29
anonymoushn wrote: post #2

How does SentencePiece choose the initial vocabulary, which is trimmed down to determine the final vocabulary which has these desirable properties?

It appears to be the top n-grams scored by the product of frequency and length. Including the frequency weighting is a bit nonstandard among ablative methods. See line 233: https://github.com/google/sentencepiece/blob/master/src/unig... I would suspect the n-gram counts don't cross pre-token boundaries, but I don't have time to find that in the code right now.

You can cross whitespace boundaries by setting flag `--split-on-whitespace` to false (it's true by default).

https://github.com/google/sentencepiece/blob/master/doc/opti...

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#38

Post by cschmidt »

woodson wrote: post #35
yuvalpinter wrote: post #25

Earlier quoted context omitted.

This can also be done within the tokenization framework, see our work here: https://arxiv.org/abs/2504.00178

How does this differ from SuperBPE, which seems to pursue a similar goal? https://arxiv.org/abs/2503.13423 Looks like parallel invention. (I’m not associated with the paper or its authors.)

Yes, they were concurrent work. (Co-author of BoundlessBPE here). A sibling comment describes the main differences. Our paper motivates why superwords can lead to such a big improvement, by overcoming a limit that pre-tokenization imposes on current tokenization methods. The SuperBPE paper has a wonderful set of downstream evaluation runs. So if you're interested in either, they are quite complimentary papers.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#39

Post by cschmidt »

anonymoushn wrote: post #33
cschmidt wrote: post #32

Earlier quoted context omitted.

Regarding $O(n L^2)$ vs $O(n L)$, that was because we somewhat sloppily tend to use the term 'tokenization' for both training a tokenizer vocab, and for tokenizing a given document. In the paper, we tried to always call the latter one segmentation or inference. The former is $O(n L^2)$ per iteration, while the latter $O(n L)$. I'll update the README to be more explicit about this.

No, the segmentation algorithm you have implemented has runtime O(N*L^2). In particular, if you want to do a hash table lookup using a string key, that takes time proportional to the length of the string, not constant time.

That's in interesting point. While your correct, of course, it is so common to consider a hash table lookup a O(1) operation, it never occurred to me. But in this case, the loops are actually really tight and the hash table lookup might be a significant part of the time, so it might well behave more like O(n L^2). I'll update the docs and paper.

Re: Tokenization for language modeling: BPE vs. Unigram Language Modeling (2020)

#40

Post by cschmidt »

cschmidt wrote: post #29
anonymoushn wrote: post #2

How does SentencePiece choose the initial vocabulary, which is trimmed down to determine the final vocabulary which has these desirable properties?

It appears to be the top n-grams scored by the product of frequency and length. Including the frequency weighting is a bit nonstandard among ablative methods. See line 233: https://github.com/google/sentencepiece/blob/master/src/unig... I would suspect the n-gram counts don't cross pre-token boundaries, but I don't have time to find that in the code right now.

Anyone reading this in the future, I meant to say the length weighting is a bit nonstandard. It is usually by frequency. Oops
Post reply on HN