cs.AIJul 18, 2026

RELIC: Revealed Principles for Learning Interpretable Composable Skills in Multi-Agent Planning

Authors: Nguyen Viet Tuan Kiet, Bui Dinh Pham, Duong Quoc Chinh, Dao Van Tung, Tran Cong Dao, Huynh Thi Thanh Binh

Organizations: Hanoi University of Science and Techonology, Hanoi, Vietnam · University of Sydney, Sydney, Australia

Abstract

Multi-agent planning becomes substantially harder when agents must improve specialized decision-making skills while keeping their executable implementations private. This setting arises when independently developed agents expose heterogeneous interfaces, observations, and capabilities, yet must coordinate under a shared team objective. Existing approaches commonly rely on centralized optimization, shared policy access, or common skill representations, assumptions that limit knowledge reuse when function signatures differ. We introduce RELIC, a framework for learning interpretable and composable programmatic skills through revealed principles. Each agent improves its own executable skill locally, while useful decision logic and coordination patterns are distilled into compact textual principles. Rather than requiring direct program exchange, these abstractions can be re-instantiated under agent-specific interfaces and reused across incompatible implementation spaces. A shared principle memory accumulates transferable knowledge and promotes abstractions that repeatedly improve team-level performance. This separation allows discoveries made by one agent to guide others while preserving local executable implementations and decentralized execution. RELIC therefore supports strategic transfer across both heterogeneous-role and shared-role cooperative teams. Extensive experiments across routing, scheduling, combinatorial optimization, and distributed coordination settings demonstrate RELIC's effectiveness against independent and joint LLM-based search methods, together with consistent benefits across task structures and LLM backbones.

Explore similar work

CardsList
Jun 24, 2026cs.AI

Offline Multi-agent Continual Cooperation via Skill Partition and Reuse

Extracting skills from multi-agent offline dataset improves learning efficiency via sharing task-invariant coordination skills among tasks. In settings where tasks occur sequentially and the space of skills grows exponentially, existing approaches that rely on heuristically designed and fixed-sized skill libraries struggle to resolve the problem of distributional shift and interference, facing catastrophic forgetting and plasticity loss. To address this problem and endow agents with the ability to continually discover and reuse coordination skills in open-environment, we propose COMAD, a principled framework for Continual Offline Multi-agent Skill Discovery via Skill Partition and Reuse. We first discover skills from mixed multi-agent behavior data with an auto-encoder to transform coordination knowledge into reusable coordination skills. Then we construct a skill-augmented policy learning objective with multi-head architectures, explicitly guiding the advantage function with reusable skills identified via a density-based reusability estimator. Theoretical analysis shows our method approximates the optimum of a continual skill discovery problem. Empirical results across diverse MARL benchmarks show that COMAD continually expands its skill library to mitigate interference, achieving superior forward and backward transfer for task streams compared to multiple baselines.
Yuchen Xiao, Lei Yuan, Ruiqi Xue +2
Unsupervised Skill DiscoveryMulti-Agent Reinforcement LearningOffline Reinforcement LearningGlobal CoordinationReuseOnline+1
AskPDF
May 8, 2026cs.AI

SkillLens: Adaptive Multi-Granularity Skill Reuse for Cost-Efficient LLM Agents

Skill libraries have become a practical way for LLM agents to reuse procedural experience across tasks. However, existing systems typically treat skills as flat, single-resolution prompt blocks. This creates a tension between relevance and cost: injecting coarse skills can introduce irrelevant or misleading context, while rewriting entire skills is expensive and often unnecessary. We propose SkillLens, a hierarchical skill-evolution framework that organizes skills into a four-layer graph of policies, strategies, procedures, and primitives, and retrieves them at mixed granularity. Given a task, SkillLens first retrieves semantically relevant skill seeds, expands them through degree-corrected random walk over the skill graph, and then uses a verifier to decide whether each visited unit should be accepted, decomposed, rewritten, or skipped. This enables the agent to reuse compatible subskills directly while adapting only locally mismatched components. To improve the system over time, SkillLens further refines multi-granularity skills and verifier in order to improve its routing decisions. We provide theoretical analysis showing that mixed-granularity adaptation incurs sublinear cost under sparse mismatch assumptions and that the evolutionary update rule monotonically improves the validation objective until a local optimum. Across MuLocbench and ALFWorld, SkillLens consistently improves over strong skill-based baselines, achieving up to a 6.31 percentage-point Acc@1 gain for bug localization and raising agent success rate from 45.00% to 51.31%.
Yongliang Miao, Ziyang Yu, Liang Zhao +2
Skill EvolutionLarge Language Model AgentsLens
AskPDF
Jun 15, 2026cs.AI

Tensor-Coord: Algebraic Decomposition of Joint Plan Tensors for Conflict-Free Multi-Agent LLM Planning

Large language models (LLMs) remain limited in multi-agent planning because independently generated plans can create coordination failures such as spatial collisions, resource contention, and temporal deadlocks. We introduce Tensor-Coord, a multilinear algebra framework that represents the joint plan of N agents as a third-order tensor T∈RN×H×AT \in R^{N \times H \times A} over agents, timesteps, and actions. Canonical Polyadic (CP) and Tucker decompositions are used to identify latent coordination structure. The minimal epsilon-approximate CP rank R* defines a computable coordination complexity measure, with CC(Pi)=(R∗−N)/NCC(Pi)=(R*-N)/N. We prove that R*=N is necessary and sufficient for plan independence. The residual E=T−TR∗E=T-T_{R*} defines a conflict score over agent pairs, timesteps, and actions, localizing failures without domain-specific rules. Tucker factors provide interpretable agent roles, temporal phases, and action clusters that are converted into natural language constraints for iterative LLM replanning. Experiments on multi-robot delivery tasks across Easy (2 agents, 5x5 grid), Medium (3 agents, 5x5 grid), and Hard (4 agents, 5x5 grid) settings show convergence to conflict-free plans in 100% of 2-agent cases within 1.4 iterations on average, 80% of 3-agent cases within 3.2 iterations, and 60% of 4-agent cases within 4.0 iterations. CP rank scaled approximately linearly as R∗(N)=3.9N+0.5R*(N) = 3.9N + 0.5, supporting its use as a predictor of coordination complexity.
Mudit Rastogi
Multi-Agent CoordinationLarge Language Model PlanningPlanning MethodsConflict
AskPDF