Building an LLM Inference Engine from Scratch: Tokenization Pipeline Notes

The development of an LLM inference engine starts from understanding and implementing the tokenizer. Before the model can perform any computation, raw text input must be converted into numerical token IDs that correspond to entries in the model vocabulary.

Loading the Tokenizer Configuration

The first step was to load the tokenizer files downloaded from Hugging Face. The tokenizer configuration contains several important components:

• Vocabulary (vocab.json): Maps token strings to integer token IDs.
• Merge rules (merges.txt or equivalent JSON structure): Defines the Byte Pair Encoding (BPE) merge priority.
• Regex pattern (tokenizer.json): Defines how raw text is initially split into smaller components.
• Special tokens: Defines reserved tokens such as beginning-of-sequence, end-of-sequence, padding, etc.

Using the nlohmann::json library in C++, the vocabulary and merge dictionaries were parsed into native C++ data structures for efficient lookup.

Example structures:

std::unordered_map<std::string, int> vocabulary;

std::unordered_map<
    std::pair<std::string, std::string>,
    int,
    PairHash
> merge_rank;

The tokenizer class was designed to manage the complete encoding pipeline:

Raw Text
   |
   v
Normalization
   |
   v
Regex Pre-tokenization
   |
   v
Byte / Unicode Conversion
   |
   v
BPE Merge Algorithm
   |
   v
Vocabulary Lookup
   |
   v
Token IDs

Text Normalization and Pre-tokenization

Modern LLM tokenizers do not directly map words to vocabulary entries. Instead, they apply a multi-stage transformation.

The regex pattern stored in tokenizer.json is used to perform pre-tokenization.

For example, the pattern separates:

• Words
• Numbers
• Punctuation
• Whitespace
• Contractions

A simplified example:
Input:

Hello world!

Regex output:

["Hello", " world", "!"]

Each segment is then processed independently by the BPE algorithm.

Byte-Level Encoding

Modern LLM tokenizers, such as GPT-2, Qwen, and many Hugging Face models, operate on bytes rather than directly on Unicode characters.

The original text:

你好

is first converted into UTF-8 bytes:

E4 BD A0
E5 A5 BD

Each byte is mapped into a special Unicode representation through a byte-to-unicode mapping.

The purpose of this mapping is to allow every possible byte value (0-255) to be represented as a valid Unicode token candidate.

Example:

Byte:
0xF0

Mapped Unicode:
ð

This creates an intermediate representation used by BPE.

Byte Pair Encoding (BPE) Merge Algorithm

The key discovery during implementation was that tokenization is not simply a vocabulary lookup.
The tokenizer does not immediately search:

"hello"

inside the vocabulary.
Instead, it performs iterative merging based on the merge rules.
Each pre-tokenized segment is first broken into individual byte/unicode units:
Example:

hello

becomes:

h e l l o

The tokenizer then checks adjacent pairs:

(h,e)
(e,l)
(l,l)
(l,o)

Each pair is searched in the merge dictionary.
The merge dictionary contains the priority ranking:

("h","e") -> 10
("he","l") -> 5
("hel","l") -> 3

A lower rank means a higher merge priority.

The algorithm repeatedly:

1. Finds all possible adjacent pairs.
2. Checks whether each pair exists in the merge dictionary.
3. Selects the pair with the lowest merge rank.
4. Combines the pair into a single token.
5. Repeats until no valid merges remain.

Vocabulary Lookup

After BPE merging is complete, the resulting token strings are searched in the vocabulary dictionary.

Example:
After merging:

["hello", "Ġworld"]

Vocabulary lookup:

hello     -> 15339
Ġworld    -> 1917

The final tokenizer output becomes:

[
  15339,
  1917
]

These integer IDs are then used as input embeddings for the transformer model.

Repo: https://github.com/NgKaiWen7/InferenceEngine/tree/tokenization