Implement Top-k and Top-p Sampling

Free with account Updated Nov 16, 2026 · 5 min read
On this page

    Problem statement

    Implement sample_next_token(logits, temperature, top_k, top_p) in NumPy. logits is a 1-D array of raw scores, one per vocabulary token. Apply temperature, then keep only the top_k highest-scoring tokens (0 means no limit), then keep the smallest set of the remaining tokens whose probabilities add up to at least top_p (1.0 means no limit), renormalise, and return the token id of one random draw. Temperature 0 means greedy decoding.

    This is one of the most frequently reported ML coding tasks for LLM roles. It looks simple; the marks are in the order of operations, the edge cases, and returning the right index.

    Example

    With these example probabilities, top-k = 3 keeps three tokens; top-p = 0.9 keeps four, because the first three only reach 0.87.
    With these example probabilities, top-k = 3 keeps three tokens; top-p = 0.9 keeps four, because the first three only reach 0.87.
    probabilities:  hit 0.45  missed 0.30  cold 0.12  full 0.08  purple 0.05
    temperature=0   → always "hit"
    top_k=3         → hit 0.52, missed 0.35, cold 0.14 (renormalised)
    top_p=0.9       → hit 0.47, missed 0.32, cold 0.13, full 0.08

    Constraints (assumed)

    • Vocabulary size V up to about 200,000; one call per generated token, so it must be vectorised.
    • 0 ≤ temperature; 0 ≤ top_k ≤ V; 0 < top_p ≤ 1.
    • A random generator can be passed in for reproducible tests.

    What this question tests

    • Knowing what each knob does and the order in which to apply them.
    • Numerical stability (shift before exp) and renormalising after filtering.
    • Correct index bookkeeping between sorted positions and token ids.
    • Handling edge cases: temperature 0, top_p very small, ties.

    Questions to ask first

    1. What should temperature 0 do? (Greedy: argmax.)
    2. If both top-k and top-p are set, which applies first? (Common convention: top-k, then top-p.)
    3. Does top-p include the token that crosses the threshold? (Yes: keep the smallest set whose sum is ≥ p.)
    4. Single sequence or a batch? (Single here; batching is a follow-up.)
    5. Any repetition penalty or banned tokens? (Not here.)