LLM Systems

Beam Search and Sequence Decoding

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

status: reviewimportance: importantdifficulty 3/5math: undergraduateread: 21mlive demo

Back to LLM Systems Next: Structured Decoding: Token Masks From Schema Automata

Concept Structure

Beam Search and Sequence Decoding

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

3prerequisites

3next concepts

4related links

Learner Contract

What this page should let you do.

You are here becauseDecode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

This LLM Systems concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisMaximum Likelihood

3 prerequisites listed; refresh them before leaning on the math or code.

Maximum Likelihood N-gram Language Models (review)Decoding & Sampling: Temperature, Top-p & Inference-Time Control

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextStructured Decoding: Token Masks From Schema Automata

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Structured Decoding: Token Masks From Schema Automata

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.

Claims1/1 reviewed

Sources5 cited

Codeattached

Demolive

Reviewed2026-07-02

Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about this Research room

ConceptBeam Search and Sequence DecodingLLM Systems EquationBeam Search and Sequence Decoding equation 1Exact equation CodeBeam Search and Sequence Decoding runnable code 1Exact runnable code DemoBeam Search and Sequence Decoding interactive demoInteractive demo ClaimBeam search keeps a bounded frontier of high-log-probability partial...Exact claim check SourceDive into Deep Learning: Beam SearchExact source

ConceptBeam Search and Sequence DecodingLLM Systems

5 sources attachedLocal snapshot ready

concept:llm-systems/beam-search

Codenearby Predictbefore reveal Roomitem handoff

01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Decoding is the moment when a model's probability distribution becomes an actual sequence.

Greedy decoding does the simplest thing: at each step, pick the next token with the highest probability. That feels reasonable until you remember that sequence probability is a product of conditional choices. A locally best first token can lead into a weak continuation, while a slightly worse first token can open a much stronger path.

Beam search keeps a small search frontier alive.

At each step:

Expand every current partial sequence by possible next tokens.
Score each new partial sequence by accumulated log probability.
Keep only the best $k$ unfinished partial sequences.
Move any sequence that reaches <eos> into the completed set.

The beam size $k$ is the width of the frontier. When $k=1$ , beam search collapses to greedy search. Larger $k$ explores more alternatives, but it also costs more and can still prune the globally best sequence.

The thing to feel is the pruning boundary. Beam search does not reason over the whole tree. It keeps a few partial hypotheses alive long enough to avoid some early mistakes.

This also explains why beam search is not sampling. Sampling draws from a probability distribution to produce diverse outputs. Beam search approximates an argmax-style search for high-scoring sequences. That makes it natural for constrained, input-grounded tasks like translation or speech recognition, and much less natural as a default for open-ended chat or creative generation.

One more wrinkle: raw sequence log probabilities usually get more negative as a sequence gets longer, because each extra token contributes another log probability. Production decoders often use length penalties or related stopping rules. Those choices are not cosmetic; they can change the winning sequence.

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt

Equation 1 $p(y_{1:T}\mid x)=\prod_{t=1}^{T}p(y_t\mid y_{<t},x).$ Equation 2 $S(y_{1:t})=\sum_{i=1}^{t}\log p(y_i\mid y_{<i},x).$

Let $x$ be the conditioning input and let $y_{1:t}$ be a generated prefix. An autoregressive model gives

p(y_{1:T}\mid x)=\prod_{t=1}^{T}p(y_t\mid y_{<t},x).

Search is easier in log space:

S(y_{1:t})=\sum_{i=1}^{t}\log p(y_i\mid y_{<i},x).

Greedy decoding chooses

y_t=\operatorname*{argmax}_{v\in\mathcal V}p(v\mid y_{<t},x).

Beam search keeps a set $B_t$ of at most $k$ unfinished prefixes. To update it, expand the frontier:

\widetilde B_{t+1} =\{(y_{1:t},v): y_{1:t}\in B_t,\ v\in\mathcal V\}.

Then keep the $k$ unfinished prefixes with largest accumulated score:

B_{t+1} =\operatorname{TopK}_{k} \left\{y_{1:t+1}\in\widetilde B_{t+1}: y_{t+1}\neq \texttt{<eos>}\right\}.

Any prefix that emits <eos> moves into a completed set $C$ . At the end, choose a completed hypothesis by a final score such as

\operatorname{score}_{\alpha}(y_{1:L}) =\frac{1}{L^\alpha} \sum_{t=1}^{L}\log p(y_t\mid y_{<t},x),

where $L$ is the non-<eos> output length and $\alpha\ge 0$ controls length normalization.

The edge cases matter:

$k=1$ gives greedy decoding.
$k=|\mathcal V|^T$ approaches exhaustive search, but that is infeasible.
Completed hypotheses should not keep expanding after <eos>.
A wider beam can change latency, memory, diversity, and task quality; it is not a monotonic "better" switch.

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt

Runnable code 1import math EOS = "<eos>" T = { (): [("a", -0.18), ("the", -0.25), ("an", -0.40)], ("a",): [(...python

import math

EOS = "<eos>"
T = {
    (): [("a", -0.18), ("the", -0.25), ("an", -0.40)],
    ("a",): [("new", -0.32), ("strange", -0.58), ("small", -0.90)],
    ("the",): [("cause", -0.28), ("results", -0.45), ("theory", -0.70)],
    ("an",): [("old", -0.95), ("interesting", -1.10)],
    ("a", "new"): [("particle", -0.22), ("method", -0.55)],
    ("the", "cause"): [("of", -0.20), ("behind", -0.42)],
    ("the", "results"): [("about", -0.48), ("idea", -0.92)],
    ("a", "new", "particle"): [(EOS, -0.25), ("collided", -0.70)],
    ("the", "cause", "of"): [("gravity", -0.30), ("it", -0.80)],
    ("the", "cause", "of", "gravity"): [(EOS, -0.05)],
}

def norm_score(tokens, score, alpha=0.7):
    length = max(1, sum(tok != EOS for tok in tokens))
    return score / (length ** alpha)

def beam_search(k=3, alpha=0.7):
    beam, done = [((), 0.0)], []
    for _ in range(5):
        expanded = []
        for prefix, score in beam:
            for tok, logp in T.get(prefix, []):
                nxt = prefix + (tok,)
                (done if tok == EOS else expanded).append((nxt, score + logp))
        beam = sorted(expanded, key=lambda x: x[1], reverse=True)[:k]
    return max(done, key=lambda x: norm_score(*x, alpha))

for k in [1, 3]:
    seq, score = beam_search(k)
    print(k, " ".join(seq), round(score, 2), round(norm_score(seq, score), 2))

The table is tiny, but the invariant is real: beam search keeps a bounded frontier of prefixes, prunes by accumulated log probability, moves <eos> sequences into a completed set, and may choose a different final sequence after length normalization.

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the Beam Search Frontier Lab as a prediction check.

Choose a beam width, predict which completed sequence wins after the length penalty, then reveal the frontier.

Expand: every active partial hypothesis proposes next tokens.
Prune: only the best $k$ unfinished prefixes remain alive.
Complete: any <eos> prefix moves into the completed tray.
Length penalty: final ranking can differ from raw cumulative log probability because the length-normalized score changes the comparison.

Before reveal, the scores and winner are locked. After reveal, compare the greedy path with the beam frontier, name the pruning boundary, and explain exactly which prefix greedy discarded too early.

Live Concept Demo

Explore Beam Search and Sequence Decoding

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 3/5undergraduatecode-aligned

Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Beam Search and Sequence Decoding should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

Prediction open01 / Intuition

Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Beam Search and Sequence Decoding should make visible.

Visual Inquiry

Make the image answer a mathematical question

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

4/4 stages readyLive demo connected

Visual cueWhich visible object should carry the first intuition?

Inspection depth2/4

Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Beam Search and Sequence Decoding easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

book · 2026Dive into Deep Learning: Beam SearchZhang, Lipton, Li, and Smola

Defines greedy search, exhaustive search, beam size, candidate expansion, highest-probability partial sequences, EOS completion, length-normalized score, and complexity.

Open source

course-notes · 2019CS224N: Neural Machine Translation, Seq2seq and AttentionStanford CS224N

Frames decoding as finding the highest-probability translation, contrasts exhaustive, sampling, greedy, and beam search, and defines beam search as maintaining K candidates.

Open source

paper · 2014Sequence to Sequence Learning with Neural NetworksSutskever, Vinyals, and Le

Primary seq2seq paper describing left-to-right beam search with B partial hypotheses, vocabulary expansion, log-probability pruning, and EOS-completed hypotheses.

Open source

book · 2026Speech and Language Processing, Chapter 7: Neural Language Models and GenerationJurafsky and Martin

Supports the caveat that beam search works well for constrained tasks such as machine translation, while open-ended LLM generation generally uses sampling.

Open source

documentation · 2026Transformers: Generation StrategiesHugging Face

Current implementation-facing source for num_beams, greedy equivalence when num_beams is 1, and beam search as keeping multiple generated sequences.

Open source

Claim Review

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources5 references

d2l-2026-beam-search, cs224n-2019-nmt-decoders, sutskever-2014-seq2seq, jurafsky-martin-slp3-generation, huggingface-2026-generation-strategies

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedBeam search keeps a bounded frontier of high-log-probability partial hypotheses, moves EOS hypotheses into a completed set, and ranks completed sequences with task-specific scoring rather than ordinary sampling.Claim metadata: source checked

D2L, CS224N, and Sutskever et al. support the search frontier, top-K partial hypotheses, cumulative/log probability scoring, EOS completion, and length-normalized ranking. SLP3 and Hugging Face support the constrained-task and implementation caveats.

Sources: Dive into Deep Learning: Beam Search, CS224N: Neural Machine Translation, Seq2seq and Attention, Sequence to Sequence Learning with Neural Networks, Speech and Language Processing, Chapter 7: Neural Language Models and Generation, Transformers: Generation StrategiesFinite toy frontier only; real decoding uses model logits, tokenizer-specific EOS behavior, implementation-specific stopping rules, task metrics, and quality tradeoffs that can make larger beams worse or inappropriate for open-ended generation.A bounded review summary is present; still check caveats and exact reference scope.

Checked D2L beam search, Stanford CS224N NMT notes, Sutskever/Vinyals/Le 2014, SLP3 generation notes, and Hugging Face generation docs for greedy failure, K-candidate beam maintenance, vocabulary expansion, log-probability pruning, EOS completion, length-normalized final scoring, constrained-task suitability, num_beams behavior, and the sampling distinction. GPT Pro/Oracle publication critique remains pending because 127.0.0.1:51672 refused connection.

Reviewer: codex-local-primary-source-audit; reviewed 2026-07-02

source-span-d2l-2026-beam-search source-span-cs224n-2019-nmt-decoders source-span-sutskever-2014-seq2seq Equation 1 Equation 2 Runnable code 1 Interactive demo

Source support candidates

book 2026Dive into Deep Learning: Beam Search

Defines greedy search, exhaustive search, beam size, candidate expansion, highest-probability partial sequences, EOS completion, length-normalized score, and complexity.

course-notes 2019CS224N: Neural Machine Translation, Seq2seq and Attention

Frames decoding as finding the highest-probability translation, contrasts exhaustive, sampling, greedy, and beam search, and defines beam search as maintaining K candidates.

paper 2014Sequence to Sequence Learning with Neural Networks

Primary seq2seq paper describing left-to-right beam search with B partial hypotheses, vocabulary expansion, log-probability pruning, and EOS-completed hypotheses.

book 2026Speech and Language Processing, Chapter 7: Neural Language Models and Generation

Supports the caveat that beam search works well for constrained tasks such as machine translation, while open-ended LLM generation generally uses sampling.

Mechanism checks

Equation 1

p(y_{1:T}\mid x)=\prod_{t=1}^{T}p(y_t\mid y_{<t},x).

Equation 2

S(y_{1:t})=\sum_{i=1}^{t}\log p(y_i\mid y_{<i},x).

Runnable code 1import math EOS = "<eos>" T = { (): [("a", -0.18), ("the", -0.25), ("an", -0.40)], ("a",): [(...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

Readiness0/3 checks ready

Predict

Before touching the demo, predict one visible change that should happen in Beam Search and Sequence Decoding.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Your answer canvas

Local checks

Claim

A concrete answer is on the canvas.

Mechanism

The answer names why the claim should hold.

Bridge

It touches the page context or a neighboring idea.

Misconception check

Grounded research drawerClose

ConceptBeam Search and Sequence DecodingLLM Systems

Runnable code comparisonBeam Search and Sequence Decoding runnable code 1EOS = "<eos>"Prediction before revealBeam Search and Sequence Decoding interactive demoManipulate one control and predict the visible change.

Grounded room questionWhat is the smallest example that makes Beam Search and Sequence Decoding click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.

Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptLLM Systems

Beam Search and Sequence Decoding

Attached question

What is the smallest example that makes Beam Search and Sequence Decoding click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action

Local action draft

This draft stays in this browser, attached to the selected learning item.

Draft noteNext action

No local draft saved.

Evidence to inspect

References to inspect: attached references on this page.
Definition, prerequisite, and contrast concept links
The equation or runnable code that makes the concept operational
One demo state that shows the invariant instead of a slogan

What would resolve this

The learner can state the mechanism in their own words
The learner can name the prerequisite that would repair confusion
The learner can predict how the mechanism changes under one perturbation

Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Beam Search and Sequence Decoding Selected item key: recorded for copy. Context: LLM Systems Page anchor: recorded for copy. Open question: What is the smallest example that makes Beam Search and Sequence Decoding click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context

concept/concept-notebook/llm-systems/beam-search
concept:llm-systems/beam-search

Learning Map

Before / Now / Try / Next

BeforeMaximum Likelihood

NowIntuition -> Math -> Code -> Demo

TryManipulate one control and predict the visible change.

NextStructured Decoding: Token Masks From Schema Automata

Intuitionready
Mathready
Codeready
Interactive Demoready

AI Companion

Ask beside the selected object

Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner.

Your question

GoalComfortStyleStuck on

Context prompt

You are my AI learning companion for Continuous Function. Current context: LLM Systems concept. Learning surface: Beam Search and Sequence Decoding. What this page says: Decode sequences by keeping a small frontier of promising partial hypotheses, then inspect how pruning, EOS completion, and length normalization change the winner. Current section: Intuition, math, code, and interactive demo. Suggested next step: Manipulate one control and predict the visible change.. Learner goal: Understand the idea. Learner comfort level: New to this. Preferred explanation style: Visual first. Task: Explain the central idea in plain language, then restate it with the exact math objects from the page. Answer in a way that helps me learn: ask one clarifying question only if needed, use intuition before notation, and end with one thing I should try on the page.

Domain

LLM Systems

llm-systemsdecodingsearchsequence-modelingmachine-translation

Prerequisites

Maximum Likelihood N-gram Language Models (review)Decoding & Sampling: Temperature, Top-p & Inference-Time Control

Leads To

Structured Decoding: Token Masks From Schema Automata Speculative Decoding: Lossless Multi-Token Generation Machine Translation (review)

Seq2seq and Encoder-Decoder Attention (review)Tokenization & Vocabulary Design Tree Search Reasoning: Allocating Inference Budget Across Prefixes (review)Structured Decoding: Token Masks From Schema Automata

Within this domain