Greedy decoding and temperature sampling: does one cost more per token than the other?

Short answer·Medium·4.0 · 0·~3 min·Relevant atOpenAI

Attempt it

Compare the per-token compute cost of greedy decoding versus temperature sampling, then explain why callers nevertheless see real cost differences between the two strategies in production traces.

Free · 2 AI evals / day

Both greedy decoding and temperature sampling run exactly the same expensive operation per token: one full forward pass through the model, which reads the entire KV cache from HBM and computes the next-token distribution over the vocabulary. What differs is what happens after the distribution is computed. - **Greedy** takes the argmax: scan the vocabulary and pick the highest-probability token. This is one cheap pass over a 30k-300k vector, microseconds of work. - **Temperature sampling** divides the logits by a temperature value, applies softmax, then draws a token at random weighted by the resulting probabilities. Also microseconds of work. Both post-softmax operations are completely negligible next to the forward pass (which involves billions of operations). So per-token cost is essentially identical between the two strategies. Where then does any cost difference come from in production traces? From output length. Greedy and sampling walk different trajectories through token space, so the same prompt may produce a 50-token response under greedy and a 200-token response under sampling (or vice versa). The total bill is per-token-cost times number-of-tokens. The per-token-cost is the same; the token count is what differs. The practical lesson: switching from sampling to greedy is not a cost lever. If you want to spend less, reduce output length (concise prompting, max_tokens caps, brevity instructions) or use a smaller model. Tuning temperature changes output style but not per-token compute.

Greedy and temperature sampling have identical per-token compute cost. The expensive part of a decode step is the forward pass: one matmul-heavy traversal of the model that reads the KV cache from HBM, produces the hidden states, and applies the LM head to compute logits over the vocabulary. Both strategies do this work identically. The selection step that follows the LM head is what differs, and it is trivially cheap. Greedy reduces over the vocabulary to find the argmax: O(V) work on a vector of V elements (typically 30k-300k). Temperature sampling first scales the logits by 1/T (an O(V) elementwise op), then applies softmax (O(V)), then draws from the resulting categorical distribution (O(V) for the cumulative-sum trick or O(V log V) for sort-based methods). All of this is a few microseconds on a modern GPU and completely dwarfed by the forward pass (which is in the millisecond range even at small batch). So a single decode step costs essentially the same under either strategy. You cannot save meaningful money by flipping a sampling switch, and you cannot meaningfully slow down a deployment by enabling sampling. Real cost differences in production traces come from a different axis: total response length. Greedy and sampling walk different trajectories through token space. For the same prompt, the chosen tokens diverge starting from any position where the second-most-probable token had non-trivial mass. Different trajectories often produce different-length responses: the model may take a more verbose path under sampling, or hit a natural stopping boundary at a different point. The billing implication is direct. A 200-token sampling response costs 4x what an 80-token greedy response costs, despite identical per-token cost. If a team A/Bs greedy versus sampling on a route and observes greedy costing less, the cause is almost always shorter average outputs under greedy, not cheaper per-token decode. The correct way to compare decoding strategies on cost:

Quick reference

TL;DR

Per token, greedy and temperature sampling cost essentially the same: one forward pass, one KV-cache read, then a trivial argmax or sample.

Memory aid

Easy to grasp

Imagine two writers told to write a story. Both take the same time to think of what word to put down next. The first writer always picks the single most likely word; the second rolls a small weighted die and picks one from a few likely words. The thinking is the same; only the final pick differs. The dice-rolling takes a tiny moment, way too small to notice. But the two stories often turn out different lengths because they walk down different paths, and the longer story costs more in total only because it has more words, not because each word was harder to write. If you compare bills you have to compare on cost-per-word, not total-bill, or you mix up the trajectory with the per-word price.

Key concepts

Decoding strategies Greedy decoding Temperature sampling Per-call cost

Detailed answer & concept explanation

~6 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Quick scan · 2–4 min

Everything important, quickly.

3 min: name the shared forward pass + KV read, note the post-softmax argmax versus sample is microseconds and irrelevant, identify output length as the real cost driver, and prescribe length-normalized cost comparison as the diagnostic discipline.

Side-by-side

Property	Greedy	Temperature sampling
Forward passes per token	1	1
KV-cache reads per token	1	1
Post-softmax operation	argmax (~3 us)	softmax + sample (~10 us)
Per-token compute	1x (baseline)	1x (within noise)
Determinism	Yes (with same input)	No (modulo seed)
Typical effect on output length	Often shorter, more terminal	Often longer, more exploratory

Real-world examples

Real products, models, and research that use this idea.

OpenAI's chat completion billing is strictly per-token (input + output); switching temperature from 0 (greedy-equivalent) to 0.7 does not change the rate.
vLLM and SGLang report identical per-step decode latency for greedy and sampling configurations on the same model and batch size.
Production A/B tests of greedy versus sampling on chat routes typically show cost differences explainable by mean-output-length differences, not by per-token cost.
Anthropic's Claude API exposes temperature as a quality knob, not a cost knob; the docs note that decoding-strategy choice does not affect billing rates.
Best-of-n and beam search are the only single-knob decoding choices that genuinely multiply per-token cost; greedy versus sampling does not.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QWhy is the LM head's logits projection not the cost difference between greedy and sampling?

QCould a clever implementation skip the softmax for greedy and save real time?

QWhat about Gumbel-max sampling versus inverse-CDF? Are they different cost?

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Claiming temperature sampling is meaningfully slower or more expensive per token than greedy. The forward pass is identical and the only difference is a trivial post-softmax operation. The real cost gap is in output length, not per-token cost.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.