Beam Search

Beam search is a decoding algorithm that searches for a high-probability output sequence rather than sampling one token at a time. At each generation step it keeps the k most probable partial sequences — called the beam width or number of hypotheses — expands each one by every plausible next token, scores the results, and prunes back to the best k. By carrying several candidate continuations forward in parallel, it avoids the trap of greedy decoding, where committing to the single best token right now can lock the model into a worse sequence overall.

How the algorithm works

Think of generation as walking a tree. The root is your prompt; every branch is a possible next token. Greedy decoding walks one path, always taking the locally best branch. Beam search instead walks k paths at once. At each depth it expands all k hypotheses, computes the cumulative log-probability of every extended sequence, and keeps only the k highest-scoring ones. When a hypothesis emits an end-of-sequence token it is set aside as a finished candidate, and at the end the algorithm returns the finished sequence with the best overall score, usually normalized by length so longer answers are not unfairly penalized. The whole search runs at inference time — nothing about the model's weights changes.

Beam width and trade-offs

A beam width of 1 is exactly greedy decoding. Common values in machine translation and summarisation are 5 to 10. Wider beams explore more candidates and often find higher-likelihood sequences, but every extra hypothesis multiplies compute and memory: the model must run a forward pass for each beam at each step, and each beam holds its own KV-cache slice of the context window. Counterintuitively, very large beams can also produce worse text — high-likelihood sequences tend to be short, bland, and repetitive — so width is tuned rather than maximised. Length penalties and repetition constraints are standard companions for exactly this reason.

When to use it — and when not to

Beam search shines on tasks with a clear "correct" target: translation, speech transcription, code or structured-data generation, anywhere you want the most likely answer and reproducibility matters. Because it is deterministic for a given model and prompt, the same input yields the same output every run — valuable when a pipeline downstream depends on stable results. For open-ended chat, brainstorming, and creative writing it tends to collapse into generic, repetitive prose, which is why stochastic methods such as top-k sampling and top-p (nucleus) sampling dominate there. Modern chat stacks default to sampling with a temperature; beam search survives mostly in translation systems, subtitle generators, and constrained-output tooling.

Determinism is worth dwelling on, because it is the property that makes beam search valuable in engineered pipelines. When a prompt drives an automated workflow — parsing a spec sheet into a database, generating configuration snippets, producing test fixtures — a decoder that returns the same answer every time turns prompt changes into something you can regression-test: run the suite before and after, diff the outputs, and know exactly what your edit changed. Sampling makes that comparison statistical instead of exact. Many teams therefore develop with sampling for exploration, then pin greedy or beam decoding (and a fixed model build) once the pipeline ships. The decoder choice becomes part of the system's contract, the same way a machinist locks a feed rate once the cut proves out.

Beam search on your own hardware

For a self-hoster the trade-off is concrete: on a local runtime such as llama.cpp or Ollama, each beam costs roughly one extra generation's worth of compute and cache memory, so a beam of 5 on a machine that comfortably streams one response may not be practical for long outputs. The sovereign advantage is that you control the decoding strategy per task rather than accepting a provider's default: beam search (or plain greedy) for deterministic, high-precision jobs like extracting structured fields from documentation; sampling for variety and natural conversation. Understanding the decoder is part of understanding the machine — the model proposes probabilities, but the decoding algorithm decides what you actually read, and it is entirely under your control on hardware you own.