Paper 2025/2205

Selective ML-Guided Beam Search for Differential-Trail Discovery in GIFT-64

Abstract

Beam search bounds differential-trail exploration, but may still expand many intermediate differences. We test whether a learned short-horizon tail-cost residual can reduce this work while leaving classical selection in control. A regressor estimates a residual adjustment to an active-nibble heuristic. With four or two rounds remaining, the post-selection policy protects the best $25\%$ of the classical frontier, removes at most $30\%$ of accepted states, and abstains when fewer than five states can be pruned. It cannot restore candidates already rejected by classical selection. We develop the method on a state-grouped GIFT-64 corpus and evaluate it on $D=8$ and $D=12$ holdouts and a $D=16$ stress test. Target recovery and the best classical cost are preserved on all $48$ holdout cases and all $18$ stress cases. Aggregate node reductions are $6.832\%$, $0.099\%$, and $0.040\%$ at $D=8$, $D=12$, and $D=16$. An equal-budget ablation fixes the frontier, protected core, and pruning quota while changing only the removed-state ranking. Learned and classical ranking preserve all $48$ holdout cases, with aggregate reductions of $2.359\%$ and $2.411\%$. Their removal sets differ on $57$ of $85$ active frontiers, but the learned score does not establish a measurable advantage over the classical control. Random ranking produces larger raw reductions but loses quality. All comparisons use a bounded classical baseline; no globally optimal trails are claimed.