BPE-Style Tokenizers: The Small Algorithm That Decides What an LLM Can See

BPE-Style Tokenizers: The Small Algorithm That Decides What an LLM Can See

Hello, I'm Shrijith Venkatramana, and I'm building LiveReview - a blast-radius aware AI code review built for your business-critical systems. Star us to help devs discover the project, give it a try, and share your feedback to help improve the product.

When you type: unbelievableness an LLM does not see the word. It sees something more like: ["un", "believ", "ableness"] Or perhaps: ["un", "believe", "ness"] Or, depending on the tokenizer: ["un", "bel", "iev", "ab", "leness"] That difference is not cosmetic. Tokenization determines the length of the model's input sequence, which affects context usage, inference cost, attention computation, vocabulary size, handling of rare words, programming-language behavior, multilingual performance, and even some model failure modes.

And one of the most widely used ideas behind modern LLM tokenizers has an unusually non-LLM origin: a 1994 data-compression algorithm by a programmer named Philip Gage. The basic idea is remarkably simple: Find things that occur together often, and give them a reusable symbol. That idea eventually went from C programmers doing data compression, to neural machine translation, to GPT-2 and the tokenization machinery surrounding today's language models.

What Problem is a Tokenizer Actually Solving?

A neural network wants numbers. Your input is text: The server returned HTTP 500. The model needs: [the, server, returned, HTTP, 500, .] which eventually becomes integer IDs such as: [464, 2126, 4710, ...] The obvious question is: Why not make every word a token? Suppose the vocabulary contains: cat dog server database running ...

Now consider: microarchitectural microarchitectures microarchitecturally You immediately run into the open-vocabulary problem. There are infinitely many possible strings. New product names appear. Developers invent identifiers. People misspell things. Languages generate long compounds. Users paste URLs, hashes, code, emojis and arbitrary Unicode. A word-level tokenizer therefore needs some fallback mechanism. At the other extreme, we could tokenize one character at a time: m i c r o a r c h i t e c t u r a l Now everything is representable, but sequences become much longer. That creates a fundamental tradeoff: word tokens <- shorter sequences, huge vocabulary, poor handling of unknown words character tokens<- tiny vocabulary, very long sequences subword tokens<- compromise BPE-style tokenization lives in that middle ground. Frequent sequences become single tokens. Rare sequences remain decomposable into smaller units. That is the key intuition.

The Strange History: from 1994 Compression to GPT

In 1994, Philip Gage published an article in The C Users Journal describing Byte Pair Encoding , or BPE. His original problem had nothing to do with language models. The idea was ordinary compression: Suppose data contains: ABABABABABAB and AB occurs constantly. Instead of repeatedly storing: A B A B A B A B ... we can create a new symbol representing: AB and replace occurrences of the pair. Do it repeatedly, and common sequences become increasingly compact. The original algorithm therefore looked roughly like: find the most frequent adjacent byte pair replace it with a new symbol repeat This is a compression algorithm. But the basic mechanism turns out to be useful for language.

In 2016, Rico Sennrich, Barry Haddow and Alexandra Birch applied BPE to neural machine translation. Their motivation was the open-vocabulary problem : machine translation systems had to deal with names, compounds and rare words that could not reasonably all appear in a fixed word vocabulary. Consider: counterrevolutionaries A word-level vocabulary might not contain it. A subword system could represent it approximately as: counter + revolution + ar + ies The exact segmentation is learned from data rather than being supplied by a linguist. This mattered because the model could now encounter a word it had never seen as a whole while still having a representation for its pieces.

Then GPT-2 made an important variation mainstream: byte-level BPE . Instead of starting from all Unicode characters, GPT-2 starts from the 256 possible byte values. That gives a tiny guaranteed base vocabulary while preserving the ability to represent arbitrary byte sequences. GPT-2 used a vocabulary of 50,257 entries, consisting of the 256-byte base plus 50,000 learned merges and a special token. ( OpenAI CDN ) So the lineage is roughly: 1994: byte compression | v 2016: subword representation for NMT | v 2019: byte-level BPE for GPT-2 | v modern LLM tokenizers

The interesting part is that almost none of this requires a sophisticated linguistic theory. It is mostly frequency statistics plus a greedy merging procedure.

How BPE Learns its Vocabulary

Let's construct a tiny tokenizer. Suppose our corpus is: low low low low low lower lower widest widest widest newest newest newest newest newest newest First, pretend our base vocabulary consists of individual characters. We represent: low as: l o w and: lower as: l o w e r Now count adjacent pairs. For example: (l, o) (o, w) (w, e) (e, r) (w, i) (i, d) (d, e) (e, s) (s, t) (n, e) Because newest appears six times, the pair: (e, s) appears six times. Likewise: (s, t) appears six times. BPE asks: Which adjacent pair is most frequent? Suppose we pick: (e, s) and create a new symbol: es Now: newest becomes: n e w es t The vocabulary has grown by one. Next we recount pairs and may discover: (es, t) is highly frequent. Merge again: est Now: newest becomes: n e w est Continue. Eventually you might learn: st est west newest depending on corpus frequencies and the exact sequence of merges. The algorithm is therefore almost embarrassingly simple.

The mathematical version Let the current token sequence for a corpus be made from symbols in vocabulary V . For every adjacent pair (a, b) , compute its frequency: f(a, b) = number of times a is immediately followed by b Then choose: (a*, b*) = argmax_(a,b) f(a, b) Create a new token: c = a || b where || means concatenation. Then replace every occurrence of: a b with: c and repeat. If we begin with B base symbols and perform K merges: |V| = B + K + special_tokens For byte-level BPE: B = 256 So with 50,000 merges: |V| ~= 50,000 + 256 plus whatever special tokens the system uses. This is a useful mental model: The tokenizer vocabulary is largely a compressed dictionary of frequently useful byte sequences.

Why This Works Surprisingly Well for Language

There is an important property hiding inside the greedy algorithm. Suppose these sequences are common: tion ing pre un http :// BPE will tend to discover them because they occur frequently. Eventually it may discover larger units: communicat + ion or perhaps: commun + ication or, for a very common word: communication as one complete token. This means the tokenizer automatically creates something resembling a hierarchy: bytes -> small fragments -> common morpheme-like units -> common words -> common multi-character sequences But an important distinction: BPE does not understand morphology. It does not know that: walk walking walked walker share a linguistic stem. It only knows that certain byte sequences occur frequently enough to be worth merging. That distinction matters when people say things like "the tokenizer understands prefixes." It does not. It has learned a segmentation that is useful according to its training statistics.

A useful example Imagine a corpus where: hyperparameter occurs 50,000 times. Then the tokenizer has an economic incentive, in vocabulary terms, to represent something like: hyperparameter compactly. But suppose: hyperparametrix appears once. A BPE tokenizer can still represent it: hyper + parameter + ix or some other decomposition. This is the main advantage over word-level tokenization. It gets compression for common patterns without making the vocabulary responsible for every possible word .

Byte-Level BPE: The Trick That Removes <unk>

Ordinary character-level BPE has an awkward problem. Unicode is enormous. If you want every possible Unicode character to be a base symbol, your initial vocabulary is already huge. GPT-2 instead starts from bytes. There are exactly: 256 possible byte values. Any Unicode string encoded as UTF-8 becomes a byte sequence: text -> UTF-8 -> bytes -> BPE merges -> token IDs This has an important consequence: there is always a fallback representation. Even if a tokenizer has never seen a particular Unicode string during training, the raw bytes can still be represented. For example, an emoji such as: 👍 is represented internally by its UTF-8 bytes: F0 9F 91 8D The tokenizer may have learned to merge those bytes, partially merge them, or leave them separate. But it does not need a vocabulary entry literally corresponding to every possible Unicode character. That is a powerful design decision.

There is another subtlety Naively running BPE over raw bytes has undesirable behavior. Suppose your corpus contains: dog dog. dog! dog? Frequency-based BPE may learn variants of entire sequences that are statistically frequent, wasting vocabulary entries on punctuation-specific combinations. GPT-2's approach therefore constrained which byte sequences could merge, while treating spaces specially. The objective was to retain the generality of byte-level representation without allowing the greedy learner to spend too much vocabulary capacity on accidental boundary variants. ( OpenAI CDN ) This is a recurring theme in tokenizer engineering: The basic algorithm is simple. Most of the engineering is deciding where the simple algorithm is allowed to operate.

The Developer Consequences: Tokens Are an Economic Unit

This is where tokenization stops being an NLP curiosity. Consider a model with a context window of: 128,000 tokens If your tokenizer turns a piece of text into: 100,000 tokens you have room for approximately: 28,000 tokens of additional context. If another tokenizer represents exactly the same text as: 80,000 tokens you now have approximately: 48,000 tokens left. That is a 71% increase in remaining context. The difference gets even more important for long-context workloads.

Attention cost For standard full self-attention, the interaction matrix is approximately: n x n so the dominant attention computation scales approximately as: O(n^2) Suppose tokenizer A gives you: n = 10,000 tokens. Tokenizer B produces 20% more: n = 12,000 The ratio of pairwise attention work is approximately: 12,000^2 / 10,000^2 = 1.44 So a 20% increase in token count can imply roughly: 44% more pairwise attention work. That is not a property of BPE itself. It is a consequence of the fact that tokenization controls sequence length . This gives us a useful engineering principle: characters -> tokenizer -> token count -> context utilization -> compute + memory + latency

Token efficiency is also model capacity Imagine two representations of the same sentence: Tokenizer A: 12 tokens Tokenizer B: 18 tokens The model using B has to predict a longer sequence. At training time that means more prediction positions. At inference time it means more autoregressive steps. For APIs, token count also becomes a billing and capacity unit because providers commonly meter usage in tokens. So tokenizer quality is not merely: "Does the text tokenize?" It is also: "How economically does this representation use the model's finite sequence budget?"

Code exposes the problem Consider: def calculate_monthly_revenue ( customer_transactions ): ... A tokenizer that is optimized around English prose may discover useful units such as: calculate monthly revenue customer But source code contains many patterns that have different frequency distributions: init HTTPRequest std::unordered_map get_user_profile ===> Programming languages are therefore an interesting tokenizer workload because identifiers, punctuation, whitespace, delimiters and repeated syntactic fragments all compete for vocabulary capacity. The result is one reason why "tokenizer efficiency" should be evaluated on the actual distribution your model serves, not only on generic English text.

At Inference Time, BPE is a Deterministic Compression Dictionary

Once training is finished, the tokenizer no longer needs to "discover" anything. It has two important artifacts: vocabulary merge rules For example, imagine the merge ranking contains: 1.e s 2.es t 3.n e 4.ne w 5.new est ... Now given: newest the encoder applies the learned rules in their defined priority. Conceptually: n e w e s t then perhaps: ne w e s t then: ne w est then eventually: new est depending on the learned merge table. The output is something like: [new, est] The exact implementation used by modern tokenizers is optimized considerably beyond this toy procedure. A naive implementation that rescans an entire corpus after every merge would be unnecessarily expensive. But the conceptual model remains: base symbols + ordered merge rules = tokenizer And that has a subtle consequence for developers: token IDs are meaningless without the tokenizer definition that produced them. Token ID: 12345 does not inherently mean "hello" or "database." It means whatever entry 12345 refers to in a particular tokenizer vocabulary. This is also why changing tokenizers can invalidate embeddings, model inputs, cached token sequences and various pieces of preprocessing infrastructure. The tokenizer is effectively part of the model's interface contract.

What BPE Does Not Solve

BPE solves one problem very well: How do we turn arbitrary text into a finite vocabulary while giving common sequences compact representations? It does not solve everything. It does not guarantee linguistically meaningful boundaries. It does not guarantee equal token efficiency across languages. It does not make arithmetic easy. It does not make code identifiers naturally interpretable.