Introduction

Every time a language model finishes your sentence, translates a paragraph, or writes a caption for a photo, it faces the same impossible-sounding challenge: pick one sequence of words from an astronomically large space of possibilities. A vocabulary of 50,000 tokens and a sentence of twenty words yields 50,00020000^{20} candidates โ€” more arrangements than atoms in the observable universe.

The naive fix is greedy search: at each step, pick the single most likely next token and commit. It is blazing fast, but it is myopic โ€” a locally brilliant choice can trap the decoder in a globally mediocre sentence.

Beam search is the middle path. At every step it keeps not one but K candidates (the "beam"), extending each by every possible next token and then keeping only the K best-scoring continuations. When the beam width K = 1 you get greedy search; as K grows you approach exhaustive search โ€” but even with K = 5 or 10, the algorithm is orders of magnitude cheaper than brute force.

The price is optimality: beam search is not guaranteed to find the highest-probability sequence. The cost is also diversity: a narrow beam can produce repetitive, over-confident output. Yet this controlled approximation has been the dominant decoding strategy in neural machine translation and large language models since around 2015 โ€” a pragmatic bet that the best K candidates carry most of the probability mass.

Try It

The tree below has branch factor 3 and depth 3. Each edge carries a cost (lower is better). Beam search keeps only the top-K paths by cumulative cost at each level, discarding the rest.

Change the beam width with the buttons, then press Run to watch the algorithm step through the tree. Notice how a narrow beam misses the globally optimal path while a wider beam finds it โ€” at the cost of considering more nodes.

<div class="controls">
  <span class="label">Beam width:</span>
  <button class="bw-btn active" data-k="1">1</button>
  <button class="bw-btn" data-k="2">2</button>
  <button class="bw-btn" data-k="3">3</button>
  <button id="run-btn" type="button">Run</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div class="step-info" id="step-info">Press Run to start.</div>
<svg id="tree-svg" viewBox="0 0 540 320" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
.label { font-size: .85rem; color: #555; }
.bw-btn { font: 600 14px system-ui; padding: .3rem .7rem; border: 1.5px solid #1d3557;
          background: #fff; color: #1d3557; border-radius: 6px; cursor: pointer; }
.bw-btn.active { background: #1d3557; color: #fff; }
button { font: 600 14px system-ui; padding: .35rem .8rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.step-info { font-size: .88rem; color: #444; min-height: 1.5em; margin-bottom: .3rem; }
#tree-svg { width: 100%; height: auto; display: block; }
.result { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .4rem; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// โ”€โ”€ Tree definition โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Nodes: id, label, level (0=root, 1, 2, 3=leaves), position (col)
// Edges: from -> to with cost. Total tree: 1 root -> 3 children -> 9 grandchildren -> 27 leaves
// We use a trimmed 1-3-9-27 tree but display only the first 9 leaves (3 per branch)
// for a 540px canvas. Optimal path: the one with minimum cumulative cost.

// Layout: 9 positions across width for leaves
// Level 0: root at x=270
// Level 1: 3 nodes
// Level 2: 9 nodes
// We'll show depth-3 with 3 branches at each level (factor 3)

const W = 540, H = 320;
const LEVELS = [
  [270],                        // root
  [100, 270, 440],              // level 1
  [40, 100, 160, 210, 270, 330, 380, 440, 500], // level 2 (leaves)
];
// Shrink to 3 levels (root + 2 more), leaves at level 2
// Costs for edges: [from-node-index][child-index] = cost
// We'll define 1 root โ†’ 3 children (costs), each child โ†’ 3 grandchildren (costs)
// Cumulative costs determine "optimal" path.
// Edge costs chosen so K=1 (greedy) is SUBOPTIMAL:
//   root->A costs only 1 (greedy picks it) but A's leaves all cost 8-10 โ†’ total 9-11
//   root->B costs 3 but B->e costs only 1 โ†’ total 4 (GLOBAL OPTIMUM)
//   K>=2 keeps B in the beam and finds the optimum; K=1 misses it.
const EDGE_COSTS = [
  // root -> level-1  (A=cheapest trap, B=optimal branch, C=mediocre)
  [1, 3, 5],
  // level-1[0]=A -> level-2 [a,b,c]  (all expensive)
  [8, 9, 10],
  // level-1[1]=B -> level-2 [d,e,f]  (e is the global best)
  [2, 1, 3],
  // level-1[2]=C -> level-2 [g,h,i]  (mediocre)
  [4, 5, 6],
];

// Compute cumulative costs for all root-to-leaf paths
// Path is identified by (l1-child, l2-child): 0-2, 0-2
function pathCost(l1, l2) {
  return EDGE_COSTS[0][l1] + EDGE_COSTS[1 + l1][l2];
}

// Find optimal (min cost) path
let optL1 = 0, optL2 = 0, optCost = Infinity;
for (let i = 0; i < 3; i++) for (let j = 0; j < 3; j++) {
  const c = pathCost(i, j);
  if (c < optCost) { optCost = c; optL1 = i; optL2 = j; }
}

// โ”€โ”€ SVG helpers โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const svg = document.getElementById('tree-svg');
const NS = 'http://www.w3.org/2000/svg';
function el(tag, attrs) {
  const e = document.createElementNS(NS, tag);
  for (const [k, v] of Object.entries(attrs)) e.setAttribute(k, v);
  return e;
}

const Y = [30, 130, 250];  // y coords for levels 0,1,2
const R = 18;               // node radius

// Node positions: level -> index -> {x, y}
const nodePos = [
  [{ x: 270, y: Y[0] }],
  [{ x: 100, y: Y[1] }, { x: 270, y: Y[1] }, { x: 440, y: Y[1] }],
  [
    { x: 40,  y: Y[2] }, { x: 100, y: Y[2] }, { x: 160, y: Y[2] },
    { x: 220, y: Y[2] }, { x: 270, y: Y[2] }, { x: 320, y: Y[2] },
    { x: 380, y: Y[2] }, { x: 440, y: Y[2] }, { x: 500, y: Y[2] },
  ],
];

// Edge list: { from: {lv,idx}, to: {lv,idx}, cost }
const edges = [];
for (let i = 0; i < 3; i++) {
  edges.push({ from: { lv: 0, idx: 0 }, to: { lv: 1, idx: i }, cost: EDGE_COSTS[0][i] });
  for (let j = 0; j < 3; j++) {
    edges.push({ from: { lv: 1, idx: i }, to: { lv: 2, idx: i * 3 + j }, cost: EDGE_COSTS[1 + i][j] });
  }
}

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let K = 1;
let stepIdx = 0;
let steps = [];    // array of beam states to animate
let timer = null;

// โ”€โ”€ Build steps โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Each step: { beam: [{lv, idx, cumCost, path:[{lv,idx}]}], pruned: [{lv,idx}] }
function buildSteps(k) {
  const result = [];
  // Step 0: just root active
  const root = [{ lv: 0, idx: 0, cumCost: 0, path: [{ lv: 0, idx: 0 }] }];
  result.push({ beam: root, pruned: [], expanded: [] });

  // Step 1: expand root -> level 1
  const expanded1 = [];
  for (const node of root) {
    for (let i = 0; i < 3; i++) {
      const cost = EDGE_COSTS[0][i];
      expanded1.push({ lv: 1, idx: i, cumCost: node.cumCost + cost, path: [...node.path, { lv: 1, idx: i }] });
    }
  }
  expanded1.sort((a, b) => a.cumCost - b.cumCost);
  const beam1 = expanded1.slice(0, k);
  const pruned1 = expanded1.slice(k);
  result.push({ beam: beam1, pruned: pruned1, expanded: expanded1 });

  // Step 2: expand beam1 -> level 2
  const expanded2 = [];
  for (const node of beam1) {
    for (let j = 0; j < 3; j++) {
      const cost = EDGE_COSTS[1 + node.idx][j];
      const leafIdx = node.idx * 3 + j;
      expanded2.push({ lv: 2, idx: leafIdx, cumCost: node.cumCost + cost, path: [...node.path, { lv: 2, idx: leafIdx }] });
    }
  }
  expanded2.sort((a, b) => a.cumCost - b.cumCost);
  const beam2 = expanded2.slice(0, k);
  const pruned2 = expanded2.slice(k);
  result.push({ beam: beam2, pruned: pruned2, expanded: expanded2 });

  return result;
}

// โ”€โ”€ Render โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function render(stepState) {
  svg.innerHTML = '';

  const beamNodes = new Set(stepState.beam.map(n => n.lv + ',' + n.idx));
  const prunedNodes = new Set(stepState.pruned.map(n => n.lv + ',' + n.idx));
  // Collect all nodes on beam paths
  const onPath = new Set();
  for (const n of stepState.beam) for (const p of n.path) onPath.add(p.lv + ',' + p.idx);

  // Draw edges
  for (const e of edges) {
    const p1 = nodePos[e.from.lv][e.from.idx];
    const p2 = nodePos[e.to.lv][e.to.idx];
    const toKey = e.to.lv + ',' + e.to.idx;
    const fromKey = e.from.lv + ',' + e.from.idx;
    const active = onPath.has(toKey) && onPath.has(fromKey);
    const pruned = prunedNodes.has(toKey);

    const line = el('line', {
      x1: p1.x, y1: p1.y, x2: p2.x, y2: p2.y,
      stroke: active ? '#e63946' : pruned ? '#ddd' : '#ccc',
      'stroke-width': active ? 2.4 : 1.2,
      'stroke-dasharray': pruned ? '4 3' : 'none',
    });
    svg.appendChild(line);

    // Edge cost label
    const mx = (p1.x + p2.x) / 2, my = (p1.y + p2.y) / 2;
    const costLbl = el('text', { x: mx + 6, y: my, 'text-anchor': 'start',
      'font-size': '11', 'font-family': 'system-ui', fill: active ? '#c92f3c' : '#888' });
    costLbl.textContent = e.cost;
    svg.appendChild(costLbl);
  }

  // Draw nodes
  for (let lv = 0; lv < 3; lv++) {
    for (let idx = 0; idx < nodePos[lv].length; idx++) {
      const { x, y } = nodePos[lv][idx];
      const key = lv + ',' + idx;
      const inBeam = beamNodes.has(key);
      const pruned = prunedNodes.has(key);
      const path = onPath.has(key);

      const fill = inBeam ? '#e63946' : pruned ? '#f0f0f0' : path ? '#ffd6d6' : '#e8eef3';
      const stroke = inBeam ? '#c92f3c' : pruned ? '#ccc' : '#9ab0c6';
      const textFill = inBeam ? '#fff' : pruned ? '#bbb' : '#1d3557';

      const circle = el('circle', { cx: x, cy: y, r: R, fill, stroke, 'stroke-width': 1.8 });
      svg.appendChild(circle);

      // Label: cumulative cost for beam nodes at level 2, else node name
      let label;
      if (lv === 0) label = 'S';
      else if (lv === 1) label = ['A','B','C'][idx];
      else label = ['a','b','c','d','e','f','g','h','i'][idx];

      const txt = el('text', { x, y: y + 5, 'text-anchor': 'middle',
        'font-size': '13', 'font-weight': '700', 'font-family': 'system-ui, monospace', fill: textFill });
      txt.textContent = label;
      svg.appendChild(txt);

      // Show cumulative cost for beam leaf nodes
      if (lv === 2 && inBeam) {
        const node = stepState.beam.find(n => n.lv === 2 && n.idx === idx);
        if (node) {
          const cost = el('text', { x, y: y + R + 14, 'text-anchor': 'middle',
            'font-size': '11', 'font-family': 'system-ui', fill: '#c92f3c', 'font-weight': '700' });
          cost.textContent = fmt('cost=%cumCost%', { cumCost: node.cumCost });
          svg.appendChild(cost);
        }
      }

      // Show cumulative cost for all expanded level-2 nodes
      if (lv === 2 && !inBeam && !pruned) {
        /* nothing โ€” unpruned expanded will be shown in next step */
      }
      if (lv === 2 && pruned) {
        const node = stepState.pruned ? stepState.pruned.find(n => n.lv === 2 && n.idx === idx) : null;
        if (node) {
          const cost = el('text', { x, y: y + R + 14, 'text-anchor': 'middle',
            'font-size': '11', 'font-family': 'system-ui', fill: '#bbb' });
          cost.textContent = fmt('cost=%cumCost%', { cumCost: node.cumCost });
          svg.appendChild(cost);
        }
      }
    }
  }

  // Legend
  const legend = [
    { color: '#e63946', label: 'In beam' },
    { color: '#f0f0f0', label: 'Pruned', stroke: '#ccc' },
    { color: '#e8eef3', label: 'Not yet visited', stroke: '#9ab0c6' },
  ];
  let lx = 10, ly = H - 10;
  for (const { color, label, stroke } of legend) {
    const c = el('circle', { cx: lx + 7, cy: ly - 5, r: 6, fill: color, stroke: stroke || color, 'stroke-width': 1.4 });
    svg.appendChild(c);
    const t = el('text', { x: lx + 17, y: ly, 'font-size': '10', 'font-family': 'system-ui', fill: '#555' });
    t.textContent = label;
    svg.appendChild(t);
    lx += 90;
  }
}

function setInfo(msg) { document.getElementById('step-info').textContent = msg; }
function setResult(msg, cls) {
  const r = document.getElementById('result');
  r.textContent = msg; r.className = 'result ' + (cls || '');
}

function stepMessages(k) {
  return [
    'Start: root node S is in the beam.',
    fmt('Level 1: expanded S โ†’ A, B, C. Keeping top-%k% by cost.', { k: k }),
    fmt('Level 2 (leaves): expanded beam. Keeping top-%k% final paths.', { k: k }),
  ];
}

// โ”€โ”€ Controls โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
document.querySelectorAll('.bw-btn').forEach(btn => {
  btn.addEventListener('click', () => {
    document.querySelectorAll('.bw-btn').forEach(b => b.classList.remove('active'));
    btn.classList.add('active');
    K = parseInt(btn.dataset.k, 10);
    stopAnim();
    stepIdx = 0;
    steps = [];
    render({ beam: [{ lv: 0, idx: 0, cumCost: 0, path: [{ lv: 0, idx: 0 }] }], pruned: [], expanded: [] });
    setInfo(fmt('Beam width set to %K%. Press Run.', { K: K }));
    setResult('');
  });
});

function stopAnim() {
  if (timer) { clearInterval(timer); timer = null; }
}

document.getElementById('run-btn').addEventListener('click', () => {
  stopAnim();
  steps = buildSteps(K);
  stepIdx = 0;
  const msgs = stepMessages(K);
  render(steps[0]);
  setInfo(msgs[0]);
  setResult('');

  timer = setInterval(() => {
    stepIdx++;
    if (stepIdx >= steps.length) {
      stopAnim();
      // Show result
      const finalBeam = steps[steps.length - 1].beam;
      const best = finalBeam[0];
      const pathLabels = best.path.map(n => {
        if (n.lv === 0) return 'S';
        if (n.lv === 1) return ['A','B','C'][n.idx];
        return ['a','b','c','d','e','f','g','h','i'][n.idx];
      }).join(' โ†’ ');
      const isOptimal = best.cumCost === optCost;
      setResult(
        fmt('Best path found: %pathLabels% (cost %cumCost%)%v%', { pathLabels: pathLabels, cumCost: best.cumCost, v: isOptimal ? ' โœ“ Optimal!' : ' โ€” ' + fmt('optimal is cost %optCost%', { optCost: optCost }) }),
        isOptimal ? 'ok' : 'bad'
      );
      setInfo(msgs[stepIdx - 1] || '');
      return;
    }
    render(steps[stepIdx]);
    setInfo(msgs[stepIdx]);
  }, 1100);
});

document.getElementById('reset-btn').addEventListener('click', () => {
  stopAnim();
  stepIdx = 0;
  steps = [];
  render({ beam: [{ lv: 0, idx: 0, cumCost: 0, path: [{ lv: 0, idx: 0 }] }], pruned: [], expanded: [] });
  setInfo('Press Run to start.');
  setResult('');
});

// Initial render
const msgs = stepMessages(K);
render({ beam: [{ lv: 0, idx: 0, cumCost: 0, path: [{ lv: 0, idx: 0 }] }], pruned: [], expanded: [] });
setInfo('Press Run to start.');
Result
Console

With beam width 1 (pure greedy) the algorithm always follows the cheapest local edge and may end up at a worse final node. With width 3 it keeps all branches at this scale and always finds the optimal path. Real language models operate with K = 4โ€“10 over vocabularies of tens of thousands โ€” still an approximation, but a very effective one.

The Real Complexity

Why not just find the best sequence exactly?

  • Exact decoding is intractable. For a vocabulary of size V and a sequence of length L, exhaustive search considers Vแดธ complete sequences โ€” infeasible for any realistic L. Even with dynamic programming tricks, finding the globally highest-probability sequence under a neural language model requires exponential time in general.
  • Beam search runs in O(Kโ‹…Vโ‹…L)O(K \cdot V \cdot L) time. At each of L steps, it scores V extensions for each of K candidates. This is polynomial in all parameters โ€” fast enough for real-time use.
  • But it gives up optimality. Beam search can and does miss the highest-scoring sequence. This is not a minor theoretical quibble: studies on neural machine translation have found that the exact optimal sequence (found by exhaustive decoding on small vocabularies) is often worse perceptually than what beam search returns โ€” a phenomenon called the beam search curse or optimal-is-bad paradox. Models trained with maximum-likelihood objectives learn to spread probability widely, making the exact MAP sequence degenerate.
  • Wider beams are not always better. Beyond a certain width, the quality of output plateaus or even degrades. Modern large language models often prefer sampling strategies (nucleus sampling, temperature scaling) over beam search for open-ended generation, precisely because beam search under-generates diversity.
  • The complexity class picture. Deciding whether a sequence with score above a threshold exists is NP-hard for certain model families. Beam search sidesteps this by returning a good sequence rather than a provably optimal one โ€” a pattern that appears throughout combinatorial search, from branch and bound to greedy graph coloring.

Where It Matters

Beam search is the silent engine behind an enormous fraction of modern AI output:

  • Neural machine translation: systems like those behind Google Translate and DeepL have used beam search (K โ‰ˆ 4โ€“10) since the sequence-to-sequence revolution of 2014โ€“2015. Each translated sentence is the top-K race.
  • Speech recognition: acoustic models decode phoneme sequences with beam search, balancing acoustic likelihood against a language model prior. The beam keeps plausible transcripts alive even when acoustics are ambiguous.
  • Image and video captioning: a visual encoder feeds a language decoder that beam-searches for the best descriptive sentence.
  • Code generation: models like GitHub Copilot generate code token by token; beam search (or close relatives) selects among continuations scored by a code-tuned language model.
  • Protein structure prediction: AlphaFold and related systems use beam-like strategies when assembling structural hypotheses across complex search spaces.
  • Summarization and dialogue: abstractive summarizers and chatbot response generators use beam search or sampling variants to produce fluent, coherent text.

The P vs NP question lurks in the background: if P = NP we might decode optimally; since we strongly believe P โ‰  NP, heuristics like beam search are not just a convenience โ€” they may be the best we can ever do in practice.

Conclusion

Beam search is a bet: keep the K most promising partial sequences at every step and hope the best answer survives the pruning. Most of the time, it does. The algorithm is fast, predictable, and tunable โ€” shrink K to go faster, grow K to improve quality up to a point.

What it cannot promise is perfection. The globally best sequence may be pruned early; wider beams can paradoxically produce worse human-perceived output; and for certain model families exact decoding is computationally intractable. Beam search lives in the pragmatic middle: not guaranteed optimal, but empirically excellent.

That trade-off โ€” tractability over optimality โ€” is the defining motif of algorithms at scale. From greedy graph coloring to simulated annealing, the most useful algorithms are often the ones that settle for a very good answer very quickly. Beam search is the version of that wisdom that speaks to us every time a language model completes a thought.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/beam-search/Content licensed under CC BY-NC 4.0.