Learning Admissible Heuristics via Cost Partitioning
Summary
This paper proposes a framework that learns admissible cost partitions for planning heuristics by leveraging Lagrangian dual equivalence, using a deep architecture with axial self-attention to guarantee admissibility by construction. It claims to be the first machine-learned heuristic provably guaranteed to be admissible.
View Cached Full Text
Cached at: 06/05/26, 02:08 AM
# Learning Admissible Heuristics via Cost Partitioning Source: [https://arxiv.org/abs/2606.04597](https://arxiv.org/abs/2606.04597) [View PDF](https://arxiv.org/pdf/2606.04597) > Abstract:Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation\. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive\. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction\. Planning states and patterns are encoded as labelled graphs, and an action\-centric variant of the Weisfeiler\-Leman algorithm extracts structural feature vectors\. A deep architecture with axial self\-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility\. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility\. To our knowledge, this is the first machine\-learned heuristic guaranteed to be admissible\. ## Submission history From: Quentin Cappart \[[view email](https://arxiv.org/show-email/1f912d48/2606.04597)\] **\[v1\]**Wed, 3 Jun 2026 08:35:04 UTC \(43 KB\)
Similar Articles
Learning and Reusing Policy Decompositions for Hierarchical Generalized Planning with LLM Agents
This paper introduces HCL-GP, a dynamic policy-learning framework that integrates generalized planning and hierarchical task decomposition to enable LLM-based agents to learn and reuse executable policy components, significantly improving performance on the AppWorld benchmark.
Safe Inference-Time Alignment via Lagrangian Reward Augmentation
Proposes LARA, a framework for safe inference-time alignment that uses Lagrangian dualization to derive an augmented reward from separate reward and cost models, improving the helpfulness-harmlessness tradeoff without retraining.
AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design
This paper introduces AHD Agent, a framework using agentic reinforcement learning to enable LLMs to autonomously design heuristics for combinatorial optimization problems by dynamically interacting with the solving environment.
Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design
This paper proposes Latent Heuristic Search (LHS), a framework that shifts heuristic discovery to a learned continuous latent manifold, using gradient-based optimization and normalizing flows to generate novel heuristics conditioned on large language models, achieving competitive results on TSP, CVRP, KSP, and Online Bin Packing.
HIPIF: Hierarchical Planning and Information Folding for Long-Horizon LLM Agent Learning
Introduces HIPIF, a method for training LLM agents to handle long-horizon tasks by hierarchical planning and information folding to reduce long-context interference, achieving strong results on three benchmarks.