arXiv cs.AI· An T. Le, Vien Ngo·· 11 小时前AI 评分21
AAC：为 ALT 启发式设计的架构可容许可微分地标压缩
AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
AI 导读
研究者提出 Architecturally Admissible Compressor（AAC），在固定标签内存预算下按查询需求自适应选择 ALT 地标，并提供两种连续松弛，其中行随机松弛可证明松弛最优与离散最优一致。
正文 · 原文
Abstract:We introduce the Architecturally Admissible Compressor (AAC), which adapts landmark-based A* heuristics to query demand under a fixed label-memory budget. AAC provides two continuous relaxations of ALT (A*, Landmarks, and Triangle inequality) selection. With exact landmark distances, every parameter value defines a lower bound on shortest-path distance. Both relaxations deploy ALT using only the selected labels. The row-stochastic relaxation takes convex combinations of landmark distances. We characterize the maximal admissibility-preserving linear classes and prove that the relaxed and discrete optima coincide. The fractional relaxation mixes subset heuristics and supports continuous greedy (AAC-CG) with exact gradients and an entropy-regularized oracle for differentiable selection. For expected heuristic value, we prove an approximation guarantee with finite-step, oracle-error, and finite-sample terms. The limiting $1-1/e$ factor is optimal for arbitrary supplied pools and query distributions unless P${=}$NP. At matched label memory, AAC-CG reduces A* expansions by $1.9$-$22.7$% relative to farthest-point ALT (FPS-ALT) in all $19$ tested combinations of graph and memory budget across six road networks and two synthetic graphs. Each combination uses one $500$-query test split; all methods share distance tables when distances are symmetric. Canonical greedy also expands fewer nodes than FPS-ALT in all $19$ graph-budget pairs. AAC-CG achieves $99.6$% of canonical greedy's mean heuristic value on test queries, averaged over these pairs. AAC makes admissibility independent of training success, while its analysis and experiments distinguish selection quality from search efficiency.
| Comments: | 80 pages. Accepted at Transactions on Machine Learning Research (TMLR). Code: this https URL |
| Subjects: | Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Robotics (cs.RO) |
| Cite as: | arXiv:2604.20744 [cs.AI] |
| (or arXiv:2604.20744v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2604.20744 arXiv-issued DOI via DataCite |
Submission history
From: An Thai Le [view email]
[v1]
Wed, 22 Apr 2026 16:31:21 UTC (867 KB)
[v2]
Wed, 4 Nov 2026 18:26:24 UTC (976 KB)
来源：arXiv cs.AI · arxiv.org