IDA* with an Incremental Model
Algorithms AIMech:IDAStarIncrementalModel DRAFT
Aliases: IDA*IM
An iterative-deepening heuristic search algorithm that learns a conditional model of search-tree cost increments, predicts later cost thresholds to target increased expansion counts, and completes the goal-finding iteration by branch-and-bound.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 637 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 458, 252, 250 lines. All distinct match contents were inspected. Semantic matching covered 8 AIO and 83 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 3 full native records were inspected. Retain IDA*IM, which learns a conditional increment model to select cost bounds and uses final branch-and-bound. Ordinary IDA* uses minimum-exceeded thresholds; RBFS controlled re-expansion changes backed-up subtree values; BFIDA* changes the traversal to breadth first. The separately usable estimator and a learned admissible heuristic have different scopes.
Claims & Grounded Evidence
5 Claims
Mechanism
#incremental-search-model
During cost-bounded depth-first search, the method records changes in f=g+h and an integer distance-to-go estimate between parents and children, conditioned on selected node types, parent distance and, online, search depth. Histograms represent real-valued cost increments. Backoff models omit conditioning features when data are unavailable. The learned model predicts search effort; it does not replace the admissible heuristic with an unconstrained learned estimate.
Mechanism
#histogram-extrapolation
The predictor propagates f-value mass through conditional offspring-increment histograms by additive convolution, accumulating estimated counts across depths. It can start from the root or from a fully generated shallow layer. Estimated mass and a target count determine a simulated bound, with pruning and a small-mass stopping criterion. The uniform-tree exactness result assumes an accurate increment model and h=0; it does not certify predictions after approximate binning, backoff or unmodeled dependencies in arbitrary trees.
Mechanism
#threshold-control-and-fallback
After an iteration without a goal, the method predicts a threshold intended to yield twice the preceding expansion count. The next threshold is bounded below by the smallest f value pruned in the completed iteration, preventing a low prediction from repeating or reducing the cutoff. A single model is updated from newly encountered search portions, and the configured ancestor-cycle check also excludes cyclic successors from model learning. The target is an estimate: discrete f-contours can make exact doubling impossible.
Limitation
#final-iteration-and-correctness-scope
A predicted threshold can exceed the cheapest solution cost, so the first encountered goal is not automatically optimal. The final iteration continues branch-and-bound below the incumbent cost and replaces it when a cheaper goal is found. The correctness argument relies on admissible lower bounds and completion of the required searches; finite relevant contours and the usual termination conditions must be retained. Consistency or pathmax supplies the nondecreasing path evaluations used by the model. Admissibility alone is not an unconditional termination guarantee for arbitrary infinite search spaces.
Limitation
#prediction-versus-runtime
The reported studies cover configured sliding-tile, vacuum-maze, synthetic-tree and weighted-pancake problems. Better expansion predictions do not guarantee lower CPU time: model and histogram maintenance add overhead, and histogram capacity affects predictions. The record does not assert universal speedups, an always-doubling expansion rate, constant memory for the complete learned model or equivalence to graph search with global duplicate elimination.
⚠️ Curated Limitations & Negative Results
- The record is scoped to the IDA*IM search integration in the inspected 2013 author manuscript. The standalone incremental estimator can also be trained offline; it is not equivalent to the complete search procedure.
- The source contains shorthand or inconsistent details: the page 6 branching-factor prose reverses the usual offspring-per-parent ratio, and Figure 3 is not certified here as executable pseudocode. The record follows the prose mechanism and count-convolution analysis while retaining these interpretation limits.
- Consistency means nondecreasing f, not necessarily strictly increasing f. Goal-zero conventions, valid lower bounds, finite relevant contours and terminating branch-and-bound remain part of any correctness claim; unrestricted admissibility alone is insufficient.
- The source’s ideal uniform-tree convolution argument does not prove model accuracy for general spaces. A chosen distance estimate need not be zero only at goal states; the paper’s proposed solution-cost extension remains outside this curated procedure.
- All 24 author-manuscript pages were visually inspected. The publisher journal layout, earlier conference full text and author implementation were not inspected. Constructed arithmetic checks are not search benchmarks or empirical replication.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable mapping for this complete adaptive state-space search algorithm was established in the inspected AIO snapshot. A graph-based language model, a general learning task and the arithmetic functions used by an estimator are different scopes.
Search Scope: Compared all 442 pinned AIO and 637 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 458, 252, 250 lines. All distinct match contents were inspected. Semantic matching covered 8 AIO and 83 native definitions, with every matched definition read. 6 full annotated AIO node/edge/generated contexts and 3 full native records were inspected. Retain IDA*IM, which learns a conditional increment model to select cost bounds and uses final branch-and-bound. Ordinary IDA* uses minimum-exceeded thresholds; RBFS controlled re-expansion changes backed-up subtree values; BFIDA* changes the traversal to breadth first. The separately usable estimator and a learned admissible heuristic have different scopes.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model over graph-structured inputs is not an adaptive shortest-path search procedure. |
AIO:ReasoningLLM
|
Language-model deduction does not identify cost-bounded depth-first search or histogram-based threshold control. |
AIO:NeuroSymbolicLLM
|
The algorithm does not require a neural language model or a hybrid neural-symbolic architecture. |
AIO:MachineLearningTask
|
Learning a search-effort model is a component, but this record denotes a full search algorithm rather than the general task of constructing learning methods. |
AIO:MathematicalFunction
|
Evaluation and convolution functions are components rather than the stateful search procedure. |
AIO:ReinforcementLearning
|
The source fits increment counts from traversed nodes; it does not define a reward-based policy or value-learning procedure balancing exploration and exploitation. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
burns2013im
|
Ethan Burns, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1007/s10472-013-9347-9
sha256:fd8b123fff90…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T18:06:02Z
Updated: 2026-10-13T18:07:41Z
Source File:
data/curated/IDAStarIncrementalModel.yaml