Curriculum

Week 12. Sampling strategies

Phase 3. Inference, GPUs, scaling · week 12 of 24

Learn in the app: tutor, coding problems →

Core: temperature, top-k, top-p, min-p, beam search, repetition penalties · Depth: constrained decoding and grammars, typical sampling · ≈ 10 h core / 19 h total

The model outputs a distribution; the selection rule decides what text you get. The same model with greedy decoding and with top-p is two different products: the first repeats itself, the second sometimes spouts nonsense from the tail. This whole week is about cutting off the tail of the distribution without killing diversity.

Step 1. The shape of the distribution

In plain terms. Logits (the model's raw scores before softmax) [2, 1, 0]. At temperature 1 the probabilities are [0.67, 0.24, 0.09]. Temperature 0.5 doubles the logits: [0.87, 0.12, 0.02], and the leader takes almost everything. Temperature 2 halves them: [0.51, 0.31, 0.19], and the choice is nearly random. The order of the tokens never changes; only how sharply the leader pulls away from the rest.

• Greedy, temperature, top-k, top-p (nucleus), min-p, typical sampling. Temperature: softmax(l/T); entropy grows with T: as T → 0 you get argmax and entropy 0, as T → ∞ a uniform distribution and log V. Typical sampling keeps the tokens whose "surprise" −log p is close to the entropy of the distribution

In plain terms. 1000 tokens: 5 good ones at 0.1 each (0.5 together) and 995 junk ones sharing the remaining 0.5 (0.0005 each). top-p = 0.9 has to collect a mass of 0.9: the five good ones give 0.5, and it makes up the other 0.4 with roughly 800 junk tokens. min-p = 0.1 sets a threshold of 0.1 × 0.1 = 0.01 relative to the leader and keeps exactly the five good ones. On a peaked distribution both behave the same; the difference shows only on a flat one.

• top-k cuts by token count and knows nothing about the model's confidence; top-p cuts by cumulative mass; min-p by the threshold p_i ≥ min_p · p_max, with no sorting. Order matters: temperature first, then the filters, because both the top-p mass and the min-p threshold depend on temperature. In sample_from_logits: temperature → top-k → min-p → top-p → softmax → sample

Step 2. Search and penalties

• Beam search: why it is good for translation and bad for open-ended generation. It keeps the b best prefixes by summed log-probability, that is, it searches for the single most probable text. In translation the answer is almost determined by the input, and the mode of the distribution is a good answer. In open-ended generation the most probable text is dull and loops: repeating a phrase makes it even more probable. It also needs length normalization
• Repetition / presence / frequency penalty. Repetition is multiplicative: a positive logit is divided by the penalty, a negative one is multiplied. Presence subtracts a constant if the token has already appeared. Frequency subtracts a constant × the number of occurrences. The first two cannot tell one repeat from ten; the third can

Step 3. Constrained generation

In plain terms. You need JSON. At the first step, the logits of all tokens that cannot start JSON are replaced with −inf. The model physically cannot choose anything else. From then on a grammar automaton remembers where we are: inside a string, after a key, after a comma. At each step it allows only valid continuations.

• Constrained decoding: JSON schemas, grammars, logit processors (functions that edit the logits before sampling). The hard part is that tokens do not line up with grammar symbols: one token may close a string and open the next key. That is why the "state → allowed tokens" table is built ahead of time. Syntax is guaranteed, content is not, and step-by-step masking distorts the distribution
• The link to calibration and distribution entropy: the same temperature calibrates a classifier's confidence (temperature scaling), and the per-step entropy is a cheap signal of the model's uncertainty

Common mistakes

• In top-p, also dropping the token at which the mass crossed the threshold: on a peaked distribution the output is empty. Caught by test_top_p_always_keeps_at_least_one; a non-adaptive cut is caught by test_top_p_adapts_to_confidence
• Forgetting to restore the original order after sorting in top-p. The tests in test_sampling.py feed already sorted logits and barely catch this; check it yourself on shuffled ones
• Dividing a negative logit by the penalty: it grows; caught by test_repetition_penalty_lowers_seen_tokens. Dividing by T = 0: caught by test_temperature_zero_is_greedy. Keeping more than k: caught by test_top_k_keeps_exactly_k

Code → nanolm/sampling.py: all strategies from scratch, one interface sample_from_logits(logits, **kwargs): apply_temperature, top_k_filter, top_p_filter, min_p_filter, apply_repetition_penalty. The task is in exercises_en/sampling.py: NANOLM_IMPL=exercises_en pytest tests/test_sampling.py -v. nanolm has no beam search; write it on top of NanoLM and compare it with sampling on the same prompt.

Math (Track D): D15: Gumbel-max, sampling from softmax as the argmax of noisy logits; D16: the maximum and minimum of n variables, the tail formula and memorylessness.

Interview question of the week: "The model in production gets stuck in a loop and repeats a paragraph. What do you tune?" A 3-minute structure: check the mode (greedy, low T, beam) → the likelihood trap → temperature and min-p/top-p → frequency penalty, not presence → measure (share of repeated n-grams, distinct-n) → check that factual accuracy has not dropped → if the repetitions are in the data too, fix the data.

Sources: Holtzman et al., The Curious Case of Neural Text Degeneration (2019); Meister et al., Typical Decoding (2022); Nguyen et al., min-p (2024); Willard & Louf, Outlines (2023).

Deeper: 05-ГЛУБИНА, section "Small additions", row "Week 12".

Week outcomes

• I can implement greedy, temperature, top-k, top-p and min-p behind one interface, sample_from_logits(logits, **kwargs).
• I can show on two distributions, a flat one and a peaked one, how top-p differs from min-p.
• I can explain why beam search tends to repeat itself in open-ended generation.
• I can explain how logit masking guarantees valid JSON.

Self-check

1. What happens to the entropy of the distribution as T → 0 and T → ∞?
2. How does frequency penalty differ from presence penalty?
3. Why do latency and throughput conflict when choosing the batch size?