Output Sampling Ledger: Greedy, Beam, and top-k/top-p in Practice

"How to pick the next token" decides both service quality and inference cost. Greedy, Beam Search, top-k/top-p sampling, temperature — what are they, when to use them, and how much do they cost? This article settles the output-sampling engineering ledger, linking to Speculative Decoding.

1. Decoding Strategies: Four Tiers of Quality & Cost

Strategy	Principle	Output quality	Compute cost	Fits
Greedy	pick the highest-prob token each step	stable but flat, repetitive	lowest	deterministic tasks: summary, translation
Beam Search	keep K best paths each step	highest (approx global)	K×	"best answer" needed
top-k sampling	sample among top-k probs	diversity + control	same as greedy	dialogue/creation
top-p sampling	sample from minimal set with cumulative prob p	dynamic adaptive	same as greedy	dialogue/creation default

Takeaway: dialogue/generation defaults to top-p (p≈0.9-0.95); deterministic answers use greedy/Beam — don't use greedy everywhere, it loops into repetition.

2. Temperature: The Distribution "Sharpen/Flatten" Switch

$$p_i' = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}$$

• T>1: flatter distribution, more random/diverse output;
• T<1: sharper, favors high-prob tokens, more deterministic;
• T→0: equivalent to greedy.

Engineering points: temperature works with top-p — truncate the low-prob tail by p first, then tune sharpness with T. Bigger T isn't better: too-high T drifts semantics; 0.7-1.0 is the creative default.

3. Where Sampling Sits in Inference Cost

Stage	Changes with sampling strategy?
Forward compute (weight reads/compute)	no (decode computes the full vocab every step)
Output token count	yes (sampling may EOS early or wander)
Speculative-decoding gain	yes (acceptance rate depends on draft/main agreement)

Takeaway: sampling itself adds almost no compute (cost is in decode forward); what really moves cost is output length and repeated calls (e.g. multiple samples to pick the best = multiplied inference compute, see Inference-time scaling).

4. Link to Speculative Decoding: Consistency Is the Premise

Speculative decoding guesses with a draft model and verifies with the main model; acceptance depends on agreement between draft q(x) and main p(x):

$$accept\_rate = E[\min(1, \frac{p(x)}{q(x)})]$$

• Sampling params (T, top-p) must match on both sides, or acceptance collapses and speculation gains vanish (see Speculative Decoding consistency check);
• This is a hidden channel where sampling affects cost: inconsistent sampling configs waste the draft model's overhead.

5. Reproducible Python: Sampling vs Greedy Cost

def decode_cost(greedy_len, sample_len, k_trials=1):
    """Output cost: total decode tokens (incl. multiple samples)"""
    return greedy_len, sample_len * k_trials

decode_cost(greedy_len=512, sample_len=480, k_trials=3)
# greedy 512 tokens vs sample-3-times 1440 tokens → cost ×2.8
# note: multiple samples for quality = multiplied inference compute; check inference-time-scaling ROI first

6. Checklist

1. Default to top-p sampling (p≈0.9-0.95, T≈0.7-1.0) for dialogue/creation; greedy/Beam for deterministic tasks;
2. Keep sampling params consistent with speculative-decoding draft config or acceptance collapses;
3. Count "sample N times to pick best" as N× inference compute; compare ROI vs a bigger model;
4. Freeze sampling params before launch and A/B them (see llm-serving-sre).

---

Organized and written by this site for learning purposes; formulas and examples are the site's own; specific versions and measurements are subject to on-site conditions.