AAC: 아키텍처 제약 하에서의 미분 가능한 랜드마크 압축 기술을 활용한 ALT 최단 경로 휴리스틱

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

본 논문에서는 **AAC (Architecturally Admissible Compressor)**라는 미분 가능한 랜드마크 선택 모듈을 소개합니다. 이 모듈은 A*, 랜드마크, 그리고 삼각형 부등식을 활용한 최단 경로 휴리스틱인 ALT에 적용되며, 결과는 설계상 허용 가능합니다. 각 순전파 과정은 삼각형 부등식의 하한 값들의 행 확률 혼합으로 구성되어 있으므로, 수렴, 보정, 또는 투영 없이도 모든 파라미터 설정에서 휴리스틱이 허용 가능합니다. 배포 시, 이 모듈은 학습된 부분 집합에 대한 고전적인 ALT 방식으로 작동하며, 신경망 인코더와 엔드투엔드 방식으로 결합되면서 기존의 도구 체인을 유지합니다. 본 연구는 고전적인 휴리스틱 검색에서 허용 가능성을 유지하면서 압축하는 전통의 첫 번째 미분 가능한 구현입니다. 정해진 메모리 프로토콜 하에서, 가장 먼 점 샘플링(FPS) 랜드마크를 사용하는 ALT (FPS-ALT)가 거리 그래프에서 증명 가능한 준최적의 커버리지를 가진다는 것을 입증했습니다. 이는 어떤 선택기(selector)도 최대 몇 퍼센트의 여유 공간을 가질 수 있음을 의미합니다. AAC는 이 한계에 매우 가깝게 작동하며, 9개의 도로 네트워크에서 0.9~3.9%p의 차이가 있고, 합성 그래프에서는 1.3%p 이하의 차이를 보였습니다. 또한, 1,500건 이상의 쿼리와 모든 테스트 과정에서 허용 가능성 위반이 전혀 없었습니다. 동일한 메모리 환경에서, AAC는 DIMACS 도로 네트워크에서 중앙값 쿼리 시 FPS-ALT보다 1.2~1.5배 더 빠릅니다. 이는 오프라인 비용을 170~1,924건의 쿼리 내에서 상쇄할 수 있음을 의미합니다. 정밀한 분석을 통해, 성능 저하의 원인이 기본 초기화로 인한 학습 목표의 편차가 아닌, 아키텍처의 용량 부족임을 확인했습니다. 첫 m개의 요소에 동일한 값을 초기화하는 방법은 확장 횟수의 격차를 완전히 해소할 수 있습니다. 본 연구에서는 AAC 모듈, 재사용 가능한 메모리 벤치마킹 프로토콜 (paired two-one-sided test (TOST) 동등성 검사 및 사전 등록 포함), 그리고 참조 압축된 차등 휴리스틱 기준을 공개합니다.

We introduce \textbf{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 \emph{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 \emph{any} selector. AAC operates near this ceiling: the gap is $0.9$--$3.9$ percentage points on 9 road networks and ${\leq}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{\times}$ 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.