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 classical toolchain (BPMX, bound substitution, A* with reopenings).
Paper: "AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT", An T. Le and Vien A. Ngo (arXiv:2604.20744).
The straight-through selector training on a 50×50 maze, compressing 48 FPS landmarks to 10. The deployed selector is AAC-CG (continuous greedy); this animation shows the ablation, whose training dynamics are the ones worth watching. 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, so it cannot exceed their max, and the compressed heuristic is admissible for every value of A: at initialization, at every intermediate checkpoint, and at convergence (Proposition 2). LinearCompressor is the only compression architecture.
Two optimizers search that class. AAC-CG, the deployed one, runs continuous greedy on the multilinear extension over the matroid of deployable selections and carries a
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, so an upstream module such as graph construction or edge-weight learning can be trained jointly with it.
- 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. The deployed selector is AAC-CG: continuous greedy on the multilinear extension of the selection objective, with a differentiable entropic linear oracle. The straight-through Gumbel-softmax selector is retained as the ablation.
| Metric | Finding |
|---|---|
| Expansion count | AAC-CG expands fewer nodes than FPS-ALT in 17 of 19 static settings (DIMACS NY at 32 B/v: 16,535 vs 19,063; Manhattan 1,154 vs 2,153) |
| Query shift | AAC-CG wins 18 of 18 in-distribution and 36 of 36 cross-distribution settings |
| Query latency | At one identical storage layout, AAC-CG's median query is below FPS-ALT's in 8 of 12 settings (Manhattan at 32 B/v: 1.61x); cycles per expansion agree across methods to within 6.6 % |
| Admissibility | Zero violations across every checkpoint, every parameter setting, by construction; row mass exactly 1.000 in all 21 audited training runs |
| Amortization | AAC-CG's offline cost amortizes within 91-2,621 queries per graph |
| Guarantee | 1 - 1/e approximation, a finite-sample term and admissibility of every training iterate in one statement (Theorem 14) |
| Candidate pool | AAC-CG beats each pool's own first-m prefix in 22 of 24 synthetic and 10 of 10 DIMACS NY settings across six generators |
# 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: 78 (69.2% reduction)
[AAC m=16] Cost: 28.04 Expansions: 71 (71.9% 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 a fifth of a point (86.2% vs 86.0%). 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 valid tracks)
python scripts/reproduce_paper.py --track dimacs
python scripts/reproduce_paper.py --track osmnx
python scripts/reproduce_paper.py --track synthetic
python scripts/reproduce_paper.py --track response # every table behind the review responseRunnable from the repository root, in the order the table pipeline requires:
python scripts/generate_tables.py # regenerate every LaTeX table from the CSVs
python scripts/generate_tables.py --check # byte-compare the regenerated tables
python scripts/generate_results_index.py --check # the artifact index matches the tree
python scripts/check_paper_consistency.py --strict # re-derive each numeric cell against its record
python scripts/check_results_quality.py # per-method schema and census invariants
python scripts/audit_results.py # schema-free sweep over every result CSV
python scripts/check_letter_numbers.py README.md results/README.md # statement numbers resolve
pytest tests -q
ruff check .
python scripts/verify_theory.py # exact-rational checks of the theory claimsThe table checks need paper/, a symlink to the LaTeX repository; without it they are skipped.
Step 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 and reopenings), Dijkstra, 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/ -- query generation, metrics, CSV provenance headers
scripts/ -- experiment scripts, figure/table generators
(see scripts/README.md)
tests/ -- pytest suite
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.