NLP: Greedy, top-k and top-p

Implement the token filters an LLM uses before it picks its next word.

What to build

A program that prints the greedy choice and the renormalized top-k and top-p sets of a next-token distribution.

Requirements

  • Order the tokens by probability, highest first; equal probabilities keep their input order.
  • Print greedy: token (the first in that order), then top-k: ... with the first k tokens, then top-p P: ... with the shortest prefix of the order whose probabilities add up to at least P (P as written in the input).
  • In both lists, print each kept token followed by its probability divided by the kept total, to three decimal places, in that order.

Input

Line 1: tokens. Line 2: their probabilities (adding up to 1). Line 3: k. Line 4: p.

Output

Three lines.

Constraints

At most 1,000 tokens; 1 ≤ k ≤ number of tokens; 0 < p ≤ 1.

Example

Input:

mat floor sofa moon
0.5 0.2 0.2 0.1
2
0.8

Output:

greedy: mat
top-2: mat 0.714 floor 0.286
top-p 0.8: mat 0.556 floor 0.222 sofa 0.222

Why it works

Both filters cut off the unlikely tail of the distribution; top-k keeps a fixed number of tokens, while top-p keeps however many are needed to cover p of the probability, and renormalizing turns the kept part into a distribution again.

Examples

Example 1 · Input
mat floor sofa moon
0.5 0.2 0.2 0.1
2
0.8
Expected output
greedy: mat
top-2: mat 0.714 floor 0.286
top-p 0.8: mat 0.556 floor 0.222 sofa 0.222
Example 2 · Input
a b c
0.2 0.7 0.1
1
0.5
Expected output
greedy: b
top-1: b 1.000
top-p 0.5: b 1.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

`sorted(range(n), key=lambda i: -probs[i])` orders token positions by probability and keeps input order for ties.

Hint 2

For top-p, add tokens in that order until the running total reaches p; compare with a small tolerance, `total >= p - 1e-9`.

Solution

Show one correct solution (try it yourself first)
tokens = input().split()
probs = [float(x) for x in input().split()]
k = int(input())
p_text = input().strip()
p = float(p_text)
order = sorted(range(len(tokens)), key=lambda i: -probs[i])


def show(kept):
    total = sum(probs[i] for i in kept)
    return " ".join(f"{tokens[i]} {probs[i] / total:.3f}" for i in kept)


print("greedy:", tokens[order[0]])
print(f"top-{k}:", show(order[:k]))
kept, running = [], 0.0
for i in order:
    kept.append(i)
    running += probs[i]
    if running >= p - 1e-9:
        break
print(f"top-p {p_text}:", show(kept))

Lesson: Attention, transformers and LLMs in practice →