Tokens and Tokenization

1. Tokenization Fundamentals

1.1 Vocabulary Representation

A tokenizer operates as a bijective lookup between a finite vocabulary of subwords \(V\) and integer identifiers \(\{0, 1, \dots, |V|-1\}\). Modern vocabulary sizes typically range from \(|V| = 32,000\) (Llama 2) to \(|V| = 128,256\) (Llama 3/4) and \(|V| = 256,000\) (Gemma). Each token index corresponds to an embedding vector in the model's input projection matrix \(W_e \in \mathbb{R}^{|V| imes d_{ ext{model}}}\).

In standard English text corpora, 1,000 tokens represent approximately 750 words (an average compression ratio of 1.33 tokens per word, or roughly 4 characters per token) [1].

1.2 Subword Tokenization Algorithms

Modern language models rely on three primary subword segmentation algorithms:

• Byte-Pair Encoding (BPE): Introduced to NLP by Sennrich et al. [2], BPE begins with a base vocabulary of individual characters or bytes. It iteratively counts the most frequent adjacent symbol pairs in the training corpus and merges them into new vocabulary entries until a target vocabulary size \(|V|\) is reached.
• Byte-Level BPE (BBPE): Introduced by Radford et al. [3] for GPT-2, BBPE treats input text as an arbitrary sequence of raw bytes (256 base tokens). This guarantees that any Unicode string or binary sequence can be tokenized without generating out-of-vocabulary (<unk>) tokens.
• WordPiece: Used in BERT [4], WordPiece chooses pair merges that maximize the likelihood of the training data under a unigram language model, rather than relying solely on raw frequency.
• Unigram Language Model: Used in SentencePiece [5] and T5, Unigram starts with an oversized vocabulary and iteratively removes subwords that have the lowest marginal impact on corpus likelihood.

2. Token Lifecycle and Processing Phases

2.1 Prefill (Input) vs. Decode (Output)

Transformer execution splits into two computationally distinct phases [6]:

• Prefill Phase (Input Tokens): All input prompt tokens are processed simultaneously in parallel. The operation is compute-bound, saturating GPU tensor cores (matrix-matrix multiplication, GEMM). During prefill, Key (\(K\)) and Value (\(V\)) activation tensors for all prompt tokens are computed and written to GPU high-bandwidth memory (HBM).
• Decode Phase (Output Tokens): Output tokens are generated sequentially, one at a time, autoregressively. Each step requires reading the entire accumulated KV cache from HBM for a single vector-matrix multiplication (GEMV). The decode phase is memory-bandwidth bound, resulting in lower hardware utilization.

2.2 Thinking and Reasoning Tokens

Hybrid reasoning models (e.g., DeepSeek-R1, Gemini 3.7 Flash Thinking, OpenAI o3) introduce thinking tokens. These are internal chain-of-thought tokens generated during test-time compute prior to emitting final responses [7]. Thinking tokens allow models to explore alternative verification paths, backtrack from logic errors, and perform self-correction. While thinking tokens are generated in the decode phase (and billed at output rates), they are typically hidden or masked from final user-facing text.

2.3 Special and Control Tokens

Tokenizers include dedicated non-printing control tokens that delineate structural boundaries:

• Sequence Boundary: <|begin_of_text|>, <|end_of_text|>, <|im_start|>, <|im_end|>.
• Tool Execution: <|call:tool_name|>, <|start_header_id|>, indicating structured tool invocations.
• Padding & Masking: <|pad|> for batch alignment and <|mask|> for masked language modeling.

3. KV Cache Scaling and Attention Mechanics

3.1 Memory Footprint Formulation

To avoid recomputing self-attention projections for past tokens at each decode step, models store the Key (\(K\)) and Value (\(V\)) tensors in a dynamic KV Cache. For a standard Multi-Head Attention (MHA) model, the memory required for the KV cache scales linearly with sequence length \(L\) [8]:

where \(B\) is batch size, \(L\) is context length, \(n_{ ext{layers}}\) is the number of transformer layers, \(d_{ ext{model}}\) is the hidden dimension, and the factor of 2 accounts for both \(K\) and \(V\) matrices. In FP16 precision (2 bytes per element), a 70B parameter model with a 128,000-token context requires approximately 160 GB of dedicated memory solely for a single user's KV cache.

3.2 Attention Architectures: MHA, MQA, and GQA

To mitigate the memory scaling bottleneck of Multi-Head Attention, modern architectures compress the key and value heads [9]:

• Multi-Head Attention (MHA): Each query head has an independent key and value head (\(h_q = h_k = h_v\)).
• Multi-Query Attention (MQA): All query heads share a single key head and a single value head (\(h_k = h_v = 1\)), reducing KV cache memory by a factor of \(h_q\).
• Grouped-Query Attention (GQA): Query heads are partitioned into \(g\) groups, with each group sharing one key and value head (\(h_k = h_v = g\)). GQA (used in Llama 3/4, Mistral, and DeepSeek) recovers nearly all MHA representation capacity while reducing KV cache size by 4x to 8x.

4. Token Economics and Prompt Caching

4.1 Cost Asymmetry Across Token Types

API pricing across commercial model providers is structured around the computational cost differential between the prefill and decode phases [10]:

• Input Tokens (Cache Miss): Moderately priced ($0.10 to $3.00 per 1M tokens) due to parallel prefill execution efficiency.
• Output & Thinking Tokens: Priced 3x to 5x higher ($0.30 to $15.00 per 1M tokens) due to recurrent memory bandwidth constraints during autoregressive decoding.
• Cached Input Tokens (Cache Hit): Discounted by 75% to 95% ($0.007 to $0.30 per 1M tokens) because precomputed KV tensors are retrieved directly from memory without GPU recomputation.

4.2 Prefix Prompt Caching

Prompt caching (implemented via PagedAttention in vLLM [8] and proprietary cloud gateways) identifies exact prefix matches in token sequences. When an agent executes multiple sequential turns sharing an identical system prompt, codebase index, or context history, the inference engine skips the prefill transformer layers entirely for the cached prefix.

Prefix caching reduces Time-To-First-Token (TTFT) latency by up to 80% and enables continuous autonomous agent loops to operate with marginal token budgets under $0.01 per turn [10].

5. Tokenizer Failure Modes and Artifacts

Because tokenizers process subwords rather than raw semantic concepts, several characteristic failure modes emerge in language models [11]:

• Arithmetic Degradation: Numbers are tokenized arbitrarily based on digit frequency (e.g., "12345" may be split as [12, 345] while "12346" is split as [123, 46]). This inconsistent chunking impairs character-level arithmetic and digit alignment.
• Character and Spelling Blindness: Tasks such as counting specific letters in a word (e.g., "How many rs in strawberry?") fail frequently because the model receives the entire subword token (["straw", "berry"]) rather than individual constituent letters.
• Non-Latin Script Token Inflation: Vocabularies optimized heavily on English corpora tokenize non-Latin scripts (e.g., Cyrillic, Arabic, Tagalog, Japanese) into multiple single-byte tokens per character. This causes a 2x to 5x increase in token consumption and inference cost for identical semantic content.
• Glitch Tokens: Vocabulary tokens trained on anomalous internet scrape patterns (e.g., Reddit usernames like SolidGoldMagikarp) occupy ungrounded regions of the embedding space, causing erratic completions when triggered [11].