Byte-pair encoding (BPE) tokenization

Deep dive

How it works

In: a byte string (training: a corpus) · Out: token ids from a vocabulary of fixed size · State: the ordered merge list (rank per pair) and a per-chunk cache · Cost: training O(corpus · log) with a heap; encoding O(n log n) per chunk

Pre-tokenization. GPT-2 splits text with

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

so " hello" (with its leading space) is one chunk and merges cannot glue words to punctuation. Later tokenizers change the regex (e.g. cl100k splits numbers into groups of at most 3 digits).

Training.

1. Count chunk frequencies in the corpus: {" the": 1.2M, " cat": 3k, …}. Work on unique chunks with weights, not on raw text.
2. Represent each chunk as a sequence of byte ids.
3. Count weighted adjacent pairs. Take the most frequent (a, b). Assign it id 256 + merges.len().
4. Replace every (a, b) occurrence in every chunk, left to right, non-overlapping.
5. Repeat until vocab_size − 256 − specials merges.

Encoding a chunk: repeatedly find the adjacent pair with the lowest rank among merges, merge all its occurrences, stop when no pair has a rank. Cache results per chunk: a few hundred thousand distinct chunks cover most text.

"low lower lowest"  chunks: "low", " lower", " lowest"
merge 1: (l,o)→lo    merge 2: (lo,w)→low    merge 3: ( ,low)→" low"   merge 4: (e,r)→er ...
encode " lowest" → [" low", "e", "s", "t"] → ... → [" low", "est"] once (e,s),(es,t) are learned

Code

use std::collections::HashMap;

pub struct Bpe { pub merges: Vec<(u32, u32)>, rank: HashMap<(u32, u32), u32>, pub vocab: Vec<Vec<u8>> }

/// Minimal pre-tokenizer: optional leading space + run of letters, digits, or other symbols.
/// (Production uses the GPT-2 / cl100k regex; this keeps the same "space belongs to next word" rule.)
pub fn pretokenize(text: &str) -> Vec<&str> {
    let class = |c: char| if c.is_alphabetic() { 0 } else if c.is_numeric() { 1 } else if c.is_whitespace() { 2 } else { 3 };
    let ch: Vec<(usize, char)> = text.char_indices().collect();
    let (mut out, mut i) = (Vec::new(), 0);
    while i < ch.len() {
        let mut j = i;
        if ch[j].1 == ' ' && j + 1 < ch.len() && class(ch[j + 1].1) != 2 { j += 1; } // " word" is one chunk
        let k = class(ch[j].1);
        while j < ch.len() && class(ch[j].1) == k { j += 1; }
        if k == 2 && j < ch.len() && j - i > 1 && ch[j - 1].1 == ' ' { j -= 1; }   // leave 1 space for next word
        out.push(&text[ch[i].0..if j < ch.len() { ch[j].0 } else { text.len() }]);
        i = j;
    }
    out
}

fn merge_pair(seq: &[u32], pair: (u32, u32), new: u32) -> Vec<u32> {
    let mut out = Vec::with_capacity(seq.len());
    let mut i = 0;
    while i < seq.len() {
        if i + 1 < seq.len() && (seq[i], seq[i + 1]) == pair { out.push(new); i += 2; }
        else { out.push(seq[i]); i += 1; }
    }
    out
}

impl Bpe {
    pub fn train(text: &str, vocab_size: usize) -> Bpe {
        let mut words: HashMap<Vec<u32>, u64> = HashMap::new();         // unique chunks with counts
        for w in pretokenize(text) { *words.entry(w.bytes().map(u32::from).collect()).or_default() += 1; }
        let mut vocab: Vec<Vec<u8>> = (0..=255u8).map(|b| vec![b]).collect();
        let mut merges = Vec::new();
        while vocab.len() < vocab_size {
            let mut counts: HashMap<(u32, u32), u64> = HashMap::new();
            for (w, &c) in &words { for p in w.windows(2) { *counts.entry((p[0], p[1])).or_default() += c; } }
            // most frequent pair; ties broken by smallest pair for determinism
            let Some((&best, _)) = counts.iter().max_by(|a, b| a.1.cmp(b.1).then(b.0.cmp(a.0))) else { break };
            let new = vocab.len() as u32;
            words = words.into_iter().map(|(w, c)| (merge_pair(&w, best, new), c))
                .fold(HashMap::new(), |mut m, (w, c)| { *m.entry(w).or_default() += c; m });
            let mut bytes = vocab[best.0 as usize].clone();
            bytes.extend_from_slice(&vocab[best.1 as usize]);
            vocab.push(bytes);
            merges.push(best);
        }
        let rank = merges.iter().enumerate().map(|(i, &p)| (p, i as u32)).collect();
        Bpe { merges, rank, vocab }
    }

    /// Apply merges in rank order within one chunk.
    fn encode_chunk(&self, chunk: &str) -> Vec<u32> {
        let mut seq: Vec<u32> = chunk.bytes().map(u32::from).collect();
        loop {
            let best = seq.windows(2).filter_map(|p| self.rank.get(&(p[0], p[1])).map(|&r| (r, (p[0], p[1])))).min();
            let Some((r, pair)) = best else { return seq };
            seq = merge_pair(&seq, pair, 256 + r);
        }
    }

    pub fn encode(&self, text: &str) -> Vec<u32> {
        pretokenize(text).into_iter().flat_map(|c| self.encode_chunk(c)).collect()
    }

    pub fn decode(&self, ids: &[u32]) -> String {
        let bytes: Vec<u8> = ids.iter().flat_map(|&i| self.vocab[i as usize].iter().copied()).collect();
        String::from_utf8_lossy(&bytes).into_owned()                     // a token may split a UTF-8 char
    }
}

fn main() {
    let corpus = "low lower lowest newer newest wider widest low low lower newest newest ".repeat(50);
    let bpe = Bpe::train(&corpus, 256 + 20);
    let show = |id: u32| String::from_utf8_lossy(&bpe.vocab[id as usize]).into_owned();
    println!("first merges: {:?}", bpe.merges.iter().take(6).map(|&(a, b)| (show(a), show(b))).collect::<Vec<_>>());
    let text = "the lowest newer widest, ünïcode 42";
    let ids = bpe.encode(text);
    println!("{} bytes -> {} tokens: {:?}", text.len(), ids.len(), ids.iter().map(|&i| show(i)).collect::<Vec<_>>());
    assert_eq!(bpe.decode(&ids), text);                                  // lossless round trip
    assert_eq!(pretokenize("a   b,\n\n 42"), vec!["a", "  ", " b", ",", "\n\n", " 42"]);
}

Complexity and constants

• Naive training recounts all pairs per merge: O(merges × unique-chunk bytes). Fine for 10k merges on a few MB of unique chunks. Production trainers keep pair counts incrementally (update only the pairs adjacent to each merge site), track where each pair occurs, and pop the best pair from a priority queue.
• Encoding the naive way is O(n²) per chunk, but chunks are short (a word). A heap with a linked list of symbols gives O(n log n). With per-chunk caching and parallelism over documents, encoding is rarely the training bottleneck (tiktoken and Hugging Face tokenizers both have Rust cores).
• Token ids fit in u16 up to 65535 vocabulary entries, u32 above. Store pretokenized training data as uint16 or uint32 arrays (data loading).
• The embedding and output layers scale with vocabulary: 2·V·d parameters if untied (embeddings).

Efficiency

• Cost: encoding is CPU-bound: a regex pretokenizer, then per-chunk merge lookups in a hash map. Token ids take 2 bytes (u16, vocabulary up to 65,536) or 4 bytes (u32). Tokenization is a small fraction of training cost, but a visible one in serving latency and corpus preprocessing.
• Levers:
  • Rust core with per-chunk cache — tiktoken is 3-6x faster than comparable open-source tokenizers (tiktoken README) — natural text, where words repeat.
  • Batch-encode documents in parallel — scales with cores, no shared state (this page) — corpus preprocessing.
  • Incremental pair counts plus a priority queue in training — from O(merges × bytes) to counting only around merge sites (this page) — large corpora.
  • Larger vocabulary — fewer tokens per text, so fewer forward positions, at 2·V·d more embedding parameters if untied (this page) — tradeoff to tune once.
• Naive → standard → state of the art:
  • Recount every pair per merge, O(n²) greedy encode per chunk · fine for a few MB only
  • Rust BPE (tokenizers, tiktoken) with cache and parallel batches · 3-6x faster than comparable open-source tokenizers
  • Heap plus linked list encode, incremental training counts · O(n log n) per chunk, training scales to TB corpora (order of)

Implementation notes

• Byte-level, not character-level: GPT-2 maps the 256 bytes to printable Unicode characters only so the vocabulary file is readable. The algorithm is on bytes.
• Special tokens (<|endoftext|>, chat markers) are matched before pre-tokenization and never produced by merges. Never let user text produce them: encode untrusted text with specials disabled.
• Train on a representative sample (a few GB is plenty) of the actual training mix, including code and the languages you care about. The vocabulary allocates tokens by frequency in that sample.
• Digits: split into single digits (Llama 1/2 SentencePiece) or groups of up to 3 (cl100k) for more consistent arithmetic.
• Decoding a stream token by token: buffer bytes until they form complete UTF-8 characters.
• Pad vocab size to a multiple of 64 or 128 for matmul efficiency, with unused ids.

Pitfalls

• Train/serve mismatch: different regex, normalization (NFKC), or merge list. Same text yields different ids and the model degrades quietly.
• Leading-space convention: "hello" and " hello" are different tokens. Prompts that end with a space push the model into a rare token.
• Glitch tokens: tokens frequent in the tokenizer's training sample but rare in the model's training data have barely-trained embeddings (e.g. Reddit usernames in GPT-2's vocabulary).
• Encoding by greedy longest match instead of merge rank: produces different, non-canonical tokenizations.
• Tokenizing documents before concatenation without an EOS token between them: the model learns to continue across document boundaries.

Variants and alternatives

In production

tiktoken (OpenAI; Rust core, GPT-2, cl100k_base, o200k_base), Hugging Face tokenizers (Rust; BPE, WordPiece, Unigram), SentencePiece (C++; Llama 1/2, T5, Gemma), Llama 3 (tiktoken-style BPE, 128k), DNABERT-2 (BPE over DNA), MidiTok (BPE over MIDI events).

Implementations

Sources

• Zhou et al., DNABERT-2: Efficient Foundation Model and Benchmark For Multi-Species Genome, ICLR 2024. paper
• Fradet et al., Byte Pair Encoding for Symbolic Music, EMNLP 2023. paper
• Gage, A New Algorithm for Data Compression, C Users Journal, 1994.
• Sennrich, Haddow, Birch, Neural Machine Translation of Rare Words with Subword Units, ACL 2016. paper
• Radford et al., Language Models are Unsupervised Multitask Learners (GPT-2), 2019. code
• Kudo and Richardson, SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing, EMNLP 2018. paper · code
• Kudo, Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates, ACL 2018. paper
• Provilkov, Emelianenko, Voita, BPE-Dropout: Simple and Effective Subword Regularization, ACL 2020. paper
• Xue et al., ByT5: Towards a Token-Free Future with Pre-trained Byte-to-Byte Models, TACL 2022. paper