Byte-pair encoding
AlgoLab runs no language model. Every merge here is counted from eight sentences written for this page, which you can read in full in the Corpus tab. A real tokeniser learns its merges from billions of words.
Byte-pair encoding turns text into a vocabulary it was not given. It starts with every sentence split into single characters, counts every pair of neighbouring tokens, replaces every occurrence of the most frequent pair with one new token, and writes that substitution down as a rule. Repeat, and the tokens grow from characters into the chunks that actually recur in the text. The list of rules, in the order they were learned, is the tokeniser.
When it is the right choice
It is the standard way a language model gets its vocabulary, and that is the honest reason to understand it: every prompt anyone writes is turned into tokens by a table built exactly like this one, which is why models count letters badly and why an unusual word costs more than a common one. Outside that, it is a real general-purpose compressor for text with repeated substructure, and it is the wrong choice when the units are already known — a fixed dictionary is faster and more predictable than a learned one, and a learned vocabulary carries whatever biases its corpus had.
How it works
- Split every sentence into single characters. Those characters are the starting vocabulary.
- Count how often each pair of neighbouring tokens occurs across the whole corpus. A pair never spans two sentences, since nothing is adjacent across a break.
- Take the pair with the highest count. Where two pairs tie, this tool keeps whichever was seen first in a left-to-right, sentence-by-sentence scan, so a shared link reproduces the same run exactly.
- Replace every occurrence of that pair with one new token, and add the substitution to the rule table. The new token can itself be merged later, which is how tokens grow past two characters.
- Repeat for as many merges as you want. Stopping early gives a smaller vocabulary and longer sequences; going further gives a larger vocabulary and shorter ones, and that trade is the only thing the merge count controls.
Worth noticing
- Frequency is not meaning. On this corpus, merge 15 joins "the·" to "t" and merge 17 makes "is·th" — neither is a word. Byte-pair encoding merges what is common, and the fact that the results are often word-shaped is a consequence rather than a goal. This is the whole reason a model splits words in places that look arbitrary.
- Every merge is a concatenation, so the whole thing is invertible: joining the tokens back up returns the original text byte for byte, at every step and not only at the end. A test in this repository asserts exactly that, and asserts that the learned rules re-applied from scratch reproduce the same tokenisation.
- The space is an ordinary symbol here, and gets merged like any other, which is why tokens such as "other·" exist. That is what byte-level encoders do, and it is why a real tokeniser usually treats " the" and "the" as two different tokens. The classic word-level formulation instead splits on whitespace first and marks the end of each word, so merges never cross a word boundary; this tool shows the byte-level variant because it needs no extra symbol on screen.
- Later rules depend on earlier ones. Rule 13 here merges "oth" with "er·", and both of those were themselves built by rules 12 and 7. The table has to be applied in order; shuffled, it produces a different tokenisation.
- The merge count is a knob with no correct setting. More merges mean a bigger vocabulary and shorter sequences, and the returns fall off: the winning pair occurs 30 times at merge 1 on this corpus and 3 times at merge 24.
Where the text comes from
The tool counts pairs in eight sentences that a person wrote for this page, held attools/bpe/src/data/corpus.v1.json and shown in full in the tool’s Corpus tab. They are 409 characters altogether, all lower case, and nothing in them is quoted. The lower case is a decision rather than an oversight: byte-pair encoding treatsT and t as different symbols, so capitals would spend the early merges on case variants and teach nothing.
The sentences were picked so that the first twenty merges are ones a reader recognises —th, the·, er·, other·,read — and two of those are four generations deep. That is not how a real tokeniser’s training corpus is chosen. Those are enormous and are not curated sentence by sentence, and the merges they produce are mostly not legible. Four hundred characters can be counted by hand and checked against the tool; billions cannot. The reason this page can promise its arithmetic is verifiable is the same reason it cannot promise to show you a real tokeniser.
A space is drawn as · throughout, because an empty cell in a row of characters reads as a missing character rather than as the space it is, and after a mergethe· would otherwise be indistinguishable from the. They are different tokens.
Cost
- Time
- O(m · n)
- Extra space
- O(n + m)
- Most merges
- 24
m is the number of merges to learn and n the number of tokens in the corpus, which shrinks as the run proceeds. The ceiling is twenty-four merges, and it is not a cost limit — the whole run generates in under a millisecond. It is the point at which the algorithm stops making a frequency decision: the winning pair occurs 30 times at merge 1, 3 times at merge 24, twice by merge 30 and once from merge 48 on. Past that, “the most frequent pair” is settled entirely by the tie-break, and the tool would be teaching its own tie-break rather than the algorithm.