Top-K Gated Macro-Actions for Neural Heuristic Search

Why it matters

Neural heuristic search reduces reliance on handcrafted heuristics, but it makes each node expansion more expensive because every extra successor often requires another neural network evaluation.

Macro-actions can shorten search depth, yet they usually increase branching. The central problem is balancing the depth reduction macros provide against the cost of exploring more successors.

What we did

• Introduce top-K gating, which keeps all primitive actions but selects only the K best macro successors at each expansion.
• Bound branching to b + K regardless of macro-pool size while preserving completeness.
• Discover macros during approximate value iteration (AVI) and integrate them into training by adding their landing states.
• Show on sliding-tile puzzles that K = 1 reduces node expansions by up to 28.6% on the 8-puzzle, 17.5% on the 15-puzzle, and 9.4% on the 24-puzzle.
• Find that random macros provide less than 3% improvement, indicating the gains come from learned macro structure rather than simply adding longer actions.

The overall pipeline is shown in Figure 1, where macro discovery and search are tightly coupled.

How it works

• Macro discovery during training: mine action subsequences of length 2-5 from GBFS trajectories under the learned heuristic.
• Training integration: add macro landing states into the AVI training distribution while keeping Bellman updates primitive-only.
• Optional utility scoring: rank macro candidates using support, applicability, benefit, and branching penalty.
• Top-K gating at search time: evaluate all valid macros but retain only the K lowest-heuristic successors.
• Cost consistency: assign each macro a cost equal to its primitive length to preserve A* correctness.

Key contributions

• Introduce top-K gating that preserves completeness and caps branching at b + K.
• Propose a macro discovery pipeline integrated with AVI training.
• Show that learned macros outperform random ones, with learned gating giving up to 28.6% lower expansions versus less than 3% for random macros.
• Demonstrate that K = 1 is Pareto-optimal, matching larger K with minimal branching overhead.
• Analyze when lower expansions do and do not translate to faster wall-clock runtime, with observed changes ranging from 21% faster to 11% slower.

^dagger Solve rate improves from 36.4% to 38.4%, so the solved-instance mean regresses slightly even though more 24-puzzle instances are solved.

Table 1 shows that K = 1 consistently reduces expansions across tested 8-puzzle, 15-puzzle, and 24-puzzle settings, with the strongest reductions at k = 100 for the 8- and 15-puzzle and at k = 50 for the 24-puzzle.