LLMs
I am currently still working through this post and its not final. There could be erros and wrong assumtions until the final draft.
In this blog post I will formulate the idea behind the building blocks of LLMs that led to models like GPT2, LLama, and Gemini and more.
Tokenization
We begin first with the process know as tokenization of text. For context LLMs can’t simply reason with just language for exmaple if we give a prompt to an llm:
How can I multiply two matrices of different size?
We have to give this english sentence a mapping from text \(\rightarrow\) number which gives a sequence of numerical tokens. We also need to adjust some vocabulary of words to numerical tokens so the llm can reason with a sequence of numerical tokens rather than words.
So given a \(\operatorname{Vocabulary}\) and a sequence of words \(\operatorname{Word} \in \operatorname{Vocabulary}\) we have a mapping to a \(\operatorname{Token}\in \mathbb{Z}\)
\[\operatorname{Word} \rightarrow \operatorname{Token}\]Now if we look into the above prompt we can see for now how we can map the context of our sentece into numerical tokens. For now I use the tokenizer from openai tiktoken for reference and we will use it without knowing how this arrow \( \rightarrow \) happens and treat it as a block box for now.
[4438, 649, 358, 31370, 1403, 36295, 315, 2204, 1404, 30, 220]
Tokens 11 Characters 51
The output of the tokeinzer for our sentence is a 11 length sequence of integers given 51 characters.
I am doing a lot of handwavy assumtions that I will clarify in a moment but for now I wanna reference the most important detail of a tokenizer. The toknezier outputs a sequence of numbers that identifies each word in the vocabulary. In a high level this is all the functionality that we want from our tokenizer. Now how the tokenizer does this is far more complicated and involved and we will step through the detials and see how the process works.
BPE
How does a tokenizer decide which pieces of text should become tokens, and how does it assign an integer ID to each piece?
A common answer is Byte-Pair Encoding, usually abbreviated as BPE. BPE is a data-driven algorithm that learns a vocabulary of frequently occurring sequences from a training corpus.
Before explaining the algorithm, it is important to clarify what a token represents. A token is not necessarily a word. Depending on the tokenizer, one token may represent an entire word such as matrix part of a word such as mat or rix a word together with its preceding space, such as ` matrix punctuation such as ?` a single byte; or a sequence of bytes that represents only part of a Unicode character.
The integer assigned to a token is simply an index into the tokenizer’s vocabulary:
\[\operatorname{TokenID} \longrightarrow \operatorname{ByteSequence}.\]For example, a vocabulary might contain mappings such as
\[\begin{aligned} 17 &\longrightarrow \texttt{b"m"},\\ 42 &\longrightarrow \texttt{b"ma"},\\ 91 &\longrightarrow \texttt{b"matrix"}. \end{aligned}\]The numerical values (17), (42), and (91) do not contain semantic meaning by themselves. They are arbitrary identifiers used to look up the corresponding token. Later, the language model maps each token ID to a learned embedding vector.
Why not tokenize using only words?
Suppose that we create one token for every complete word. This works for common words, but it produces several problems.
First, natural language contains an enormous number of possible words. Names, spelling variations, technical terms, source code, URLs, and newly invented words would require an extremely large vocabulary.
Second, a word-level tokenizer cannot naturally handle words that did not occur in its training vocabulary. We would either need an unknown-word token such as <UNK> or a fallback method for decomposing the word.
At the other extreme, we could represent text using individual characters or bytes. This gives us a small vocabulary and allows us to represent arbitrary text, but it creates much longer input sequences.
BPE provides a compromise:
\[\text{bytes or characters} \quad\longleftrightarrow\quad \text{subwords} \quad\longleftrightarrow\quad \text{words}.\]Frequently occurring sequences can become large tokens, while rare sequences remain decomposed into smaller tokens. BPE was adapted for neural machine translation by Sennrich, Haddow, and Birch as a way to represent rare and previously unseen words using subword units.
The main idea
BPE begins with a small collection of initial symbols. It repeatedly performs the following operation:
- Count every adjacent pair of symbols in the training corpus.
- Find the pair that occurs most frequently.
- Join that pair to create a new symbol.
- Add the new symbol to the vocabulary.
- Replace occurrences of that pair in the training corpus.
- Repeat until the desired vocabulary size is reached.
For example, suppose that the pair
m a
occurs frequently in the training corpus. BPE may merge it into
ma
Later, the pair
ma t
may also occur frequently and become
mat
Additional merges might eventually create
matrix
as a single token. However, this only happens when the sequence is sufficiently frequent in the training corpus. A rare word may remain represented by several smaller tokens.
The algorithm therefore learns its vocabulary from the statistical structure of the training data rather than from a manually constructed dictionary.
Training a BPE vocabulary
Let (C) be the training corpus and let (V_{\max}) be the desired vocabulary size. For byte-level BPE, the initial vocabulary contains all 256 possible byte values:
\[V_0 = {0,1,\ldots,255}.\]Each byte can therefore be represented even if it never appeared during tokenizer training. Larger tokens are constructed by concatenating these initial byte tokens.
A simplified version of BPE training is the following:
BPE-TRAIN(C, V_max):
pieces ← PRETOKENIZE(C)
for each piece in pieces:
piece ← UTF8_BYTES(piece)
V ← all 256 individual byte values
R ← empty merge-rank map
next_rank ← 256
while |V| < V_max:
counts ← empty frequency map
for each piece in pieces:
for each adjacent pair (a, b) in piece:
counts[(a, b)] ← counts[(a, b)] + 1
if counts is empty:
break
(a, b) ← most frequent pair in counts
t_new ← a ‖ b
R[(a, b)] ← next_rank
V ← V ∪ {t_new}
next_rank ← next_rank + 1
for each piece in pieces:
replace every non-overlapping occurrence
of (a, b) with t_new
return (V, R)
Here, \(a \vert b\) means that the two byte sequences are concatenated.
The order in which merges are learned is important. Earlier merges receive a higher priority than later merges. We can represent this priority using a rank:
\[R(a,b)= \text{the iteration during which }(a,b)\text{ was learned}.\]A smaller rank means that the pair was learned earlier and should be applied first during encoding.
It is also important to distinguish the tokenizer-training corpus from the language-model-training corpus. The BPE algorithm is used first to learn a fixed vocabulary and merge table. Once the tokenizer has been trained, those rules are frozen and used to convert the language model’s text into token IDs.
Encoding text using learned BPE rules
When encoding a new prompt, we do not count which pairs are most frequent in that prompt. Instead, we apply the merge priorities that were learned during tokenizer training.
Given an input sequence (X) and a learned merge-rank map (R), encoding works as follows:
BPE-ENCODE(X, R):
output ← []
for each chunk in PRETOKENIZE(X):
S ← UTF8_BYTES(chunk)
while |S| > 1:
best_pair ← NONE
best_rank ← ∞
for each adjacent pair (S[i], S[i + 1]):
if (S[i], S[i + 1]) is in R:
rank ← R[(S[i], S[i + 1])]
if rank < best_rank:
best_rank ← rank
best_pair ← (S[i], S[i + 1])
if best_pair is NONE:
break
replace every non-overlapping occurrence
of best_pair with its concatenation
append the token IDs corresponding to S to output
return output
The key difference is therefore:
\[\boxed{ \begin{aligned} \text{Training:}&\quad \text{merge the most frequent pair},\\ \text{Encoding:}&\quad \text{merge the available pair with the smallest learned rank}. \end{aligned} }\]Training discovers the rules. Encoding follows those rules.
A small encoding example
Suppose the input chunk is
matrix
and suppose that UTF-8 represents every character here using one byte. We begin with
[m, a, t, r, i, x]
Assume that the tokenizer previously learned the following merge rules:
(m, a) rank 10
(r, i) rank 18
(ma, t) rank 25
(mat, ri) rank 50
(matri, x) rank 70
We first inspect all currently adjacent pairs:
(m, a), (a, t), (t, r), (r, i), (i, x)
The available learned pairs are (m, a) and (r, i). Because (m, a) has the smaller rank, it is merged first:
[ma, t, r, i, x]
The available pairs now include (r, i) and (ma, t). The smallest rank belongs to (r, i):
[ma, t, ri, x]
Next, (ma, t) is merged:
[mat, ri, x]
The remaining learned rules produce
[matri, x]
and finally
[matrix]
The final token is then replaced by its integer ID from the vocabulary.
This example is hypothetical. Whether matrix becomes one token, two tokens, or several tokens depends entirely on the tokenizer’s training data, vocabulary size, pre-tokenization rules, and learned merge order.
How GPT-2 used byte-level BPE
GPT-2 did not use ordinary word-level BPE. OpenAI used a byte-level BPE tokenizer.
The input text was first converted to UTF-8 bytes. Because one byte has (2^8=256) possible values, the tokenizer needed only 256 basic symbols to provide coverage of arbitrary byte sequences. Learned BPE merges then created larger tokens from frequently occurring byte sequences. OpenAI described this as a compromise between the efficiency of word-level language models and the generality of byte-level models. GPT-2 used a total vocabulary size of 50,257 tokens.
Conceptually, the pipeline was
\[\text{Unicode text} \longrightarrow \text{pre-tokenized chunks} \longrightarrow \text{UTF-8 bytes} \longrightarrow \text{BPE byte sequences} \longrightarrow \text{token IDs}.\]GPT-2 also used a regular expression before applying BPE. This pre-tokenization step separated text into chunks resembling words, numbers, punctuation, contractions, and whitespace. BPE was then applied independently within each chunk.
This restriction matters. If BPE were applied to an entire document without boundaries, it could learn undesirable tokens that arbitrarily join unrelated categories of text. OpenAI reported that directly applying BPE to unrestricted byte sequences created wasteful variations of common words combined with different punctuation. GPT-2 therefore restricted merges across character categories, while allowing spaces to remain associated with the text following them.
This is why GPT-style tokenizers often contain tokens such as
" matrix"
rather than separate tokens for
" "
"matrix"
The preceding space becomes part of the token. Consequently, the strings matrix and ` matrix` may have different token IDs.
The released GPT-2 implementation performs the following operations:
- Use a regular expression to split the input into chunks.
- Encode each chunk as UTF-8 bytes.
- Reversibly map those bytes to Unicode symbols used internally by the implementation.
- Begin with one symbol for each byte.
- Repeatedly select the adjacent pair with the smallest learned BPE rank.
- Replace that pair with its merged representation.
- Look up the resulting symbols in the token-to-ID vocabulary.
The byte-to-Unicode conversion in the original implementation should not be confused with ordinary Unicode tokenization. It was an internal reversible representation that allowed the BPE implementation to manipulate bytes as printable symbols. The underlying information was still based on UTF-8 bytes.
GPT-2 BPE and tiktoken
OpenAI’s tiktoken library is a fast implementation of BPE tokenization used with several OpenAI encodings. The general principles are similar to GPT-2’s tokenizer:
- text is split using a regular-expression pattern;
- each chunk is converted to UTF-8 bytes;
- each byte begins as an individual token;
- learned merge ranks determine which adjacent byte sequences are combined; and
- the final byte sequences are mapped to token IDs.
OpenAI’s tiktoken implementation explicitly begins with the 256 byte tokens, counts adjacent pairs during training, and repeatedly adds the most frequent pair to the vocabulary. During encoding, it instead selects the currently available pair with the smallest merge rank.
However, tiktoken is a library rather than one universal vocabulary. Different OpenAI models can use different encodings, regular-expression patterns, vocabulary sizes, special tokens, and merge ranks. Therefore, token IDs are meaningful only when the encoding is specified.
For example, this result:
[4438, 649, 358, 31370, 1403, 36295, 315, 2204, 1404, 30, 220]
is incomplete unless we also state which encoding produced it. The same text can produce different token IDs under gpt2, cl100k_base, o200k_base, or another encoding.
We can inspect both the IDs and their underlying byte sequences with tiktoken:
import tiktoken
text = "How can I multiply two matrices of different size?"
encoding = tiktoken.get_encoding("cl100k_base")
token_ids = encoding.encode(text)
token_bytes = [
encoding.decode_single_token_bytes(token_id)
for token_id in token_ids
]
print(token_ids)
print(token_bytes)
print(encoding.decode(token_ids))
The entries in token_bytes provide a more informative view than the IDs alone because they show which part of the input each token represents.
A simplified Python implementation
The following implementation demonstrates the central BPE logic. It is intentionally simpler than GPT-2 or tiktoken, but it includes the important distinction between pre-tokenization, training, and encoding.
from collections import Counter
from collections.abc import Iterable
import regex
ByteToken = bytes
Pair = tuple[ByteToken, ByteToken]
def pretokenize(text: str) -> list[str]:
"""
A simplified Unicode-aware pre-tokenizer.
Production tokenizers use more carefully designed patterns,
especially for contractions and whitespace.
"""
pattern = (
r"\s?\p{L}+"
r"|\s?\p{N}+"
r"|\s?[^\s\p{L}\p{N}]+"
r"|\s+"
)
return regex.findall(pattern, text)
def byte_symbols(piece: str) -> list[ByteToken]:
"""Represent a piece as individual UTF-8 byte tokens."""
return [bytes([value]) for value in piece.encode("utf-8")]
def count_pairs(pieces: Iterable[list[ByteToken]]) -> Counter[Pair]:
"""Count adjacent pairs without crossing piece boundaries."""
counts: Counter[Pair] = Counter()
for piece in pieces:
counts.update(zip(piece, piece[1:]))
return counts
def merge_pair(
symbols: list[ByteToken],
target: Pair,
) -> list[ByteToken]:
"""Merge non-overlapping occurrences of one adjacent pair."""
merged: list[ByteToken] = []
i = 0
while i < len(symbols):
if (
i + 1 < len(symbols)
and (symbols[i], symbols[i + 1]) == target
):
merged.append(symbols[i] + symbols[i + 1])
i += 2
else:
merged.append(symbols[i])
i += 1
return merged
def train_bpe(
corpus: str,
vocabulary_size: int,
) -> dict[Pair, int]:
"""
Learn BPE merge ranks.
Ranks 0, 1, 2, ... describe the order in which merges
were learned. A smaller rank has higher priority.
"""
if vocabulary_size < 256:
raise ValueError("Byte-level BPE requires at least 256 tokens.")
pieces = [
byte_symbols(piece)
for piece in pretokenize(corpus)
]
merges: dict[Pair, int] = {}
number_of_merges = vocabulary_size - 256
for rank in range(number_of_merges):
pair_counts = count_pairs(pieces)
if not pair_counts:
break
# A production implementation should specify a deterministic
# tie-breaking rule when multiple pairs have equal frequency.
best_pair = max(
pair_counts,
key=lambda pair: pair_counts[pair],
)
merges[best_pair] = rank
pieces = [
merge_pair(piece, best_pair)
for piece in pieces
]
return merges
def encode_piece(
piece: str,
merge_ranks: dict[Pair, int],
) -> list[ByteToken]:
"""Apply already learned BPE rules to one piece."""
symbols = byte_symbols(piece)
while len(symbols) > 1:
candidates = [
(merge_ranks[pair], pair)
for pair in zip(symbols, symbols[1:])
if pair in merge_ranks
]
if not candidates:
break
_, best_pair = min(candidates)
symbols = merge_pair(symbols, best_pair)
return symbols
def encode(
text: str,
merge_ranks: dict[Pair, int],
) -> list[ByteToken]:
"""Encode text into final BPE byte sequences."""
output: list[ByteToken] = []
for piece in pretokenize(text):
output.extend(encode_piece(piece, merge_ranks))
return output
This implementation returns byte sequences rather than integer IDs. Once the final vocabulary has been constructed, each byte sequence can be assigned an integer:
def build_vocabulary(
merge_ranks: dict[Pair, int],
) -> dict[bytes, int]:
vocabulary = {
bytes([value]): value
for value in range(256)
}
ordered_merges = sorted(
merge_ranks,
key=merge_ranks.get,
)
for token_id, (left, right) in enumerate(
ordered_merges,
start=256,
):
vocabulary[left + right] = token_id
return vocabulary
Encoding can then map the final byte tokens to their IDs:
merge_ranks = train_bpe(training_corpus, vocabulary_size=500)
vocabulary = build_vocabulary(merge_ranks)
byte_tokens = encode(
"How can I multiply two matrices of different size?",
merge_ranks,
)
token_ids = [vocabulary[token] for token in byte_tokens]
Runtime complexity
For a chunk containing \(n \) initial byte symbols, the simple encoding implementation repeatedly scans the current sequence to find the best pair and then constructs a new sequence after performing a merge.
There can be at most \(n-1\) successful merge rounds. A scan or reconstruction can require \(O(n)\) time, giving the straightforward implementation a worst-case running time of
\[O(n^2).\]This bound describes the simple implementation, not necessarily a production tokenizer. Practical implementations can use caching, linked structures, priority queues, batch processing, and optimized native code to avoid repeatedly performing all of the same work. tiktoken, for example, implements the performance-critical tokenizer logic outside ordinary Python while exposing a Python interface. Its educational implementation intentionally uses a simpler algorithm to make the merge process easier to understand.
The most important idea is not the optimization but the separation between two processes:
\[\boxed{ \text{Learn frequent merges once during tokenizer training} }\]and
\[\boxed{ \text{Reuse those fixed merge priorities when encoding every prompt}. }\]After encoding, the language model receives the token IDs, converts them to embedding vectors, and begins the Transformer computation that we will examine in the following sections.