Symmetry Orbits as the Unit of Work in Multi-Agent LLM Planning

Multi-agent language-model planners split a large job into subtasks and hand each one to a separate agent or reasoning loop. Many real plans contain subtasks that are interchangeable: three identical vehicles to route, two travelers who need matching rooms, several jobs with the same structure on identical machines. Today's systems pay full price for each copy. They generate a plan for every copy, check every copy, and repair every copy when something breaks. If a validator rejects a partial plan, the system learns nothing about the mirror-image plan that differs only by swapping two identical vehicles, and it may propose and reject that plan as well.

We propose that the planner should treat the orbit, meaning the set of subtasks that a symmetry of the problem maps onto one another, as its unit of work. The decomposer writes the task as a small labeled graph of subtasks, resources, and constraints. An exact graph-automorphism routine finds which subtasks are interchangeable. The agents then do three things with that information. They solve only one representative per orbit and move the solution to the other members by relabeling. They propagate every validator rejection to all symmetric images of the rejected partial plan. They refuse to expand decomposition branches that differ only by a permutation of interchangeable parts. The claim is that this cuts language-model calls in proportion to orbit size without lowering pass rates, and that it does better than the obvious alternatives: exact-duplicate caching, embedding-similarity skill reuse, and simply asking the model to notice symmetry.

Where this sits

Classical symmetry-aware search supplies the method. Orbit-based pruning and partition caching in branch-and-bound let Computing Twin-width with SAT and Branch & Bound more than double the number of Treewidth Lib instances solved to optimality. Grouping vertices with identical neighborhoods let Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach cut search branches to as little as 0.01% of McSplitDAL. SymmPi matches one copy of a symmetric component and then permutes the matches to cover the rest, with a 25x average speedup attributable to that module. Our "solve one, transport to many" step is SymmPi's match-then-combine pattern moved from subgraph matching to agent subtasks. This literature also constrains the design. SymmPi loses its advantage on asymmetric patterns, and Generalizing JPS Symmetry Detection reduced node generation 6.7x but runtime only about 2x because checking its pruning rules costs time. The method must therefore cost almost nothing when no symmetry exists, and we measure that directly.

The multi-agent work motivates the gap. TDAG builds a fresh subagent for every subtask and reuses past routines only through SentenceBERT retrieval from a skill library. ALAS limits repairs to the affected part of the plan through its Localized Cascading Repair Protocol, which saves 60% of tokens. It still treats every failure as unique, even when an identical failure already occurred on an interchangeable resource. ALAS also supplies something we reuse: an engine-agnostic intermediate representation and an isolated validator, a separate model call with a fresh context that judges plans. Our labeled constraint graph is an extension of that representation.

The nearest work bundles symmetry and agents, but in different senses. LoopBench studies agents breaking symmetry among themselves to avoid oscillation on odd cycles; it does not prune a shared plan space. The multi-agent path-finding papers (Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding, Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search) prune symmetric conflict resolutions, but only for geometric grid paths and without language models. Tree searches with language-model agents such as ToC and STATe-of-Thoughts prune by value scores or uncertainty. They expand permuted but equivalent branches as separate nodes.

Core Claim

Some subtasks are exactly interchangeable under a symmetry of the problem's constraint graph. For these, a validated solution to one representative, relabeled, is a correct solution for every orbit member, provided the members are coupled only through constraints that the symmetry preserves. A rejected partial plan is likewise rejected in every relabeled form; this is the classical idea of a "symmetric nogood," a ruled-out assignment that rules out its images too.

The number of expensive generation calls then scales with the number of orbits $|V/G|$ rather than the number of subtasks $|V|$. Here $V$ is the set of subtasks and $G$ is the automorphism group of the labeled graph. Each transported solution costs one cheap validator call instead of a full generation loop. The savings ratio follows from counting one full generation per orbit instead of per subtask:

$$\rho = \frac{|V|}{|V/G|}.$$

The proposal stands or falls on whether real language-model planners can produce a constraint graph faithful enough that the symmetries it reveals are true ones.

Research Program

We first build the representation layer. The decomposer agent outputs subtasks as typed nodes. It also outputs resources and constraints (budget, deadlines, precedence, capacity) as labeled nodes and edges, with each entity's attributes written as labels. Any attribute the decomposer cannot fill is marked as unknown and blocks symmetry. This is the conservative choice: two hotels are interchangeable only if every recorded attribute matches.

Next, an exact labeled-automorphism routine computes orbits over the subtasks and over decomposition choices. Orbits are recomputed only when the graph changes. This follows the twin-width caching idea of skipping repeated full isomorphism checks.

Three mechanisms then act on the orbits. The first is representative solving: the full agent loop solves one member per orbit, and an isolated validator checks each relabeled copy. A copy that fails is demoted to its own orbit and solved normally. The second is orbit nogoods: each validator rejection is stored in canonical form, so any later proposal whose canonical form matches is rejected without a model call. The third is canonical expansion: when the decomposer branches over assignments of interchangeable parts, for example which identical vehicle takes which ride, it expands only the lexicographically least representative of each equivalence class.

Shared resources are the hard case. Interchangeable subtasks that draw on one budget cannot simply be copied. We handle this with a SymmPi-style combination step: transported solutions are first checked jointly against the coupling constraints, and only the remainder is re-planned. We report how often that step falls back to full planning.

Baselines

The naive reference point is each host system run unchanged: no symmetry handling, the same models, the same token budget.

On its own suites, the strongest existing method is ALAS. It reports an 83.7% aggregated success rate with 60% token reduction and a 1.82x speedup over traditional multi-agent settings (ALAS). It is the right main competitor because it already attacks repeated work, through localized repair. We implement our mechanisms inside ALAS's own intermediate representation and validator, so the only difference is orbit handling. Beating it means equal or higher success on Urban Ride Assignment and the scheduling suites with a statistically clear reduction in tokens and calls beyond ALAS's own savings.

On planning benchmarks, the strongest reported multi-agent system is LRPLAN. It reports a 21.67% final pass rate on TravelPlanner and a 74.60% full completion rate on TimeArena-Static (LRPLAN). We add our layer to an LRPLAN-style planner-refiner pair with the same models and compare at matched compute. Beating it means matching pass rate at lower cost, or higher pass rate at equal cost.

On ItineraryBench, TDAG reports a fine-grained score of 49.08 against ReAct's 43.02 (TDAG).

Three ablations isolate the key ingredient. The first is a transposition table: exact-duplicate state hashing that merges only identical states reached in different orders. The second is TDAG-style embedding-similarity reuse of earlier subtask solutions. The third is our full system with each of the three mechanisms removed in turn. All variants share the same tuning budget, with thresholds chosen on a held-out split.

Why not just…?

Why not just cache identical states, as a transposition table does in tree search? This is the closest cheap alternative, and it does catch commutative edit orders of the kind ToC expands separately. It cannot catch states that are different but mirror images, such as vehicle A on ride 1 and B on ride 2 versus the reverse. Those mirror-image states are where the factor $\rho$ comes from. The transposition-table ablation measures exactly how much of our saving is ordinary duplication. If it captures most of the saving on real benchmarks, the automorphism machinery is not justified, and we will report that.

Why not just reuse similar past solutions through retrieval, as TDAG's skill library does? Similarity retrieval has no notion of correctness. Two subtasks that look alike but differ in one hidden constraint get the same retrieved routine, and the error flows downstream. That is the cascading-failure mode TDAG itself documents, with a 34.78% failure rate for static plan-and-execute on ItineraryBench. The comparison that settles this is the embedding-reuse ablation evaluated on false-reuse rate: transported solutions that the validator later rejects. Our exact orbits should show a much lower false-reuse rate at similar savings. If they do not, retrieval is the simpler answer.

Why not just prompt the decomposer to notice interchangeable subtasks? Strong reasoning models clearly can reason about symmetry; LoopBench shows O3 discovering symmetry-breaking tactics. But that paper also shows small models near 0% proximity, and MACM notes that models struggle to track equivalence in geometric condition mining. A prompted-symmetry ablation, at two model sizes, tests whether an exact routine adds anything over asking the model. We expect the gap to be largest for smaller models.

Why not just give scheduling instances to a classical solver with symmetry-breaking constraints? For pure job-shop instances a classical solver is the right tool, and we include one as a reference ceiling. The proposal targets settings like TravelPlanner and Urban Ride Assignment, where implicit commonsense constraints keep the language model necessary. LRPLAN documents exactly this weakness of purely deductive systems on implicit constraints.

Proposed Experiments

We run on TravelPlanner, ItineraryBench, TimeArena-Static, and the ALAS suites: DMU, TA, ABZ, SWV, YN, Urban Ride Assignment, and Family Reunion. Metrics are each benchmark's native pass or success rate, plus language-model calls, tokens, wall-clock time, false-symmetry rate, and the share of rejections caught by orbit nogoods without a model call.

Natural symmetry in these benchmarks varies and is often modest. We therefore also build controlled variants that add $k$ interchangeable copies of an entity: identical vehicles, group travelers with matching needs, identical rooms. This lets $\rho$ be dialed in.

The decisive checks are three. First, cost should fall roughly linearly in measured $\rho$ on the controlled variants, with no loss in pass rate. Second, on instances with no detected symmetry, overhead should stay below a few percent of total tokens, avoiding the JPS-style trap where checking costs eat the gains. Third, the false-symmetry rate from model-written graphs must be low enough that validator-caught demotions do not erase the savings. If the third check fails, the honest conclusion is that faithful representation, not symmetry exploitation, is the bottleneck for language-model planners.