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

AI summary

Overview

Research area: Multi-agent planning, LLM-guided program search, and interpretable programmatic skill transfer (with ties to automated heuristic design and cooperative multi-agent learning).

Technical level: Advanced. The paper assumes familiarity with Monte Carlo tree-search style UCB selection, multi-agent credit assignment, and LLM-based code search.

Scope: The paper introduces RELIC, a framework in which cooperating agents with incompatible program signatures improve private executable skills while sharing only short textual "revealed principles," and evaluates it on routing, scheduling, combinatorial optimization, and distributed coordination benchmarks.

What This Paper Is About

Multi-agent teams become hard to improve when each agent was built independently, exposes a different interface and different observations, and its executable implementation cannot be handed to teammates. A useful strategic idea found by one agent may therefore be unusable by another, because the code cannot be called through the teammate's signature. RELIC's goal is to let agents improve their own private programs while transferring the decision logic — not the code — as compact natural-language principles that recipients re-instantiate under their own interfaces.

Key Contributions

1. Problem formulation. The authors formalize cooperative programmatic skill learning in two coupled settings: heterogeneous agent signatures with restricted implementation sharing, and streaming task environments where data arrive in non-stationary batches and the team must continually adapt.
2. The RELIC framework. RELIC separates private executable-skill optimization from cross-agent knowledge transfer, combining contextual team-level evaluation, textual revealed principles, and a shared public principle memory that retains transferable coordination knowledge according to its observed downstream utility.
3. Broad empirical evaluation. Experiments cover heterogeneous-role and shared-role settings across cooperative routing, scheduling, combinatorial optimization, and distributed coordination, compared against independent LLM-based heuristic search and joint multi-function optimization, under both incompatible and common skill structures.
4. Mechanism and robustness analysis. The paper isolates principle-mediated transfer, the public principle memory, and private search through ablations, and tests robustness across multiple LLM backbones.

Main Findings

• RELIC leads most heterogeneous routing and scheduling settings. Table 1 reports gap-only comparisons under two sets of A/B/C signatures (myopic-greedy / teammate-aware / global planner for path planning; deadline sentinel / value harvester / system regulator for scheduling). RELIC attains a 0.00% gap on MAPP-PC, MAPP-AR, and MAS-ST at both sizes 50 and 80 under the first signature set, and on MAPP-PC, MAPP-AR (both sizes), MAS-FS, and MAS-ST under the second.
• The advantage survives interface changes. The paper states RELIC's benefit persists when callable interfaces, available observations, and role-specific responsibilities change, which the independently adapted baselines cannot match.
• Exceptions occur on weakly coupled objectives. The authors report that the few cases where RELIC is not best arise mainly where cross-role transfer adds less benefit. In Table 1's second signature block, RELIC's gap on MAPP-DS is 1.98% (size 50) and 16.05% (size 80) against 0.00% for ReEvo-ind., and 0.45% / 1.26% on MAS-JD against 0.00% for MOTIF.
• Backbone-dependent results, not backbone-dependent success. Qwen-3.6-Flash obtains the best mean on DGC (849.28 ± 0.00), DiMES (1900.08 ± 16.60), and SensorDCSP (39.63 ± 10.13), while GPT-4o-mini is best on SHDS (2795.42 ± 223.44) at 120 variables. DeepSeek-V4-Flash is also reported (DGC 894.62 ± 38.20, DiMES 1907.14 ± 34.91, SensorDCSP 51.45 ± 38.60, SHDS 2872.18 ± 398.53). Because the leading backbone changes across domains, the authors conclude the gains do not depend on a single generator, though their magnitude remains model- and problem-dependent.
• Transfer extends beyond routing and scheduling. In Table 3, RELIC obtains the best mean in four of eight columns: both FSTSP sizes (8.54 ± 0.12 and 12.06 ± 0.12) and both FJAGV sizes (18078 ± 241 and 78110 ± 767), and stays close to best on HMTSP (74.90 ± 0.03 and 133.43 ± 0.11) and MRCPS (929.28 ± 5.46 and 1969.82 ± 19.63).
• Components are complementary, not redundant. Table 4 ablations show degrading results when removing the public tree, Bridge, Lift, Reflect, or private UCB. Removing Reflect produces the largest gaps among the path-planning variants (9.52% and 7.31% on MAPP-PC), while on scheduling the largest gaps appear for w/o Bridge on MAS-ST (14.09% and 18.34%).
• Operators play distinct roles. Table 5 reports that Lift accounts for 49.70% of selections, 8.90% success, 5.20% mean gain, and 48.10% of positive gain; Bridge is selected 27.10% of the time with the highest success rate (9.50%) and 29.80% gain share; Reflect is selected 23.20%, has 9.00% success, and the largest downside rate (73.00%).
• Misleading principles propagate, and selection limits the damage. Figure 2's Mislead intervention (injecting corrupted principles) shows the strongest effect on tightly coupled tasks; the authors state that principle selection reduces the damage because misleading principles fail to accumulate downstream endorsement and are down-selected via Equation 19, though it does not eliminate error propagation.
• Role-aware feedback helps when peers are absent. Under the NoPeer intervention (peer principles removed), structured Reflect feedback is reported as less harmful than a single scalar signal.

Methodology in Plain English

RELIC runs in rounds over batches of tasks. Each agent keeps a private tree of candidate programs; the root is a seed skill and each child is an LLM-generated revision of its parent. A trusted orchestrator picks which agent to revise and which of three operators to use:

• Lift adapts a principle revealed by a teammate (stored in the agent's local archive).
• Bridge retrieves a principle from the shared public tree that has already accumulated evidence of working elsewhere.
• Reflect uses an orchestrator-written credit summary that compares the full team against the team with that agent removed, identifying when the agent is decisive, redundant, or harmful.

The LLM then writes a candidate program that must conform to that agent's own signature. The orchestrator inserts the candidate into the current team, leaves all teammates fixed, and measures the contextual marginal gain on a mixed evaluation batch built from the new data plus small replay samples from the two preceding batches. Candidates judged by the score alone are not trusted; only gains measured in team context count. Successful programs are distilled into short natural-language revealed principles describing an applicable context, a decision rule, and an intended coordination effect — deliberately excluding executable code and interface-specific variables.

Principles go into a public tree alongside their retrieval counts and cumulative positive endorsement. Bridge retrieval follows a UCB-style rule that favors principles with strong observed downstream impact while still exploring less-used ones; every Bridge revision increments the retrieval count, and positive gain adds to the endorsement. Low-endorsement leaves are pruned to keep the shared memory compact. After training, execution is fully decentralized — agents act only through their own programs, and the public memory is used for learning rather than runtime control.

Evaluation used EoH-ind., ReEvo-ind., MCTS-AHD-ind., HiFo-ind., and MOTIF as baselines, each run three times under the same data splits, LLM backbone, proposal budget, and execution limits, with five training batches, replay from the two preceding batches, and ten proposals per role per batch.

Why This Matters

The paper's distinctive claim is that strategy, not code, is the right transfer currency between independently built agents. That reframes an assumption baked into most LLM-based heuristic design work — that the optimizer can inspect and reuse the programs it is improving — and offers an alternative when interfaces, observations, and roles diverge.

Real-world settings the benchmarks model:

• Logistics and warehouse fleets, where different vendors supply robots or vehicles with different APIs that must still coordinate on shared routes and deadlines.
• Scheduling under shared resources, such as jobs, machines, and service teams where one role sets deadlines, another harvests value, and another regulates system load.
• Sensor and distributed constraint networks (the DGC, DiMES, SensorDCSP, and SHDS benchmarks at 120 variables), where local decisions interact through shared constraints and no single controller sees everything.
• Combinatorial optimization pipelines (HMTSP, FSTSP, FJAGV, MRCPS), where different roles construct different parts of a solver and one role's choice shapes the others' feasible options.

Industry relevance: the setting maps onto multi-vendor automation and federated tooling, where organizations want agents to coordinate without exchanging proprietary implementations. The paper is explicit that this is an implementation non-disclosure boundary, not formal privacy — the orchestrator is trusted to execute candidate programs, revealed principles deliberately expose strategy-level information, and RELIC provides no differential-privacy or cryptographic guarantees.

Future Directions

• Handling changes that require simultaneous agent updates. The paper notes that its one-agent-at-a-time coordinate updates simplify credit assignment and keep intermediate teams executable but may miss improvements requiring several agents to change at once.
• Stronger safeguards for corrupted transfer. The Mislead results show a faulty principle can be re-instantiated by multiple agents and align them around the same coordination pattern; principle selection limits but does not eliminate this propagation.
• Grounded confidentiality guarantees. The authors frame implementation non-disclosure as an assumption rather than a formal guarantee, leaving open whether privacy or confidentiality mechanisms can be added.
• Verifying semantic fidelity of transferred principles. The paper states that textual principles offer neither semantic fidelity nor formal confidentiality, so whether a recipient's re-instantiation truly preserves the contributor's intent remains unresolved. The paper content is truncated before the conclusion's full list of directions, so additional items are not reported.

Target Audience

Researchers and practitioners working on LLM-based program or heuristic search, multi-agent planning and coordination, and interpretable skill transfer. It is also relevant to engineers building multi-agent systems from independently developed components with incompatible interfaces, and to readers interested in how team-level credit signals can be turned into reusable, inspectable knowledge. The paper's heavy use of formal notation, UCB-derived selection rules, and ablation tables makes it most accessible to readers with a background in reinforcement learning or automated algorithm design; the framework's core idea, however, is stated in plain language in the introduction and methodology overview.

Authors’ abstract

Multi-agent planning becomes substantially harder when agents must improve specialized decision-making skills while keeping their internal implementations private. This regime arises when agents are developed independently, expose different interfaces and capabilities, and must nevertheless coordinate without sharing executable policies. Prior research has largely assumed centralized optimization, shared policy access, or common skill representations, making it poorly suited to privacy-constrained cooperation. We introduce RELIC, a framework for learning interpretable and composable skills via revealed principles. Each agent refines its own programmatic skill through private LLM-guided search, while a trusted orchestrator evaluates proposed updates solely through team-level performance. Successful behaviors are not broadcast as code; instead, they are abstracted into portable principles that other agents can instantiate within their own interfaces and recombine with local strategies. This separates coordination from implementation sharing, enabling cross-agent transfer under heterogeneous skill signatures. RELIC thus introduces a new paradigm for privacy-preserving skill learning and coordination in multi-agent planning.