Decoding Strategies: Temperature, Sampling, and Constrained Generation

Language model generation is fundamentally a search problem: at each step, the model assigns a probability to every token in its vocabulary (typically 32,000–128,000 tokens), and the decoding strategy decides which token to select next.

The model outputs raw logits — unnormalized scores for each vocabulary token. These are converted to probabilities via softmax: p(token_i) = exp(logit_i) / Σ exp(logit_j). A logit of 5.0 for "dog" and 3.0 for "cat" gives probabilities of 0.88 and 0.12 respectively. The decoding strategy then samples or selects from this distribution.

The key insight most engineers miss: the model's logit distribution captures its "beliefs" about what token should come next given all prior context. This distribution is fixed once the forward pass is complete. Decoding parameters do not change what the model knows or believes — they only change how we sample from the distribution the model already produced. Temperature=0.1 and temperature=1.0 query the exact same logit distribution; temperature only sharpens or flattens that distribution before sampling.

This has a critical implication: if the model assigns 40% probability to a wrong answer and 35% to a correct answer, lowering the temperature to near-zero will confidently select the wrong answer. Temperature cannot fix a model that has the wrong beliefs — only training can do that.

Three fundamental decoding families:

1. Deterministic: always select the same token (greedy, beam search). Reproducible, consistent, inflexible.
2. Stochastic sampling: sample from the probability distribution (temperature, top-k, top-p). Diverse, creative, variable.
3. Constrained decoding: modify the logit distribution to enforce output structure before sampling. Guarantees format compliance.

Greedy decoding selects the single highest-probability token at each step: token_t = argmax p(token | context). It is deterministic (same input always produces the same output), fast (no additional computation beyond the forward pass), and consistent.

Where greedy fails: greedy is myopic. It maximizes local probability at each step without considering how that choice affects future tokens. A token that is slightly less probable now might enable a much more probable sequence later. The classic failure: "I want to go to the store to buy [milk]" — greedy selects "milk" (probability 0.4) but the ground truth is "groceries" which would have enabled a higher-probability continuation. Over long sequences, greedy accumulates suboptimal choices, leading to generic, repetitive text.

Beam search maintains B=4 (or B=8) hypotheses in parallel. At each step, it expands all B beams by considering the top tokens, scores each expanded hypothesis by total log-probability, and keeps the top-B. This is approximate tree search over the token sequence.

Length normalization: without it, beam search systematically prefers shorter sequences (longer sequences accumulate lower log-probabilities from multiplying many values < 1). The fix: divide the total log-probability by sequence length^α, where α ≈ 0.6–0.7. Too low α: still prefers short sequences. Too high α: prefers nonsensically long sequences.

Why beam search ≠ better for open-ended generation: Holtzman et al. (2020) show that beam search produces text that is more likely according to the model but less preferred by humans for open-ended generation. High-probability text is predictable and generic. Human-preferred text explores lower-probability continuations that are surprising and natural. Beam search optimizes the wrong objective for creative tasks. Use beam search for: machine translation, summarization with high factual requirement, code generation where you want the most likely correct solution. Do not use for: dialogue, creative writing, any open-ended generation.

Temperature modifies the softmax before sampling. The standard softmax is p_i = exp(logit_i) / Σ exp(logit_j). Temperature-scaled softmax is p_i = exp(logit_i / T) / Σ exp(logit_j / T).

Effect of temperature:

• T → 0: dividing by a very small number amplifies differences between logits. The highest-logit token gets probability ~1.0; all others get ~0. Equivalent to greedy decoding. Deterministic, repetitive, conservative.
• T = 1.0: original model distribution unchanged. Samples as the model "intends."
• T > 1.0: dividing by a number > 1 compresses the logit differences. The distribution flattens toward uniform. All tokens become equally likely. At T = ∞, the distribution is exactly uniform — every token in the vocabulary has the same probability.

The non-obvious insight: temperature doesn't change the model's beliefs — it only sharpens or flattens the probability distribution. At T=0.1, the model is not "more confident" — the logits are identical. You are just sampling more deterministically from the same distribution. This means T=0.1 and T=1.0 will produce different outputs but both can be equally "correct" given a model with well-calibrated probabilities. T=0.1 samples the model's most likely response; T=1.0 samples a more representative response.

Practical guidance:

• T=0 (or 0.0): code generation, structured extraction, factual QA — where correctness matters and diversity does not.
• T=0.3–0.5: summarization, translation — low diversity acceptable, slight variation to avoid repetition.
• T=0.7–0.9: dialogue, Q&A assistants — natural variation without becoming incoherent.
• T=1.0–1.2: creative writing, brainstorming, story generation — maximize diversity.
• T > 1.5: generally incoherent for most models. Use only for intentional randomness or ablation studies.

The problem with pure temperature sampling: even at T=0.8, the full vocabulary can be sampled from — 50,257 tokens for GPT-2, 128,256 for LLaMA-3. This includes tokens with probability 0.000001 that produce incoherent continuations. Truncation samplers solve this by restricting sampling to a high-probability subset.

Top-k sampling: sort tokens by probability, keep the top-k, renormalize, sample. Simple, fast. The problem: k is a fixed count, which is inappropriate when the probability distribution has different shapes. When the model is uncertain (flat distribution), k=50 might still include only 30% of the probability mass. When the model is highly confident (peaked distribution), k=50 might include tokens with probabilities as low as 0.00001 — introducing incoherence.

Nucleus / top-p sampling (Holtzman et al. 2020): instead of a fixed count, keep the minimal set of tokens that covers at least p% of the probability mass. If p=0.9, include tokens until their cumulative probability reaches 0.9. When the model is confident, this might be just 2–3 tokens. When uncertain, it might be 500 tokens. The cutoff adapts to the model's certainty. Top-p=0.9–0.95 is the production standard for most generation tasks.

Min-p sampling (2024): a newer approach that has shown strong empirical performance for creative tasks. Include token i if and only if its probability exceeds p_min × max_prob, where max_prob is the probability of the most likely token. This is a relative threshold: if the top token has probability 0.6 and p_min=0.1, include all tokens with probability ≥ 0.06. When the top token is highly probable (peaked distribution), the threshold is high — few tokens included. When no token is dominant (flat distribution), the threshold is low — more tokens included. Min-p better preserves coherence than top-p at high temperatures and outperforms top-p on creative writing benchmarks according to Llama community evaluations.

Combining parameters: in production, top-p and temperature are used together. Temperature=0.8 + top-p=0.9 is more controlled than temperature=0.8 alone because top-p cuts off low-probability nonsense. Temperature=1.2 + top-p=0.95 enables high diversity while staying within the nucleus. The order of operations: apply temperature to logits → compute softmax probabilities → apply top-p (or top-k or min-p) truncation → renormalize → sample.

Repetition in generated text is a common failure mode, especially with greedy decoding and long outputs. At each step, the model's highest-probability next token is often the same token it just generated — "the the the the" in pathological cases, or more subtly, repeating the same phrase every few sentences.

Two distinct penalty mechanisms (from GPT-4 API parameters):

Presence penalty (range -2.0 to 2.0, typical use: 0.1–0.6): subtracts a fixed value from the logit of any token that has appeared at least once in the output. A token seen once gets the same penalty as a token seen ten times. Effect: reduces the probability of reusing any previously used token, regardless of how many times it was used. Good for: encouraging diverse vocabulary, reducing any repetition. Bad for: necessary repetitions (code variable names, proper nouns) are penalized the same as filler words.

Frequency penalty (range -2.0 to 2.0, typical use: 0.1–0.4): subtracts a value proportional to how many times the token has appeared. A token seen once gets a small penalty; seen five times gets a 5× larger penalty. Effect: allows tokens to appear 1–2 times naturally but discourages them from dominating the output. More nuanced than presence penalty. Good for: long-form generation where some repetition is acceptable but spiraling repetition is not.

Production recommendations:

• Code generation: presence_penalty=0, frequency_penalty=0. Penalties disrupt variable name consistency and break syntactic patterns.
• Dialogue: presence_penalty=0.1–0.2. Discourages the model from repeating the same phrase it used two turns ago.
• Long-form creative writing: frequency_penalty=0.2–0.4. Allows natural repetition of key nouns but prevents paragraphs that recycle the same vocabulary.
• Never use penalties > 0.8 — aggressive penalties make the model avoid even correct token choices and degrade output quality significantly.

Instruction-based format constraints ("always output JSON") achieve ~85–90% compliance in practice. For production systems where downstream code parses the output, 10–15% failure rate is unacceptable.

Constrained decoding solves this by modifying the logit distribution at each generation step. At step t, a finite-state machine (or LALR parser for grammars) tracks which tokens are valid given the tokens generated so far. Invalid tokens get logit = -∞ (effectively zero probability). The model can only generate tokens that advance the finite state machine toward a valid final state.

Outlines library (dottxt-ai): the leading open-source constrained decoding library. Accepts a Pydantic model or a regex and compiles it into a token-level finite-state machine. At each step, it masks the logit vector to allow only valid next tokens. Compatible with llama.cpp, vLLM, and Hugging Face Transformers.

Key insight: constrained decoding doesn't change the model's behavior for the valid parts of the output — it only prevents structurally invalid tokens. The model still makes its own choices among the valid tokens. So a constrained-decoded JSON output will have the correct schema but the content of each field still depends on the model's generation quality.

OpenAI and Anthropic alternatives: for API-served models, function calling / tool use provides similar guarantees without requiring local model hosting. The API enforces schema conformance server-side. The main limitation: you cannot use arbitrary regex constraints — only the JSON schema format they support.

When constrained decoding adds meaningful latency: for schemas with many possible valid tokens at each step (large JSON schemas, complex grammars), the finite-state machine lookup adds ~5–15% overhead per token. For simple schemas (enums, fixed-format outputs), overhead is < 2%. Not a significant concern for most production use cases.