Evaluate Only Enough: Per-Node Early Exit for Multi-Heuristic A*

Optimal search algorithms such as A find the cheapest path by repeatedly expanding the node with the lowest estimated total cost. That estimate uses a heuristic, a guess of the remaining cost that must never overestimate it (an admissible* heuristic). When several admissible heuristics are available, taking their maximum gives a tighter guess and fewer expanded nodes. It also means paying for every heuristic at every node. On game maps this cost is large enough that the maximum is slower in wall-clock time than cheaper tricks, even though it expands fewer nodes (A* Search with Inconsistent Heuristics). Deep-learning inference ran into the same waste: every input got the same computation. Coarse-to-fine gating and early exit, which spend heavy computation only on hard inputs, now cut video-model cost by half or more (LiteEval, FrameExit).

This note carries early exit into A. The key observation is that A never needs to know a node's heuristic value exactly. It only needs to answer one question: is this node's estimated cost still at or below the smallest estimate among the other nodes waiting to be expanded (the OPEN list)? We therefore evaluate heuristics one at a time, cheapest and most promising first. We stop as soon as the running maximum answers that question with "no", and put the node back in the queue with its raised value. A small learned gate decides, for the remaining nodes, whether finishing the evaluation is worth its cost. The maximum of any subset of admissible heuristics is itself admissible, so every choice the gate makes keeps the returned path optimal. The gate affects only speed. Stopping at different points on different nodes creates heuristic inconsistency, meaning the estimate can drop by more than the edge cost between neighbouring nodes. We handle this with bidirectional pathmax (BPMX, defined below). BPMX also lets values propagated from neighbours count as free heuristic evaluations.

Core Claim

Write the evaluation function as $f(n) = g(n) + h(n)$, where $g(n)$ is the known cost to reach node $n$ and $h(n)$ is the heuristic. Let $h_1,\dots,h_k$ be admissible heuristics with per-call costs $t_1,\dots,t_k$, and let $F$ be the minimum $f$-value on OPEN. After computing a subset $S$ of the heuristics at node $n$, the partial estimate is

$$\hat f_S(n) = g(n) + \max\big(h_{\text{prop}}(n), \max_{i \in S} h_i(n)\big),$$

where $h_{\text{prop}}(n)$ is the lower bound pushed onto $n$ by BPMX from its neighbours. BPMX is the rule $h(u) \leftarrow \max(h(u), h(v) - c(u,v))$ of Inconsistent Heuristics, which lifts a node's estimate using a higher estimate at a neighbour $v$ one edge of cost $c(u,v)$ away.

There are two exit rules. The deferral exit fires when $\hat f_S(n) > F$. It is lossless: the node would not be expanded next anyway, so we reinsert it and resume evaluating later if it resurfaces. The expansion exit fires when $\hat f_S(n) \le F$ and a learned gate predicts that the remaining heuristics are unlikely to push $n$ above $F$ by enough to repay their cost. The node is then expanded with a looser but still admissible bound.

Our claims are as follows. With only the deferral exit and consistent base heuristics, the algorithm expands exactly the nodes AMax expands (up to tie-breaking), never re-expands a node, and computes strictly fewer heuristic calls. With the expansion exit added, it can beat both AMax and single-heuristic BPMX in wall-clock time. The dynamic inconsistency this introduces stays bounded in practice once BPMX is applied. The lossless half is our organised version of lazy evaluation, not the main contribution. The contribution is the lossy gate, its interaction with propagation, and a measurement of the inconsistency it creates.

Why this gap is real

Four prior works motivate the gap. Multi-Dimensional Heuristic Searching frames search time as nodes expanded times time per node, and shows that extra landmark dimensions can raise per-node time faster than they cut expansions. A* Search with Inconsistent Heuristics finds that A*Max loses to BPMX on 116 game maps purely because it evaluates every heuristic at every node. A Comparison of Cost Partitioning Algorithms for Optimal Classical Planning shows that optimal cost partitioning, which solves a linear program at every state, prunes better than saturated cost partitioning but loses on coverage because of that per-state cost. Every one of these works applies its evaluator uniformly.

The theory that shapes our design comes from two sources. The Optimality of A* Revisited establishes that under inconsistent admissible heuristics A is only weakly optimal in node count, so our lossy variant cannot be expected to dominate AMax in expansions, only in time. Efficient Budgeted Graph Search bounds re-expansions under inconsistency at a measured constant runtime cost, which gives us a safety net if dynamic inconsistency ever becomes harmful.

We reuse methods from two places: BPMX from Zahavi et al. and its A* adaptation from Sturtevant et al., and the gating-with-state-reuse idea from LiteEval. In LiteEval, copying coarse state into the fine model was essential; removing it dropped mAP from 80% to 65.7% on FCVID. Our analogue is that propagated bounds are carried into the full evaluation rather than discarded.

Research Program

We would build the algorithm in three layers and study each separately.

The first layer is the lossless deferral exit with a fixed heuristic order sorted by cost. We would prove the equal-expansions and no-re-expansion properties for consistent base heuristics.

The second layer adds learned heuristic ordering and the expansion gate. The gate is a tiny model, logistic regression or a two-layer MLP, trained offline on logged A*Max runs. Its inputs are cheap: the current gap $F - \hat f_S(n)$, $g(n)$, which heuristics have already been computed, how often each remaining heuristic has historically raised a node's value in this region, and the size of the latest BPMX lift. Its label is whether the full maximum would have deferred the node. The gate fires the expansion exit when the predicted saving is less than the remaining evaluation cost, which we measure in wall-clock time rather than FLOPs.

The third layer is analysis. For each node we log inconsistency events, the gap between the partial and full value, re-expansions, and BPMX lifts. For the lossy variant we would try to bound re-expansions as a function of the gate's false-exit rate, in the spirit of the polynomial grid bound of Sturtevant et al.

We would apply the method in three domains. On grid pathfinding, the heuristics are multiple differential heuristics, which estimate distance using precomputed distances to landmark cells. On permutation puzzles, the heuristics are multiple pattern database lookups, precomputed tables of exact costs for simplified versions of the puzzle. In classical planning, the cheap bound is saturated cost partitioning and the expensive one is the optimal partitioning linear program. The planning case is where the lossy gate matters most. Optimal partitioning at every expanded node is exactly what Seipp et al. found too costly, so only a gate that skips the linear program on most expanded nodes can help there.

Baselines

The naive reference point is A* with a single cheap heuristic (octile distance on grids, one pattern database on puzzles, saturated partitioning in planning), with no maximum and no propagation. It fixes the floor for both expansions and time.

The strongest wall-clock competitor on grids is A with BPMX using one differential heuristic per node, as in A* Search with Inconsistent Heuristics. That paper reports it as roughly 5x faster than standard A on game maps, and faster than AMax despite expanding more nodes. We beat it if we are faster in median and 90th-percentile wall-clock time on the same maps and landmark sets. The expansion-optimal competitor is AMax over the same heuristics. Our lossless variant should match its expansions exactly while making fewer heuristic calls, and our lossy variant should beat it in time.

For inconsistent base heuristics we compare against BGSe from Efficient Budgeted Graph Search. On Dragon Age maps with compressed differential heuristics it reduced expansions from about 30,788 to 12,650, at roughly 17% extra raw time. We also compare against a combination of BGSe with our gate.

On puzzles, the competitor is random single lookup with BPMX from Inconsistent Heuristics, reported about 24x faster than a consistent lookup on Rubik's Cube. In planning, the competitor is $h^{SCP}_{div}$, which Seipp et al. report achieved the highest coverage on 1,667 International Planning Competition tasks. The file gives no numeric coverage value, so no reported result was found on Lacuna for $h^{SCP}_{div}$ coverage. We would rerun it under identical time and memory limits in Fast Downward.

We would also implement a standard lazy baseline, which applies the cheap heuristic when a node is generated and all heuristics when it is popped. Lazy evaluation appears in the file only as a reviewer suggestion with no reported numbers.

Four ablations isolate the key ingredients: fixed versus learned heuristic order, deferral exit only versus deferral plus expansion exit, with versus without counting propagated bounds as free evaluations, and a random expansion gate matched to the learned gate's exit rate. All methods share one C++ code base, the same heuristic implementations and memory, and the same hardware. Every tunable threshold gets the same tuning budget on held-out maps or domains.

Why not just…?

Why not just pick one heuristic at random per node and rely on BPMX? This is the strongest cheap alternative, and on Rubik's Cube it gave about a 24x speedup (Inconsistent Heuristics). It ignores the state entirely, however. It spends a lookup on nodes already provably above $F$, and it never tightens the bound on the few nodes where tightening decides the search. Our random-gate ablation, matched in heuristic calls per node, tests exactly this. If random selection matches the learned gate, the gate is not earning its place and we would report that.

Why not just use lazy evaluation? Lazy evaluation still pays for every heuristic on every node it pops. The deferral exit is a strict refinement of it, since it stops mid-evaluation. Lazy evaluation also cannot help in planning, where the linear program would still be solved at every expanded state. This is a genuine threat on grids, where differential heuristics are cheap, so the lossless gain may be small there. The lazy baseline measures how much of our gain comes from the lossy gate.

Why not just use saturated cost partitioning and forget the linear program? Seipp et al. show that saturated partitioning wins under uniform application. Optimal partitioning dominates it in pruning, though, and loses only on time. If our gate cannot trigger the linear program on a small enough fraction of expanded states to gain coverage, then saturated partitioning simply stands. That is a legitimate negative result we would report.

Why not just use BGSe to handle the inconsistency? BGSe controls re-expansions but does nothing about per-node evaluation time, which is our target. The two are complementary, so we test the combination. If BPMX alone keeps re-expansions near zero under our gate, the 17% overhead reported for BGSe is unnecessary.

Proposed Experiments

We would use the 116 commercial game maps and Dragon Age: Origins scenarios from Benchmarks for Grid-Based Pathfinding, with 4 to 16 differential heuristics, both exact and compressed. We would add the 15-puzzle, the 17-pancake puzzle, and Rubik's Cube with several pattern databases, and the IPC task suite in Fast Downward. Metrics are wall-clock time, distinct expansions, re-expansions, heuristic calls per expanded node, linear programs solved, and coverage.

Three checks are decisive. First, on consistent differential heuristics the lossless variant must match AMax's expansion count exactly, with zero re-expansions, while making fewer heuristic calls. Failing this would falsify the core claim. Second, the lossy variant must beat A with BPMX in wall-clock time on game maps as the number of heuristics grows. The crossover point, where extra heuristics stop paying off, should move out compared with A*Max, which gives a direct test of the nodes-times-time-per-node argument. Third, in planning, gated optimal partitioning must solve more tasks than $h^{SCP}_{div}$ within the same limits, and we would report the fraction of expanded states that invoked the linear program. We would also plot re-expansions against the gate's false-exit rate to show whether dynamic inconsistency stays bounded.