Text Into Token IDs

Tokenization is the first irreversible interface boundary in transformer inference. You hand the system a Unicode string such as What is the capital of France?; the tokenizer emits a finite sequence of integer IDs; and from that point onward the neural network sees only integers, vector rows, and tensor shapes. That sounds mundane, but it is not a bookkeeping footnote. Token boundaries determine which learned embeddings are fetched, where the model can reuse statistical structure, how long the prompt becomes, and how much later attention work the model must perform.

The reason this stage exists is simple: dense numerical models cannot economically consume raw text. A string is variable-length, encoding-dependent, full of ambiguous boundaries, and too large if represented naively as a one-hot vector over all possible character sequences. Tokenization solves that by mapping text into a closed vocabulary of manageable size. The model pays a fixed price for a vocabulary of V entries, and every prompt becomes a sequence over [0, V-1]. Without that compression step, every later matrix would be larger, sparser, and operationally uglier.

Following the running example exactly

The prompt enters as bytes, not as abstract words. In UTF-8, What is the capital of France? is a short byte sequence containing ASCII code points, spaces, and the final question mark. A GPT-2-style byte-level BPE tokenizer first preserves the raw bytes, then applies its learned merge rules over byte-derived symbols. Internally, leading spaces are often represented as part of the next token, which is why token strings frequently look like is or France rather than splitting the space into its own standalone piece.

Raw text
    What is the capital of France?

UTF-8 bytes
    57 68 61 74 20 69 73 20 74 68 65 20 63 61 70 69 74 61 6C 20 6F 66 20 46 72 61 6E 63 65 3F

GPT-2 style token pieces
    ["What", " is", " the", " capital", " of", " France", "?"]

Representative GPT-2 token IDs
    [2061, 318, 262, 3139, 286, 4881, 30]

That example matters because it already shows three non-obvious facts. First, token IDs are tokenizer-specific; a different model family can assign different numbers to the same visible pieces. Second, spaces are often fused into tokens because they are statistically meaningful and very common. Third, the sentence length that matters for inference is not character count or word count; it is token count. For the rest of this chapter, the operational object for our running example is therefore the integer vector [2061, 318, 262, 3139, 286, 4881, 30] with shape [T] where T = 7.

Tokens are not words

Engineers new to LLM internals often assume a token is just a word with a smaller integer attached. That is wrong often enough to be dangerous. A token can be a whole word, a prefix, a suffix, punctuation, a space-prefixed fragment, a byte fallback, or a model-specific special symbol. The classic demonstration is unbelievable. A subword tokenizer may emit ["un", "believ", "able"]. The model does not know that those pieces are morally part of one English word; it only knows that three learned IDs arrived in that order.

Why is that compromise useful? Because natural language has productive structure. Prefixes, stems, and suffixes recur across many words. If the vocabulary stored every surface word separately, rare words would either explode the vocabulary or fall back to an unknown token too often. If the vocabulary stored only characters or bytes, prompts would become much longer, and every later attention layer would do more work. Subwords let the system reuse frequent pieces while retaining manageable sequence length.

How BPE learns the merge table

Byte Pair Encoding, or BPE, is usually explained as an inference-time tokenizer, but its critical machinery is learned offline during tokenizer training. Start with a base alphabet. In a character BPE that might be Unicode code points or pretokenized characters; in a byte-level BPE it is the 256 possible bytes. Represent each training word as a sequence of those primitive symbols. Then repeatedly count adjacent symbol pairs across the corpus, choose the most frequent pair, merge it into a new symbol, rewrite the corpus using that new symbol, and repeat until the target vocabulary size is reached.

(a, b)* = argmax_(a,b) count_adjacent(a, b)

In English: at each BPE training step, find the adjacent pair that appears most often, then promote that pair into its own new symbol. You are effectively saying, this pair is common enough that future encodings should treat it as one reusable chunk instead of two separate pieces.

The key artifact is not the rewritten training corpus; it is the ranked merge table produced by this loop. At inference time the tokenizer does not relearn anything. It simply consults the frozen merge ranks and applies them deterministically. Operationally, that makes tokenizer inference a static lookup problem backed by tables created once during tokenizer training. The expensive counting and pair selection happened long before the model ever answered a user prompt.

There is an important distinction here between the tokenizer training objective and the model training objective. BPE training is about choosing reusable text pieces. It does not optimize next-token prediction loss directly. Later, the language model learns embeddings and weight matrices over whatever token inventory the tokenizer handed it. If the tokenizer chooses poor boundaries, the model must compensate downstream. That is why tokenization affects behavior more than many introductions admit.

The actual encoding algorithm at inference time

Once the vocabulary and merge ranks are fixed, encoding is conceptually simple. Normalize or pretokenize if the tokenizer family requires it. Convert text into primitive symbols, often bytes. Look at adjacent symbols and merge the best-ranked pairs until no permitted merge remains, or equivalently perform longest-prefix matching against a compiled lexicon. Finally translate each resulting token piece to its integer ID. Real implementations use tries, radix tables, or precompiled state machines to avoid literally rescanning pair lists from scratch, but the visible behavior is the same.

typedef struct {
    MergeRank merge_rank;
    TokenIdMap vocab;
    SpecialTokenMap special;
} Tokenizer;

vector<int> encode(Tokenizer* tok, string text) {
    vector<int> out;
    vector<Piece> spans = pretokenize(text, tok->special);

    for (Piece span : spans) {
        if (span.is_special) {
            out.push_back(tok->special.id_of(span.text));
            continue;
        }

        vector<Symbol> symbols = to_base_symbols(span.text);   // bytes or chars
        while (true) {
            Pair best = find_lowest_rank_merge(symbols, tok->merge_rank);
            if (!best.exists) break;
            apply_merge(symbols, best);
        }

        for (Symbol s : symbols) {
            out.push_back(tok->vocab.id_of(s));
        }
    }
    return out;
}

runtime_work ≈ O(N_bytes)

In English: a compiled production tokenizer is usually close to linear in the number of input bytes, not quadratic in the number of possible substrings. The constant factors matter a lot, because Unicode handling, prefix matching, and allocation strategy decide whether tokenization feels instant or becomes a measurable front-end bottleneck.

For our running example, the process is small enough to reason about by inspection. The tokenizer sees the text, recognizes no special token override, converts the ASCII characters to bytes, applies merge ranks that favor common space-prefixed English fragments, and emits seven IDs. If you invoke the tokenizer again with the same string, you get the same seven IDs. The tokenizer is deterministic and stateless. There is no hidden adaptive cache, no gradient update, and no per-session memory of previous prompts.

BPE versus WordPiece versus SentencePiece

Modern models do not all use the same tokenization family. BPE is popular in decoder-only LLMs. WordPiece was used heavily in BERT-style encoders. SentencePiece generalized the idea and removed the assumption that spaces must be handled by an external pretokenizer. The families share a goal, but they differ in how pieces are represented, how unknown text is handled, and whether training is framed as pure pair merging or as a unigram-style probability model over subword pieces.

The practical consequence is visible in robustness. A byte-level GPT-2 or GPT-4-style tokenizer can always represent arbitrary binary-ish text because every byte already exists in the base alphabet. That largely eliminates the need for an unknown token. WordPiece, by contrast, often uses UNK when a sequence cannot be decomposed under its learned vocabulary. SentencePiece lives in between: it can operate on raw strings, optionally normalize them, and can be configured with byte fallback for difficult cases such as rare scripts, malformed text, or emoji-heavy content.

Unicode, normalization, and ugly edge cases

Unicode handling is not optional polish. The string a user sees on screen can have multiple canonically equivalent encodings. A precomposed character like é may appear as one code point or as e plus a combining accent. Emoji sequences can include zero-width joiners. Regional flags are pairs of indicator symbols. If the tokenizer normalizes to NFC or NFKC during training but not during inference, or vice versa, the same visible prompt may map to different IDs. That breaks reproducibility and can degrade model behavior in subtle ways.

Byte-level tokenizers dodge some of that by operating on raw UTF-8 bytes after minimal text preparation. They do not need to understand code point boundaries to remain lossless; they only need a reversible byte-to-symbol mapping. The price is that visually similar strings with different underlying byte sequences remain different to the model. SentencePiece often normalizes more aggressively, which can improve consistency but also means the tokenizer is making stronger editorial choices about what counts as the same text. Neither approach is universally correct; each is a product decision with model-quality implications.

Special tokens deserve separate treatment because they are part of the tokenizer-model contract. Some decoder-only models automatically prepend BOS; others do not. Some chat templates inject begin-of-turn and end-of-turn markers that are just as important as the visible user text. Padding may be ignored by attention masks later, but it still occupies positions in the token array. And in byte-level tokenizers, UNK can be effectively obsolete because every byte sequence is representable, even if the resulting segmentation is ugly.

Decoding token IDs back to text

Decoding is the reverse path: take token IDs, map each ID back to its token piece, concatenate the underlying bytes or text fragments in the correct order, then convert bytes back to a display string. The operation sounds trivial, but you still need to define policies. Should BOS and EOS be rendered or skipped? Are invalid byte sequences permitted? Does the tokenizer preserve leading-space markers as raw bytes or as synthetic symbols that must be postprocessed? A good decoder is judged by round-trip fidelity: decode(encode(text)) should reproduce the original normalized form exactly.

string decode(Tokenizer* tok, vector<int> ids, bool skip_special) {
    ByteBuffer bytes;
    for (int id : ids) {
        if (skip_special && tok->special.contains(id)) continue;
        Piece p = tok->vocab.piece_of(id);
        append_piece_bytes(bytes, p);
    }
    return utf8_or_raw_bytes(bytes);
}

decoded_text = Decode(token_ids; vocab, special_policy)

In English: decoding is another deterministic table lookup plus byte assembly problem. It is the inverse mapping of the tokenizer, modulo any normalization or special-token policy baked into the tokenizer family.

Shapes, cost, and classifications

Even though tokenization is not a tensor-heavy stage, shape discipline still matters. Serving code needs to know how many token IDs were produced, whether padding was inserted, how maximum context length is enforced, and what the exact BOS or EOS policy is. Bugs at this stage are cheap in FLOPs but expensive in consequences, because every later stage trusts the IDs it receives.

Vocabulary size trade-offs

A tokenizer with a 32K vocabulary usually emits more tokens than one with 64K or 128K, because it has fewer whole fragments available and must fall back to smaller pieces more often. That increases sequence length, which later raises attention cost. But a larger vocabulary also enlarges the embedding matrix and, if embeddings are untied, the output projection matrix. So the tokenizer is participating in a global model trade-off, not a standalone text-processing preference.

T ≈ N_text / avg_text_per_token

In English: if each token covers more text on average, the sequence gets shorter. That helps downstream inference latency, but only because you already paid for a bigger vocabulary and therefore bigger model tables.

Hardware behavior and common optimisations

Tokenization usually belongs on the CPU. It is branchy, table-driven, light on arithmetic intensity, and often tightly coupled to request parsing, chat templating, and network I/O. GPUs excel at large regular arrays with high arithmetic density; tokenization is mostly the opposite. You can batch tokenization on GPUs or vector accelerators, but unless your serving stack is dominated by extremely large ingress batches, the engineering gain is modest. FPGAs can implement deterministic prefix automata efficiently, yet the opportunity cost is high because tokenization is rarely the dominant end-to-end bottleneck.

Common optimisations are straightforward systems work: compile merge rules into tries or DFAs, memory-map large vocab files, SIMD-scan for ASCII-heavy fast paths, separate Unicode normalization from hot loops when policy allows, reuse output buffers, avoid per-token heap allocation, and parallelize across independent requests rather than within one tiny prompt. None of these change the token IDs; they only reduce front-end latency and CPU noise.

Database lens and systems lens

The database analogy is a parser plus dictionary-encoding pipeline. Raw text arrives as an external data format. The tokenizer normalizes it, segments it, and dictionary-encodes recurring fragments into integer surrogate keys. Larger recurring fragments reduce later row count, just as better compression or better dictionary encoding can shrink later query work. Special tokens behave like control rows injected by the query protocol rather than by the user payload itself.

The systems-programming analogy is a lexer with a very opinionated symbol table. The merge table is like a precomputed grammar of useful local compounds. The token vocabulary is a bidirectional string table. Encoding is lexing plus interning; decoding is de-interning plus byte reassembly. Once you view it that way, most implementation concerns become familiar: input validation, normalization policy, memory layout, deterministic replay, and round-trip correctness.

Common implementation mistakes

Most tokenizer bugs are not mathematically impressive. They are contract bugs. Teams accidentally normalize text differently at training and inference time. They strip or insert leading spaces incorrectly. They forget that chat templates contribute hidden tokens. They use character counts instead of token counts when enforcing context limits. They assume the tokenizer is interchangeable across model families when the IDs and special-token conventions are different. Or they fail round-trip tests, so decode(encode(text)) mutates punctuation, whitespace, or non-ASCII text.

If you were implementing this yourself…

Start with a reference tokenizer and a tiny golden corpus. Verify exact token IDs for plain ASCII, accented text, emoji, combining marks, and strings containing special tokens. Then implement encode and decode so they round-trip cleanly. Only after correctness is locked down should you optimize tries, buffer reuse, batch throughput, or memory mapping. Tokenizers are easy to make fast and wrong.

For the running example, the correct end state of this chapter is boring in the best possible way. The string What is the capital of France? enters. The tokenizer deterministically emits [2061, 318, 262, 3139, 286, 4881, 30]. That vector is the handoff to the next subsystem. Nothing magical happened, but every later number the model computes depends on this exact boundary choice. In other words, tokenization is only a front-end stage right up until it is wrong. Then it affects everything.