discussion: exploring possible collaboration between gigatoken and ffbpe

[clouds56]

Hello @marcelroed, impressive work.

I've also been working on tokenizer optimizations, focusing on speed, especially for CJK scenarios. My work is here https://github.com/tokn-ai/ffbpe (nobody knows it right now). If you're interested, I'd really like to explore a possible collaboration to see if we can combine the strengths of both.

From what I understand, your work mainly optimizes the pretokenizer level (without changing the final pretokenizer output), while mine changes the pretokenizer output itself and also improves the merge process.

1. The largest tricks improving CJK pretokenizer is add a "bigram" pass. Specifically, I build a bigram lookup table directly from the target vocab. Then, during the pre-tokenization stage, I further split tokens based on this table, i.e. any adjacent character pairs not present in the bigram table are forcibly split apart. This significantly speeds up the subsequent merge process by increasing cache hit rate.
2. Another natural trick: I treat encoding (inference) as if it were training, just skipping the frequency‑based sorting step for pre‑merge during encoding. This gives a noticeable speed boost when encoding large corpora, though it comes with a slight performance degradation on pure English text.

I found your approach to NEON and SWAR especially interesting. As I continue developing my project, I am considering building on some of the concepts introduced in your work. I will, of course, clearly acknowledge your contribution and use the citation provided in your README where appropriate.

here's benchmark from my macOS,

Corpus	FFBPE	Gigatoken	Speedup
English	55.4 MB/s	1,342 MB/s	24.2×
Chinese	37.5 MB/s	42.7 MB/s	1.14×

[marcelroed]

Thanks for submitting a high quality issue! I've thought about opening an issue to push for CJK speeds, and I've been thinking a bit about how to optimize this case.

Can you elaborate a bit more on your bigram pass? I'm not quite sure I understand the proposal. The current problem is indeed that pretokenization still leaves very long byte sequences that don't cache well. BPE merging doesn't really show up in profiling when running on English code even with a lot of unicode, but it might be worth optimizing the merge process for these cases as well.

I would definitely be very interested in collaborating on this if you have good ideas! I'll have a look at your code when I have some more time to think about this problem.

This issue is high priority to me, but to be clear up front, I would prefer to deliberate a bit to ensure the implementation is likely to be close to optimal and amenable to optimization before starting implementation. It might take a while doing preliminary experiments to find ways to ensure this while being careful that proposed techniques don't collide with existing English performance. I'll get started with adding some CJK-specific profiling to make it easier to determine where things are going wrong.

[clouds56]

In a single word, "splitting pretokens at impossible merge boundaries using the vocabulary"

The encoder scans each pretoken’s adjacent bytes or Unicode scalars. If an adjacent pair never appears anywhere inside any vocabulary token, no valid BPE merge can ever cross that boundary. The pretoken can therefore be divided there and each segment encoded independently.

So we could cut long sequence to improve cache hit rate.

Vocabulary-bigram splitting	Median encode	Throughput
Disabled	337.2 ms	15.0 MiB/s
Enabled	185.9 ms	27.2 MiB/s

limitation:

The likely reason is that GPT‑2’s vocabulary fits Chinese poorly, producing long UTF‑8 byte sequences with many boundaries that can never be crossed by a merge. The optimization identifies those boundaries and divides the expensive BPE work into much smaller pieces.

There're some more complex improvement in my repo, but this one is the most cheap and worthy.