Nucleus (Top-p) Filtering on a Probability List
Problem statement
When a language model samples its next token with nucleus (top-p) sampling, it first cuts off the unlikely tail of the distribution. It keeps the smallest set of most probable tokens whose total probability reaches a threshold $p$, renormalizes that set, and samples only from it.
Implement the filtering step. You are given probs, a list of $n$ non-negative probabilities that sum to 1, and a threshold $p$ with $0 < p \le 1$. Return a list of the same length, in the same order as the input, where:
- Kept entries: walk from the highest probability down and keep entries until the running sum of the kept probabilities is at least $p$ (a sum exactly equal to $p$ counts as reaching it). When probabilities are equal, the entry with the lower index comes first.
- Renormalization: each kept entry is divided by the sum of the kept entries, so they sum to 1.
- Everything else: every other entry is
0.0.
def top_p_filter(probs: list[float], p: float) -> list[float]:
...
Constraints
- $1 \le n \le 300$
probs[i]$\ge 0$ and the entries sum to 1- $0 < p \le 1$
- Outputs are compared with a relative tolerance of $10^{-9}$.
Examples
Example 1: probs = [0.2, 0.2, 0.3, 0.3], p = 0.5 returns [0.0, 0.0, 0.5, 0.5]. The two 0.3 entries already sum to 0.6, which reaches 0.5. Renormalized they are 0.5 each, and they stay in their original positions.
Example 2: probs = [0.25, 0.5, 0.125, 0.125], p = 0.75 returns [0.3333..., 0.6666..., 0.0, 0.0]. 0.5 + 0.25 = 0.75 reaches $p$ exactly, so the 0.125 entries are dropped.
Example 3: probs = [0.25, 0.25, 0.25, 0.25], p = 0.6 returns [0.3333..., 0.3333..., 0.3333..., 0.0]. Three entries are needed, and the tie is broken by index.
Show hint
If the probabilities were already sorted from most to least likely, what shape would the kept set have?
Relevant roles: LLM Engineer, ML Engineer, Deep Learning Engineer and AI Engineer.
Related free problems
- Temperature, Top-k, Top-p and Min-p Sampling from ScratchML CodingMedium
- Greedy, Top-k and Top-p Decoding in NumPyML CodingMedium