Overview
Beam Search expands candidate states level by level, pruning all but a fixed number of highest-scoring states.
CoreSource checked
Beam Search
Keeps only the best few partial solutions while exploring a large search space.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Intermediate
- Family
- Heuristic Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
beam widthcandidate scorelevel expansionpruning
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(b * w)
Average
O(depth * b * w)
Worst
O(depth * b * w)
Space
O(w)
When to Use
- Use when full search is too large but partial candidates can be scored meaningfully.
- Use when sequence decoding is a central requirement.
When Not to Use
- Avoid when the scoring function is unreliable for incomplete candidates.
- Avoid when the objective is noisy, discontinuous, or violates the method's assumptions.
What It Does
- Expands partial candidates
- Scores each candidate
- Keeps a fixed-width beam
Use Cases
- Sequence decoding
- Heuristic planning
- Approximate combinatorial search
Inputs
- Initial state
- Expansion function
- Scoring function
- Beam width
Outputs
- Best found candidate
Key Formulas (1)
Beam pruning
beamnext = topk(expand(beamcurrent), k = beamwidth)
beam_next = top_k(expand(beam_current), k = beam_width)Keeps only the best-scoring expanded candidates.
Pseudocode
- 1.Start with the initial candidate in the beam
- 2.Expand every candidate in the current beam
- 3.Score all expansions
- 4.Keep the best beam-width candidates
- 5.Repeat until candidates are complete
Canonical Example
- Input
- beam width = 2, candidates score [9, 7, 3]
- Output
- kept = top two candidates
- Explanation
- The search continues only from the best-scoring partial solutions.
Implementation Notes
- Deduplicate equivalent states before selecting the next beam.
- Track objective value, step size, and convergence criteria at each iteration.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Increasing beam width improves coverage but can quickly erase the performance benefit.
- Stopping too early or using unscaled variables can make a good method look broken.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a search tree where only the top few nodes survive at each depth.
Step 1 of 5: Start with the initial candidate in the beam
optimization-landscapeNotes
A narrow beam is fast but can prune the globally best solution early.
Sources (1)
What each reference supports for this entry.
Artificial Intelligence: A Modern Approach
BookReference text for search, local search, beam search, and constraint-satisfaction backtracking.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageSpecializesBreadth-First Search
Beam search is a width-limited search strategy derived from level-wise expansion.
Alternative toGreedy Best-First Search
Both use scores to prioritize candidate states.
Related Algorithms
Tags
OptimizationHeuristic SearchSearch