Decoding Algorithms

The right runbook passage in context still isn't the final answer. A language model has to turn its next-token scores into actual text, one token at a time.

Suppose retrieval found this evidence:

Canary rollback is approved when error rate exceeds 5% and the deploy owner acknowledges the page. This deploy has 7% errors and owner acknowledgement.

The answer should communicate approval. Yet a model may assign some probability to pending, blocked, or an irrelevant token such as coupon. Decoding is the algorithm that selects a continuation from those scores. It can make output deterministic, diverse, shorter, constrained, or faster to serve. It can't rescue missing evidence or guarantee that a fluent token is supported by the runbook.

You'll build the critical pieces yourself: stable softmax, greedy generation, temperature and truncation, seeded sampling, output masks, beam search, length-aware scoring, and a decoder evaluation receipt. Those are the controls that must be understood before comparing an LLM product experiment.

Start with one next-token distribution

For readable arithmetic, pretend each word below is a single token. The prompt ends with:

Assume a model produces these raw scores, called logits, for the next token:

Logits aren't probabilities: they can be negative and don't sum to one. Softmax turns them into a probability distribution:

$$p_i = \frac{\exp(z_i - m)}{\sum_j \exp(z_j - m)} \qquad \text{where} \qquad m = \max_j z_j$$

Subtracting the maximum logit doesn't change the probabilities because it rescales every exponential by the same constant. It does prevent overflow when scores become large, which matters in real inference code.

The distribution tells a precise story: approved is most likely, but the model hasn't assigned zero probability to unsupported text. Sampling policy therefore affects product behavior.

Numerical stability is part of correctness

The stable formula isn't an optional optimization. Directly calculating exp(1000) overflows ordinary floating-point arithmetic even though the correct softmax distribution is well behaved.

A decoder with unstable arithmetic doesn't produce "slightly different" text. It produces invalid probabilities or fails to generate at all.

Greedy decoding gives a reproducible baseline

Generation is autoregressive: after selecting one token, the system appends it to the sequence and asks the model for new logits for the next position. In a transformer service, a key-value (KV) cache stores attention state used by later steps; memory management for that growing cache is a central serving concern.^{[1]Reference 1Efficient Memory Management for Large Language Model Serving with PagedAttention.https://arxiv.org/abs/2309.06180}

Greedy decoding chooses the highest-logit token at every step. Two captured model steps for our runbook answer are enough to implement the decoder without pretending we have a full model in the notebook.

Greedy generation is useful for tests and structured responses because the policy contains no random draw. Its limitation is just as important: picking the best next token doesn't explore a weaker first token that could lead to a better complete sequence.

Temperature reshapes probability mass

Temperature divides every logit by a positive value $T$ before softmax:

$$p_i(T) = \operatorname{softmax}\left(\frac{z_i}{T}\right)$$

• T < 1 sharpens the distribution, pushing more mass toward the current winner.
• T > 1 flattens it, giving lower-scored tokens more opportunity to be sampled.
• Temperature doesn't delete any candidate with finite logit.

The formula requires T > 0. For a deterministic baseline, use greedy selection rather than dividing logits by zero.

Entropy measures the uncertainty of a distribution. Higher entropy here means the decoder has more plausible ways to vary the next token, including harmful ones.

At higher temperature, the unsupported coupon continuation receives more probability along with genuinely useful variation. The printed 0.000 value at T=0.5 is rounded; the finite-logit token still has a small positive probability. Temperature is a diversity control, not a groundedness control.

Sampling needs a recorded randomness contract

A sampling decoder draws from probabilities rather than taking the maximum. This is useful when multiple outputs are acceptable, but it makes comparisons noisy unless you record the policy and the random seed used by your own experiment harness.

The next lab uses Python's random-number generator, so the same seed exactly replays the same draws in this local implementation.

Production backends may have their own reproducibility contract, and hardware or implementation changes can defeat byte-for-byte replay. At minimum, store the model identifier, prompt version, decoder settings, token limit, and any supported seed alongside each evaluation output.

Top-k and top-p truncate the tail

Temperature leaves every token in play. Top-k sampling keeps up to k highest-probability candidates, then renormalizes their probability mass before drawing. Top-k was used for neural story generation before nucleus sampling was proposed.^{[2]Reference 2Hierarchical Neural Story Generation.https://arxiv.org/abs/1805.04833}

Top-p, also called nucleus sampling, keeps the smallest high-probability prefix whose cumulative mass reaches a threshold p, then renormalizes and samples from that nucleus. Holtzman et al. proposed it after finding that open-ended likelihood-maximizing generation can become repetitive, while unrestricted sampling can draw from an unreliable tail.^{[3]Reference 3The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

This is the defining contrast:

In many production serving stacks the composition order is temperature reshape first, then top-k, then top-p (nucleus), then sample. The labs above apply each filter alone on already-normalized probabilities so you can see each control in isolation. When you combine them, apply temperature on logits before softmax, truncate the resulting distribution, renormalize, and only then draw.

Constraints enforce form, not truth

An incident assistant often needs structured output, such as a rollback_status field with allowed values. A token mask can remove invalid values before selection. This is constrained decoding.

Make the distinction explicit:

• A schema mask can stop the assistant from emitting coupon as a rollback status.
• Evidence validation is still needed to stop the assistant from choosing a valid but unsupported value such as blocked.

The output shows why structured generation and grounded generation are different requirements. Good production evaluations test both.

This fixture makes each status one token. In a real tokenizer, a valid value may span several tokens. Production constrained decoding tracks allowed prefixes after every generated token rather than applying one static final-value mask.

Beam search compares partial sequences

Greedy selection can miss a better continuation at a later step. Suppose the response prefix is The rollback request, and the model has two ways to continue:

Greedy picks approved immediately. At this fixed two-step horizon, beam search with width 2 retains both approved and is, expands each path, then selects is approved because that partial path scores higher.

This teaching fixture gives each retained prefix one captured second-token continuation. A real beam decoder expands every allowed next token for every retained prefix, combines the new log-probability scores, and prunes back to the configured beam width after each step. Unfinished prefixes remain candidates until an end-of-sequence token or another stop condition marks them complete.

Implement the fixture's two-step search in log space. Adding log probabilities is numerically safer than multiplying many tiny probabilities across a long sequence.

Beam search is useful when complete-sequence likelihood matters, such as input-grounded transformation or tightly formatted output. For open-ended generation, Holtzman et al. found that maximization-based decoding, including beam search, can produce bland or repetitive text.^{[3]Reference 3The Curious Case of Neural Text Degeneration.https://arxiv.org/abs/1904.09751}

Length changes the score you're optimizing

Raw sequence probability shrinks with each generated token because it multiplies values no larger than one. That creates a preference for short completions. Beam-search systems therefore define a length-scoring policy rather than comparing raw totals blindly. For example, Google's neural machine translation system used length normalization and a coverage penalty in its beam search.^{[4]Reference 4Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.https://arxiv.org/abs/1609.08144}

The simplified lab below uses average log probability to make the issue visible. It isn't a universal beam-search formula; a serving stack must document the formula it uses.

Search scores optimize a measurable objective. They don't automatically optimize usefulness, groundedness, or operator clarity. Those need evaluations.

Speculative decoding is a serving optimization

Temperature, truncation, constraints, and beam search change how text is selected. Speculative decoding addresses a different bottleneck: autoregressive generation normally needs a costly target-model step for each accepted token.

Leviathan, Kalman, and Matias describe a draft-and-verify algorithm in which a faster approximation model proposes tokens and the target model checks several proposals in parallel. Their exact sampling procedure preserves the target model's output distribution while reducing latency in suitable workloads.^{[5]Reference 5Fast Inference from Transformers via Speculative Decoding.https://arxiv.org/abs/2211.17192}

Keep this boundary clear:

A shortcut that accepts draft tokens without the target algorithm's verification and correction isn't equivalent speculative decoding. It's a different generator, so evaluate it under its own contract.

Evaluate decoder settings before an A/B test

Suppose a model change and a sampler change land together. If incident resolution improves, you won't know which change caused it. Every generation evaluation should keep a decoder receipt beside each output:

• model and prompt version
• evidence or retrieval snapshot identifier
• decoding mode, temperature, top-k, top-p, beam width, and length policy
• seed when the stack supports one
• maximum tokens, stop rules, and any output constraints
• groundedness judgment and task outcome

This tiny offline evaluation table treats approved as the only response supported by the retrieved runbook and compares three recorded decoder runs.

This isn't proof that greedy is always best. It verifies the procedure: compare decoders on held-out evidence and preserve settings so the next experiment measures the product change you meant to test.

A decoder review checklist

Before shipping a generated incident answer, separate these questions:

Practice tasks

1. Add logits [1000.0, 999.0, 998.0] to stable-softmax.py. Explain why subtracting the maximum changes numeric safety without changing the probabilities.
2. Change top-p-adapts-to-the-distribution.py to use threshold=0.70. Predict which tokens remain for the peaked and flat distributions before running it.
3. Extend mask-invalid-status-tokens.py with a two-token allowed value such as needs review. Sketch the prefix states a production decoder must allow.
4. Add a second candidate continuation under each retained prefix in two-step-beam-search.py. Prune back to beam width 2 after expansion and confirm the winner.
5. Write one decoder receipt for an incident-assistant evaluation run: model version, prompt version, evidence snapshot, selection settings, token limit, stop rules, constraints, seed support, groundedness label, and latency.

Practice guidance

1. Stable probabilities stay [0.665, 0.245, 0.090]. Shifting logits changes their absolute values, not their differences.
2. With p=0.70, the peaked distribution needs approved and pending; the flat distribution needs approved, pending, and blocked.
3. A static final-value set isn't enough. After generating needs, the decoder must still allow the continuation that completes needs review while rejecting prefixes that can never reach a valid value.
4. Expand every retained prefix, add log probabilities, sort all new prefixes, and keep only the best two. That's the repeated prune step omitted from the tiny walkthrough.
5. Keep the decoder receipt beside output and judgment so model, retrieval, decoder, and serving changes can be separated before online testing.