CONCEPT Cited by 2 sources

Beam search

Definition

Beam search is an approximate decoding algorithm for autoregressive models that explores an output space by keeping the k most-probable partial sequences ("beams") alive at every generation step, instead of greedily committing to the single highest-probability token (greedy decoding) or enumerating all sequences (exhaustive, intractable). At each step every surviving beam is expanded by all candidate next tokens, the resulting sequences are scored by cumulative log-probability, and only the top-k are retained. The parameter k is the beam width — larger k explores more of the tree (higher recall of high-probability sequences) at higher compute and memory cost.

Beam search navigates a decision tree of potential outputs, "keeping the most promising 'beams' or sequences active at each step" with the goal of surfacing the highest-scoring sequences overall rather than the one that looked best token-by-token. (Source: sources/2026-10-16-spotify-advancing-generative-recommendation-inference-trt-llm)

Why it matters for generative recommendation

Beam search is the candidate-generation primitive in generative-retrieval recommenders. Instead of scoring a predetermined candidate set, the model generates the semantic-ID token sequences of relevant items one codeword at a time; beam search explores multiple semantic-ID paths simultaneously, and the surviving top sequences are translated back to catalog items to serve recommendations. The beam width directly sets how many candidates the generative retriever produces — it is the knob that replaces the "retrieve N candidates" step of a classic retrieval→ranking funnel.

The serving-infra cost: it is hard on inference engines

Beam search is substantially more expensive and more awkward to serve than plain completion/greedy decoding, and engine support varies widely — which is a first-class system-design concern, not an implementation detail:

• KV-cache churn. Beams share prefixes and then diverge; as the top-k set changes between steps, partially filled KV blocks for pruned beams may need to be recomputed or recopied. An engine that handles beam search outside the core GPU engine pays this as extra GPU work plus CPU-side orchestration bottlenecks.
• Where the beam logic lives decides utilization. vLLM's beam search "operates outside the core GPU engine, which introduces CPU-side bottlenecks and additional GPU work due to the recomputation of partially filled KV blocks" — so Spotify couldn't saturate high-end GPUs and deliberately chose lower-tier accelerators for its January 2026 launch. By contrast, TensorRT-LLM implements beam search inside the sampler, which "reduces host overheads and, combined with overlap scheduling, ensures good GPU utilization" — yielding up to 54% cost reduction on beam-search workloads (Qwen3 1.7B). (Source: sources/2026-10-16-spotify-advancing-generative-recommendation-inference-trt-llm)
• Returning multiple sequences. Serving a generative retriever needs the whole top-k beam set returned, not just the single best sequence — a capability some engines lacked until recently (TRT-LLM added "returning multiple sequences in beam search" in v1.2.0rc3 via the Spotify × NVIDIA collaboration).

Seen in

• 2026-10-16 Spotify × NVIDIA — Generative recommendation inference on TensorRT-LLM — beam search is the candidate-generation technique behind Spotify's Large Personalized Language Model; the engine's beam-search implementation location (sampler-internal vs outside-the-engine) is the root cause of a measured 54% cost difference between TRT-LLM and vLLM on Qwen3 1.7B. (Source: sources/2026-10-16-spotify-advancing-generative-recommendation-inference-trt-llm)
• 2026-06-02 Instacart — From Scoring to Spelling — beam search is the decode strategy in the TIGER-inspired generative ads retrieval model ("beam search at serve time, not greedy decoding"); first- class beam-search support is named as a reason the stack needed TensorRT-LLM. (Source: sources/2026-06-02-instacart-from-scoring-to-spelling-rebuilding-ads-retrieval-at-instacart)

Related

• concepts/kv-cache — partial-block recompute of pruned beams is beam search's dominant serving tax.
• concepts/retrieval-ranking-funnel — beam width is the generative-retrieval replacement for the "retrieve N candidates" stage.
• systems/tiger-generative-retrieval — the generative-retrieval architecture that decodes semantic IDs via beam search.
• systems/vllm — beam search outside the GPU engine (CPU bottleneck + KV recompute).
• systems/tensorrt-llm — beam search in the sampler + overlap scheduling.
• systems/sglang — sibling engine; candidate scoring rather than beam search.