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\):
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.
solve(logits, probs, min_p, B, V); do not change the signature or use external libraries beyond the standard GPU frameworks.probs buffer. Every row must sum to exactly 1; masked positions must be exactly 0.
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}
\]
B ≤ 256V ≤ 200,000min_p ≤ 1.0logits[b, i] ≤ 50.0float32B = 64, V = 128,000, min_p = 0.05