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

• URL: http://arxiv.org/abs/2604.20744v1
• Date: Wed, 22 Apr 2026 16:31:21 GMT
• Title: AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
• Abstract summary: AAC is a differentiable landmark-election module for ALT (A*, Landmarks, and Triangle) shortest-paths.<n>It is the first differentiable instance of the compress-while-admisibility tradition in classical search.
• Score: 1.2891210250935148
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Directional Contextual Representations for Dependency Relations: Why Cross-Direction Pairing Fails [22.49571926071395]
  We show that pairing a token's forward state against a emphcandidate's backward state (cross-direction'' pairing, $F_i$ vs. $B_j$) consistently emphunderperforms same-direction pairing, and the penalty emphgrows, not shrinks, with token distance, both paired-bootstrap significant.
  arXiv  Detail & Related papers  (2026-08-21T00:50:25Z)
• Omni2LoRA: Coherence-Preserving Parametric Memory for Efficient Omni Language Models [65.49950267695267]
  We introduce Omni2LoRA, a framework for efficient parametric memory compression via coherence-preserving context distillation.<n>By converting multimodal memory into a fixed-budget, reusable parameter state, our method drives answer-time multimodal-token load to zero.
  arXiv  Detail & Related papers  (2026-08-10T07:49:10Z)
• Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates [1.2891210250935148]
  We give a certificate-carrying sub-quadratic method for MDPs with bounded transition support.<n>An approximate-nearest-neighbor index selects the pairs updated by the exact restricted operator.<n>Local index quality alone cannot control global error.
  arXiv  Detail & Related papers  (2026-08-07T03:32:40Z)
• Kernelized Linear Attention: Breaking the Capacity Wall with Symmetric Cones [4.847095054351615]
  Linear attention promises constant-time recurrent inference but degrades sharply on associative recall.<n>We introduce Kernelized Linear Attention Activations (KATA), a framework whose feature maps are derived from first principles.<n>We show that rank-one positive semi-definite features offer a favorable capacity--interference tradeoff.
  arXiv  Detail & Related papers  (2026-07-19T21:46:09Z)
• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  We operationalize the floor as the emphTri-Audit Protocol, a two-axis reporting protocol that separates a prompt-side deductive registry attribute from a model-side empirical corollary.<n>A constrained best-of-family search over deterministic and guarded learned filters on CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of twenty-eight pass-preserving rows, twelve-changed-of-record learned-can
  arXiv  Detail & Related papers  (2026-06-02T08:22:14Z)
• The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
  ListOPD brings a student to in-domain with an 8B-SFT baseline at one-fifth the parameters.<n>On Amazon Fashion, three pre-registered tests--a fine-grid cliff interval test, and a small-clip cross-prediction--fall within their locked prediction windows--with the small-clip value matching the closed-form prediction below grid resolution.
  arXiv  Detail & Related papers  (2026-05-09T06:48:00Z)
• A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification [0.0]
  PLACE (Persistence-Landmark Analytic Classification Engine) is a closed-form pipeline for classifying point clouds and graphs.<n>Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone.
  arXiv  Detail & Related papers  (2026-05-04T17:15:01Z)
• Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence [6.908972852063454]
  Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners.<n>We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting.<n>Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions.
  arXiv  Detail & Related papers  (2026-04-15T02:32:30Z)
• Mild Over-Parameterization Benefits Asymmetric Tensor PCA [12.923414933046574]
  Asymmetric PCA (ATPCA) is prototypical model for studying the trade-offs between sample complexity, computation, and memory.<n>We focus on the setting where $overlinek geq 4$ is even and consider descent-based algorithms under a limited memory budget.
  arXiv  Detail & Related papers  (2026-04-11T13:34:48Z)
• Label-Free Cross-Task LoRA Merging with Null-Space Compression [50.63908869296697]
  We introduce Null-Space Compression (NSC) Merging, a label-free, output-agnostic method that sets merge weights from adapter geometry.<n>NSC achieves state-of-the-art performance across twenty heterogeneous vision tasks with balanced gains where prior methods overfit subsets of tasks.
  arXiv  Detail & Related papers  (2026-03-27T11:34:41Z)
• Dynamic Large Concept Models: Latent Reasoning in an Adaptive Semantic Space [56.37266873329401]
  Large Language Models (LLMs) apply uniform computation to all tokens, despite language exhibiting highly non-uniform information density.<n>We propose $textbfDynamic Large Concept Models (DLCM)$, a hierarchical language modeling framework that learns semantic boundaries from latent representations and shifts from tokens to a compressed concept space where reasoning is more efficient.
  arXiv  Detail & Related papers  (2025-12-31T04:19:33Z)
• Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
  We propose an acquisition-level scalar $S_mathcal B$ based on instrument-resolved phase space.<n>We show theoretically that (S_mathcal B) correctly identifies the phase-space coherence of periodic sampling.<n>$|S_mathcal B|$ consistently ranks sampling geometries and predicts downstream reconstruction/recognition difficulty emphwithout training.
  arXiv  Detail & Related papers  (2025-12-22T10:03:51Z)
• Spectral Sentinel: Scalable Byzantine-Robust Decentralized Federated Learning via Sketched Random Matrix Theory on Blockchain [0.0]
  Byzantine clients poison gradients under heterogeneous (Non-IID) data.<n>We propose Spectral Sentinel, a Byzantine detection and aggregation framework.<n>We implement the full system with blockchain integration on Polygon networks.
  arXiv  Detail & Related papers  (2025-12-14T09:43:03Z)
• Binary perceptron computational gap -- a parametric fl RDT view [2.538209532048867]
  asymmetric binary perceptron (ABP) likely exhibits two phase transitioning constraint density thresholds.<n>We consider a particular parametric utilization of emphfully lifted random duality theory (fl RDT) [85] and study its potential ABP's algorithmic implications.
  arXiv  Detail & Related papers  (2025-11-02T18:23:49Z)
• The Alignment Bottleneck [0.0]
  We model the loop as a two-stage cascade $U to H to Y$ given $S$, with cognitive capacity $C_textcog|S$ and average total capacity $barC_texttot|S$.<n>It pairs a data size-independent Fano lower bound proved on a separable codebook mixture with a PAC-Bayes upper bound whose KL term is controlled by the same channel via $m, barC_texttot|S$.
  arXiv  Detail & Related papers  (2025-09-19T12:38:30Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  We study linear contextual bandits in the misspecified setting, where the expected reward function can be approximated by a linear function class. We show that our algorithm enjoys the same gap-dependent regret bound $tilde O (d2/Delta)$ as in the well-specified setting up to logarithmic factors.
  arXiv  Detail & Related papers  (2023-03-16T15:24:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.