LLMs and Generative AI β€Ί The LLM Landscape β€Ί Day 243

Day 243: Tokens, Context Windows, and Sampling

Day 243 of 365 β€” 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.

Course
LLMs and Generative AI
Category
The LLM Landscape
Reading time
β‰ˆ 35 min
Practical time
β‰ˆ 50 min
Lesson duration
1h 25m
Last verified
2026-08-29

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

  1. 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
  2. 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
  3. 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.
  4. 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:

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:

  1. It ingests the prompt tokens.
  2. It projects queries, keys, and values through 80 Transformer layers.
  3. It stores Key and Value tensors in GPU VRAM (The KV Cache).
  4. It computes a probability distribution across $128,000$ possible vocabulary tokens.
  5. It applies mathematical logit transformations (Temperature, Top-$k$, Top-$p$, Repetition Penalties).
  6. It samples exactly 1 token.
  7. 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

Diagram: how text is split into tokens for a language model

Think of an author improvising a story in front of a live audience:


Historical background

Diagram: the historical progression of text tokenisation methods

Visual comparison of LLM sampling strategies comparing Greedy, Temperature, Top-k, and Nucleus Top-p sampling

  1. 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…”).
  2. 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.
  3. 2022 (FlashAttention & Dao et al.): Optimized attention memory traffic, laying the hardware foundation for multi-thousand token KV caching.
  4. 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:

What it is NOT:


Why it was created and what problems it solves

Decoding strategies solve critical generation failure modes:

  1. Degenerative Repetition Loops: Prevents models from repeating the same sentence indefinitely when stuck in high-probability loops.
  2. Hallucination Suppression in Deterministic Tasks: Ensures code, JSON, and math extraction select the exact optimal tokens without stochastic noise ($T=0$).
  3. 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

Diagram: how raw model outputs become a single sampled token

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:


2. KV Cache Mechanics & Memory Footprint

Diagram: how attention cache memory grows with context length and concurrency

KV cache memory scaling and generation dynamics diagram showing prefill vs token-by-token autoregressive decoding

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)


3. Prefill vs. Generation: The Hardware Chasm

Diagram: prompt processing compared with token generation by hardware behaviour

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   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?


5. Grouped-Query Attention (GQA) & KV-Cache Compression

Diagram: how grouped-query attention reduces cached attention state

In standard Multi-Head Attention (MHA), every query head has its own Key and Value head ($H_Q = H_K = H_V = 64$).


6. Tokenizer Mechanics & Language Fertility Ratios

Why does tokenization quality determine latency, cost, and cross-lingual performance?


An everyday analogy

Diagram: speaking without revision compared with writing with revision

Think of a chef cooking a 10-course banquet:


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

Diagram: the reproducibility, cost, safety and testing implications of probabilistic sampling

  1. 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).
  2. 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 StrategyParameter TuningPrimary AdvantageBest Use Case
Greedy Argmax$T = 0$100% DeterministicCode, Math, SQL, JSON
Top-p Nucleus$T = 0.7, p = 0.9$Natural BalanceGeneral Chat & Reasoning
Min-P Sampling$T = 0.8, min_p = 0.05$Adaptive ConfidenceCreative Writing, Roleplay
Beam Search$beams = 4$Global OptimalityTranslation, Summarization

Diagram: probabilistic sampling compared with beam search

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   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

Diagram: when varied sampling is appropriate and when deterministic output is required

When to Use Temperature & Top-p Tuning:

When NOT to use:


The AI connection

Knowledge check

  1. How does Temperature scaling alter the entropy of the Softmax distribution?
  2. What is the fundamental difference between Top-$k$ filtering and Top-$p$ Nucleus sampling?
  3. Why is autoregressive token decoding memory-bandwidth bound on GPUs?
  4. How is the total VRAM required for the Key-Value (KV) cache calculated?
  5. 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

Common mistakes


Practice assignment

  1. Implement Min-P Sampling in PyTorch and compare its output token diversity against Top-$p$ sampling across 1,000 simulated generation steps.
  2. 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:

Quiz

Q1. How does Temperature scaling (z_i / T) affect the Softmax output probability distribution of an LLM?

  1. T below 1 sharpens; above 1 flattens the distribution
  2. Temperature controls the physical heat of the GPU
  3. Temperature increases the context window size
  4. 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)?

  1. Sampling only punctuation tokens
  2. Keep the smallest set whose probability mass reaches p
  3. Selecting the top 10 tokens regardless of probability
  4. 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?

  1. Because tokenizers use too much RAM
  2. Because CPUs do not have memory
  3. Each token reloads all weights and the KV cache
  4. 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?

  1. KV_bytes = VocabSize * SeqLen
  2. KV_bytes = BatchSize * 1,000
  3. KV_bytes = ModelParams * 6
  4. 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?

  1. Drop tokens below min_p times the top probability
  2. Selecting the minimum probability token to maximize chaos
  3. Minimizing the price of API calls
  4. 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


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.