Tokenization, Embeddings & Language Modeling

1. The Tokenization Problem

Tokenization converts raw text into a sequence of discrete symbols (tokens) that a language model can process. The quality of tokenization fundamentally impacts model performance, as it determines the granularity at which the model processes information.

1.1 Desiderata for Tokenization

1. Deterministic: Same input always produces same tokens
2. Reversible: Tokens can be losslessly converted back to text
3. Compact: Frequent patterns are single tokens
4. Semantically coherent: Tokens correspond to meaningful units
5. Language-agnostic: Works across multiple languages

2. Byte Pair Encoding (BPE)

2.1 Algorithm

BPE (Sennrich et al., 2016) is a greedy tokenization algorithm that iteratively merges the most frequent pair of adjacent symbols.

Initialization: Start with a vocabulary of individual characters:

Merge iteration: At each step :

1. Count all adjacent pairs in the tokenized corpus:

1. Find the most frequent pair:

1. Merge all occurrences of into a new token :

1. Replace all instances in the corpus:

Termination: After merges (or when all pairs have count 1).

2.2 BPE Example

Initial: l o w _ </w>  (5 tokens, 4 pairs)

Iteration 1: Most frequent pair is (e, r) → merge to "er"
Iteration 2: Most frequent pair is (er, </w>) → merge to "er</w>"
Iteration 3: Most frequent pair is (l, o) → merge to "lo"
...
Final vocabulary: {l, o, w, e, r, er, er</w>, lo, low, ...}

2.3 BPE Merge Visualization

2.4 BPE Complexity

Time complexity: where is the number of merges and is the corpus size. With efficient data structures (priority queues), this can be reduced to for the counting step.

2.5 Byte-level BPE

GPT-2 introduced byte-level BPE, operating on UTF-8 bytes rather than Unicode characters:

This ensures any text can be tokenized without unknown tokens, as every character has a byte representation.

3. WordPiece

3.1 Algorithm

WordPiece (Schuster & Nakajima, 2012) differs from BPE in its merge criterion. Instead of merging the most frequent pair, WordPiece merges the pair that maximizes the language model likelihood:

This is equivalent to maximizing the pointwise mutual information (PMI):

3.2 WordPiece vs BPE

4. SentencePiece

4.1 Overview

SentencePiece (Kudo & Richardson, 2018) is a language-agnostic tokenizer that treats the input as a raw stream of characters (including spaces). It treats space as a special character (▁) and can perform BPE or unigram tokenization.

4.2 Unigram Language Model

SentencePiece also implements the unigram algorithm, which starts with a large vocabulary and prunes:

At each step, remove the token whose removal least impacts the corpus likelihood:

where the log-likelihood is:

5. Word Embeddings

5.1 Word2Vec

Word2Vec (Mikolov et al., 2013) learns embeddings through prediction tasks:

Skip-gram: Predict context words given a center word:

where is the context window size and:

CBOW: Predict center word from context:

Negative sampling (efficient approximation):

where is the unigram distribution raised to the 3/4 power.

5.2 GloVe

GloVe (Pennington et al., 2014) learns embeddings from global co-occurrence statistics.

Co-occurrence matrix: = number of times word appears in the context of word .

Objective function:

where:

• are the word and context vectors
• are bias terms
• is a weighting function with and

5.3 GloVe Co-occurrence Visualization

6. Contextual Embeddings

6.1 From Static to Contextual

Static embeddings (Word2Vec, GloVe) assign a fixed vector to each word regardless of context:

Contextual embeddings (ELMo, BERT, GPT) produce context-dependent representations:

where depends on the entire input sequence.

6.2 Transformer Embedding Layer

For a token with vocabulary embedding and position :

where is the positional encoding function.

7. Positional Encodings

7.1 Sinusoidal Encodings

Original Transformer (Vaswani et al., 2017):

Properties:

• Unique encoding for each position
• Relative positions can be learned as linear transformations
• Fixed (not learned), generalizes to unseen sequence lengths

7.2 Learned Positional Embeddings

where is a learned embedding matrix. Limited to positions.

7.3 Rotary Position Embeddings (RoPE)

RoPE (Su et al., 2021) encodes position by rotating the embedding vector in 2D subspaces:

For a position and dimension pair :

where are frequency parameters.

Key property: The dot product between two rotated vectors depends only on their relative position:

This means attention scores naturally decay with relative distance.

7.4 RoPE Rotation Visualization

f(x, m) = R(m) · x, where R(m) = diag(R₀(mθ₀), R₁(mθ₁), ..., R_{d/2-1}(mθ_{d/2-1}))

7.5 ALiBi (Attention with Linear Biases)

ALiBi (Press et al., 2022) adds a linear bias to attention scores based on distance:

where is a head-specific slope. The attention score becomes:

ALiBi slopes are set as geometric sequence:

for head out of total heads.

Advantages:

• No learned parameters
• Extrapolates to longer sequences
• Simple to implement

8. Tokenization Impact on Model Performance

8.1 Compression Ratio

The compression ratio measures how efficiently tokenization represents text:

Higher CR means the model sees more text per token, effectively increasing context window size.

8.2 Vocabulary Size Tradeoffs

8.3 Multilingual Challenges

Different languages have different morphological structures:

• Isolating (Chinese): minimal morphology, characters map to words
• Agglutinative (Turkish): long words from many morphemes
• Fusional (English): moderate morphology

BPE/WordPiece handle this by learning language-specific merges, but tokenizer quality varies across languages.

9. Implementation

from tokenizers import Tokenizer, models, trainers, pre_tokenizers

def train_bpe_tokenizer(corpus_files, vocab_size=32000):
    tokenizer = Tokenizer(models.BPE())

    # Byte-level BPE (GPT-2 style)
    tokenizer.pre_tokenizer = pre_tokenizers.ByteLevel(
        add_prefix_space=False
    )

    trainer = trainers.BpeTrainer(
        vocab_size=vocab_size,
        special_tokens=["<|pad|>", "<tool_call>", "</tool_call>"],
        min_frequency=2,
        show_progress=True
    )

    tokenizer.train(corpus_files, trainer)
    return tokenizer

# Usage
tokenizer = train_bpe_tokenizer(["corpus.txt"], vocab_size=32000)
encoded = tokenizer.encode("Hello, world!")
print(encoded.tokens)  # ['Hello', ',', 'Ġworld', '!']
print(encoded.ids)     # [15339, 11, 995, 0]

RoPE Implementation

import torch
import math

class RotaryPositionalEmbedding(torch.nn.Module):
    def __init__(self, dim, max_seq_len=2048, base=10000):
        super().__init__()
        self.dim = dim
        inv_freq = 1.0 / (base ** (torch.arange(0, dim, 2).float() / dim))
        self.register_buffer("inv_freq", inv_freq)

        t = torch.arange(max_seq_len).float()
        freqs = torch.outer(t, inv_freq)
        emb = torch.cat([freqs, freqs], dim=-1)
        self.register_buffer("cos_cached", emb.cos())
        self.register_buffer("sin_cached", emb.sin())

    def forward(self, x, seq_len):
        return (
            self.cos_cached[:seq_len],
            self.sin_cached[:seq_len]
        )

def apply_rotary_pos_emb(q, k, cos, sin):
    q_rot = q * cos + rotate_half(q) * sin
    k_rot = k * cos + rotate_half(k) * sin
    return q_rot, k_rot

def rotate_half(x):
    x1, x2 = x.chunk(2, dim=-1)
    return torch.cat([-x2, x1], dim=-1)

10. References

1. Sennrich et al. (2016). "Neural Machine Translation of Rare Words with Subword Units." ACL.
2. Kudo & Richardson (2018). "SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing." EMNLP.
3. Mikolov et al. (2013). "Efficient Estimation of Word Representations in Vector Space." ICLR.
4. Pennington et al. (2014). "GloVe: Global Vectors for Word Representation." EMNLP.
5. Su et al. (2021). "RoFormer: Enhanced Transformer with Rotary Position Embedding." arXiv.
6. Press et al. (2022). "Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation." ICLR.