# AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT

arXiv: https://arxiv.org/abs/2604.20744 · HTML: https://mlsanity.com/paper/2604.20744/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 55 references that are in the map.
- First posted on arXiv 22 Apr 2026.

## Builds on (most cited first, 28 of 28)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Concrete Autoencoders for Differentiable Feature Selection and Reconstruction](https://mlsanity.com/paper/1901.09346/) (2019)
- [Path Planning using Neural A* Search](https://mlsanity.com/paper/2009.07476/) (2020)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [Route Planning in Transportation Networks](https://mlsanity.com/paper/1504.05140/) (2015)
- [TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers](https://mlsanity.com/paper/2212.11730/) (2022)
- [Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling](https://mlsanity.com/paper/1304.4661/) (2013)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)
- [The FastMap Algorithm for Shortest Path Computations](https://mlsanity.com/paper/1706.02792/) (2017)
- [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022)
- [DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context](https://mlsanity.com/paper/2405.04923/) (2024)
- [On Using Admissible Bounds for Learning Forward Search Heuristics](https://mlsanity.com/paper/2308.11905/) (2023)
- [iA*: Imperative Learning-based A* Search for Path Planning](https://mlsanity.com/paper/2403.15870/) (2024)
- [Embeddings and labeling schemes for A*](https://mlsanity.com/paper/2111.10041/) (2021)
- [Customizable Contraction Hierarchies](https://mlsanity.com/paper/1402.0402/) (2014)
- [Indirectly Parameterized Concrete Autoencoders](https://mlsanity.com/paper/2403.00563/) (2024)
- [Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search](https://mlsanity.com/paper/2511.10264/) (2025)
- [Learning Admissible Heuristics for A*: Theory and Practice](https://mlsanity.com/paper/2509.22626/) (2025)
- [EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding](https://mlsanity.com/paper/2408.11341/) (2024)
- [An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks](https://mlsanity.com/paper/2602.04068/) (2026)
- [UPath: Universal Planner Across Topological Heterogeneity For Grid-Based Pathfinding](https://mlsanity.com/paper/2602.23789/) (2026)

## Abstract (arXiv)

We introduce AAC (Architecturally Admissible Compressor), a differentiable landmark-selection module for ALT (A*, Landmarks, and Triangle inequality) shortest-path heuristics whose outputs are admissible by construction: each forward pass is a row-stochastic mixture of triangle-inequality lower bounds, so the heuristic is admissible for every parameter setting without requiring convergence, calibration, or projection. At deployment, the module reduces to classical ALT on a learned subset, composing end-to-end with neural encoders while preserving the classical toolchain. The construction is the first differentiable instance of the compress-while-preserving-admissibility tradition in classical heuristic search. Under a matched per-vertex memory protocol, we establish that ALT with farthest-point-sampling landmarks (FPS-ALT) has provably near-optimal coverage on metric graphs, leaving at most a few percentage points of headroom for any selector. AAC operates near this ceiling: the gap is 0.9--3.9 percentage points on 9 road networks and ≤1.3 percentage points on synthetic graphs, with zero admissibility violations across 1,500+ queries and all logged runs. At matched memory, AAC is also 1.2--1.5× faster than FPS-ALT at the median query on DIMACS road networks, amortizing its offline cost within 170--1,924 queries. A controlled ablation isolates the binding constraint: training-objective drift under default initialization, not architectural capacity; identity-on-first-m initialization closes the expansion-count gap entirely. We release the module, a reusable matched-memory benchmarking protocol with paired two-one-sided-test (TOST) equivalence and pre-registration, and a reference compressed-differential-heuristics baseline.