Greedy decoding grabs the single highest-probability token at every step and never looks back — so it can walk straight past the most-probable sequence. Beam search keeps the top B partial sequences alive at once, scoring each by cumulative log-probability (a running sum of logs, never a product). Down the center, data flows: the token tree goes in, the beams search, the chosen sequence comes out. The blue team builds and defends; the red team attacks.
source Alex Graves, Sequence Transduction with Recurrent Neural Networks (2012) — arxiv.org/abs/1211.3711, which decodes with a beam of width 4000. AMBER beam search itself is older than this paper (speech recognition, e.g. Lowerre's HARPY, 1976); Graves 2012 is cited as a clear sequence-decoding reference, not the origin. Rendered, not quoted.
A decoder assigns each next token a probability given the prefix. Take logs: a sequence's score is the sum of its step log-probs — and log(p·q) = log p + log q, so summing logs is exactly scoring by the sequence's probability, without underflow.
Beam(B): expand every kept beam by every next token, then keep the top B partial sequences by cumulative score. B=1 is greedy. Larger B lets an early low-probability token survive if it pays off later.
On the fixed demo tree, live scores of the chosen sequence:
| who | sequence | Σ log p | prob |
|---|
Beam search does not invent scores — it searches over what a model could say next. The distribution at each step is exactly the output of a causal language model conditioned on the prefix.
Its neighbour the-causal-mask is what produces those next-token log-probs by forbidding a position from seeing the future. That sphere emits the tree; this sphere walks it. Each sphere is the next one's premise.
The blue team's live check: re-run greedy, beam, and an exhaustive brute-force search over the fixed demo tree and confirm beam ≥ greedy and beam finds the global best. If red tampers, this badge turns red.
A tiny decoder over vocabulary {A, B} for 3 steps — 8 complete sequences. At each prefix the model gives a proper probability over the next token; the branch log-prob is ln(p). This is the whole input the search sees.
| prefix | P(A) | P(B) | ln P(A) | ln P(B) |
|---|
The trap: A is the likeliest first token (0.6), but its whole subtree is flat — while the rarer B hides one sharp continuation (BAA, p = 0.324). Greedy takes the bait.
Fixed demo tree: greedy is provably beaten by beam. The witness self-checks against this tree.
Kept beam alive; pruned beam dropped. Every score is computed on the spot.
| step | kept beams (seq : Σlogp) |
|---|
Change B or the tree — greedy, beam, and the brute-force optimum are all re-searched live, never looked up.
What the machine produces, proven on the demo tree: greedy returns AAA (p = 0.15), but beam with B ≥ 2 returns BAA (p = 0.324) — the global optimum, matching an exhaustive search over all 8 sequences. Scores are cumulative log-probs: ln(0.324) = −1.1272.
The blue team's witness (left) confirms beam ≥ greedy and beam = optimum live; the red team (right) tries to make the search return junk.
Worse, log-prob sum favours short sequences (every added token subtracts), so raw beam search is length-biased — real decoders add length normalization. And the global optimum under the model is only as good as the model: a confident wrong distribution is searched faithfully to a confident wrong answer.
"Beam search finds the best sequence." Cut. It finds the best only if the beam never prunes an on-path prefix — a guarantee only exhaustive width (B ≥ vocab^depth) gives. Here B=2 happens to suffice; it need not in general.
"Bigger beam is always better." Cut. Monotonic improvement is not guaranteed; empirically large beams can degrade quality (the "beam search curse" in NMT). The adversary is right to distrust it.
"Scores multiply the probabilities." Kept, corrected. Scores sum the logs — equal in ranking to multiplying probs, but numerically stable. The self-check asserts sum-of-logs equals log-of-product.
The red team's move: at each step keep the WORST B beams (lowest cumulative log-prob) instead of the best. The search then returns a low-probability sequence — worse even than greedy. The blue team's witness (window 7) is watching.
Flip the pruning to keep the lowest scores and the search returns junk (BBA, p = 0.02) — the witness recomputes, sees beam < greedy, and turns red. Nothing is faked; the attack is real and it is caught.