LLMs and Generative AI βΊ The LLM Landscape βΊ Day 243
Day 243: Tokens, Context Windows, and Sampling
Master the runtime mechanics of autoregressive language models: understand BPE tokenization quirks across languages and code, calculate exact KV-cache VRAM consumption (2 * B * S * L * H * D), compare compute-bound prompt prefill with memory-bandwidth bound token decoding, implement probabilistic sampling transformations (Temperature scaling, Top-k, Nucleus Top-p, Min-P, and Repetition penalties), and build a modular sampling engine in PyTorch.
Hands-on lab for this lesson
Lab files on GitHub: https://github.com/ai-roadmap-365/ai-roadmap-365.github.io/tree/main/labs/sections/llms-and-generative-ai/day-243-tokens-context-windows-and-sampling
- Get the hands-on files. Clone the labs repository once (you can reuse this clone for every lesson). This works on macOS, Linux, and Windows (PowerShell or WSL):
git clone https://github.com/ai-roadmap-365/ai-roadmap-365.github.io.git cd ai-roadmap-365.github.io - Open this lesson's lab. Move into the directory for this specific day. Every lab lives at the same predictable path β section / subsection / week / day:
cd labs/sections/llms-and-generative-ai/day-243-tokens-context-windows-and-sampling - Read the lab guide. Open `README.md` in that directory. It lists the exact commands, what each does, the expected output, and how to check your work β read it before running anything.
- Run it and check your work. Follow the README's "How to run" section: run the example first to see the finished result, then complete the numbered exercises in `starter/`, then run the tests. The tests pass (exit 0) only when your work is correct.
bash tests/run_tests.sh # or the test command named in the lab README
You can also open the lab as a local page (works offline, shows the file tree and expected output).
Learning objectives
By the end of this lesson you will be able to:
- Calculate exact KV-cache memory requirements for LLM inference across model configurations and batch sizes.
- Contrast compute-bound prompt prefill (GEMM) with memory-bandwidth bound token generation (GEMV).
- Implement Temperature logit scaling: z_i / T and understand its impact on entropy and determinism.
- Implement Top-k and Top-p (Nucleus) cumulative mass logit masking in PyTorch.
- Apply frequency and presence repetition penalties to eliminate degenerative loops in generation.
Prerequisites
Why this matters
When an LLM outputs text on your screen, it is not generating complete sentences in a single flash of computation.
It is running a tight, highly optimized, sequential mathematical loop:
- It ingests the prompt tokens.
- It projects queries, keys, and values through 80 Transformer layers.
- It stores Key and Value tensors in GPU VRAM (The KV Cache).
- It computes a probability distribution across $128,000$ possible vocabulary tokens.
- It applies mathematical logit transformations (Temperature, Top-$k$, Top-$p$, Repetition Penalties).
- It samples exactly 1 token.
- It appends that token to the context and repeats the loop!
Understanding this generation cycle is the difference between an amateur who wonders why their model generates repetitive gibberish, and a Senior AI Engineer who can tune sampling hyperparameters for deterministic code extraction ($T=0$), optimize KV-cache memory allocation, and prevent degenerative token loops.
Today, you will master the mathematics of probabilistic sampling, calculate exact KV-cache VRAM consumption, and build a complete customizable sampling engine in PyTorch.
The idea in plain language
Think of an author improvising a story in front of a live audience:
- The Context Window & Memory (The KV Cache): A whiteboard behind the author recording every character, plot point, and spoken dialogue from the beginning of the book. If the whiteboard runs out of space (Context Limit), the author suffers amnesia and forgets earlier plotlines.
- Greedy Decoding ($T=0$): The author always picks the single most statistically predictable word. Highly reliable for a math proof, but boring and robotic for creative fiction.
- High Temperature ($T=1.5$): The author drinks 4 shots of espresso. They pick wild, unexpected, bizarre adjectives and metaphors (High Entropy).
- Top-$p$ Nucleus Sampling: The author considers only words that make coherent sense ($90%$ cumulative probability mass). If the next word is obvious (e.g. βThe Eiffelβ¦β), they only consider βTowerβ. If the plot is at a crossroads, they consider a dozen creative paths!
Historical background
- Early NLP (Beam Search & Greedy): Machine translation relied on Beam Search, which seeks the globally optimal joint sequence probability. However, when applied to open-ended text generation, beam search caused models to fall into repetitive loops (βI donβt know, I donβt know, I donβt knowβ¦β).
- 2019 (Holtzman et al. & Nucleus Sampling): Published The Curious Case of Neural Text De-generation, proving that human text does not follow maximum probability paths. They introduced Top-$p$ (Nucleus) sampling, revolutionizing natural language generation.
- 2022 (FlashAttention & Dao et al.): Optimized attention memory traffic, laying the hardware foundation for multi-thousand token KV caching.
- 2024 (Min-P Sampling & Grouped-Query Attention): Community researchers introduced Min-P sampling as an adaptive alternative to Top-$p$, while foundation models adopted Grouped-Query Attention (GQA) to slash KV-cache sizes by $8\times$.
What it is β and what it is not
What LLM Sampling IS:
- Controlled Stochastic Selection: Transforming raw logit outputs $z \in R^[V]$ into a filtered, normalized probability distribution from which candidate tokens are drawn.
What it is NOT:
- Not Pure Randomness: Sampling is strictly constrained by the modelβs learned probability manifold. Setting temperature to $0.7$ does not produce random dictionary words; it samples from the modelβs top plausible continuations.
Why it was created and what problems it solves
Decoding strategies solve critical generation failure modes:
- Degenerative Repetition Loops: Prevents models from repeating the same sentence indefinitely when stuck in high-probability loops.
- Hallucination Suppression in Deterministic Tasks: Ensures code, JSON, and math extraction select the exact optimal tokens without stochastic noise ($T=0$).
- VRAM Exhaustion Management: Allows infrastructure engineers to budget precise GPU memory for concurrent user sessions based on sequence length.
How it works
Let us dissect the mathematical formulation of probabilistic sampling, repetition penalties, and KV-cache scaling.
1. The Probabilistic Sampling Pipeline
Given raw output logits $z = [z_1, z_2, β¦, z_V]$ from the final Linear classification head over vocabulary $V$:
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β LLM LOGIT TRANSFORMATION PIPELINE β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 1. Raw Logits: z_i β
β 2. Repetition Penalties: z_i = z_i - (freq * f_pen) - (pres * p_pen) β
β 3. Temperature Scaling: z_i' = z_i / T β
β 4. Top-k Truncation: keep top K logits; set rest to -infinity β
β 5. Top-p (Nucleus) Masking: keep cumulative mass sum >= P β
β 6. Min-P Truncation: discard tokens where P_i < min_p * P_max β
β 7. Softmax Normalization: P_i = exp(z_i') / sum(exp(z_j')) β
β 8. Categorical Draw: sample token w ~ Categorical(P) β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Mathematical Formulas:
-
Temperature Scaling ($T > 0$):
P(w_i) = \frac{\exp(z_i / T)}{\sum_{j=1}^V \exp(z_j / T)}- As $T \to 0$: $P(w_[max]) \to 1.0$ (Greedy argmax).
- As $T \to \infty$: $P(w_i) \to 1/V$ (Uniform random noise).
-
Top-$p$ (Nucleus) Condition: Find the smallest index set $S \subset (1, β¦, V)$ such that:
\sum_{i \in S} P(w_i) \ge p \quad \text{and} \quad \forall i \in S, j \notin S: P(w_i) \ge P(w_j) -
Frequency & Presence Penalties (OpenAI formulation):
z_i^{\text{penalized}} = z_i - (c_i \times \text{penalty}_{\text{freq}}) - (\mathbb{I}(c_i > 0) \times \text{penalty}_{\text{pres}})Where $c_i$ is the count of how many times token $i$ has already appeared in the output sequence.
2. KV Cache Mechanics & Memory Footprint
During self-attention at layer $l$, token $t$ must attend to all previous tokens $1, β¦, t-1$. Instead of recomputing key and value vectors $K_(1:t-1)$ and $V_(1:t-1)$ on every generation step, they are cached in GPU VRAM!
The KV Cache VRAM Equation:
For a model with $L$ layers, $H_[KV]$ key-value attention heads, head dimension $D$, batch size $B$, and sequence length $S$, using FP16/BF16 ($2 bytes per element$):
\text{KV Cache Size (Bytes)} = 2 \times B \times S \times L \times (H_{KV} \times D) \times 2\text{ bytes}
(The leading factor of 2 accounts for both Keys and Values).
Concrete Example: LLaMA-3-70B (Grouped-Query Attention)
-
Layers $L = 80$, $H_[KV] = 8$ heads, $D = 128$, Precision = 2 bytes (BF16):
-
Per-Token KV Footprint:
\text{KV per token} = 2 \times 80 \times (8 \times 128) \times 2 = 327,680\text{ bytes} \approx 320\text{ KB per token} -
For an 8,192 Context Sequence (Batch = 1):
320\text{ KB} \times 8,192 = 2.62\text{ GB of VRAM per active request!} -
For Batch Size = 32 at 8k Context: The KV cache alone consumes $83.8 GB of GPU VRAM$βexceeding the memory of an entire NVIDIA A100 GPU!
3. Prefill vs. Generation: The Hardware Chasm
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β PREFILL VS. DECODING COMPARISON β
ββββββββββββββββββββββ¬βββββββββββββββββββββββββ¬βββββββββββββββββββββββββββ€
β Attribute β Prompt Prefill Phase β Token Decoding Phase β
ββββββββββββββββββββββΌβββββββββββββββββββββββββΌβββββββββββββββββββββββββββ€
β Operation β GEMM (Matrix-Matrix) β GEMV (Matrix-Vector) β
β Input Size β All Prompt Tokens (N) β Exactly 1 Token β
β Hardware Bottleneckβ Compute-Bound (TFLOPS) β Memory-Bandwidth (HBM) β
β Arithmetic Intens. β High (> 100 FLOP/byte) β Very Low (~1 FLOP/byte) β
β Hardware Saturationβ > 65% Tensor Core MFU β < 5% Tensor Core MFU β
ββββββββββββββββββββββ΄βββββββββββββββββββββββββ΄βββββββββββββββββββββββββββ
4. Speculative Decoding: Beating the Memory-Bandwidth Wall
Because autoregressive decoding is memory-bandwidth bound ($1$ token per forward pass), how can we accelerate generation without modifying the target model weights?
- The Speculative Protocol (Leviathan et al., 2023):
-
A small, fast βdraft modelβ (e.g. LLaMA-3-8B) speculatively generates $K = 5$ tokens autoregressively.
-
The massive βtarget modelβ (e.g. LLaMA-3-70B) evaluates all $5$ candidate tokens simultaneously in a single parallel forward pass (GEMM)!
-
The target model verifies each token using Rejection Sampling:
\alpha = \min\left(1, \frac{P_{\text{target}}(x_{t+k})}{P_{\text{draft}}(x_{t+k})}\right) -
If a token is rejected, generation branches and continues from the target modelβs corrected token.
-
- Speedup: Achieves $2\times$ to $3\times$ lower latency with zero degradation in output distribution!
5. Grouped-Query Attention (GQA) & KV-Cache Compression
In standard Multi-Head Attention (MHA), every query head has its own Key and Value head ($H_Q = H_K = H_V = 64$).
- The GQA Innovation (Ainslie et al., 2023): Multiple query heads share a single Key and Value head ($H_Q = 64, H_[KV] = 8$).
- The Impact: Slashes the KV-cache memory footprint by an exact factor of $8\times$, enabling massive context lengths (128k tokens) on commodity GPU memory with less than $0.5%$ loss in benchmark accuracy!
6. Tokenizer Mechanics & Language Fertility Ratios
Why does tokenization quality determine latency, cost, and cross-lingual performance?
- Byte Pair Encoding (BPE): Merges frequent subword byte sequences into vocabulary tokens (vocabulary sizes typically $128k$ in modern models).
- The Fertility Ratio: The average number of tokens generated per word.
- In English, 1,000 words $\approx 1,300$ tokens (fertility $\approx 1.3$).
- In non-Latin scripts (Hindi, Arabic, Thai) with legacy tokenizers, 1,000 words could generate $3,500+$ tokens (fertility $> 3.5$), resulting in $3\times$ higher latency and cost! Modern expanded vocabularies ($128k$ in LLaMA-3) achieved cross-lingual token parity.
An everyday analogy
Think of a chef cooking a 10-course banquet:
- Prompt Prefill Phase (The Prep Kitchen): Chopping 50 pounds of vegetables, preparing broths, and marinating meats all at once with full staff efficiency (High Parallelism / Compute Bound).
- Token Decoding Phase (Plating Courses One by One): Delivering Course 1, waiting for the guest to take a bite, carrying the plate back, delivering Course 2β¦ No matter how fast the chef is, they must walk back and forth for every single forkful (Memory-Bandwidth Bound / Latency Bound).
Examples in practice
Let us build a Complete PyTorch Probabilistic Sampling Engine:
import torch
import torch.nn.functional as F
from typing import Optional, List
class LLMSampler:
def __init__(self, temperature: float = 0.7, top_k: int = 50, top_p: float = 0.9,
min_p: float = 0.0, freq_penalty: float = 0.0, pres_penalty: float = 0.0):
self.temperature = max(temperature, 1e-5)
self.top_k = top_k
self.top_p = top_p
self.min_p = min_p
self.freq_penalty = freq_penalty
self.pres_penalty = pres_penalty
def sample_next_token(self, logits: torch.Tensor, generated_tokens: Optional[List[int]] = None) -> int:
logits = logits.clone().float()
# 1. Apply Repetition Penalties
if generated_tokens and (self.freq_penalty > 0 or self.pres_penalty > 0):
counts = torch.bincount(torch.tensor(generated_tokens), minlength=logits.shape[-1])
logits = logits - (counts * self.freq_penalty) - ((counts > 0).float() * self.pres_penalty)
# 2. Temperature Scaling
logits = logits / self.temperature
# 3. Top-k Filtering
if self.top_k > 0:
topk_vals, _ = torch.topk(logits, min(self.top_k, logits.shape[-1]))
min_topk = topk_vals[-1]
logits[logits < min_topk] = -float('inf')
# 4. Top-p (Nucleus) Filtering
if 0.0 < self.top_p < 1.0:
sorted_logits, sorted_indices = torch.sort(logits, descending=True)
cumulative_probs = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)
# Remove tokens with cumulative probability above top_p threshold
sorted_indices_to_remove = cumulative_probs > self.top_p
sorted_indices_to_remove[1:] = sorted_indices_to_remove[:-1].clone()
sorted_indices_to_remove[0] = False
indices_to_remove = sorted_indices[sorted_indices_to_remove]
logits[indices_to_remove] = -float('inf')
# 5. Softmax & Categorical Sample
probs = F.softmax(logits, dim=-1)
next_token = torch.multinomial(probs, num_samples=1).item()
return int(next_token)
Implications: security, privacy, performance, scalability, and cost
- Greedy Determinism vs. Non-Deterministic GPU Atomic Addition:
- Even with $T=0$, multi-GPU distributed serving (vLLM Tensor Parallelism) can produce non-deterministic token variations across runs due to floating-point non-associativity in parallel reduction operations (
cublasGemm).
- Even with $T=0$, multi-GPU distributed serving (vLLM Tensor Parallelism) can produce non-deterministic token variations across runs due to floating-point non-associativity in parallel reduction operations (
- Context Window Degradation (βLost in the Middleβ):
- Empirical studies show that LLMs retrieve facts from the very beginning and very end of a context window with high fidelity, but exhibit lower recall for facts located in the middle $40%-60%$ range.
Alternatives: free, open source, and commercial
| Decoding Strategy | Parameter Tuning | Primary Advantage | Best Use Case |
|---|---|---|---|
| Greedy Argmax | $T = 0$ | 100% Deterministic | Code, Math, SQL, JSON |
| Top-p Nucleus | $T = 0.7, p = 0.9$ | Natural Balance | General Chat & Reasoning |
| Min-P Sampling | $T = 0.8, min_p = 0.05$ | Adaptive Confidence | Creative Writing, Roleplay |
| Beam Search | $beams = 4$ | Global Optimality | Translation, Summarization |
Comparison with related concepts
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β SAMPLING PARAMETER CHEAT SHEET β
ββββββββββββββββββββββ¬ββββββββββββββββββ¬βββββββββββββββββββ¬βββββββββββββββ€
β Task Type β Temperature (T) β Top-p (Nucleus) β Rep. Penalty β
ββββββββββββββββββββββΌββββββββββββββββββΌβββββββββββββββββββΌβββββββββββββββ€
β Code & Unit Tests β 0.0 (Greedy) β 1.0 (Disabled) β 0.0 β
β Math Proofs & Logicβ 0.1 - 0.2 β 0.95 β 0.0 β
β General Assistant β 0.7 β 0.90 β 0.1 β
β Creative Fiction β 0.9 - 1.1 β 0.95 β 0.2 β
ββββββββββββββββββββββ΄ββββββββββββββββββ΄βββββββββββββββββββ΄βββββββββββββββ
When to use it β and when not to
When to Use Temperature & Top-p Tuning:
- Every production LLM application! Correct sampling parameter selection is mandatory to ensure code generators are deterministic while chat assistants sound engaging.
When NOT to use:
- Do not apply high temperature ($T > 0.5$) or heavy repetition penalties to JSON or structured database queries, as repetition penalties will penalize closing brackets (
)) and quotes ("), causing malformed JSON syntax errors!
The AI connection
- Tokens are the unit of both cost and capability, so understanding them explains pricing, context limits and several odd model behaviours at once.
- Sampling parameters change output character more than most prompt edits do, which makes them a first-class product setting rather than a tuning detail.
- The attention cache is what bounds concurrency, so serving capacity is a memory question rather than a compute one.
- Tokenisation is unequal across languages, which means identical content costs several times more in some languages than in English.
- Generation is memory-bandwidth bound, which is why batching and speculative methods work and why raw arithmetic throughput does not help.
Knowledge check
- How does Temperature scaling alter the entropy of the Softmax distribution?
- What is the fundamental difference between Top-$k$ filtering and Top-$p$ Nucleus sampling?
- Why is autoregressive token decoding memory-bandwidth bound on GPUs?
- How is the total VRAM required for the Key-Value (KV) cache calculated?
- Why should repetition penalties be disabled or minimized when generating structured JSON schemas?
Hands-on exercise
In this lab, you will build and test a modular probabilistic sampling and KV-cache calculation engine in PyTorch: implement Temperature scaling, Top-$k$ masking, Top-$p$ Nucleus truncation, frequency repetition penalties, and calculate exact KV-cache VRAM consumption across model architectures.
Expected output
[Tokens, Context Windows, and Sampling Verification Suite]
Testing KV-Cache Memory Calculator:
Model: LLaMA-3-70B (80 Layers, 8 KV Heads, Dim 128, BF16)
Context: 8,192 Tokens (Batch Size = 1) -> 2.62 GB VRAM [EXACT MATCH]
Context: 8,192 Tokens (Batch Size = 32) -> 83.89 GB VRAM [SCALING VERIFIED]
Testing Probabilistic Sampling Engine:
Greedy Mode (T = 0): Selected Token Index = 42 (P = 0.85) [100% DETERMINISTIC]
High Temp Mode (T = 1.5): Flattened Distribution (Entropy Increased)
Top-p Masking (p = 0.90): Retained Top 3 Tokens, Set 127,997 Tail Logits to -inf
Repetition Penalty: Reduced Token 42 Logit from 10.5 to 6.5 after 2 Occurrences
Test Suite: 3 passed in 0.43s
Validate your work
Run the automated test runner:
./tests/run_tests.sh
Troubleshooting
- When applying Top-$p$ masking, ensure the highest-probability token is never masked out, even if its single probability exceeds $p$.
Common mistakes
- Applying temperature after Softmax: Temperature scaling MUST divide raw logits before computing the Softmax exponential.
Practice assignment
- Implement Min-P Sampling in PyTorch and compare its output token diversity against Top-$p$ sampling across 1,000 simulated generation steps.
- Build an interactive KV-Cache Sizing Calculator CLI that accepts model parameters ($L, H, D$) and outputs maximum batch concurrency on 80GB GPUs.
Extension challenge
Implement a Toy Speculative Decoding Engine:
- Build a Python simulator where a 1B draft model generates 4 speculative candidate tokens, and a 70B target model evaluates all 4 tokens in a single parallel forward pass using rejection sampling.
Quiz
Q1. How does Temperature scaling (z_i / T) affect the Softmax output probability distribution of an LLM?
- T below 1 sharpens; above 1 flattens the distribution
- Temperature controls the physical heat of the GPU
- Temperature increases the context window size
- Temperature converts words into ASCII codes
Show answer
Answer: A. T below 1 sharpens; above 1 flattens the distribution
Temperature rescales logits prior to Softmax: low T sharpens peaks, high T flattens the distribution.
Q2. What is Top-p (Nucleus) sampling (Holtzman et al., 2019)?
- Sampling only punctuation tokens
- Keep the smallest set whose probability mass reaches p
- Selecting the top 10 tokens regardless of probability
- A technique for training neural networks on radioactive nuclei
Show answer
Answer: B. Keep the smallest set whose probability mass reaches p
Nucleus sampling dynamically selects the smallest set of tokens whose cumulative mass reaches threshold p.
Q3. Why is autoregressive token generation in LLMs classified as Memory-Bandwidth Bound rather than Compute-Bound?
- Because tokenizers use too much RAM
- Because CPUs do not have memory
- Each token reloads all weights and the KV cache
- Because hard drives are too slow
Show answer
Answer: C. Each token reloads all weights and the KV cache
Token decoding performs low-FLOP vector-matrix multiplies per memory byte loaded, saturating HBM memory bandwidth.
Q4. How is the total VRAM required for the Key-Value (KV) cache calculated for an LLM sequence?
- KV_bytes = VocabSize * SeqLen
- KV_bytes = BatchSize * 1,000
- KV_bytes = ModelParams * 6
- 2 * batch * length * layers * heads * dim * bytes
Show answer
Answer: D. 2 * batch * length * layers * heads * dim * bytes
KV cache stores 2 tensors (Key and Value) per layer, proportional to batch size, sequence length, and hidden dimension.
Q5. What is the purpose of the Min-P sampling strategy introduced as an alternative to Top-p?
- Drop tokens below min_p times the top probability
- Selecting the minimum probability token to maximize chaos
- Minimizing the price of API calls
- Reducing prompt length
Show answer
Answer: A. Drop tokens below min_p times the top probability
Min-P truncates tokens whose probability is below a fraction min_p of the top token probability.
Glossary
- KV Cache
- Key-Value Cache: storing the computed key and value attention activation tensors for all previous tokens in GPU VRAM to avoid quadratic recomputation during generation.
- Temperature (T)
- A hyperparameter scaling raw model logits (z_i / T) before the Softmax function to control output randomness and entropy.
- Top-k Sampling
- A decoding strategy restricting token sampling to the top k highest probability tokens, masking out all lower-ranked tokens.
- Top-p (Nucleus) Sampling
- A decoding strategy restricting token sampling to the smallest dynamic subset of tokens whose cumulative probability mass exceeds threshold p.
- Min-P Sampling
- A sampling filter discarding tokens whose probability is lower than min_p times the probability of the most likely candidate token.
- Presence Penalty
- A fixed logit penalty subtracted from any token that has appeared at least once in the generated output to encourage topic exploration.
- Frequency Penalty
- A proportional logit penalty subtracted based on the exact frequency count of a token in the generated output to prevent repetitive loops.
- Prompt Prefill Phase
- The initial compute-bound forward pass processing the entire prompt in parallel, generating the initial KV cache and first output token.
Sources and further reading
- The Curious Case of Neural Text De-generation (Nucleus Sampling) β ICLR 2020 (accessed 2026-08-29)
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness β NeurIPS 2022 (accessed 2026-08-29)
- Efficient Memory Management for Large Language Model Serving with PagedAttention β SOSP 2023 (accessed 2026-08-29)
Kept in this browser, no account needed. Your progress page turns the whole record into one link you can bookmark or open on another device.