Introduction

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.

Build a Vocabulary

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.

<!-- BPE tokenizer demo — train a vocabulary step by step -->
<div class="controls">
  <label for="corpus-input">Training text</label>
  <textarea id="corpus-input" rows="3" placeholder="Enter some text…">the cat sat on the mat the cat ate the rat</textarea>
  <div class="row">
    <label for="vocab-size">Target vocab size:</label>
    <input id="vocab-size" type="number" min="10" max="60" value="30" />
    <button id="btn-init" type="button">Initialize</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">Vocabulary <span id="vocab-count"></span></div>
    <div id="vocab-display" class="vocab-chips"></div>
  </div>
  <div class="btns">
    <button id="btn-step" type="button">Step (one merge)</button>
    <button id="btn-run" type="button">Run all merges</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="status" id="status"></div>
</div>

/* root styles — tokens, vocab chips, controls */
* { 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; }
/* merge announcement banner */
.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; }
/* scrollable token sequence display */
.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; }
/* vocabulary chips panel */
.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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Byte-Pair Encoding training loop
// 1. Tokenize corpus into characters (+ </w> word boundary)
// 2. Count all adjacent symbol pairs across the token sequences
// 3. Merge the most frequent pair; add the merged symbol to vocab. Repeat.

let tokens = [];       // current token sequences (one list of symbols per word)
let vocab = new Set(); // current vocabulary set
let merges = [];       // ordered merge table (replayed at inference time)
let targetVocab = 30;
let running = false;

// Initialize: split text into words, then into characters
function initTokens(text) {
  // extract lowercase words
  const words = text.trim().toLowerCase().match(/[a-z']+/g) || [];
  tokens = [];
  vocab = new Set();
  merges = [];
  for (const w of words) {
    const chars = w.split('');
    // append </w> to mark end of word (standard BPE convention)
    chars.push('</w>');
    tokens.push(chars);
    chars.forEach(c => vocab.add(c));
  }
  return tokens.length > 0;
}

// Count frequency of every adjacent symbol pair in the corpus
function countPairs() {
  const freq = new Map();
  for (const word of tokens) {
    for (let i = 0; i < word.length - 1; i++) {
      const key = word[i] + '\x00' + word[i + 1];
      freq.set(key, (freq.get(key) || 0) + 1);
    }
  }
  return freq;
}

// Find the single most-frequent adjacent pair
function bestPair(freq) {
  let best = null, bestCount = 0;
  for (const [k, v] of freq) {
    if (v > bestCount) { best = k; bestCount = v; }
  }
  return best ? { pair: best.split('\x00'), count: bestCount } : null;
}

// Replace every occurrence of (a, b) with the merged symbol ab
function applyMerge(a, b) {
  const merged = a + b;
  for (const word of tokens) {
    for (let i = 0; i < word.length - 1; ) {
      if (word[i] === a && word[i + 1] === b) {
        word.splice(i, 2, merged);
      } else {
        i++;
      }
    }
  }
  vocab.add(merged);
  merges.push([a, b]);
}

// Render the current token sequences (first 12 words)
function renderTokens(highlight) {
  const el = document.getElementById('token-display');
  el.innerHTML = '';
  // show only the first 12 words to keep the display manageable
  const display = tokens.slice(0, 12);
  for (let wi = 0; wi < display.length; wi++) {
    if (wi > 0) {
      const sep = document.createElement('span');
      sep.className = 'tok tok-sep'; sep.textContent = '|';
      el.appendChild(sep);
    }
    for (const t of display[wi]) {
      const span = document.createElement('span');
      const isNew = highlight && t === highlight[0] + highlight[1];
      span.className = 'tok ' + (isNew ? 'tok-new' : 'tok-char');
      span.textContent = t;
      el.appendChild(span);
    }
  }
  if (tokens.length > 12) {
    const dots = document.createElement('span');
    dots.className = 'tok tok-sep'; dots.textContent = '…';
    el.appendChild(dots);
  }
}

function renderVocab(newToken) {
  const el = document.getElementById('vocab-display');
  el.innerHTML = '';
  document.getElementById('vocab-count').textContent =
    '(' + vocab.size + ' / ' + targetVocab + ')';
  // sort by length desc so multi-char tokens appear first
  const sorted = [...vocab].sort((a, b) => b.length - a.length || a.localeCompare(b));
  for (const v of sorted) {
    const chip = document.createElement('span');
    chip.className = 'chip' + (v === newToken ? ' new-chip' : '');
    chip.textContent = v;
    el.appendChild(chip);
  }
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg; el.className = 'status ' + (cls || '');
}

function step() {
  if (vocab.size >= targetVocab) {
    setStatus('Vocabulary complete — all merges applied.', 'done');
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    return false;
  }
  const freq = countPairs();
  if (!freq.size) {
    setStatus('No more pairs to merge.', 'done');
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    return false;
  }
  const top = bestPair(freq);
  const merged = top.pair[0] + top.pair[1];
  applyMerge(top.pair[0], top.pair[1]);
  document.getElementById('merge-info').innerHTML =
    fmt('Merged: <span class="hi">%v%</span> + <span class="hi">%v2%</span> → <span class="hi">%merged%</span> &nbsp;(×%count%)', { v: top.pair[0], v2: top.pair[1], merged: merged, count: top.count });
  renderTokens(top.pair);
  renderVocab(merged);
  setStatus(fmt('Merge %length% applied.', { length: merges.length }), 'info');
  return true;
}

document.getElementById('btn-init').addEventListener('click', () => {
  const text = document.getElementById('corpus-input').value;
  targetVocab = parseInt(document.getElementById('vocab-size').value, 10) || 30;
  if (!initTokens(text)) { setStatus('Please enter some text first.', 'info'); return; }
  document.getElementById('panel').style.display = 'block';
  document.getElementById('merge-info').innerHTML = 'Ready — click Step to run one merge at a time.';
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
  renderTokens(null);
  renderVocab(null);
  setStatus(fmt('Initialized with %size% base symbols. Click Step or Run all merges.', { size: vocab.size }), 'info');
});

document.getElementById('btn-step').addEventListener('click', step);

document.getElementById('btn-run').addEventListener('click', async () => {
  if (running) return;
  running = true;
  document.getElementById('btn-run').disabled = true;
  // animate each merge with a short delay so changes are visible
  while (step()) {
    await new Promise(r => setTimeout(r, 60));
  }
  running = false;
});

document.getElementById('btn-reset').addEventListener('click', () => {
  document.getElementById('panel').style.display = 'none';
  document.getElementById('merge-info').innerHTML = '';
  tokens = []; vocab = new Set(); merges = [];
  running = false;
});
Result
Console

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.

The Real Complexity

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

Training (building the merge table):

  • Each of the kk merge steps scans the current token sequence to count all pairs — O(n)O(n) per step, O(n⋅k)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(nlog⁡k)O(n \log k) with a trie, or simply O(n⋅k)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⋅V)O(n \cdot V) time, where VV 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/byte-pair-encoding/Content licensed under CC BY-NC 4.0.