External-memory approach for BPE training where merges depend on text adjacency (160 GB corpus)

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:

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.

The challenge: Supermerges turn BPE from a frequency-counting problem into a sequence-rewriting problem, forcing you to invent an external-memory data structure that supports both random localized updates and global top-pair queries over 160 GB.

All newsletters