Many optimal search algorithms do not know how expensive the answer is until they find it. Iterative-deepening search (IDA*, depth-first search that is restarted with a larger cost bound each time it fails) guesses a bound, searches everything under it, and starts over with a bigger one. This is the cow-path problem in disguise. The searcher walks out along a line of possible costs toward an unknown target, the optimal solution cost, and pays for every failed excursion. Competitive analysis tells us how to schedule those excursions so that total work stays within a constant factor of what an oracle would spend. The oracle knows the answer and runs a single search.
We propose that the pattern database (PDB) the solver already holds can act as a prediction of where that target lies. A PDB is a lookup table of exact distances in a simplified version of the problem, and it is normally used only as an admissible heuristic. It also contains two further pieces of information. First, a trusted lower bound on the optimal cost. Second, a histogram of heuristic values from which the cost of a search under any given bound can be estimated. Treating these as a hint in the sense of learning-augmented online algorithms gives a re-search schedule with two properties: it approaches oracle work when the PDB's forecast is good, and it never does worse than a fixed constant times oracle work when the forecast is bad. Because the forecast sharpens as the PDB grows, the same experiments measure something absent from both literatures, namely how the attainable competitive ratio of search falls as more memory is spent on abstraction.
Core Claim
The re-search problem has the same structure as single-ray search. Let $W^*$ be the number of node expansions the oracle needs: one bounded search at exactly the optimal cost $C^*$. A schedule runs bounded searches with work budgets $w_1 < w_2 < \dots$ and stops at the first budget that both covers the optimal bound and completes. Its competitive ratio is
$$\rho = \frac{\sum_{i \le k} w_i}{W^*},$$
where $k$ is the index of the successful iteration. Without advice, geometric budget doubling achieves the optimal single-ray guarantee. Via the duality between contract scheduling and ray search shown in Contract Algorithms and Robots on Rays, the optimal acceleration ratio for one problem on one processor is $R^*_{1,1} = 4$.
Online Search With a Hint shows, for search on a line, that a position hint lets a searcher trade robustness $r$ (the worst-case ratio when the hint is wrong) for consistency $c$ (the ratio when it is right). It reports a Pareto-optimal consistency of $\frac{b_r+1}{b_r-1}$ at robustness $r$. It treats the hint as an exogenous number of unknown origin.
Our claim has two parts. First, the PDB supplies a structured hint that is half-trusted: the lower bound $h(s) \le C^*$ is guaranteed by admissibility, while the work forecast $\hat W$ is not. Second, one-ray schedules that use this hint can reach consistency close to 1 at robustness near 4. The second part is an empirical bet; the theory below tells us how close to 1 is attainable.
Research Program
The theoretical part derives the consistency–robustness frontier for single-ray search when the hint has two parts, a hard lower bound and a soft position estimate. We then extend it to an error-dependent ratio that degrades smoothly with $|\log(\hat W / W^*)|$. Angelopoulos's analysis is for a line with two directions. The one-ray case with a one-sided trusted bound is a different setting, and we expect a cleaner frontier. The natural construction is a geometric schedule with ratio $b_r$, phase-shifted so that one budget lands just above $\hat W$ and no budget falls below the work implied by $h(s)$. We will also ask whether a single-ray analogue of Angelopoulos's "limit of 3" holds: a floor on consistency at fixed robustness, regardless of how informative the hint is.
The algorithmic part builds the hint from the PDB itself. The forecast of work under bound $b$ is computed by counting, in the PDB's value histogram, how many abstract states have heuristic value at most $b - g$ at each depth $g$, propagated by the heuristic branching factor. The forecast of $C^*$ is the smallest bound whose forecast work matches typical solution depth, offset from $h(s)$ by a per-domain slack learned from a few calibration instances.
Each iteration is run as a contract: a bounded depth-first search that is aborted when its node budget runs out. Aborting, rather than finishing, is what makes the robustness guarantee hold in the units we actually pay, which are node expansions.
The memory part sweeps PDB size from small projections up to the largest tables that fit in RAM. For each size we record both heuristic quality and achieved consistency. This turns Gap 1 of the research file, a "PDB-advised competitive ratio" as a function of bits of memory, into a measured curve. A second stage extends the schedule to batches of $n$ instances on $m$ processors, where the unadvised baseline is the cyclic optimum $R^*_{m,n}$ from the same duality paper. We describe it but do not make it the core.
Baselines
The naive reference is standard IDA*. It raises the bound to the smallest cost that exceeded the previous one. On unit-cost puzzles this is near-oracle, because the work per bound grows by roughly the branching factor. On domains with many distinct path costs it can re-search almost once per distinct cost value, so its overhead is unbounded relative to oracle work.
The strongest principled competitor is unadvised geometric budget doubling run as contracts, with the guaranteed ratio of 4 from Contract Algorithms and Robots on Rays. The research file contains no empirical measurements of re-search overhead on our benchmarks, so we record: no reported result found on Lacuna for the measured expansion ratio of budgeted re-search on the sliding-tile puzzle, Towers of Hanoi, or the planning benchmarks. Budgeted re-search schemes of this kind probably exist in the heuristic search literature outside our file. Doubling stands in for them, and we will add any such scheme we can obtain under the same settings.
The second strong competitor is the fully trusting schedule. It runs one search at the forecast bound and falls back to doubling only after that search fails. It shows how much robustness costs when the forecast is good.
All schedules use the same PDBs, the same search code, the same node-expansion accounting and the same per-instance time limit. The oracle cost $W^*$ is computed once per instance by running the bounded search at the true optimal cost, found offline.
The method beats doubling if its median ratio across instances falls clearly below doubling's median and its worst observed ratio stays within its proven robustness bound. It beats full trust if its 95th-percentile ratio is substantially lower, even if trust wins on the median.
The key ablation keeps the schedule fixed and swaps the hint source. The variants are the PDB forecast; $h(s)$ alone with no histogram; a hint from a PDB whose values have been randomly permuted, which keeps the memory but removes the information; and the oracle hint, which gives an upper bound on any possible gain. This isolates whether the PDB's structure, rather than the schedule's shape, produces the gain.
Why not just…?
Why not just use plain geometric doubling, since it already has a constant worst case? This is the most serious threat. On unit-cost domains, doubling's typical overhead may already be small, and the gain from a hint would then be marginal. We treat the unit-cost 4×4 sliding-tile puzzle as a sanity check where little gain is expected. The case for the proposal rests on domains with many distinct costs and irregular growth in work. If the measured gap between doubling and the oracle hint is below about 1.3× there too, the hint is not worth having, and the experiments will say so.
Why not just run A* and avoid re-search entirely? A* stores every generated node. Anchor Search reports that on 32-disk 4-peg Towers of Hanoi, standard greedy best-first search and bidirectional baselines frequently failed from memory exhaustion. That is exactly the regime where memory goes into the PDB and the search itself must use little memory. In the memory sweep, A* runs with the same total memory budget, so it competes with the PDB for that memory.
Why not just learn a cost predictor from instance features instead of reading the PDB? It is a fair alternative, and the PDB's advantage is that it comes for free and has a guaranteed lower bound. We include a regression predictor trained on the same calibration instances as a hint source in the ablation. If it matches the PDB forecast, the contribution narrows to the robust schedule plus the memory curve.
Why not compute better heuristics online instead of storing tables? Implicit Abstraction Heuristics found that their polynomial-time fork heuristic was too slow to compute per node, and the precomputed version solved 74 more planning instances. Precomputation is the setting where the extra predictive information in the table exists at all.
Proposed Experiments
The benchmarks come from the research file. The 100 Korf instances of the 4×4 sliding-tile puzzle serve as the unit-cost sanity check. We add a variant in which each tile has its own move cost, which creates many distinct path costs. 4-peg Towers of Hanoi from 22 to 32 disks, as used in Anchor Search and Recent Progress in Heuristic Search, provides huge state spaces. Rubik's Cube uses the corner PDB of Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. International Planning Competition domains with action costs use the abstraction heuristics of Implicit Abstraction Heuristics.
The metrics are the per-instance ratio $\rho$ in node expansions and in wall-clock time, reported at the median, the 95th percentile and the maximum. We also report the number of instances solved within a fixed time limit.
There are three decisive checks. First, the worst observed $\rho$ of the advised schedule must never exceed its proven robustness bound. Any violation means the contract implementation is wrong. Second, on the variable-cost domains, the PDB-forecast hint must recover a large share of the gap between doubling and the oracle hint, and the permuted-PDB control must recover almost none of it. Third, the curve of median $\rho$ against PDB memory must fall monotonically as the table grows. A flat curve would refute the claim that abstraction memory buys competitive advantage, as distinct from merely buying a better heuristic.
References
- Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems
- Online search with a hint
- Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
- Implicit Abstraction Heuristics
- Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem
- Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases