Byte-Pair Encoding

Every large language model — GPT, LLaMA, BERT — begins with the same invisible step: it tokenizes the input. Before any attention mechanism fires, the raw text is sliced into a sequence of tokens drawn from a fixed vocabulary. Those tokens are not characters, and they are not always whole words. They are the output of a surprisingly simple algorithm called Byte-Pair Encoding (BPE).

BPE was invented in 1994 as a lossless data-compression scheme: find the most frequent pair of adjacent bytes, replace every occurrence with a new byte, repeat. In 2016, Rico Sennrich, Barry Haddow and Alexandra Birch adapted it for neural machine translation, and it has dominated NLP ever since.

The idea is disarmingly simple. Start with a vocabulary of individual characters (or bytes). Count every adjacent pair of symbols in the training corpus. Merge the most frequent pair into a new symbol. Repeat until the vocabulary reaches its target size — typically 30,000 to 100,000 tokens. The result is a vocabulary that covers common words as single tokens, splits rare words into recognizable pieces, and handles any unseen text without ever hitting an unknown-word problem.

Enter any short text and set a target vocabulary size, then step through the BPE training loop one merge at a time. Each step shows you the most frequent pair and the updated token sequence.

<!-- {{c_bpe_demo}} -->
<div class="controls">
  <label for="corpus-input">{{label_corpus}}</label>
  <textarea id="corpus-input" rows="3" placeholder="{{placeholder_corpus}}">{{default_corpus}}</textarea>
  <div class="row">
    <label for="vocab-size">{{label_vocab_size}}</label>
    <input id="vocab-size" type="number" min="10" max="60" value="30" />
    <button id="btn-init" type="button">{{btn_init}}</button>
  </div>
</div>
<div class="panel" id="panel" style="display:none">
  <div class="merge-row" id="merge-info"></div>
  <div class="token-wrap" id="token-display"></div>
  <div class="vocab-section">
    <div class="vocab-label">{{label_vocab}} <span id="vocab-count"></span></div>
    <div id="vocab-display" class="vocab-chips"></div>
  </div>
  <div class="btns">
    <button id="btn-step" type="button">{{btn_step}}</button>
    <button id="btn-run" type="button">{{btn_run}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="status" id="status"></div>
</div>

/* {{c_style_root}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .8rem; }
label { font-weight: 600; font-size: .85rem; color: #444; }
textarea { width: 100%; border: 1px solid #cdd9e3; border-radius: 6px; padding: .4rem .6rem;
           font: 13px/1.4 system-ui, sans-serif; resize: vertical; }
input[type=number] { width: 64px; border: 1px solid #cdd9e3; border-radius: 6px;
                     padding: .35rem .5rem; font-size: 13px; }
.row { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }
.panel { margin-top: .4rem; }
/* {{c_style_merge_row}} */
.merge-row { background: #eef3fb; border: 1px solid #bcd0ef; border-radius: 8px;
             padding: .5rem .8rem; font-size: .9rem; min-height: 2rem; margin-bottom: .6rem; }
.merge-row .hi { font-weight: 700; color: #1d3557; background: #d0e4ff;
                 border-radius: 4px; padding: 1px 4px; }
/* {{c_style_tokens}} */
.token-wrap { display: flex; flex-wrap: wrap; gap: 3px; margin-bottom: .7rem;
              max-height: 120px; overflow-y: auto; border: 1px solid #e0e6ed;
              border-radius: 8px; padding: .4rem; background: #fafbfc; }
.tok { border-radius: 4px; padding: 1px 5px; font: 13px/1.6 ui-monospace, monospace;
       border: 1px solid transparent; }
.tok-char { background: #e8eef3; border-color: #cdd9e3; color: #1d3557; }
.tok-new  { background: #d0f0d9; border-color: #7ecb9a; color: #145528; }
.tok-sep  { color: #999; font-size: 11px; align-self: center; }
/* {{c_style_vocab}} */
.vocab-section { margin: .4rem 0 .6rem; }
.vocab-label { font-weight: 600; font-size: .82rem; color: #555; margin-bottom: .3rem; }
.vocab-chips { display: flex; flex-wrap: wrap; gap: 3px; max-height: 90px; overflow-y: auto; }
.chip { font: 12px/1.5 ui-monospace, monospace; background: #f0f4f8; border: 1px solid #d0d9e4;
        border-radius: 4px; padding: 1px 6px; color: #334; }
.chip.new-chip { background: #d0f0d9; border-color: #7ecb9a; color: #145528; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.2em; }
.status.done { color: #0a7d33; }
.status.info { color: #1d3557; }

// Code not found

Watch how common substrings — "th", "he", "er" — get merged first, followed by full syllables and eventually whole common words. The same merge table produced here is exactly what a real tokenizer applies at inference time: it replays every merge in order on new text, splitting into the longest matching tokens.

BPE is fast, but understanding why requires separating two problems.

Training (building the merge table):

• Each of the $k$ merge steps scans the current token sequence to count all pairs — $O(n)$ per step, $O(n \cdot k)$ total. With priority queues the constant factor is small, and training a 32,000-token vocabulary on a billion-word corpus finishes in minutes on a laptop.
• The result is deterministic: given the same corpus and vocabulary size, you always get the same merge table.

Inference (tokenizing new text):

• Applying the merge table is $O(n \log k)$ with a trie, or simply $O(n \cdot k)$ by re-scanning. Either way it is linear in practice and fast enough to be invisible inside an LLM call.

The harder question — finding the segmentation that maximizes likelihood under a language model — is a different beast. Unigram LM tokenization (used by SentencePiece) solves it with the Viterbi algorithm in $O(n \cdot V)$ time, where $V$ is the vocabulary size. BPE sidesteps this by being greedy: it always merges the globally most frequent pair, never reconsidering. That greediness means BPE is not optimal in the information-theoretic sense, but it is consistent and produces vocabularies that work extremely well in practice.

See also pattern matching for how trie-based tokenizers run at inference time, and compression for where BPE's data-compression roots lie.

BPE's elegant tradeoff — fixed vocabulary, open-ended coverage — makes it the default choice wherever a model must handle text:

• Large language models: GPT-2, GPT-3, GPT-4 and LLaMA all use BPE (or a byte-level variant, BBPE, that treats raw bytes as the base alphabet, handling any Unicode without a special unknown token).
• Neural machine translation: the original Sennrich et al. (2016) application. A shared BPE vocabulary across source and target languages lets the model exploit shared subword structure — "unbeliev" appears in both English and French cognates.
• BERT and its variants: BERT uses WordPiece, a close relative of BPE that picks merges by maximizing likelihood rather than raw frequency. The vocabulary structure is nearly identical.
• Code generation: tokenizers for code (StarCoder, CodeLlama) learn that def, self., -> and import deserve their own tokens, compressing programs into far fewer tokens than character-level encoding.
• Multilingual models: a single BPE vocabulary trained on many languages simultaneously forces the model to share tokens across languages with overlapping scripts — improving low-resource performance via transfer.

The choice of vocabulary size is a real engineering tradeoff: 32 k tokens underrepresents rare languages; 100 k tokens bloats the embedding table and slows attention over long contexts. BPE lets practitioners tune that tradeoff without changing the algorithm.

Byte-Pair Encoding is a reminder that the most influential ideas in computing are often old, simple and repurposed. A lossless compression trick from 1994 became — with one key insight from Sennrich et al. — the invisible gateway through which every modern language model perceives text.

The greedy merge loop is easy to implement in an afternoon. What makes it powerful is not algorithmic sophistication but data: the merge table reflects the statistical structure of the corpus it was trained on, and that structure is then baked permanently into every weight of the downstream model. Change the tokenizer and you change what the model can see; keep it fixed and every future model inherits those decisions.

The next time an LLM gets a word wrong — misses a prefix, confuses a name, struggles with an agglutinative language — there is a good chance the root cause lives not in the transformer weights but in the merge table produced by this modest greedy algorithm.