Top-k and top-p filtering

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 by TOKEN P pairs 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

Example 1 · Input
blue grey clear green
0.5 0.25 0.15 0.1
2
0.8
Expected output
top-k: blue grey
top-p: blue grey clear
renormalized: blue 0.556 grey 0.278 clear 0.167
Example 2 · Input
a b
0.6 0.4
1
0.5
Expected output
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 →