2026-06-28
Stack Overflow: View Question
Tags: rust, data-structures, nlp, stringtokenizer, memory-access
Score: 0 | Views: 58
The asker is training a BPE tokenizer with "supermerges" (arXiv 2504.00178) on a 160 GB corpus. Standard BPE only needs a word-frequency dictionary because merges happen within tokens — order between words is irrelevant. Supermerges break that assumption: they merge adjacent words in the running text, so training must see the corpus as a sequence, not a multiset. That defeats every shortcut that makes classical BPE training tractable.
Why it's hard: Each merge iteration rewrites the sequence (every chosen pair collapses to a new symbol), shifts adjacency boundaries, and changes the counts of neighboring pairs. With 160 GB of tokens you cannot keep the sequence in RAM, and you cannot reduce it to a frequency table because the adjacency graph itself is the input. Naively re-scanning the whole corpus per merge means thousands of full passes over disk — the linear regression the asker fit almost certainly extrapolates to weeks or months.
A workable direction — incremental external-memory BPE:
HashMap<(u32,u32), u64>, or better, a count-min sketch followed by an exact recount for the top-K candidates. This fits in RAM even when the corpus doesn't.Gotchas: tombstones balloon over many iterations — periodically compact each chunk. The inverted-index files for very common pairs (early iterations) will be enormous; a hybrid of "scan if pair frequency > threshold, index otherwise" avoids paying index-maintenance cost for pairs you'd read sequentially anyway. Watch for the classic BPE bug where overlapping occurrences of the same pair (e.g. AAA with pair (A,A)) get double-merged — use a left-to-right greedy sweep within each occurrence list. Finally, the delta updates must be applied atomically per position, since a single merge changes counts for both neighbors; doing them out of order corrupts the table.
