Before sampling, applications cut off the unlikely tokens. Apply both common filters.
What to build
A program that finds the top-k and top-p sets of tokens and renormalizes the top-p probabilities.
Requirements
- Rank tokens by probability, highest first; equal probabilities keep their input order.
- Print
top-k:followed by the first k ranked tokens. - Print
top-p:followed by the smallest prefix of the ranking whose probabilities add up to at least p. - Print
renormalized:followed byTOKEN Ppairs for the top-p tokens, each probability divided by their total, with 3 decimal places.
Input
Line 1: the tokens. Line 2: their probabilities (adding up to 1). Line 3: k. Line 4: p.
Output
Three lines.
Constraints
1 to 1000 tokens; 1 ≤ k ≤ number of tokens; 0 < p ≤ 0.99.
Example
Input:
blue grey clear green
0.5 0.25 0.15 0.1
2
0.8
Output:
top-k: blue grey
top-p: blue grey clear
renormalized: blue 0.556 grey 0.278 clear 0.167
Why it works
Both filters remove the long tail of unlikely tokens that can derail generation; renormalizing makes the kept probabilities a proper distribution again.
Examples
blue grey clear green 0.5 0.25 0.15 0.1 2 0.8
top-k: blue grey top-p: blue grey clear renormalized: blue 0.556 grey 0.278 clear 0.167
a b 0.6 0.4 1 0.5
top-k: a top-p: a renormalized: a 1.000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the tokens by probability from highest to lowest; keep the input order for equal probabilities.
Hint 2
Top-k is the first k; top-p adds tokens from the top until their total is at least p.
Hint 3
Renormalize the top-p tokens by dividing each probability by their total.
Solution
Show one correct solution (try it yourself first)
tokens = input().split()
probs = list(map(float, input().split()))
k = int(input())
p = float(input())
ranked = sorted(zip(tokens, probs), key=lambda tp: -tp[1])
print("top-k:", *[t for t, _ in ranked[:k]])
kept, total = [], 0.0
for t, q in ranked:
kept.append((t, q))
total += q
if total >= p:
break
print("top-p:", *[t for t, _ in kept])
print("renormalized:", *[f"{t} {q / total:.3f}" for t, q in kept])
Lesson: Decoding: temperature, top-k, top-p and beam search →