Beam search using limited discrepancy backtracking
Algorithms AIMech:BULB DRAFT
Aliases: BULB, Limited discrepancy beam search
A memory-bounded beam search that explores heuristic-ranked slices using increasing limited-discrepancy budgets and removes backtracked slices so that alternative beams can be examined.
Identity Notes & Concept Scope
BULB denotes Furcy and Koenig’s Beam search Using Limited discrepancy Backtracking. A discrepancy selects a nonpreferred successor slice; it is not a numerical heuristic error or an action cost. The inspected algorithm is presented for unit-cost state-space search and seeks a path, not necessarily a shortest path. 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
3 Claims
Mechanism
#search-procedure
Keep one slice of up to the beam width at each active depth. Rank eligible successors by heuristic value and divide them into slices. A probe follows the preferred slice without spending discrepancy allowance and explores nonpreferred slices with a reduced allowance, removing slices from the active hash table on backtracking. Outer iterations increase the allowance; a full table causes the current probe to stop and backtrack.
Limitation
#memory-qualified-completeness
The paper qualifies completeness by the memory needed to retain a beam to a solution and describes the base method as approximate in solution length. Its conclusion discusses conversion to an anytime algorithm as an extension, not an automatic guarantee of the presented stopping rule.
Limitation
#depth-label-inconsistency
Visual inspection identifies an apparent inconsistency between the recursive depth increment and the depth label assigned to generated successors. The next-level interpretation comes from the adjacent prose; no corrected reference implementation or author erratum was established by this review.
⚠️ Curated Limitations & Negative Results
- Completeness is conditional on enough memory to store a beam along a solution path. A fixed memory budget and arbitrary beam width do not guarantee solving every instance.
- The method need not return a shortest path. An anytime extension is discussed separately from the base procedure.
- The O(B*d) storage statement concerns retained slices along the active search; temporary successor generation, heuristic data and other implementation storage need separate accounting.
- The active hash table prevents cycles involving retained states and some transpositions, but it is not a permanent global closed list of every state ever visited.
- Figure 4 has an apparent depth-label inconsistency: nextSlice labels a successor with depth although the caller next probes depth+1. The prose describes a next-level slice. This record follows that described mechanism and does not certify the literal pseudocode as executable.
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
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
David Furcy, Sven Koenig
|
primary paper
full_text
|
sha256:25fa7ecf4d94…
|
conditional-properties
|
David Furcy, Sven Koenig
|
primary paper
full_text
|
sha256:25fa7ecf4d94…
|
pseudocode-caveat
|
David Furcy, Sven Koenig
|
primary paper
full_text
|
sha256:25fa7ecf4d94…
|
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/BULB.yaml