Module 3 · Reading 3.7 (decoding half) · read before S20: Decoding & Inference

The PDF posted in Canvas is the assigned version of this reading. It is built from this page, so the text is identical; anything here marked as deep reading is optional and is not in the PDF.

This session covers the decoding half; the alignment half is the S21 reading.

A trained language model does not produce text. It produces, at each step, a probability distribution over the next token, and someone has to decide what to do with it. That decision, called decoding, is not an afterthought: the same model can sound repetitive and robotic or fluent and varied depending on how you sample from it. Decoding is also where users meet the model, through prompts — and the discovery that a pretrained model can be steered into new tasks purely through its input, with no weight updates, was one of the genuine surprises of the GPT-3 era.

This reading covers those two layers: sampling algorithms you will implement and run, and prompting and in-context learning with an honest account of what is and is not understood. The third layer, the alignment pipeline that converts a text predictor into a usable assistant, is the S21 reading.

How to read this

From distribution to token: the decoding zoo

Suppose the model, given the prefix “The cat”, assigns next-token probabilities. The choices:

  • Greedy decoding picks the argmax at every step. It is deterministic and locally optimal, but locally optimal steps do not compose into globally good text; greedy (and its lookahead cousin, beam search) is notorious for loops like “I don’t know. I don’t know. I don’t know.” Holtzman et al. (2020) documented this neural text degeneration and observed that maximizing likelihood produces text measurably unlike human writing, which routinely uses lower-probability words.
  • Temperature sampling divides the logits by a temperature \(T\) before the softmax: \(p_i \propto \exp(\text{logit}_i / T)\). \(T = 1\) recovers the model’s distribution; \(T \lt 1\) sharpens it toward the mode; \(T \gt 1\) flattens it toward uniform; \(T \to 0\) recovers greedy.
  • Top-k sampling (used prominently by Fan et al., 2018) keeps only the \(k\) most probable tokens, renormalizes, and samples. It caps how far into the tail you can wander, but a fixed \(k\) is crude: when the distribution is flat, \(k\) may be too small; when it is peaked, too large.
  • Top-p (nucleus) sampling (Holtzman et al., 2020) keeps the smallest set of top tokens whose cumulative probability reaches \(p\) (the “nucleus”) and samples within it. The kept set adapts to the distribution’s shape: broad when the model is uncertain, narrow when it is confident.

All four are a dozen lines of code, and the way to build intuition is to watch them reshape one fixed distribution:

import torch
import torch.nn.functional as F

torch.manual_seed(0)

# A fixed toy next-token distribution: pretend the model just read "The cat"
vocab = ["sat", "ran", "slept", "is", "jumped", "flew", "quantum", "lasagna"]
logits = torch.tensor([2.0, 1.5, 1.2, 0.8, 0.5, -0.5, -2.0, -3.0])
probs = F.softmax(logits, dim=-1)
print("true distribution:")
for tok, p in zip(vocab, probs):
    print(f"  {tok:>8}: {p.item():.4f}")

def sample(logits, n, temperature=1.0, top_k=None, top_p=None):
    logits = logits / temperature
    if top_k is not None:
        kth = torch.topk(logits, top_k).values[-1]
        logits = logits.masked_fill(logits < kth, float("-inf"))
    if top_p is not None:
        sorted_logits, sorted_idx = torch.sort(logits, descending=True)
        cum = torch.cumsum(F.softmax(sorted_logits, dim=-1), dim=-1)
        # keep the smallest prefix whose cumulative probability reaches top_p
        cut = torch.searchsorted(cum, torch.tensor(top_p)).item() + 1
        keep = sorted_idx[:cut]
        mask = torch.full_like(logits, float("-inf"))
        mask[keep] = logits[keep]
        logits = mask
    p = F.softmax(logits, dim=-1)
    return torch.multinomial(p, n, replacement=True)

def freq_table(samples):
    counts = torch.bincount(samples, minlength=len(vocab)).float() / len(samples)
    return "  ".join(f"{vocab[i]}:{counts[i]:.3f}"
                     for i in range(len(vocab)) if counts[i] > 0)

N = 10000
print(f"\ngreedy: always '{vocab[int(torch.argmax(logits))]}'")
for T in [0.5, 1.0, 2.0]:
    s = sample(logits, N, temperature=T)
    print(f"T={T:>3}: {freq_table(s)}")
s = sample(logits, N, top_k=3)
print(f"top-k (k=3):  {freq_table(s)}")
s = sample(logits, N, top_p=0.9)
print(f"top-p (p=0.9): {freq_table(s)}")

Running this prints:

true distribution:
       sat: 0.3721
       ran: 0.2257
     slept: 0.1672
        is: 0.1121
    jumped: 0.0830
      flew: 0.0305
   quantum: 0.0068
   lasagna: 0.0025

greedy: always 'sat'
T=0.5: sat:0.577  ran:0.218  slept:0.116  is:0.053  jumped:0.032  flew:0.004  quantum:0.000
T=1.0: sat:0.366  ran:0.226  slept:0.168  is:0.113  jumped:0.087  flew:0.031  quantum:0.007  lasagna:0.002
T=2.0: sat:0.257  ran:0.191  slept:0.165  is:0.140  jumped:0.125  flew:0.067  quantum:0.034  lasagna:0.020
top-k (k=3):  sat:0.483  ran:0.295  slept:0.222
top-p (p=0.9): sat:0.394  ran:0.230  slept:0.179  is:0.116  jumped:0.081

At T = 1.0, 10,000 samples reproduce the true distribution to within sampling noise (0.366 versus 0.3721 for “sat”). At T = 0.5 the mode’s share jumps from 0.37 to 0.58 and the tail nearly vanishes — “quantum” appears so rarely it rounds to 0.000. At T = 2.0 the distribution flattens: implausible tokens like “lasagna” rise from 0.25% to 2%. This is the whole temperature story: it trades diversity against fidelity to the model’s ranking, and it never reorders tokens. Top-k with k = 3 and top-p with p = 0.9 both truncate the tail, but notice they kept different sets (3 versus 5 tokens): the nucleus adapted to include everything down to “jumped.”

Getting top-p right

Top-p has a sneaky boundary condition, and implementations that look correct fail it. The natural first attempt (“keep tokens while cumulative probability is below \(p\)”) breaks when a single token carries more mass than \(p\): the very first cumulative sum already exceeds \(p\), nothing is kept, and the sampler crashes or silently returns garbage. The correct rule keeps the smallest prefix whose cumulative mass reaches \(p\), which means a token is dropped only if the mass before it already reached \(p\). The standard trick is to shift the cumulative sum by one position.

import torch

torch.manual_seed(0)

def top_p_filter_buggy(probs, p):
    """Keep tokens while cumulative probability stays BELOW p. Looks right; isn't."""
    sorted_p, sorted_idx = torch.sort(probs, descending=True)
    cum = torch.cumsum(sorted_p, dim=-1)
    keep = sorted_idx[cum < p]
    out = torch.zeros_like(probs)
    out[keep] = probs[keep]
    return out / out.sum() if out.sum() > 0 else out

def top_p_filter(probs, p):
    # probs: shape (V,), one next-token distribution (not a batch)
    """Smallest prefix of the sorted tokens whose cumulative probability >= p."""
    sorted_p, sorted_idx = torch.sort(probs, descending=True)
    cum = torch.cumsum(sorted_p, dim=-1)
    # shift: a token is removed only if the mass BEFORE it already reached p,
    # so the top token always survives
    remove = cum - sorted_p >= p
    keep = sorted_idx[~remove]
    out = torch.zeros_like(probs)
    out[keep] = probs[keep]
    return out / out.sum()

def show(q):
    return "[" + ", ".join(f"{v:.4f}" for v in q.tolist()) + "]"

vocab = ["yes", "no", "maybe", "perhaps", "possibly"]
p = 0.9

# Edge case: one token already carries more mass than p
probs = torch.tensor([0.97, 0.015, 0.008, 0.004, 0.003])
print(f"peaked distribution {show(probs)}, p={p}")
print(f"  buggy   -> {show(top_p_filter_buggy(probs, p))}")
print(f"  correct -> {show(top_p_filter(probs, p))}")

# Boundary case: the token that crosses p must stay in the nucleus
probs = torch.tensor([0.40, 0.25, 0.20, 0.10, 0.05])
print(f"\nflat distribution {show(probs)}, p={p}")
for name, fn in [("buggy", top_p_filter_buggy), ("correct", top_p_filter)]:
    q = fn(probs, p)
    kept = [vocab[i] for i in range(len(vocab)) if q[i] > 0]
    print(f"  {name:>7} keeps {kept} -> {show(q)}")

Running this prints:

peaked distribution [0.9700, 0.0150, 0.0080, 0.0040, 0.0030], p=0.9
  buggy   -> [0.0000, 0.0000, 0.0000, 0.0000, 0.0000]
  correct -> [1.0000, 0.0000, 0.0000, 0.0000, 0.0000]

flat distribution [0.4000, 0.2500, 0.2000, 0.1000, 0.0500], p=0.9
    buggy keeps ['yes', 'no', 'maybe'] -> [0.4706, 0.2941, 0.2353, 0.0000, 0.0000]
  correct keeps ['yes', 'no', 'maybe', 'perhaps'] -> [0.4211, 0.2632, 0.2105, 0.1053, 0.0000]

The peaked case is the killer: the buggy filter returns an all-zero distribution (every downstream multinomial call fails), while the correct filter degrades gracefully to greedy. The flat case shows a subtler discrepancy: cumulative mass hits 0.85 after three tokens and 0.95 after four, so the token that crosses p = 0.9 (“perhaps”) belongs in the nucleus, and the buggy version wrongly excludes it. Both behaviors matter in production, where samplers see millions of distributions and every edge case eventually arrives.

Pitfall. Decoding parameters are part of your experiment, not neutral plumbing. Two evaluations of the same checkpoint can differ dramatically because one used greedy decoding and the other T = 0.8, p = 0.95; benchmark scores, “creativity” impressions, and even safety behavior all shift with sampling settings. When you compare models (in a paper, in HW, or in your project), fix and report the full decoding configuration (temperature, top-k/top-p, maximum length, stop conditions, and the random seed if sampling), and when a result seems surprising, check the sampler before theorizing about the model.

Beam search and the length problem

Sampling methods draw one continuation; sometimes you want the most probable one. Finding it exactly is intractable (the number of sequences grows exponentially with length), and greedy decoding’s step-by-step argmax gives no guarantee, because the best sequence can start with a token that is not the best first step. Beam search is the classic compromise: at each step, keep the \(k\) highest-scoring prefixes (the “beam”), extend each by every possible next token, and prune back to the top \(k\). Completed sequences (those that produced an end-of-sequence token) go into a finished pool, and the final answer is the best finished hypothesis. With \(k = 1\) it collapses to greedy; as \(k\) grows it approaches exhaustive search at linear-in-\(k\) cost.

Beam search has a well-documented failure mode of its own: it prefers short outputs. Every token multiplies in another probability (adds another negative number to the log score), so a five-token sentence competes against three-token sentences with two extra penalties on its ledger. Translation systems built on beam search noticed this early, and the fix that stuck comes from Google’s 2016 neural MT system (Wu et al., 2016): divide each hypothesis’s log-probability by a length penalty \(\operatorname{lp}(Y) = \bigl((5 + \lvert Y\rvert) / 6\bigr)^{\alpha}\), where \(\lvert Y\rvert\) is the output length and \(\alpha\) (tuned, with the paper reporting values around 0.6-0.7) controls how aggressively longer outputs are favored. The toy model below is small enough to check every claim by brute force:

# Beam search on a hand-specified bigram language model, small enough to
# check against brute-force enumeration. Shows (1) greedy missing the best
# sequence, (2) why raw log-probability favors short outputs, and (3) the
# GNMT length penalty fixing the ranking.
import math
from itertools import product

# next-token distributions, conditioned on the previous token only
model = {
    "<s>":    {"the": 0.55, "a": 0.45},
    "the":    {"man": 0.25, "boat": 0.25, "sat": 0.25, "old": 0.25},
    "a":      {"boat": 0.90, "man": 0.05, "sat": 0.05},
    "man":    {"<eos>": 0.90, "sat": 0.10},
    "old":    {"man": 0.90, "<eos>": 0.10},
    "sat":    {"<eos>": 1.00},
    "boat":   {"<eos>": 0.50, "sailed": 0.50},
    "sailed": {"away": 0.95, "<eos>": 0.05},
    "away":   {"<eos>": 0.95, "sailed": 0.05},
}
MAX_LEN = 6

def logp(seq):
    """Total log-probability of a complete sequence (ends with <eos>)."""
    total, prev = 0.0, "<s>"
    for tok in seq:
        total += math.log(model[prev][tok])
        prev = tok
    return total

def beam_search(width):
    beams = [(0.0, ["<s>"])]
    finished = []
    for _ in range(MAX_LEN):
        candidates = []
        for score, seq in beams:
            for tok, p in model[seq[-1]].items():
                cand = (score + math.log(p), seq + [tok])
                (finished if tok == "<eos>" else candidates).append(cand)
        beams = sorted(candidates, reverse=True)[:width]
        if not beams:
            break
    return sorted(finished, reverse=True)

def gnmt_penalty(seq, alpha=0.7):
    """Wu et al. (2016): divide log-prob by ((5 + |Y|) / 6)^alpha."""
    n_tokens = len(seq) - 1                      # exclude <s>... count words+eos
    return ((5 + n_tokens) / 6) ** alpha

def show(seq):
    return " ".join(seq[1:-1])

# greedy = beam search with width 1
greedy = beam_search(1)[0]
wide = beam_search(3)
print(f"greedy (width 1) : '{show(greedy[1])}'  logp = {greedy[0]:.4f}")
print(f"beam (width 3)   : '{show(wide[0][1])}'  logp = {wide[0][0]:.4f}")

# brute force: enumerate every sequence up to MAX_LEN to find the true argmax
best = max(
    ((logp(list(seq) + ["<eos>"]), ["<s>"] + list(seq) + ["<eos>"])
     for L in range(1, MAX_LEN)
     for seq in product([t for t in model if t != "<s>"], repeat=L)
     if all(b in model.get(a, {}) for a, b in zip(["<s>"] + list(seq), list(seq) + ["<eos>"]))),
    key=lambda x: x[0])
print(f"exhaustive best  : '{show(best[1])}'  logp = {best[0]:.4f}")

print(f"\ntop finished hypotheses, two rankings (alpha = 0.7):")
print(f"{'sequence':>24} {'logp':>9} {'logp/penalty':>13}")
for score, seq in wide[:4]:
    print(f"{show(seq):>24} {score:>9.4f} {score / gnmt_penalty(seq):>13.4f}")
reranked = sorted(wide[:4], key=lambda x: x[0] / gnmt_penalty(x[1]), reverse=True)
print(f"\nraw ranking picks      : '{show(wide[0][1])}'")
print(f"length-penalty ranking : '{show(reranked[0][1])}'")

Running this prints:

greedy (width 1) : 'the sat'  logp = -1.9841
beam (width 3)   : 'a boat'  logp = -1.5970
exhaustive best  : 'a boat'  logp = -1.5970

top finished hypotheses, two rankings (alpha = 0.7):
                sequence      logp  logp/penalty
                  a boat   -1.5970       -1.3057
      a boat sailed away   -1.6996       -1.1886
                 the sat   -1.9841       -1.6222
             the old man   -2.1949       -1.6525

raw ranking picks      : 'a boat'
length-penalty ranking : 'a boat sailed away'

The first block is the greedy trap in miniature: “the” is the more probable first token (0.55 versus 0.45), so greedy commits to it, but everything after “the” is a flat 0.25 while “a” funnels 0.9 of its mass into “boat”; the width-3 beam finds “a boat” at log-probability -1.5970, and brute-force enumeration confirms that is the global optimum. The second block shows the length effect: “a boat sailed away” tells a more complete story at only slightly lower raw log-probability (-1.6996), because each of its extra tokens was nearly certain — yet raw ranking still puts the two-token sequence first. Dividing by the GNMT penalty flips the order. That \(\alpha\) is a tuned dial, not a principle, is worth sitting with: the “most likely output” of a generation system is partly an artifact of a normalization constant someone fit to a validation set.

Where does this leave beam search today? It remains common for tasks such as translation and speech transcription, but the best beam width and even whether beam search helps are task-, model-, metric-, and latency-dependent. Small beams such as 4–10 are conventional starting points, not universal defaults. Open-ended generation usually favors sampling.

Historical note. Beam search is decades older than neural language models. It emerged from 1970s speech-recognition research; by most accounts the term comes from CMU’s Harpy system (mid-1970s), which pruned its search of acoustic hypotheses to a “beam” of promising candidates. It was then the standard decoder in statistical machine translation throughout the 2000s. Neural MT inherited it wholesale in the mid-2010s, length penalty and all. The degeneration findings of 2019-2020 then pushed open-ended generation toward sampling, making decoding one of the rare subfields where the older technique and its replacement both remain in daily production use, each in its own niche.

Speculative decoding: faster sampling, same distribution

Autoregressive generation is often memory-bandwidth-bound at small batch sizes: producing one token streams every weight through the GPU but does little arithmetic with them, while verifying \(k\) proposed tokens in parallel costs barely more than verifying one. Speculative decoding (Leviathan et al., 2023) exploits that asymmetry: a small, fast draft model \(q\) proposes a run of tokens, the large target model \(p\) scores them all in one parallel pass, and an accept/reject rule keeps a prefix. The rule is the whole trick: accept a drafted token \(x\) with probability \(\min(1,\, p(x)/q(x))\), and on rejection sample from the residual distribution proportional to \(\max(p(x) - q(x),\, 0)\). The exact algorithm preserves the distribution of the target sampling procedure, provided probabilities, accept/reject logic, residual sampling, stopping rules, and any filters are implemented consistently. A poor draft preserves that output guarantee but lowers acceptance and can erase or reverse the speed benefit. The single-token simulation below verifies the core identity; a sequence implementation has additional bookkeeping.

# Speculative sampling in miniature. A cheap draft model q proposes a token;
# the target model p accepts it with probability min(1, p(x)/q(x)); on
# rejection we sample from the residual max(p - q, 0), renormalized.
# Claim to verify: the output distribution is EXACTLY p, for any q.
import torch

torch.manual_seed(0)

p = torch.tensor([0.55, 0.25, 0.10, 0.06, 0.04])   # target model's next-token dist

def speculative_step(p, q, gen):
    x = torch.multinomial(q, 1, generator=gen).item()      # draft proposes
    if torch.rand(1, generator=gen).item() < min(1.0, (p[x] / q[x]).item()):
        return x, True                                     # target accepts
    residual = (p - q).clamp(min=0)                        # else resample from
    residual /= residual.sum()                             # normalized excess
    return torch.multinomial(residual, 1, generator=gen).item(), False

drafts = {
    "q = p (perfect draft)": p.clone(),
    "q close to p":          torch.tensor([0.45, 0.30, 0.12, 0.08, 0.05]),
    "q far from p":          torch.tensor([0.05, 0.05, 0.10, 0.30, 0.50]),
    "q uniform":             torch.full((5,), 0.2),
}

N = 200_000
gen = torch.Generator().manual_seed(1)
print(f"target p = {[f'{v:.2f}' for v in p.tolist()]}")
print(f"{'draft model':>22} {'accept rate':>12} {'1 - TV(p,q)':>12} {'max |freq - p|':>15}")
for name, q in drafts.items():
    counts = torch.zeros(5)
    accepted = 0
    for _ in range(N):
        x, ok = speculative_step(p, q, gen)
        counts[x] += 1
        accepted += ok
    freqs = counts / N
    theory = torch.minimum(p, q).sum().item()   # E[accept] = sum_x min(p, q)
    print(f"{name:>22} {accepted / N:>12.4f} {theory:>12.4f} "
          f"{(freqs - p).abs().max().item():>15.4f}")

# Why acceptance rate is the whole game: with a draft of gamma tokens per
# target-model call, the expected number of tokens produced per call is
# (1 - a^(gamma+1)) / (1 - a) for per-token acceptance rate a.
print(f"\nexpected tokens per target-model call (draft length gamma):")
print(f"{'a':>6} {'gamma=2':>8} {'gamma=4':>8} {'gamma=8':>8}")
for a in [0.5, 0.7, 0.9]:
    row = [(1 - a ** (g + 1)) / (1 - a) for g in (2, 4, 8)]
    print(f"{a:>6} {row[0]:>8.2f} {row[1]:>8.2f} {row[2]:>8.2f}")

Running this prints:

target p = ['0.55', '0.25', '0.10', '0.06', '0.04']
           draft model  accept rate  1 - TV(p,q)  max |freq - p|
 q = p (perfect draft)       1.0000       1.0000          0.0011
          q close to p       0.8994       0.9000          0.0007
          q far from p       0.2998       0.3000          0.0012
             q uniform       0.5987       0.6000          0.0006

expected tokens per target-model call (draft length gamma):
     a  gamma=2  gamma=4  gamma=8
   0.5     1.75     1.94     2.00
   0.7     2.19     2.77     3.20
   0.9     2.71     4.10     6.13

Read the last column first: every draft matches \(p\) within sampling noise under this exact routine. “Correctness” here means preservation of the target output distribution, not zero computational cost: a bad draft spends proposal and verification work for little acceptance. The measured acceptance rate tracks its theoretical value \(\sum_x \min(p(x), q(x))\) to within sampling noise (0.8994 against 0.9000, 0.2998 against 0.3000), which is one minus the total variation distance between draft and target (the 1 - TV(p,q) column), a tidy identity linking a systems trick to a probability metric. The bottom table is an independence approximation, and realized wall-clock speedup depends on hardware, batch size, draft cost, and implementation; the Leviathan et al. paper reports 2-3x wall-clock speedups on T5-XXL.

Constrained and structured decoding

Sometimes output must satisfy hard requirements. Constrained decoding can mask tokens according to an automaton or grammar. Commercial APIs expose JSON/schema and function-calling interfaces, but providers may combine grammar masking, validation, repair, or retries; the public interface alone does not justify claiming one hidden implementation.

Two honest caveats. First, constraining changes the distribution: renormalizing over legal tokens at each step is not the same as conditioning the model’s distribution on global validity; the model may be forced down a path it assigned low probability, and greedy legality can paint it into corners (all continuations legal now, all bad later). Second, constraints interact with tokenization: a grammar over characters must be lifted to the model’s subword vocabulary, where a single token can span a boundary the grammar cares about — a fiddly translation layer, and a classic source of bugs (recall tokenization). Constrained decoding guarantees syntax, not semantics: the JSON will parse; whether its contents are right is still the model’s problem.

Prompting and in-context learning

The GPT-3 paper (Brown et al., 2020) is titled “Language Models are Few-Shot Learners” because of a then-startling observation: put a few input-output examples in the prompt (no gradient updates) and the model performs the task on a new input. The paper reports that this in-context learning improves both with model scale and with the number of demonstrations, and on some benchmarks approached fine-tuned models of the time. A prompt with \(k\) examples is called \(k\)-shot; instructions with no examples, zero-shot. Later work showed that how you prompt matters as much as what: asking models to produce intermediate reasoning steps (chain-of-thought prompting; Wei et al., 2022) substantially improves performance on multi-step problems, with the paper reporting the benefit growing with scale.

Why does in-context learning work at all? Be careful here, because the honest answer is: partially open. What can be said with support. First, next-token prediction on internet-scale text is implicitly multi-task — the corpus contains countless examples of patterns being continued, formats being followed, and instructions being obeyed, so “continue this pattern” is squarely in-distribution. Second, mechanistic work has found concrete circuits that plausibly participate: Olsson et al. (2022) describe induction heads, attention heads that find an earlier occurrence of the current token and copy what followed it, and report correlational and interventional evidence linking their formation to in-context learning ability. Third, a theoretical line of work (e.g., von Oswald et al., 2023) shows that Transformers can implement learning-algorithm-like updates (such as gradient-descent steps on a linear model) inside their forward pass in stylized settings. None of these amounts to a complete account of what a 100-billion-parameter model does with your five examples; treat confident one-sentence explanations of in-context learning with suspicion, including this paragraph’s.

A practical corollary of “the prompt is the interface”: prompt sensitivity. Reorderings of demonstrations, phrasing changes, even formatting can shift accuracy by many points on some tasks — one reason prompt-based evaluations need multiple prompts and error bars, a theme we return to in evaluation.

Common pitfalls

  • Symptom: generated text loops on a phrase indefinitely. Cause: greedy or low-temperature decoding trapped in a high-probability cycle — the degeneration failure Holtzman et al. documented. Fix: use nucleus or temperature sampling; repetition penalties help but treat symptoms, not causes.
  • Symptom: sampler crashes with “invalid multinomial distribution” on rare inputs. Cause: a top-p filter that keeps tokens strictly below the threshold, returning an empty nucleus when one token exceeds p. Fix: use the shifted-cumulative-sum implementation above and unit-test the peaked-distribution edge case.
  • Symptom: your few-shot evaluation numbers swing by several points between runs. Cause: in-context learning is sensitive to demonstration choice, order, and formatting, and sampling adds variance on top. Fix: evaluate with multiple prompt variants and seeds, and report mean and spread, not a single lucky number.

Try it yourself

  1. In the beam-search script, sweep the width over 1, 2, 3, 5 and the length-penalty alpha over 0.0, 0.7, 1.5, printing the winning sequence for each combination. At what width does the search recover the exhaustive optimum, and at what alpha does the ranking start favoring the longest hypothesis regardless of probability?
  2. Extend the decoding script to compute the empirical entropy of the samples at each temperature (\(-\sum p \log p\) of the frequency table) and plot or print entropy versus T for T in {0.25, 0.5, 1, 2, 4}.
  3. Implement min-p sampling (keep tokens whose probability is at least min_p times the top token’s probability) and compare the kept sets against top-p on both distributions from the edge-case script.
  4. Combine filters in both orders (top-k-then-temperature versus temperature-then-top-k) on the toy distribution with k = 3, T = 2.0. Do the empirical frequencies differ, and can you explain why?

Further reading

  • Holtzman et al., “The Curious Case of Neural Text Degeneration,” ICLR 2020. arxiv.org/abs/1904.09751 — the degeneration study that motivated nucleus sampling; its Figure 1 alone justifies the whole decoding zoo.
  • Wu et al., “Google’s Neural Machine Translation System,” 2016. arxiv.org/abs/1609.08144 — Section 7 defines the length penalty our beam-search example uses.
  • Leviathan, Kalman, Matias, “Fast Inference from Transformers via Speculative Decoding,” ICML 2023. arxiv.org/abs/2211.17192 — the accept/reject scheme our simulation implements, with the acceptance-rate and speedup analysis.
  • Brown et al., “Language Models are Few-Shot Learners,” NeurIPS 2020. arxiv.org/abs/2005.14165 — the paper that made prompting a research topic; skim Section 3 for the few-shot evaluation format.
  • Olsson et al., “In-context Learning and Induction Heads,” Transformer Circuits Thread, 2022. transformer-circuits.pub/2022/in-context-learning-and-induction-heads/index.html — the mechanistic evidence on how in-context learning might work.
  • d2l.ai, “Beam Search” (decoding fundamentals). d2l.ai/chapter_recurrent-modern/beam-search.html — a textbook walkthrough with figures, complementary to our from-scratch implementation.

Before class you should be able to

  • Predict how temperature, top-k, and top-p each reshape a given next-token distribution
  • Spot the buggy top-p implementation and explain the edge case that breaks it
  • Explain why greedy decoding can miss the most probable sequence, and what beam width trades
  • State what the GNMT length penalty corrects and why the bias exists
  • State speculative decoding’s correctness guarantee and what the acceptance rate controls
  • Define k-shot prompting and in-context learning, and why prompt sensitivity demands error bars
  • List the decoding settings you must fix and report when comparing models

Connects to

  • This session is covered by Quiz 3 (Module 3: S13–S22), given at S23.
  • HW3 (due at S22): the sampling implementations here are directly reusable for generating text from your Transformer.
  • Project evaluations that involve generation should fix and report the full decoding configuration — a rubric-relevant habit from this reading.

← S19 · Fine-Tuning & LoRA · All readings · S21 · Alignment: SFT, RLHF, DPO →