Sampling & Decoding Strategies

Sampling - used during decoding (generation) phase of inference to choose next token after softmax.

• Deterministic greedy decoding - taking the single highest-probability token.

• Deterministic Beam Search
  • Maintain n “beams” (partial hypotheses) at each generation step.
  • For each beam, expand all possible next tokens; keep the top n combined sequences by total proba (log-).
  • Continue until each beam emits EOS token or reaches max length, then pick the best full sequence.

• Stochastic Sampling

• At each step, an LLM computes a proba distribution over its entire vocabulary.

• Optionally, modify that distribution using temperature parameter T:

  • Low T<1: makes the distribution peakier (more deterministic).

  • High T>1: makes it flatter (more random).

• Adjust that distribution and draw a random token:

  • Pure (Multinomial) Sampling - draw a random token based on model’s proba distribution – more probable tokens have a higher chance of being picked up (see notes for an example).

  • Top-k Sampling
    Select k most probable tokens, renormalize their probas (so their probas sum to 1 again), then do pure multinomial sample.

  • Nucleus (Top-p) Sampling
    Select the smallest set of tokens whose cumulative proba ≥ p, renormalize their probas (so their probas sum to 1 again), then do pure multinomial sample. Tokens are sorted by probability in descending order, then you start picking tokens going from highest to lowest proba and stop when the cumulative proba ≥ p.

• Repeat until an end-token or length limit

Notes

• Top-k and top-p methods eliminate the rare low-proba tokens.

• The rare low-proba tokens can still be selected during multinomial sampling, but chances r very low.

• Example of multinomial sampling:

  • Let’s say that after softmax we have this vocab:

    • Token A → 0.60, Token B → 0.25, Token C → 0.15

  • We turn these into running totals (cumulative):

    • A: 0.00 up to 0.60, B: 0.60 up to 0.85, C: 0.85 up to 1.00

  • Then we draw one uniform random number e.g. 0.72. => falls into range of B => B is selected.

  • Conclusion: each token’s “slice” = exactly its probability => tokens w/larger proba selected more often, but low-proba tokens still have a chance—proportional to their slice size.

Integration Details

• API/Library Level
  Most frameworks (e.g. Hugging Face Transformers, OpenAI API) let you specify a decoding_strategy or do_sample=True/False, num_beams=…, top_k=…, top_p=…, temperature=… when you call the model’s .generate() method.

• Iterative Loop
  For each new token position i:

  1. Pass the current token sequence into the model → get logits for position i+1.

  2. Softmax → probabilities.

  3. Apply beam search or stochastic sampling → pick next token(s).

  4. Append to sequence(s), update beams or continue sampling.

When to Use Stochastic Sampling

• Diversity & Creativity
  Greedy or beam search decoding tends to produce utterly predictable, repetitive text (“I am a… I am a…”) because it always picks the highest-probability token. Stochastic sampling injects controlled randomness.

• Better Approximation of Human Language
  Natural language is inherently non-deterministic. Sampling better mirrors that variability, making conversations or creative tasks feel more authentic.

• Controllable Randomness
  By tuning temperature, k, or p, you can dial up creativity (randomness) or dial it down for more safe, coherent outputs (e.g., poetry vs. technical instructions).

When to Use Deterministic Sampling

• High‐precision tasks (e.g., code completion, math proofs) sometimes prefer greedy or beam search to maximize accuracy and reduce hallucinations.

• Strict consistency requirements (e.g., formal document drafting) may benefit from more deterministic decoding.