AAC is a differentiable landmark-selection module for ALT (A*, Landmarks, and Triangle inequality) shortest-path heuristics. It compresses a large set of teacher landmarks into a small, search-efficient subset via gradient descent -- and its outputs are admissible by construction: a row-stochastic compression matrix produces convex combinations of triangle-inequality lower bounds, so the heuristic is admissible for every parameter setting, at every training epoch, without convergence assumptions or post-hoc calibration.
At deployment the module reduces to classical ALT on the learned subset, preserving the full classical toolchain (BPMX, bound substitution, bidirectional search).
Paper: "AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT" -- An T. Le and Vien A. Ngo (arXiv:2604.20744).
AAC training on a 50×50 maze, compressing 48 FPS landmarks to 10. Left: A* expansion heatmap with teacher landmarks (gray dots) and learned AAC landmarks (colored diamonds). Middle: selection matrix concentrating each compressed row on one teacher landmark (deployment takes the argmax). Right: heuristic gap loss converging. The heuristic is admissible at every frame.
AAC learns which landmarks matter by parameterizing a row-stochastic compression matrix A over a pool of K teacher landmarks (selected by farthest-point sampling). Each of the m output dimensions is a convex combination of teacher distances. Since a convex combination of admissible lower bounds is itself admissible (Proposition 2 in the paper), the compressed heuristic is admissible for every value of A -- not just at convergence, but at initialization and every intermediate checkpoint.
During training, Gumbel-softmax annealing sharpens each row of A from a diffuse mixture toward a one-hot selection, so the final model selects a discrete landmark subset. The training objective minimizes the gap between the learned heuristic and the teacher, driving the selected landmarks toward those that most reduce A* node expansions.
LinearCompressor is the only compression architecture. Its rows are row-stochastic, so each output is a convex combination of triangle-inequality bounds and cannot exceed their max (Proposition 2). At inference the rows collapse to one-hot, making the compressed heuristic exactly ALT on the selected subset (Corollary 3).
Standard farthest-point sampling (FPS) places landmarks to maximize geometric spread -- a reasonable spatial heuristic, but one that is entirely query-agnostic and cannot adapt to graph structure. AAC landmarks are selected by gradient descent to minimize search cost, which means they concentrate on structurally important locations (corridor junctions, bottleneck edges) rather than simply maximizing pairwise distance.
| FPS Landmarks | AAC Landmarks | |
|---|---|---|
| How selected | Greedy farthest-point sampling | Gradient-based differentiable selection |
| Optimizes for | Spatial coverage (max-min distance) | Search efficiency (min A* expansions) |
| Adapts to graph | No -- fixed once computed | Yes -- learns bottleneck structure |
| Memory | Full K landmarks | Compressed subset m ≪ K |
| Admissibility | By triangle inequality | By construction (convex combination) |
- Memory-constrained deployment: Compress a large landmark table (e.g., K=48 → m=10) for onboard robot planning. On the maze above this yields 4.8× memory reduction while retaining 83% expansion savings over uninformed search.
- End-to-end differentiability: Gradients flow through the heuristic, enabling joint optimization with upstream modules such as graph construction or edge-weight learning.
- Anytime admissibility: Every intermediate checkpoint produces a valid admissible heuristic. A partially-trained model can be deployed immediately -- no waiting for convergence, no post-hoc verification.
A* search expansions on a 30×30 maze: Dijkstra (no heuristic) vs ALT (K=16 landmarks) vs AAC (m=16 from K₀=32). At matched memory both focus the search hard (843 -> 69 and 89 expansions); on this instance FPS-ALT is ahead. Regenerate with python scripts/generate_readme_gif.py.
Under a matched per-vertex memory protocol on 9 road networks + 3 synthetic graph families:
| Metric | Finding |
|---|---|
| Expansion count | FPS-ALT leads AAC by 0.9-3.9 pp on roads, ≤1.3 pp on synthetic graphs |
| Query latency | Withdrawn: the old figure measured an implementation gap between ALT and AAC, not the method. See Stale results |
| Admissibility | Zero violations across every checkpoint, every parameter setting, by construction |
| Amortization | AAC's offline cost amortizes within 170-1,924 queries per graph |
| Binding constraint | Training-objective drift, not architecture; identity initialization closes the gap |
Some of these numbers predate the correctness fixes made after b6ec01b; see Stale results for which ones and how to regenerate them.
# From source (Python 3.11+, PyTorch 2.12+)
pip install -e ".[dev,experiments]"
# Or with conda:
conda env create -f environment.yml
conda activate aac
# Or with uv (recommended):
uv syncHardware used in the paper: Intel Core Ultra 9 285K (CPU experiments), NVIDIA RTX 5090 (Warcraft contextual training), 128 GB RAM.
Three self-contained demos -- no dataset downloads needed:
# Grid navigation with obstacles
python examples/demo_grid_navigation.py
# Road routing with memory-accuracy tradeoff
python examples/demo_road_routing.py
# End-to-end differentiable terrain routing
python examples/demo_terrain_routing.pyGrid navigation output (matched memory, K=16 vs m=16):
[Dijkstra] Cost: 28.04 Expansions: 253
[ALT K=16] Cost: 28.04 Expansions: 69 (72.7% reduction)
[AAC m=16] Cost: 28.04 Expansions: 68 (73.1% reduction)
Memory: ALT = 16 values/vertex, AAC = 16 values/vertex (matched)
All paths optimal (cost = 28.04)
One query is noisy; over the demo's 50-query benchmark ALT leads by half a point (86.8% vs 86.3%). All three demos pin the FPS start vertex, so runs are reproducible.
# Full pipeline: all experiments + tables + figures + verification (~hours)
python scripts/reproduce_paper.py
# Fast: regenerate tables and figures from existing CSVs (seconds)
python scripts/reproduce_paper.py --tables-only
# Single track (see --help for the 11 valid tracks)
python scripts/reproduce_paper.py --track dimacs
python scripts/reproduce_paper.py --track osmnx
python scripts/reproduce_paper.py --track syntheticStep 0: Download all datasets (run once, ~400 MB total):
python scripts/download_all_data.py # all datasets
python scripts/download_all_data.py --dimacs # DIMACS road graphs only
python scripts/download_all_data.py --osmnx # OSMnx city/country graphs only
python scripts/download_all_data.py --warcraft # Warcraft terrain maps onlysrc/
aac/ -- core library
heuristics.py -- shared landmark heuristic factory (ALT and AAC), max combiner
compression/ -- LinearCompressor, smooth heuristic construction
search/ -- A* (with BPMX), Dijkstra, bidirectional A*, batch search
baselines/ -- ALT, CDH, FastMap reference implementations
embeddings/ -- FPS anchor selection, SSSP teacher labels
contextual/ -- end-to-end differentiable pipeline
(encoder -> shortest paths -> compress -> heuristic)
train/ -- training loop (gap-closing objective,
Gumbel-softmax annealing, fused AdamW)
viz/ -- shared figure styling (Okabe-Ito palette)
graphs/ -- graph types (CSR), I/O (NPZ), loaders
(DIMACS, OSMnx, Warcraft, PBF, MovingAI)
utils/ -- numerics (sentinel handling, safe log),
memory accounting
experiments/ -- Hydra-configured experiment runners
(DIMACS, OSMnx, Warcraft, Cabspotting)
scripts/ -- experiment scripts, figure/table generators
(50+ scripts, see scripts/README.md)
tests/ -- pytest suite (20 modules, ~217 tests)
results/ -- experiment outputs (CSVs, logs); see results/README.md
examples/ -- three self-contained demos (no dataset downloads)
For the per-experiment file index and provenance chain, see results/README.md.
| Optimization | Effect |
|---|---|
Graph.csr_lists() caches the CSR-to-Python-list conversion per graph, not per query |
short query on a 90k-node grid: 22.7 ms to 0.41 ms |
| Contextual pipeline runs exact Bellman-Ford with no autograd tape, differentiating the fixed point via a softmin-weighted adjoint | forward+backward on a 12x12 grid: 4.2 s to 3.7 ms, and values exact at every temperature |
Training loops run single-threaded (torch_threads); their tensors are below a useful parallel grain |
200 epochs at K=64: 158 s to 1.1 s |
| Heuristic callables evaluate on numpy, not torch | FastMap h: 6.9 to 1.6 us per call |
| ALT and AAC share one heuristic factory over vertex-major tables, with the target row hoisted out of the per-node call and a one-time sentinel scan replacing per-query masking | 30 queries on a 90k-node grid: 2244 ms to 1115 ms, expansion counts unchanged |
torch.optim.AdamW(fused=True) on CUDA |
~20% training speedup |
| Eval-mode compression indexes instead of multiplying by a one-hot matrix | removes float32 rounding that could violate admissibility |
Small compression steps run under torch_threads(1); the thread pool costs more than a (V, m) gather below ~300k vertices |
building labels for a 400-vertex graph: 18 ms to 18 us |
Log-domain operations use torch.logsumexp with shift-stabilization; the 1e18 sentinel avoids inf-inf NaN propagation.
If you find this work useful, please consider citing:
@article{le2026aac,
title={AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT},
author={Le, An T. and Ngo, Vien A.},
journal={arXiv preprint arXiv:2604.20744},
year={2026}
}Apache License 2.0. See LICENSE for the full text.
Copyright © 2026 An T. Le and Vien A. Ngo.