✨ TL;DR
AAC introduces a differentiable landmark-selection module for ALT shortest-path heuristics that maintains admissibility by construction through row-stochastic mixtures of triangle-inequality bounds. The method achieves near-optimal landmark coverage on road networks while being 1.2–1.5× faster than classical farthest-point sampling at matched memory.
Shortest-path heuristics like ALT (A*, Landmarks, and Triangle inequality) rely on carefully selected landmarks to compute admissible lower bounds. Classical landmark selection methods like farthest-point sampling are effective but not learnable, and learning-based approaches risk violating admissibility constraints—a critical property for optimal pathfinding. There is a need for differentiable landmark selection that preserves admissibility by construction while enabling end-to-end learning with neural encoders.
AAC (Architecturally Admissible Compressor) is a differentiable module that selects landmarks through a row-stochastic mixture of triangle-inequality lower bounds, ensuring admissibility for every parameter setting without requiring convergence, calibration, or post-hoc projection. At deployment, the learned soft selection reduces to classical ALT on a discrete subset of landmarks. The construction composes end-to-end with neural encoders while preserving the classical ALT toolchain. The authors also establish that farthest-point-sampling ALT (FPS-ALT) achieves provably near-optimal coverage on metric graphs under matched per-vertex memory constraints.
What the paper shows.
AAC achieves zero admissibility violations across 1,500+ queries and all logged runs. On 9 DIMACS road networks at matched memory, AAC is 1.2–1.5× faster than FPS-ALT at the median query, amortizing its offline cost within 170–1,924 queries. The gap between AAC and the theoretical optimum is 0.9–3.9 percentage points on road networks and ≤1.3 percentage points on synthetic graphs. An ablation study shows that identity-on-first-m initialization eliminates the expansion-count gap entirely, demonstrating that capacity is sufficient and initialization strategy is the key factor.
The paper focuses on matched per-vertex memory protocols, which may not reflect all practical deployment scenarios with different memory budgets. The theoretical near-optimality result for FPS-ALT applies specifically to metric graphs; generalization to other graph classes is not discussed. The evaluation is primarily on road networks and synthetic graphs; applicability to other domains (e.g., general directed graphs) is unclear. The paper does not extensively compare against other recent learning-based heuristic methods beyond the compressed-differential-heuristics baseline.
✨ Generated by Claude · Apr 25, 2026 · Read the PDF for authoritative content.