Deep learning: Greedy decoding and beam search

Generate text from next-token probabilities in two ways and compare them.

What to build

A program that decodes the most likely sequence from a next-token table with greedy search and with beam search.

Requirements

  • The table gives, for each token, the probability of each possible next token. Generation starts after the token START and ends at END or after M tokens. A sequence's probability is the product of its steps' probabilities. Beam search keeps B candidates per step as described in the hints; when no unfinished candidates remain or M tokens have been generated, the answer is the most probable kept sequence (ties: alphabetical).
  • Print greedy: TOKENS (P) and beam: TOKENS (P), tokens without START and probabilities with four decimal places.

Input

Line 1: B and M. Line 2: r. Then r lines TOKEN NEXT1 P1 NEXT2 P2 ….

Output

Two lines.

Constraints

B ≤ 10; M ≤ 20; at most 50 tokens.

Example

Input:

2 5
6
START a 0.6 b 0.4
a c 0.5 d 0.5
b e 0.9 c 0.1
c END 1.0
d END 1.0
e END 1.0

Output:

greedy: a c END (0.3000)
beam: b e END (0.3600)

Why it works

Greedy search commits to the best single step and can miss a better whole sequence; beam search keeps several partial sequences alive, so a weaker first step that leads to stronger continuations can still win.

Examples

Example 1 · Input
2 5
6
START a 0.6 b 0.4
a c 0.5 d 0.5
b e 0.9 c 0.1
c END 1.0
d END 1.0
e END 1.0
Expected output
greedy: a c END (0.3000)
beam: b e END (0.3600)
Example 2 · Input
1 5
6
START a 0.6 b 0.4
a c 0.5 d 0.5
b e 0.9 c 0.1
c END 1.0
d END 1.0
e END 1.0
Expected output
greedy: a c END (0.3000)
beam: a c END (0.3000)

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

Hints

Hint 1

Greedy: from START, repeatedly take the most likely next token (ties: alphabetical) until END or M tokens.

Hint 2

Beam: at each step extend every unfinished sequence by every possible next token, rank all candidates by probability (ties: by token sequence, alphabetically), keep the best B, and set aside those ending in END.

Solution

Show one correct solution (try it yourself first)
B, M = map(int, input().split())
table = {}
for _ in range(int(input())):
    token, *rest = input().split()
    table[token] = {rest[i]: float(rest[i + 1]) for i in range(0, len(rest), 2)}

seq, prob, word = [], 1.0, "START"
while len(seq) < M and table.get(word):
    word, p = min(table[word].items(), key=lambda item: (-item[1], item[0]))
    seq.append(word)
    prob *= p
    if word == "END":
        break

beams, finished = [((), 1.0)], []
for _ in range(M):
    candidates = []
    for s, p in beams:
        last = s[-1] if s else "START"
        for token, q in table.get(last, {}).items():
            candidates.append((s + (token,), p * q))
    if not candidates:
        break
    candidates.sort(key=lambda c: (-c[1], c[0]))
    kept = candidates[:B]
    finished += [c for c in kept if c[0][-1] == "END"]
    beams = [c for c in kept if c[0][-1] != "END"]
    if not beams:
        break
best = min(finished + beams, key=lambda c: (-c[1], c[0]))
print(f"greedy: {' '.join(seq)} ({prob:.4f})")
print(f"beam: {' '.join(best[0])} ({best[1]:.4f})")

Lesson: Transformers →