AskAiml
Sign in Get started

Sampling and decoding

Greedy, beam, temperature, top-k, top-p, and the sampling choices that shape output quality.

⚑ Module 5 7 min read Not started

Why this matters

You have a trained model. It outputs a probability distribution over the next token. Now what? The choice of decoding strategy β€” greedy, beam, top-k, top-p, temperature, mirostat, contrastive β€” determines whether your model feels creative, terse, repetitive, or off-the-rails. Every API parameter (temperature, top_p, frequency_penalty, seed) maps to a decoding decision.

Master these, and you can debug "the model keeps repeating itself" or "outputs are too generic" in seconds.

Learning objectives

  1. Implement greedy, beam, top-k, top-p, and temperature sampling.
  2. Reason about what each parameter changes.
  3. Understand structured-output sampling (constrained / grammar-based).
  4. Implement the OpenAI-compatible sampling parameters from scratch.
  5. Recognise modern variants (mirostat, contrastive, min-p, Ξ·-sampling).

1. The setup

After the final layer, the model produces logits z ∈ R^V (one per vocabulary token). We turn that into the next token via a decoding policy.

python
def decode_step(logits, **kwargs) -> int:
    """Return the next token id."""
    ...

2. Greedy decoding

python
def greedy(logits): return int(logits.argmax(-1))

Always pick the most probable token. Deterministic. Used for:

  • Translation (BLEU loves it).
  • Classification / extraction (no creativity needed).
  • Tool calls where determinism matters.

Pathology: repetition. ("The cat sat on the mat. The cat sat on the mat.")

Track the top-B running sequences ranked by joint probability:

At step t:
  for each beam:
    expand by every token; keep top-B over all beams.

Used by translation/summarisation (T5, BART, NMT). Generally avoided in chat-style LLMs because it produces bland, "averaged" text. Doesn't model human-like variation.

Modern note: Beam search of width 4-10 still wins on translation eval; for chat, sampling wins.

4. Temperature

Rescale logits before softmax:

p_i = softmax(z_i / T)
  • T = 1: original distribution.
  • T β†’ 0: argmax (greedy).
  • T > 1: flatter, more random.
  • T < 1: sharper, more confident.

Typical chat: T = 0.7-1.0. For deterministic tool use: T = 0.0 (and pin a seed).

python
def softmax_T(logits, T):
    return F.softmax(logits / max(T, 1e-6), dim=-1)

5. Top-k sampling

Restrict to the k highest-probability tokens; renormalise; sample.

python
def top_k(logits, k):
    v, _ = torch.topk(logits, k)
    logits = torch.where(logits < v[-1], torch.tensor(-float("inf")), logits)
    return torch.multinomial(F.softmax(logits, -1), 1).item()

Removes the long tail of low-probability garbage. Typical k = 40-100. Simple and effective.

6. Top-p (nucleus) sampling

Take the smallest set whose cumulative probability β‰₯ p, then sample from those.

python
def top_p(logits, p):
    sorted_logits, idx = torch.sort(logits, descending=True)
    sorted_probs = F.softmax(sorted_logits, dim=-1)
    cum = sorted_probs.cumsum(-1)
    cutoff = (cum > p).nonzero()[0].item() + 1
    sorted_logits[cutoff:] = -float("inf")
    final = torch.full_like(logits, -float("inf"))
    final.scatter_(0, idx, sorted_logits)
    return torch.multinomial(F.softmax(final, -1), 1).item()

Adapts to context: if the model is confident (peaked distribution), few tokens; if uncertain (flat), more.

Typical p = 0.9-0.95. Often combined with top-k: top_p=0.95, top_k=40.

7. Min-p (Nguyen 2024)

Keep tokens with probability β‰₯ min_p Γ— max_prob. Robust to flat distributions; popular in 2024-2025 open-source serving.

python
def min_p(logits, min_p):
    probs = F.softmax(logits, -1)
    cutoff = min_p * probs.max()
    logits = torch.where(probs < cutoff, torch.tensor(-float("inf")), logits)
    return torch.multinomial(F.softmax(logits, -1), 1).item()

Often gives better quality than top-p with simpler tuning. Default in many community llama.cpp configs.

8. Repetition / frequency / presence penalties

OpenAI / HF expose:

  • frequency_penalty: subtract Ξ± Γ— count(token) from logits.
  • presence_penalty: subtract Ξ± once if token appeared at all.

These reduce loops without hurting fluency. Typical: 0.0-0.5.

python
def apply_freq_penalty(logits, history, penalty):
    counts = torch.bincount(history, minlength=logits.size(-1)).float()
    logits = logits - penalty * counts
    return logits

9. Combining everything (the typical pipeline)

python
def sample_step(logits, history, T=0.8, top_p=0.95, top_k=40,
                rep_penalty=0.0, min_p=0.0):
    if rep_penalty:
        logits = apply_freq_penalty(logits, history, rep_penalty)
    logits = logits / max(T, 1e-6)
    if top_k > 0:
        v, _ = torch.topk(logits, top_k)
        logits = torch.where(logits < v[-1], torch.tensor(-float("inf")), logits)
    if 0.0 < top_p < 1.0:
        logits = filter_top_p(logits, top_p)        # as above
    if min_p > 0.0:
        logits = filter_min_p(logits, min_p)
    probs = F.softmax(logits, -1)
    return torch.multinomial(probs, 1).item()

This is essentially what transformers.generate(do_sample=True, ...) and vLLM's SamplingParams do under the hood.

10. Logits bias and constrained generation

You can force tokens by adding a large positive (or negative) bias before sampling:

python
forced_tokens = [json_open_brace_id]
logits[forced_tokens] += 50.0

Modern frameworks generalise this:

  • Outlines / Guidance / JSONFormer β€” compile a JSON schema or regex into a finite-state automaton; at each step, mask all logits that would violate the grammar. Used to guarantee structured outputs.
  • Lark grammars β€” sample any token sequence in a context-free grammar.
  • Logit processors (HF) β€” generic LogitsProcessor interface.

Example with Outlines:

python
import outlines
from pydantic import BaseModel

class Person(BaseModel):
    name: str
    age: int

m = outlines.models.transformers("HuggingFaceTB/SmolLM2-1.7B-Instruct")
gen = outlines.generate.json(m, Person)
print(gen("Alice is 32 years old."))

The model cannot produce invalid JSON because the sampler masks every illegal token.

11. Mirostat and contrastive decoding (for completeness)

  • Mirostat (Basu et al., 2021): dynamically adjusts top-k each step to keep the running cross-entropy near a target value. Reduces repetition; reduces tail-of-distribution garbage.
  • Contrastive decoding (Li et al., 2022): sample from log p_large(x) - Ξ± log p_small(x) to suppress generic small-model tokens. Used in some research; not common in production.

You will rarely set these in a real product, but you may see them in benchmark configs.

12. Best-of-N and self-consistency (sampling at the system level)

Beyond per-token decoding, you can also:

  • Best-of-N: sample N completions, score them with a verifier or reward model, return the best. Used in retrieval-augmented QA, math.
  • Self-consistency (Wang et al., 2022): sample N CoT chains, take the majority answer. Used heavily for math/reasoning. Cheap and effective.

These are decoding strategies at a higher level and are part of what reasoning models exploit at test-time (Phase 4).

Hands-on lab (3 hours)

sampling_lab.ipynb:

  1. Load Qwen2.5-1.5B-Instruct. Generate 5 completions for the same prompt with T=[0.0, 0.5, 1.0, 1.3, 1.7]. Discuss qualitative differences.
  2. Implement top_k, top_p, min_p from scratch. Compare outputs for the same seed and prompt.
  3. Plot a histogram of next-token probabilities for a peaked vs flat context. Show how each filter behaves.
  4. Use outlines to force JSON output of {"name": str, "age": int}. Verify every generation parses.
  5. Implement self-consistency on 3 GSM8K problems: sample 8 chains, majority-vote the answer. Measure accuracy gain vs single sample.
  6. Bonus: implement frequency + presence penalties; generate a 500-token completion and show repetition drops.

Common pitfalls

  1. temperature=0 with top_p<1.0 β€” pointless; T=0 is already greedy.
  2. Setting top_p=0.0 thinking it means "no truncation" β€” it means only the most probable token. Use 1.0 to disable.
  3. Frequency penalty too high β†’ robot speak ("a brown dog the cat said it ran fast was").
  4. Beam search on chat β€” bland averaged text. Use sampling.
  5. Mixing structured-output libraries that bypass the model's chat template β€” outputs look right but the model thinks it is mid-sentence.

Self-check

  1. Difference between top-k and top-p?
  2. What does temperature 0 do?
  3. What is min-p, and why prefer it sometimes over top-p?
  4. How do constrained-output libraries (Outlines, Guidance) work mechanically?
  5. What does self-consistency exploit?

References

  • Holtzman et al. (2019), "The Curious Case of Neural Text Degeneration" (top-p / nucleus).
  • Fan et al. (2018), "Hierarchical Neural Story Generation" (top-k).
  • Nguyen et al. (2024), "Min-p Sampling: Balancing Creativity and Coherence at High Temperature."
  • Wang et al. (2022), "Self-Consistency Improves Chain of Thought Reasoning in Language Models."
  • Outlines docs.
  • HuggingFace LogitsProcessor docs.

Sign in to save your progress and earn badges.