Breadth-first beam search
Algorithms AIMech:BeamSearch DRAFT
Aliases: Beam search
A heuristic search procedure that advances by depth layers, retaining at most a chosen beam width of the best-ranked candidate nodes for each next layer and discarding the other candidates.
Identity Notes & Concept Scope
This record denotes the conventional breadth-first form of beam search. Wider historical uses of beam search also include global best-first frontier truncation and other heuristic pruning procedures. A width of one follows a single surviving continuation; it is not the unbounded global-frontier algorithm curated as greedy best-first search. No normalized identity match was found across the 442 AIO and 130 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations and search-order contrasts, plus incidental lightbulb and wet-bulb dependency substrings, not existing concept records.
Claims & Grounded Evidence
2 Claims
Mechanism
#search-procedure
Expand the retained nodes in the current depth layer, rank their eligible successors with the chosen heuristic or evaluation rule, and retain at most the beam width for the next layer. Candidates removed by this width rule are not systematically recovered by the basic procedure.
Limitation
#policy-boundaries
The comparative study distinguishes layer-limited and whole-frontier beam policies, and shows why duplicate handling must be specified separately. Its non-unit-cost examples challenge a universal claim that widening a beam always improves the returned solution.
⚠️ Curated Limitations & Negative Results
- Width pruning can discard every path to a solution or every optimal path, so basic beam search has no general completeness or optimality guarantee.
- A layer-width bound does not by itself bound all memory: stored predecessor information, retained earlier layers, generated successors and any global duplicate table must also be accounted for.
- Ranking, ties, goal stopping and duplicate handling are additional choices. Increasing the beam width does not guarantee an improvement in returned solution quality for every implementation and problem.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.
Search Scope: All 442 pinned AIO labels and scoped synonyms and 130 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm. |
AIO:ReasoningLLM
|
Language-task deductive inference does not denote general state-space search. |
AIO:NeuroSymbolicLLM
|
A language-model architecture combining neural and symbolic components is not the search procedure itself. |
AIO:MachineLearningTask
|
Building methods that learn from data is not the identity of an algorithm traversing a specified graph. |
AIO:MathematicalFunction
|
The search procedure is distinct from the mathematical functions it may evaluate. |
AIO:ReinforcementLearning
|
A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Rong Zhou, Eric A. Hansen
|
primary paper
full_text
|
sha256:eb2ac12fea9d…
|
comparison-paper
|
Christopher Wilt, Jordan Thayer, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1609/socs.v1i1.18182
sha256:cfc3cf8f422b…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T06:01:43Z
Updated: 2026-10-11T06:01:43Z
Source File:
data/curated/BeamSearch.yaml