cschmidt

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.

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.

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.

Somehow I didn't get any notifications of your PR. Sorry about that. I'll take a look.

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.

Are you planning to publish your results when you're done?

That probably would have worked. I just discovered there was a bug, and it popped up a thing about 4, so I didn't actually try the old version.

Claude 3.8 wrote me some code this morning, and I was running into a bug. I switched to 4 and gave it its own code. It pointed out the bug right away and fixed it. So an upgrade for me :-)

This paper was accepted as a poster to NeurIPS 2024, so it isn't just a pre-print. There is a presentation video and slides here:

https://neurips.cc/virtual/2024/poster/94849

The underlying data has been open sourced as discussed on his blog here https://timothynguyen.org/2024/11/07/open-sourced-my-work-on...

Here's a paper reviewing the various choices, that is often mentioned in discussions around data structures for text editors:

https://www.cs.unm.edu/~crowley/papers/sds.pdf

It seems like Helix is using it https://github.com/helix-editor/helix/blob/master/docs/archi...

I also had a science fiction book from my childhood that I kept trying to find. Eventually I did find the title and author through a chat with ChatGPT, unlike in this case. (It was Midworld by Alan Dean Foster, if anyone is curious. I'm not sure why that particular book stuck in my head.)

Actually, you can solve the assignment problem as a linear program (LP). Just do

    min sum_i sum_j c_{ij}*x_{ij}

    s.t. sum_i x_{ij} == 1, for all j
         sum_j x_{ij} == 1, for all i

and you automagically get an integer solution in the x_{ij} due to the structure of the constraints.

CVXPY would be a good way to implement this these days.

I'm curious if you're aware of some papers from around 2005 on using contextual entropy to do unsupervised word segmentation on Chinese, and other languages that don't use spaces for word boundaries.

https://aclanthology.org/Y03-1017/ https://aclanthology.org/I05-1009/ https://aclanthology.org/P06-2056/

Exactly the same approach of segmenting a word when the entropy goes up compared to the previous byte.

This exact line of reasoning is the cover story on the Economist this week:

Briefing: https://www.economist.com/briefing/2024/10/24/glp-1s-like-oz...

Leader (opinion piece): https://www.economist.com/leaders/2024/10/24/its-not-just-ob...

(sorry, paywalled)

Cool, that’s just what I was wondering.

Branch and bound is all about changing the bounds on a given fractional variable and resolving. It wasn't clear whether you could re-start from the previous solution with the new bound and quickly reoptimize.

The "Model Building in Mathematical Programming" book by Williams is unique in that it talks about how to formulate LP and MILP problems, rather than focusing on the algorithm side of how the simplex algorithm works. That's nice to know, but not really necessary. You really need to get some intuition on thinking about objectives and constraints.

https://www.wiley.com/en-us/Model+Building+in+Mathematical+P...

I wonder if this technique works well in branch and bound for Mixed Integer Linear Programming applications. They seem to be just applying it to plain LP applications. While there certainly are some use cases for large LPs, it seems like MILP is where the action is.

Personally, I've used FDR, but FWER is meant to be good as well. I guess I don't have a preference.

If you work for a large website (as I used to), they probably run hundreds of tests a week across various groups. So false positives are a real problem, and often you don't see the gain suggested by the A/B when rolling it out.

I agree that Bonferroni is often too pessimistic. If you Bonferroni correct you'll usually find nothing is significant. And I take your point that you could adjust the $\alpha$. But then of course, you can make things significant or not as you like by the choice.

False Discover Rate is less conservative, and I have used it successfully in the past.

People have strong incentives to find significant results that can be rolled out, so you don't want that person choosing $\alpha$. They will also be peaking at the results every day of a weekly test, and wanting to roll it out if it bumps into significance. I just mention this because the most useful A/B libraries are ones that are resistant to human nature. PM's will talk about things being "almost significant" at 0.2 everywhere I've worked.

It would probably be good to have something considering multiple comparisons (False Discovery Rate, Bonferroni correction), which is often the bane of running a whole series of A/B tests. And, as another poster has mentioned, an anytime approach that is resistant to early stopping due to peaking [1].

For those who haven't read about Fisher's tea experiment: There was a woman who claimed she could tell if the milk was put into the cup before or after pouring the tea. Fished didn't think so, and developed the experimental technique to test this idea. Indeed she could, getting them all right iirc.

[1] see https://media.trustradius.com/product-downloadables/UP/GB/AD... for a discussion of the problems with a t-test. There is also a more detailed whitepaper from Optimizely somewhere

Cory Doctorow has a good blog post explaining why Amazon is so bad. Amazon is now an ad business

https://doctorow.medium.com/how-monopoly-enshittified-amazon...

The "worked example effect" they talk about it interesting. The idea that you learn best from worked examples lines up with my experience. However, it seems like higher math abandons this completely. So many math textbooks are just in "theorem, proof" form, with almost no examples or even motivation.

Another article on the same topic:

https://cosmosmagazine.com/history/archaeology/indigenous-au...

I liked this part. They got Knuth to review it, and found mistakes. That's kind of cool, in its own way.

    We are deeply grateful to Donald E. Knuth for his thorough review, 
    which not only enhanced the quality of this paper (including fixing
    several errors) but has also inspired us for higher standards.

The NYTimes had an good interactive story on this same topic this week:

https://www.nytimes.com/interactive/2024/03/09/upshot/affirm...

I've been downloading and reading various chapters of this book for what seems like years now. I'd love a hard copy. I know it says "When will the whole book be finished? Don't ask." But it seems like when the missing Chapter 12 is added ("We also expect to release Chapter 12 soon in an updated release.") it would be a great time to print it. I can hope....

I love the R3 SA profile, where all the keys have the same profile as the third row of regular SA. Not as sculpted as regular SA, which I find too much.

There is also an excellent book about Erdos for adults:

The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth

https://www.amazon.com/Man-Who-Loved-Only-Numbers/dp/0786884...