← All problems
#104 Min P Sampling Medium

Implement batched min-p sampling, a logit-filtering primitive used in modern LLM serving stacks such as vLLM, Hugging Face TGI, and llama.cpp. Given a batch of logits logits of shape \(B \times V\) and a scalar min_p in \([0, 1]\), produce a batch of filtered probabilities probs of the same shape. For each row \(b\):

  1. Convert logits to probabilities with softmax: \(p_{b,i} = \exp(z_{b,i}) / \sum_j \exp(z_{b,j})\).
  2. Find the maximum probability in the row: \(p^{\max}_b = \max_i p_{b,i}\).
  3. Mask every token whose probability is below \(\text{min\_p} \cdot p^{\max}_b\) (set it to 0).
  4. Renormalize the surviving probabilities so they sum to 1.

Unlike top-k or top-p sampling, min-p does not require any sort: the cutoff is defined relative to the row's most likely token, which makes it well-suited to GPU parallelization while still adapting to how peaked or flat each distribution is.

Implementation Requirements

Example

With B = 2, V = 4, min_p = 0.1:

Input logits (2×4): \[ \begin{bmatrix} 1.0 & 2.0 & 3.0 & 4.0 \\ -1.0 & 0.0 & 1.0 & -2.0 \end{bmatrix} \]

For row 0, \(\max z = 4\) so \(e = [e^{-3}, e^{-2}, e^{-1}, e^{0}] \approx [0.0498, 0.1353, 0.3679, 1.0000]\). The first entry falls below the threshold \(\text{min\_p} = 0.1\) (note that \(e^{-3} / \sum e < 0.1 \cdot e^{0} / \sum e\)), so it is masked. Renormalizing the rest gives row 0 of probs. For row 1, \(\max z = 1\) and the last entry is masked by the same reasoning.

Output probs (2×4): \[ \begin{bmatrix} 0.0000 & 0.0900 & 0.2447 & 0.6652 \\ 0.0900 & 0.2447 & 0.6652 & 0.0000 \end{bmatrix} \]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.