LearnML Algorithms & EvaluationDecoding Algorithms

🚀MediumInference Optimization

Decoding Algorithms

Turn retrieved evidence into controlled text by implementing stable softmax, sampling filters, constrained decoding, beam search, and reproducible generation audits.

16 min read

Learning path

Step 35 of 155 in the full curriculum

Core Retrieval Algorithms Experiment Design and A/B Testing

The previous chapter put the right policy passage into a support assistant's context. That wasn't the final answer. A language model still has to turn its next-token scores into actual text, one token at a time.

Suppose retrieval found this evidence:

Annual-plan purchases are refundable within 30 days. This customer purchased 12 days ago.

The answer should communicate eligibility. Yet a model may assign some probability to pending, denied, 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 policy.

In this chapter, 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.

Refund evidence places a purchase at day 12 inside a 30-day policy window, above a candidate matrix comparing softmax probability, greedy selection, schema allowance, and policy support for eligible, pending, denied, and coupon. — The same next-token distribution supports different questions. Greedy selects the largest probability, a schema removes invalid forms such as `coupon`, and the retrieved 30-day policy is still needed to establish that only `eligible` is supported for a purchase made 12 days ago.

Start With One Next-Token Distribution

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

text

Evidence: Annual-plan purchases are refundable within 30 days. Purchase age: 12 days.
Answer: Your refund request is

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

Token	Logit	Interpretation
`eligible`	`3.0`	Supported by the retrieved policy.
`pending`	`2.5`	Plausible service language, but it doesn't answer eligibility.
`denied`	`1.0`	Conflicts with the evidence.
`coupon`	`-1.0`	Off-topic tail 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.

stable-softmax.py

from math import exp

tokens = ["eligible", "pending", "denied", "coupon"]
logits = [3.0, 2.5, 1.0, -1.0]

def softmax(scores: list[float]) -> list[float]:
    offset = max(scores)
    weights = [exp(score - offset) for score in scores]
    total = sum(weights)
    return [weight / total for weight in weights]

probabilities = softmax(logits)
for token, score, probability in zip(tokens, logits, probabilities):
    print(f"{token:8} logit={score:>4.1f} probability={probability:.3f}")
print(f"sum={sum(probabilities):.3f}")

Output

eligible logit= 3.0 probability=0.568
pending  logit= 2.5 probability=0.345
denied   logit= 1.0 probability=0.077
coupon   logit=-1.0 probability=0.010
sum=1.000

The distribution tells a precise story: eligible 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.

avoid-softmax-overflow.py

from math import exp

large_logits = [1000.0, 999.0, 998.0]

try:
    raw_weights = [exp(score) for score in large_logits]
    naive = [weight / sum(raw_weights) for weight in raw_weights]
    print("naive:", naive)
except OverflowError:
    print("naive softmax: overflow")

offset = max(large_logits)
stable_weights = [exp(score - offset) for score in large_logits]
stable = [weight / sum(stable_weights) for weight in stable_weights]
print("stable:", [round(probability, 3) for probability in stable])

Output

naive softmax: overflow
stable: [0.665, 0.245, 0.09]

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

Stable softmax matrix tracing eligible, pending, denied, and coupon from raw logits through max-shifted scores, exponential weights, normalized probabilities, greedy selection, and the updated response prefix. — For this captured step, subtracting the maximum logit produces shifted scores from `0.0` to `-4.0`. Their exponential weights sum to `1.760`; normalization gives `eligible` probability `0.568`, greedy selection appends it, and the updated prefix becomes the next model input.

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]

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

greedy-generation-loop.py

captured_logits = [
    {"eligible": 3.0, "pending": 2.5, "denied": 1.0, "coupon": -1.0},
    {".": 4.0, "today": 1.5, "after": 0.5},
]

def greedy_token(scores: dict[str, float]) -> str:
    return max(scores, key=scores.get)

generated = []
for step, scores in enumerate(captured_logits, start=1):
    chosen = greedy_token(scores)
    generated.append(chosen)
    print(f"step {step}: chose {chosen!r} from {len(scores)} candidates")

answer = "Your refund request is " + " ".join(generated).replace(" .", ".")
print(answer)

Output

step 1: chose 'eligible' from 4 candidates
step 2: chose '.' from 3 candidates
Your refund request is eligible.

Greedy generation is valuable 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.

temperature-and-entropy.py

from math import exp, log

tokens = ["eligible", "pending", "denied", "coupon"]
logits = [3.0, 2.5, 1.0, -1.0]

def softmax(scores: list[float]) -> list[float]:
    offset = max(scores)
    weights = [exp(score - offset) for score in scores]
    total = sum(weights)
    return [weight / total for weight in weights]

def entropy(probabilities: list[float]) -> float:
    return -sum(p * log(p) for p in probabilities)

for temperature in (0.5, 1.0, 2.0):
    probabilities = softmax([score / temperature for score in logits])
    table = dict(zip(tokens, probabilities))
    print(
        f"T={temperature:.1f}: eligible={table['eligible']:.3f} "
        f"coupon={table['coupon']:.3f} entropy={entropy(probabilities):.3f}"
    )

Output

T=0.5: eligible=0.721 coupon=0.000 entropy=0.647
T=1.0: eligible=0.568 coupon=0.010 entropy=0.933
T=2.0: eligible=0.438 coupon=0.059 entropy=1.190

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.

seeded-sampling.py

from random import Random

tokens = ["eligible", "pending", "denied", "coupon"]
probabilities = [0.568, 0.345, 0.077, 0.010]

def draw_sequence(seed: int, length: int = 8) -> list[str]:
    rng = Random(seed)
    return rng.choices(tokens, weights=probabilities, k=length)

for seed in (7, 7, 21):
    print(f"seed={seed}: {' '.join(draw_sequence(seed))}")

Output

seed=7: eligible eligible pending eligible eligible eligible eligible eligible
seed=7: eligible eligible pending eligible eligible eligible eligible eligible
seed=21: eligible pending pending eligible eligible pending pending eligible

Production backends may have their own reproducibility contract, and hardware or implementation changes can defeat byte-for-byte replay. At minimum, store 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]

top-k-filter.py

tokens = ["eligible", "pending", "denied", "coupon"]
probabilities = [0.568, 0.345, 0.077, 0.010]

def top_k(items: list[str], probs: list[float], k: int) -> list[tuple[str, float]]:
    ranked = sorted(zip(items, probs), key=lambda row: row[1], reverse=True)[:k]
    retained_mass = sum(probability for _, probability in ranked)
    return [(token, probability / retained_mass) for token, probability in ranked]

for token, probability in top_k(tokens, probabilities, k=2):
    print(f"{token:8} renormalized={probability:.3f}")

Output

eligible renormalized=0.622
pending  renormalized=0.378

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]

top-p-adapts-to-the-distribution.py

def nucleus(probabilities: dict[str, float], threshold: float) -> list[str]:
    ranked = sorted(probabilities.items(), key=lambda row: row[1], reverse=True)
    kept = []
    cumulative = 0.0
    for token, probability in ranked:
        kept.append(token)
        cumulative += probability
        if cumulative >= threshold:
            break
    return kept

peaked = {"eligible": 0.568, "pending": 0.345, "denied": 0.077, "coupon": 0.010}
flat = {"eligible": 0.28, "pending": 0.25, "denied": 0.24, "coupon": 0.23}

print("peaked p=0.90:", nucleus(peaked, 0.90))
print("flat   p=0.90:", nucleus(flat, 0.90))

Output

peaked p=0.90: ['eligible', 'pending']
flat   p=0.90: ['eligible', 'pending', 'denied', 'coupon']

This is the defining contrast:

Decoder control	Changes probabilities?	Removes candidates?	Candidate count
Temperature	Yes	No	Unchanged
Top-k	Renormalizes retained tokens	Yes	Up to `k`
Top-p	Renormalizes retained tokens	Yes	Adapts to each distribution

Constraints Enforce Form, Not Truth

An e-commerce assistant often needs structured output, such as a refund_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 refund status.
Evidence validation is still needed to stop the assistant from choosing a valid but unsupported value such as denied.

mask-invalid-status-tokens.py

logits = {"coupon": 6.0, "denied": 4.0, "eligible": 3.0, "pending": 2.0}
schema_values = {"eligible", "pending", "denied"}
supported_by_policy = {"eligible"}

def constrained_greedy(scores: dict[str, float], allowed: set[str]) -> str:
    candidates = {token: score for token, score in scores.items() if token in allowed}
    if not candidates:
        raise ValueError("constraint removed every token")
    return max(candidates, key=candidates.get)

print("unconstrained:", max(logits, key=logits.get))
print("schema-only:", constrained_greedy(logits, schema_values))
print("policy-supported:", constrained_greedy(logits, supported_by_policy))

Output

unconstrained: coupon
schema-only: denied
policy-supported: eligible

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 Your refund request, and the model has two ways to continue:

First token	Probability	Strongest next token	Probability	Joint probability after two steps
`eligible`	`0.40`	`.`	`0.20`	`0.080`
`is`	`0.35`	`eligible`	`0.70`	`0.245`
`denied`	`0.25`	`.`	`0.30`	`0.075`

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

Beam search keeps two paths and late score wins. — Path width follows probability. Greedy commits to eligible at 0.40, while beam width two preserves is at 0.35; its 0.70 continuation produces the winning 0.245 joint score.

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.

two-step-beam-search.py

from math import exp, log

first_step = {"eligible": 0.40, "is": 0.35, "denied": 0.25}
second_step = {
    "eligible": {".": 0.20},
    "is": {"eligible": 0.70},
    "denied": {".": 0.30},
}

greedy_first = max(first_step, key=first_step.get)
greedy_second = max(second_step[greedy_first], key=second_step[greedy_first].get)
greedy_probability = first_step[greedy_first] * second_step[greedy_first][greedy_second]

prefixes = sorted(first_step, key=first_step.get, reverse=True)[:2]
candidates = []
for first in prefixes:
    for second, p_second in second_step[first].items():
        candidates.append(((first, second), log(first_step[first]) + log(p_second)))

winner, winner_log_probability = max(candidates, key=lambda row: row[1])
print("greedy:", f"{greedy_first} {greedy_second}", f"probability={greedy_probability:.3f}")
print("beam:", " ".join(winner), f"probability={exp(winner_log_probability):.3f}")

Output

greedy: eligible . probability=0.080
beam: is eligible probability=0.245

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]

Length Changes the Score You Are 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]

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 actually uses.

length-aware-sequence-score.py

candidates = [
    {"text": "eligible", "log_probability": -0.25, "tokens": 1},
    {"text": "eligible within 30 days", "log_probability": -0.42, "tokens": 4},
]

raw_winner = max(candidates, key=lambda row: row["log_probability"])
normalized_winner = max(candidates, key=lambda row: row["log_probability"] / row["tokens"])

print("raw winner:", raw_winner["text"])
print("length-normalized winner:", normalized_winner["text"])
for row in candidates:
    average = row["log_probability"] / row["tokens"]
    print(f"{row['text']:24} raw={row['log_probability']:.3f} average={average:.3f}")

Output

raw winner: eligible
length-normalized winner: eligible within 30 days
eligible                 raw=-0.250 average=-0.250
eligible within 30 days  raw=-0.420 average=-0.105

Search scores optimize a measurable objective. They don't automatically optimize usefulness, groundedness, or customer 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]

Keep this boundary clear:

Technique	Primary purpose	Can it change selected-output distribution?
Temperature / top-k / top-p	Change diversity and tail risk	Yes
Beam search / length scoring	Search for high-scoring sequences	Yes
Token constraints	Enforce allowable forms	Yes
Exact speculative decoding	Produce target distribution faster	No

A shortcut that accepts draft tokens without the target algorithm's verification and correction isn't equivalent speculative decoding. It is a different generator and must be evaluated as such.

Evaluate Decoder Settings Before an A/B Test

Suppose a model change and a sampler change land together. If support 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

Here is a tiny offline evaluation table. It treats eligible as the only response supported by the retrieved policy and compares three recorded decoder runs.

decoder-receipt-evaluation.py

runs = {
    "greedy T=1": ["eligible", "eligible", "eligible", "eligible"],
    "sample T=2": ["eligible", "pending", "coupon", "denied"],
    "top-p p=.9": ["eligible", "pending", "eligible", "eligible"],
}
supported = {"eligible"}

for receipt, outputs in runs.items():
    grounded = sum(output in supported for output in outputs)
    rate = grounded / len(outputs)
    print(f"{receipt:12} grounded={grounded}/{len(outputs)} rate={rate:.2f}")

Output

greedy T=1   grounded=4/4 rate=1.00
sample T=2   grounded=1/4 rate=0.25
top-p p=.9   grounded=3/4 rate=0.75

This isn't proof that greedy is always best. It proves 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 support answer, separate these questions:

Review question	Failure symptom	Evidence to collect
Are logits converted stably?	`NaN`, overflow, or invalid probabilities.	Large-logit unit test.
Is diversity deliberate?	Unsupported tail tokens appear unexpectedly.	Temperature/top-p sweep with groundedness labels.
Are formats enforced?	Invalid status or JSON value reaches application code.	Constraint and schema tests.
Is sequence scoring appropriate?	Replies are too short or oddly generic.	Beam/length policy report.
Is evaluation reproducible?	Two experiments can't be compared.	Decoder receipts and fixed eval cases.
Is latency optimization equivalent?	Faster serving silently changes answers.	Target-distribution audit for speculative serving.

Practice Tasks

Add logits [1000.0, 999.0, 998.0] to stable-softmax.py. Explain why subtracting the maximum changes numeric safety without changing the probabilities.
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.
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.
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.
Write one decoder receipt for a refund-support evaluation run: model version, prompt version, evidence snapshot, selection settings, token limit, stop rules, constraints, seed support, groundedness label, and latency.

Practice guidance

Stable probabilities stay [0.665, 0.245, 0.090]. Shifting logits changes their absolute values, not their differences.
With p=0.70, the peaked distribution needs eligible and pending; the flat distribution needs eligible, pending, and denied.
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.
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.
Keep the decoder receipt beside output and judgment so model, retrieval, decoder, and serving changes can be separated before online testing.

Key Concepts

logits and numerically stable softmax
greedy autoregressive decoding
temperature and entropy
top-k and nucleus (top-p) sampling
seeded local sampling and decoder receipts
constrained decoding versus groundedness
beam search in log-probability space
length-aware sequence scoring
speculative decoding as latency optimization

Evaluation rubric

Foundational: Converts refund-response logits into stable probabilities and explains why eligible is grounded while coupon isn't.
Intermediate: Implements temperature, top-k, top-p, constraints, and beam search and predicts each lab's result before running it.
Advanced: Designs an evaluation receipt that distinguishes model, retrieval, decoding, and serving changes before an online experiment.

Follow-up questions

Common pitfalls

Symptom	Cause	Fix
Large logits lead to invalid probabilities.	Softmax exponentiated raw values without shifting.	Subtract the maximum logit before `exp`.
Output becomes more varied but also less supported.	Temperature flattened probability mass into the tail.	Evaluate groundedness, then use deliberate truncation or constraints.
Valid JSON contains a policy-wrong status.	Schema enforcement was mistaken for factual validation.	Test generated values against retrieved evidence.
Beam output is extremely short.	Raw sequence scores favor fewer multiplied probabilities.	Declare and evaluate a length-scoring policy.
A model experiment can't be reproduced.	Decoder settings or retrieval snapshot wasn't logged.	Store a decoder receipt with every evaluated output.

Next Step

Continue to Experiment Design and A/B Testing

You can now separate model scores, decoding policy, groundedness, and serving behavior. Next you will design a controlled experiment that can tell whether a retrieval or generation change actually improves the support product.

PreviousCore Retrieval Algorithms

Share this article

X Facebook LinkedIn Bluesky Reddit Hacker News Email

References

Efficient Memory Management for Large Language Model Serving with PagedAttention.

Kwon, W., et al. · 2023 · SOSP 2023

Hierarchical Neural Story Generation.

Fan, A., Lewis, M., & Dauphin, Y. · 2018 · ACL 2018

The Curious Case of Neural Text Degeneration.

Holtzman, A., et al. · 2020 · ICLR 2020

Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.

Wu, Y., et al. · 2016

Fast Inference from Transformers via Speculative Decoding.

Leviathan, Y., Kalman, M., & Matias, Y. · 2023 · ICML 2023

Back to Topics

LearnML Algorithms & EvaluationDecoding Algorithms

🚀MediumInference Optimization

Decoding Algorithms

Turn retrieved evidence into controlled text by implementing stable softmax, sampling filters, constrained decoding, beam search, and reproducible generation audits.

16 min read

Learning path

Step 35 of 155 in the full curriculum

Core Retrieval Algorithms Experiment Design and A/B Testing

Suppose retrieval found this evidence:

Annual-plan purchases are refundable within 30 days. This customer purchased 12 days ago.

Start With One Next-Token Distribution

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

text

Evidence: Annual-plan purchases are refundable within 30 days. Purchase age: 12 days.
Answer: Your refund request is

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

Token	Logit	Interpretation
`eligible`	`3.0`	Supported by the retrieved policy.
`pending`	`2.5`	Plausible service language, but it doesn't answer eligibility.
`denied`	`1.0`	Conflicts with the evidence.
`coupon`	`-1.0`	Off-topic tail 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

stable-softmax.py

from math import exp

tokens = ["eligible", "pending", "denied", "coupon"]
logits = [3.0, 2.5, 1.0, -1.0]

def softmax(scores: list[float]) -> list[float]:
    offset = max(scores)
    weights = [exp(score - offset) for score in scores]
    total = sum(weights)
    return [weight / total for weight in weights]

probabilities = softmax(logits)
for token, score, probability in zip(tokens, logits, probabilities):
    print(f"{token:8} logit={score:>4.1f} probability={probability:.3f}")
print(f"sum={sum(probabilities):.3f}")

Output

eligible logit= 3.0 probability=0.568
pending  logit= 2.5 probability=0.345
denied   logit= 1.0 probability=0.077
coupon   logit=-1.0 probability=0.010
sum=1.000

The distribution tells a precise story: eligible 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.

avoid-softmax-overflow.py

from math import exp

large_logits = [1000.0, 999.0, 998.0]

try:
    raw_weights = [exp(score) for score in large_logits]
    naive = [weight / sum(raw_weights) for weight in raw_weights]
    print("naive:", naive)
except OverflowError:
    print("naive softmax: overflow")

offset = max(large_logits)
stable_weights = [exp(score - offset) for score in large_logits]
stable = [weight / sum(stable_weights) for weight in stable_weights]
print("stable:", [round(probability, 3) for probability in stable])

Output

naive softmax: overflow
stable: [0.665, 0.245, 0.09]

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

greedy-generation-loop.py

captured_logits = [
    {"eligible": 3.0, "pending": 2.5, "denied": 1.0, "coupon": -1.0},
    {".": 4.0, "today": 1.5, "after": 0.5},
]

def greedy_token(scores: dict[str, float]) -> str:
    return max(scores, key=scores.get)

generated = []
for step, scores in enumerate(captured_logits, start=1):
    chosen = greedy_token(scores)
    generated.append(chosen)
    print(f"step {step}: chose {chosen!r} from {len(scores)} candidates")

answer = "Your refund request is " + " ".join(generated).replace(" .", ".")
print(answer)

Output

step 1: chose 'eligible' from 4 candidates
step 2: chose '.' from 3 candidates
Your refund request is eligible.

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.

temperature-and-entropy.py

from math import exp, log

tokens = ["eligible", "pending", "denied", "coupon"]
logits = [3.0, 2.5, 1.0, -1.0]

def softmax(scores: list[float]) -> list[float]:
    offset = max(scores)
    weights = [exp(score - offset) for score in scores]
    total = sum(weights)
    return [weight / total for weight in weights]

def entropy(probabilities: list[float]) -> float:
    return -sum(p * log(p) for p in probabilities)

for temperature in (0.5, 1.0, 2.0):
    probabilities = softmax([score / temperature for score in logits])
    table = dict(zip(tokens, probabilities))
    print(
        f"T={temperature:.1f}: eligible={table['eligible']:.3f} "
        f"coupon={table['coupon']:.3f} entropy={entropy(probabilities):.3f}"
    )

Output

T=0.5: eligible=0.721 coupon=0.000 entropy=0.647
T=1.0: eligible=0.568 coupon=0.010 entropy=0.933
T=2.0: eligible=0.438 coupon=0.059 entropy=1.190

Sampling Needs a Recorded Randomness Contract

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

seeded-sampling.py

from random import Random

tokens = ["eligible", "pending", "denied", "coupon"]
probabilities = [0.568, 0.345, 0.077, 0.010]

def draw_sequence(seed: int, length: int = 8) -> list[str]:
    rng = Random(seed)
    return rng.choices(tokens, weights=probabilities, k=length)

for seed in (7, 7, 21):
    print(f"seed={seed}: {' '.join(draw_sequence(seed))}")

Output

seed=7: eligible eligible pending eligible eligible eligible eligible eligible
seed=7: eligible eligible pending eligible eligible eligible eligible eligible
seed=21: eligible pending pending eligible eligible pending pending eligible

Top-k and Top-p Truncate the Tail

top-k-filter.py

tokens = ["eligible", "pending", "denied", "coupon"]
probabilities = [0.568, 0.345, 0.077, 0.010]

def top_k(items: list[str], probs: list[float], k: int) -> list[tuple[str, float]]:
    ranked = sorted(zip(items, probs), key=lambda row: row[1], reverse=True)[:k]
    retained_mass = sum(probability for _, probability in ranked)
    return [(token, probability / retained_mass) for token, probability in ranked]

for token, probability in top_k(tokens, probabilities, k=2):
    print(f"{token:8} renormalized={probability:.3f}")

Output

eligible renormalized=0.622
pending  renormalized=0.378

top-p-adapts-to-the-distribution.py

def nucleus(probabilities: dict[str, float], threshold: float) -> list[str]:
    ranked = sorted(probabilities.items(), key=lambda row: row[1], reverse=True)
    kept = []
    cumulative = 0.0
    for token, probability in ranked:
        kept.append(token)
        cumulative += probability
        if cumulative >= threshold:
            break
    return kept

peaked = {"eligible": 0.568, "pending": 0.345, "denied": 0.077, "coupon": 0.010}
flat = {"eligible": 0.28, "pending": 0.25, "denied": 0.24, "coupon": 0.23}

print("peaked p=0.90:", nucleus(peaked, 0.90))
print("flat   p=0.90:", nucleus(flat, 0.90))

Output

peaked p=0.90: ['eligible', 'pending']
flat   p=0.90: ['eligible', 'pending', 'denied', 'coupon']

This is the defining contrast:

Decoder control	Changes probabilities?	Removes candidates?	Candidate count
Temperature	Yes	No	Unchanged
Top-k	Renormalizes retained tokens	Yes	Up to `k`
Top-p	Renormalizes retained tokens	Yes	Adapts to each distribution

Constraints Enforce Form, Not Truth

An e-commerce assistant often needs structured output, such as a refund_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 refund status.
Evidence validation is still needed to stop the assistant from choosing a valid but unsupported value such as denied.

mask-invalid-status-tokens.py

logits = {"coupon": 6.0, "denied": 4.0, "eligible": 3.0, "pending": 2.0}
schema_values = {"eligible", "pending", "denied"}
supported_by_policy = {"eligible"}

def constrained_greedy(scores: dict[str, float], allowed: set[str]) -> str:
    candidates = {token: score for token, score in scores.items() if token in allowed}
    if not candidates:
        raise ValueError("constraint removed every token")
    return max(candidates, key=candidates.get)

print("unconstrained:", max(logits, key=logits.get))
print("schema-only:", constrained_greedy(logits, schema_values))
print("policy-supported:", constrained_greedy(logits, supported_by_policy))

Output

unconstrained: coupon
schema-only: denied
policy-supported: eligible

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

Beam Search Compares Partial Sequences

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

First token	Probability	Strongest next token	Probability	Joint probability after two steps
`eligible`	`0.40`	`.`	`0.20`	`0.080`
`is`	`0.35`	`eligible`	`0.70`	`0.245`
`denied`	`0.25`	`.`	`0.30`	`0.075`

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.

two-step-beam-search.py

from math import exp, log

first_step = {"eligible": 0.40, "is": 0.35, "denied": 0.25}
second_step = {
    "eligible": {".": 0.20},
    "is": {"eligible": 0.70},
    "denied": {".": 0.30},
}

greedy_first = max(first_step, key=first_step.get)
greedy_second = max(second_step[greedy_first], key=second_step[greedy_first].get)
greedy_probability = first_step[greedy_first] * second_step[greedy_first][greedy_second]

prefixes = sorted(first_step, key=first_step.get, reverse=True)[:2]
candidates = []
for first in prefixes:
    for second, p_second in second_step[first].items():
        candidates.append(((first, second), log(first_step[first]) + log(p_second)))

winner, winner_log_probability = max(candidates, key=lambda row: row[1])
print("greedy:", f"{greedy_first} {greedy_second}", f"probability={greedy_probability:.3f}")
print("beam:", " ".join(winner), f"probability={exp(winner_log_probability):.3f}")

Output

greedy: eligible . probability=0.080
beam: is eligible probability=0.245

Length Changes the Score You Are Optimizing

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 actually uses.

length-aware-sequence-score.py

candidates = [
    {"text": "eligible", "log_probability": -0.25, "tokens": 1},
    {"text": "eligible within 30 days", "log_probability": -0.42, "tokens": 4},
]

raw_winner = max(candidates, key=lambda row: row["log_probability"])
normalized_winner = max(candidates, key=lambda row: row["log_probability"] / row["tokens"])

print("raw winner:", raw_winner["text"])
print("length-normalized winner:", normalized_winner["text"])
for row in candidates:
    average = row["log_probability"] / row["tokens"]
    print(f"{row['text']:24} raw={row['log_probability']:.3f} average={average:.3f}")

Output

raw winner: eligible
length-normalized winner: eligible within 30 days
eligible                 raw=-0.250 average=-0.250
eligible within 30 days  raw=-0.420 average=-0.105

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

Speculative Decoding Is a Serving Optimization

Keep this boundary clear:

Technique	Primary purpose	Can it change selected-output distribution?
Temperature / top-k / top-p	Change diversity and tail risk	Yes
Beam search / length scoring	Search for high-scoring sequences	Yes
Token constraints	Enforce allowable forms	Yes
Exact speculative decoding	Produce target distribution faster	No

A shortcut that accepts draft tokens without the target algorithm's verification and correction isn't equivalent speculative decoding. It is a different generator and must be evaluated as such.

Evaluate Decoder Settings Before an A/B Test

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

Here is a tiny offline evaluation table. It treats eligible as the only response supported by the retrieved policy and compares three recorded decoder runs.

decoder-receipt-evaluation.py

runs = {
    "greedy T=1": ["eligible", "eligible", "eligible", "eligible"],
    "sample T=2": ["eligible", "pending", "coupon", "denied"],
    "top-p p=.9": ["eligible", "pending", "eligible", "eligible"],
}
supported = {"eligible"}

for receipt, outputs in runs.items():
    grounded = sum(output in supported for output in outputs)
    rate = grounded / len(outputs)
    print(f"{receipt:12} grounded={grounded}/{len(outputs)} rate={rate:.2f}")

Output

greedy T=1   grounded=4/4 rate=1.00
sample T=2   grounded=1/4 rate=0.25
top-p p=.9   grounded=3/4 rate=0.75

This isn't proof that greedy is always best. It proves 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 support answer, separate these questions:

Review question	Failure symptom	Evidence to collect
Are logits converted stably?	`NaN`, overflow, or invalid probabilities.	Large-logit unit test.
Is diversity deliberate?	Unsupported tail tokens appear unexpectedly.	Temperature/top-p sweep with groundedness labels.
Are formats enforced?	Invalid status or JSON value reaches application code.	Constraint and schema tests.
Is sequence scoring appropriate?	Replies are too short or oddly generic.	Beam/length policy report.
Is evaluation reproducible?	Two experiments can't be compared.	Decoder receipts and fixed eval cases.
Is latency optimization equivalent?	Faster serving silently changes answers.	Target-distribution audit for speculative serving.

Practice Tasks

Add logits [1000.0, 999.0, 998.0] to stable-softmax.py. Explain why subtracting the maximum changes numeric safety without changing the probabilities.
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.
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.
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.
Write one decoder receipt for a refund-support evaluation run: model version, prompt version, evidence snapshot, selection settings, token limit, stop rules, constraints, seed support, groundedness label, and latency.

Practice guidance

Stable probabilities stay [0.665, 0.245, 0.090]. Shifting logits changes their absolute values, not their differences.
With p=0.70, the peaked distribution needs eligible and pending; the flat distribution needs eligible, pending, and denied.
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.
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.
Keep the decoder receipt beside output and judgment so model, retrieval, decoder, and serving changes can be separated before online testing.

Key Concepts

logits and numerically stable softmax
greedy autoregressive decoding
temperature and entropy
top-k and nucleus (top-p) sampling
seeded local sampling and decoder receipts
constrained decoding versus groundedness
beam search in log-probability space
length-aware sequence scoring
speculative decoding as latency optimization

Evaluation rubric

Foundational: Converts refund-response logits into stable probabilities and explains why eligible is grounded while coupon isn't.
Intermediate: Implements temperature, top-k, top-p, constraints, and beam search and predicts each lab's result before running it.
Advanced: Designs an evaluation receipt that distinguishes model, retrieval, decoding, and serving changes before an online experiment.

Follow-up questions

Common pitfalls

Symptom	Cause	Fix
Large logits lead to invalid probabilities.	Softmax exponentiated raw values without shifting.	Subtract the maximum logit before `exp`.
Output becomes more varied but also less supported.	Temperature flattened probability mass into the tail.	Evaluate groundedness, then use deliberate truncation or constraints.
Valid JSON contains a policy-wrong status.	Schema enforcement was mistaken for factual validation.	Test generated values against retrieved evidence.
Beam output is extremely short.	Raw sequence scores favor fewer multiplied probabilities.	Declare and evaluate a length-scoring policy.
A model experiment can't be reproduced.	Decoder settings or retrieval snapshot wasn't logged.	Store a decoder receipt with every evaluated output.

Next Step

Continue to Experiment Design and A/B Testing

PreviousCore Retrieval Algorithms

Share this article

X Facebook LinkedIn Bluesky Reddit Hacker News Email

References

Efficient Memory Management for Large Language Model Serving with PagedAttention.

Kwon, W., et al. · 2023 · SOSP 2023

Hierarchical Neural Story Generation.

Fan, A., Lewis, M., & Dauphin, Y. · 2018 · ACL 2018

The Curious Case of Neural Text Degeneration.

Holtzman, A., et al. · 2020 · ICLR 2020

Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.

Wu, Y., et al. · 2016

Fast Inference from Transformers via Speculative Decoding.

Leviathan, Y., Kalman, M., & Matias, Y. · 2023 · ICML 2023

Decoding Algorithms

Start With One Next-Token Distribution

Numerical Stability Is Part of Correctness

Greedy Decoding Gives a Reproducible Baseline

Temperature Reshapes Probability Mass

Sampling Needs a Recorded Randomness Contract

Top-k and Top-p Truncate the Tail

Constraints Enforce Form, Not Truth

Beam Search Compares Partial Sequences

Length Changes the Score You Are Optimizing

Speculative Decoding Is a Serving Optimization

Evaluate Decoder Settings Before an A/B Test

A Decoder Review Checklist

Practice Tasks

Practice guidance

Key Concepts

Evaluation rubric

Follow-up questions

Common pitfalls

Mastery Check

Decoding Algorithms

Start With One Next-Token Distribution

Numerical Stability Is Part of Correctness

Greedy Decoding Gives a Reproducible Baseline

Temperature Reshapes Probability Mass

Sampling Needs a Recorded Randomness Contract

Top-k and Top-p Truncate the Tail

Constraints Enforce Form, Not Truth

Beam Search Compares Partial Sequences

Length Changes the Score You Are Optimizing

Speculative Decoding Is a Serving Optimization

Evaluate Decoder Settings Before an A/B Test

A Decoder Review Checklist

Practice Tasks

Practice guidance

Key Concepts

Evaluation rubric

Follow-up questions

Common pitfalls

Mastery Check

Decoding Algorithms

Start With One Next-Token Distribution

Numerical Stability Is Part of Correctness

Greedy Decoding Gives a Reproducible Baseline

Temperature Reshapes Probability Mass

Sampling Needs a Recorded Randomness Contract

Top-k and Top-p Truncate the Tail

Constraints Enforce Form, Not Truth

Beam Search Compares Partial Sequences

Length Changes the Score You Are Optimizing

Speculative Decoding Is a Serving Optimization

Evaluate Decoder Settings Before an A/B Test

A Decoder Review Checklist

Practice Tasks

Practice guidance

Key Concepts

Evaluation rubric

Follow-up questions

Why subtract the maximum logit before exponentiating?

Why can top-p help when temperature alone makes output noisy?

Why doesn't constrained decoding prove that an answer is grounded?

How is exact speculative decoding different from sampling configuration?

Common pitfalls

Mastery Check

Decoding Algorithms

Start With One Next-Token Distribution

Numerical Stability Is Part of Correctness

Greedy Decoding Gives a Reproducible Baseline

Temperature Reshapes Probability Mass

Sampling Needs a Recorded Randomness Contract

Top-k and Top-p Truncate the Tail

Constraints Enforce Form, Not Truth

Beam Search Compares Partial Sequences

Length Changes the Score You Are Optimizing

Speculative Decoding Is a Serving Optimization

Evaluate Decoder Settings Before an A/B Test

A Decoder Review Checklist

Practice Tasks

Practice guidance

Key Concepts

Evaluation rubric

Follow-up questions

Why subtract the maximum logit before exponentiating?

Why can top-p help when temperature alone makes output noisy?

Why doesn't constrained decoding prove that an answer is grounded?

How is exact speculative decoding different from sampling configuration?

Common pitfalls

Mastery Check