Skip to content

PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

PARCO is a reinforcement-learning framework that solves multi-agent combinatorial optimization (CO) problems by decoding all agents' actions in parallel rather than sequentially. It introduces transformer-based communication layers, a multiple pointer mechanism, and a priority-based conflict handler to achieve better solution quality and up to 24.7× lower inference latency than autoregressive baselines.

Problem

Existing autoregressive (AR) neural CO solvers for multi-agent settings suffer from two core deficiencies: (1) poor agent coordination leading to suboptimal solutions and weak generalization across problem sizes and agent counts, and (2) high inference latency because sequential token generation scales with the total number of agent actions rather than the longest single-agent trajectory.

Method

PARCO reformulates multi-agent CO as a cooperative Markov game where all M agents select actions simultaneously at each construction step. The architecture has three novel components:

  1. Communication Layers: After forming per-agent context embeddings (static agent embedding + dynamic state projection + environment feature projection), multi-head self-attention across agents followed by an MLP allows agents to attend to each other's current states before acting.
  2. Multiple Pointer Mechanism: A single shared decoder computes a joint logit matrix U ∈ ℝ^{M×N} over all agents and nodes via masked cross-attention, outputting independent probability distributions per agent in one forward pass.
  3. Priority-based Conflict Handler: When multiple agents select the same node, the agent with the highest action probability wins the conflict and the others receive a fallback ("stay") action, reducing total construction steps by ~4% in practice. Training uses REINFORCE with a shared baseline; parallel decoding reduces total steps from Σ_m T_m to max_m T_m.

Key Contributions

  • Parallel autoregressive framework for multi-agent CO applicable across problem classes (routing, scheduling).
  • Transformer Communication Layers enabling inter-agent coordination at each decoding step without fixing the number of agents.
  • Multiple Pointer Mechanism for simultaneous multi-agent action decoding with a single decoder.
  • Learned Priority-based Conflict Handler outperforming random and heuristic tie-breaking rules.
  • Strong zero-shot generalization to problem sizes and agent counts up to 10× those seen in training.

Results

HCVRP (min-max heterogeneous VRP): - PARCO (greedy) achieves 8.37% gap at N=60, M=3 vs. SISRs optimum; best neural greedy result. - PARCO (sampling) achieves 5.15% gap at N=100, M=7, outperforming 2D-Ptr (s.) at 5.17% and ET (s.) at 11.91%, at ~0.09s vs. 0.24–0.92s for competitors.

OMDCPDP (open multi-depot pickup & delivery): - PARCO (s.) achieves 0.00% gap (best known) across all tested configurations (N=50/100, M=5–20). - Outperforms OR-Tools (30–60s) at 0.02–0.04s inference; HAM collapses at larger M (e.g., 20.52% gap at N=50, M=10) while PARCO maintains <3% gap.

FFSP (flexible flow shop scheduling): - PARCO (s.) reaches 0.0% gap (best known) on all six tested configurations, including N=100 where Gurobi cannot find solutions within time limits. - More than 4× faster than MatNet (s.) (e.g., 0.99s vs. 3.88s at N=20, M=12).

Generalization (OMDCPDP, zero-shot): - At N=1000, M=200: PARCO (s.) achieves 0.00% gap; HAM achieves 7.63% and OR-Tools (600s) 36.81%.

Speedup vs. AR baselines: - 3.3× speedup at M=10, 6.5× at M=20, 24.7× at M=50 (Figure 4).

Limitations

  • Requires a fixed, pre-specified number of agents M at training time; cannot directly handle problems where M is unknown or variable at inference.
  • Authors propose workarounds (batch rollout over candidate M values, or a prediction module) but leave these to future work.
  • Fallback "stay" actions during conflict resolution add extra construction steps, though this does not affect final solution feasibility.

Relevance to Agentic AI / LLM Agents

PARCO is directly relevant as a study of how to coordinate multiple autonomous agents making simultaneous decisions under shared constraints — a core architectural challenge in multi-agent LLM systems. The communication layer design (cross-agent attention before action selection) mirrors emerging patterns in multi-agent LLM frameworks where agents broadcast partial states before committing to actions. The parallel decoding mechanism with conflict resolution addresses the same token-budget / latency trade-off that motivates speculative decoding in LLMs, and the generalization results (10× scale-up zero-shot) suggest that learned coordination policies can transfer across problem scales, informing how agent orchestration modules might be trained for deployment.