PaperlayerView exact revision on arXiv

Source-linked AI summary

GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning

Wenjian Wu, Zesheng Jia, Jiaying Tang, Benyuan Yang, Jin Wang

arXiv:2609.00577v1cs.LGcs.AIcs.NE

TL;DR

Large-scale multi-agent combinatorial optimization remains difficult because parallel autoregressive solvers weaken under scale shifts and may generate conflicting actions. GeoPAR combines sparse geometry modeling with cache-guided conflict-aware assignment, improving zero-shot generalization while reducing rollout effort and maintaining efficient inference. Its main reported limitation is uneven improvement under extreme agent-density settings.

  • Problem

    Parallel autoregressive solvers face shifted local geometric structures at larger scales and independently generated conflicting task selections.

  • Method

    GeoPAR uses projection-window candidate neighborhoods, sparse edge-biased attention, and a reused geometric cache for conflict-aware parallel assignment.

  • Results

    Across HCVRP and OMDCPDP, GeoPAR improves large-scale zero-shot generalization while reducing ineffective simultaneous decisions and rollout steps.

  • Takeaways & Limitations

    GeoPAR preserves locally relevant actions and supports efficient parallel inference on larger instances than those used for training.

  • Takeaways & Limitations

    GeoPAR’s improvements are uneven under extreme agent-density settings, with very low-density HCVRP remaining sensitive to fleet scarcity.

Abstract

from arXiv · show

Multi-agent combinatorial optimization problems are notoriously challenging due to their NP-hard nature. Recent parallel autoregressive neural solvers improve inference efficiency by allowing agents to make decisions simultaneously, but their performance often degrades on large-scale instances. This is largely attributable to weak modeling of local geometric structures and the fact that conflicting task selections are handled only after action generation. To address these limitations, we propose GeoPAR, a geometry-guided parallel autoregressive reinforcement learning framework for scalable multi-agent combinatorial optimization. GeoPAR integrates three key components: (1) a projection-window sparse geometry mechanism that builds lightweight local candidate neighborhoods through multi-directional projections, (2) sparse edge-biased attention that injects these geometric relations into node representations, and (3) cache-guided conflict-aware assignment that reuses the geometric cache during decoding to suppress duplicate selections of exclusive tasks. Experiments on heterogeneous vehicle routing and open multi-depot pickup-and-delivery problems show that GeoPAR improves large-scale zero-shot generalization while substantially reducing rollout steps and maintaining efficient inference.

1 Introduction

Multi-agent combinatorial optimization is difficult because many problems are NP-hard and require efficient coordination among heterogeneous agents. GeoPAR addresses large-scale parallel-decoding weaknesses by modeling local geometry and suppressing conflicting task selections during assignment.

  • Motivation: Efficient coordination remains challenging when heterogeneous agents with distinct attributes must construct feasible solutions under complex constraints.
  • Motivation: NP-hard multi-agent combinatorial optimization often makes globally optimal solutions difficult to obtain within practical time limits.Conventional solvers also incur substantial computational costs and depend on problem-specific handcrafted heuristics.
  • Neural combinatorial optimization: Reinforcement-learning neural combinatorial optimization learns construction policies without manually labeled optimal solutions and can produce near-optimal decisions quickly.Autoregressive models construct feasible solutions step by step, but sequential decoding increases latency.
  • Challenges: Parallel autoregressive methods face scale-shifted local geometry and conflicts created when agents independently propose actions.Policies trained on small graphs may lose effective local successor structures on larger graphs, while simultaneous proposals can require later conflict repair.
  • GeoPAR: GeoPAR builds projection-window candidate neighborhoods, injects local geometry through sparse edge-biased attention, and reuses a geometric cache for conflict-aware assignment.The assignment mechanism suppresses duplicate task selections among simultaneous agent actions.
  • Reported evaluation: GeoPAR provides favorable large-scale generalization in solution quality, rollout steps, and inference time across multiple multi-agent combinatorial optimization tasks.

2 Related Work

Related work spans sequential and parallel neural combinatorial optimization, methods for large-scale generalization, and inference-time acceleration. These approaches trade off latency, adaptation cost, decomposition quality, or iterative refinement requirements.

  • Inference efficiency: GeoPAR achieves average inference-time speedups of 7.5× versus PARCO and 33.8× versus 2D-Ptr on large-scale instances.The experiments maintain a constant agent density of one agent per k tasks by setting M as N/k.
  • Multi-agent AR methods: Autoregressive neural routing solvers construct task allocations sequentially with dynamic state updates and feasibility masks, but this structure creates high generation latency.Recent parallel autoregressive methods introduce multiple pointers to reduce the sequential construction horizon.
  • Large-scale NCO methods: Large-scale NCO generalization remains challenging when models trained on small instances are applied to larger test instances.
  • Large-scale NCO methods: Adaptation-based methods reduce scale gaps through test-stage projection, extra decoder computation, or instance-specific adjustment, but add inference costs.
  • Large-scale NCO methods: Divide-and-conquer methods depend substantially on partitioning and merging strategies, while local-search methods require iterative refinement and may be problem-specific.

3 Preliminaries

The framework models collaborative multi-agent optimization as a Markov decision process in which agents choose actions jointly while conflicts are resolved before environment transitions. Parallel autoregressive decoding preserves autoregression across steps without imposing an ordering among agents within each step.

  • Collaborative Multi-Agent MDP: The collaborative multi-agent MDP defines states, agent-indexed feasible actions, transition dynamics, rewards, and a conflict-handling function.Feasible actions include task selection, waiting, and returning to a depot.
  • Collaborative Multi-Agent MDP: At each decision step, agents select actions that form a joint action distributed by the policy over the agents’ feasible action sets.
  • Conflict handling: The conflict handler removes or replaces duplicated assignments with waiting, producing an executable conflict-free joint action sequence.The environment then transitions and returns a reward based on that executable action.
  • Parallel autoregressive decoding: Parallel autoregressive models decode multiple agents’ actions simultaneously at each step while remaining autoregressive across decision steps.This avoids imposing an arbitrary sequential ordering on agents within a step, although raw simultaneous proposals may still conflict.

4 Method: GeoPAR

GeoPAR combines sparse geometric encoding with parallel decoding and cache-guided conflict-aware assignment for scalable heterogeneous multi-agent optimization. Its reusable geometric cache supports both local representation learning and feasible joint-action construction.

  • Overview: GeoPAR projects heterogeneous agents and task nodes into a shared representation space before geometry-aware encoding and parallel action construction.Separate projections preserve distinct agent and task feature spaces while enabling later interaction modeling.
  • Projection-Window Sparse Encoder: Projection-window neighborhoods sort task nodes along multiple directions and retain nearby rank positions, creating a lightweight sparse geometric cache.Before truncation, each node has at most 1 + 2w|R| candidates; TopK retains at most K candidates by rank distance.
  • Sparse Edge-Biased Enhancement: Sparse edge-biased attention injects edge geometry, candidate-source information, and projection-rank proximity into local node aggregation.Node embeddings also receive agent-conditioned updates, and the enhanced representations proceed through subsequent encoder layers.
  • Parallel Autoregressive Decoder: At each step, dynamic agent queries combine encoded embeddings with agent and environment states to produce parallel, feasibility-masked action scores.The decoder uses one dynamic query per active agent and scores actions from the same current state.
  • Cache-Guided Assignment: Candidate pools combine high-probability decoder actions, cache-based geometric successors, and task-native heuristic candidates before assignment scoring.Training additionally includes a few random feasible actions for exploration; hard infeasibility is handled by the feasibility mask.
  • Cache-Guided Assignment: Conflict-aware sampling and resolution maintain consumed exclusive actions, preventing duplicate assignments and returning feasible joint actions under the feasibility-mask and safe-fallback assumptions.Training excludes consumed exclusive actions, while inference assigns each conflict to the highest-scoring agent.

5 Experiments

Experiments evaluate GeoPAR across HCVRP and OMDCPDP, comparing conventional and neural baselines, zero-shot scale transfer, geometric candidate construction, projection-direction sensitivity, component interactions, and robustness across scales and agent densities.

  • Experimental Settings: GeoPAR is evaluated on HCVRP and OMDCPDP against conventional and neural baselines using objective value, gap, rollout steps, and inference time.HCVRP models heterogeneous capacitated vehicles, while OMDCPDP models open multi-depot pickup-and-delivery routing.
  • Overall Performance and Zero-Shot Scalability: Under large-scale zero-shot transfer, GeoPAR maintains locally meaningful candidate sets, reduces duplicate parallel selections, and achieves more effective inference than competing approaches.Sequential baselines become slower as N grows, while PARCO shortens construction but shows unstable solution quality.
  • Overall Performance and Zero-Shot Scalability: GeoPAR also performs better in large-scale OMDCPDP settings while retaining a short construction process, indicating applicability beyond Euclidean vehicle routing.The assignment layer filters decisions using dynamic feasibility and task exclusivity.
  • Projection-Window Fidelity and Sensitivity: Projection preserves most route edges with recall close to KNN while avoiding dense pairwise computation, balancing local coverage and cache-construction cost.Projection outperforms Random and Radius in retained task-to-task transitions.
  • Projection-Window Fidelity and Sensitivity: Using q=4 reduces rollout steps while maintaining solution quality; compared with q=8, its objective gap stays below 0.5% and runtime falls by up to 17.2%.The q=8 cache increases raw candidate slots from 69 to 137 and adds runtime overhead.
  • Component Analysis of Cache-Guided Assignment: Component analysis shows that conflict-aware assignment mainly reduces rollout waste, while combining geometric priorities with conflict handling improves quality and efficiency on dense instances.GeoScore gives the fewest rollout steps and shortest runtime on 3000- and 5000-node instances, whereas Full CA trades some efficiency for improved solution quality.
  • Robustness Across Problem Families, Scales, and Agent Densities: Across problem families and scales, GeoPAR remains below one second per OMDCPDP instance at N=20000, although the highest HCVRP agent density adds runtime at the largest scale.Higher agent density lowers the HCVRP min–max objective, while OMDCPDP objectives increase naturally with the number of requests.

6 Conclusion

GeoPAR targets large-scale multi-agent combinatorial optimization by combining reusable geometric structure with conflict-aware parallel assignment. Its supported scope includes heterogeneous vehicle routing and open multi-depot pickup-and-delivery settings, with a remaining limitation under extreme agent density.

  • 6 Conclusion: GeoPAR combines a projection-window cache, sparse edge-biased attention, and cache-guided conflict-aware assignment for large-scale multi-agent optimization.The framework preserves locally relevant actions and reduces ineffective simultaneous decisions.
  • 6 Conclusion: PWin improves local candidate quality, whereas CA assignment improves progress during parallel decoding.Ablations identify complementary roles for the two components.
  • 6 Conclusion: GeoPAR’s improvements are uneven under extreme agent-density settings, and very low-density HCVRP remains challenging because solution quality is sensitive to fleet scarcity.Adapting candidate construction and assignment priorities to agent-density shifts is identified as future work.
  • HCVRP: In HCVRP, each customer must be visited exactly once, while feasible parallel actions cannot assign the same customer to multiple vehicles.Capacity, duplicate-customer, and already-served actions are masked or repaired.
  • HCVRP: HCVRP evaluates route duration through a makespan objective, with the policy reward defined as its negative value.A rollout step is one parallel construction step in which all active vehicles may propose actions.
  • OMDCPDP: OMDCPDP requires pickup-before-delivery precedence, exclusive task actions within each parallel step, and open routes that need not return to depots.Its evaluation objective is cumulative delivery-arrival cost.

B.1 Implementation-Specific Model Settings

The implementation uses fixed multi-directional projection caches and sparse geometry features to build compact candidate pools for conflict-aware decoding. Candidate sources are ranked and deduplicated under feasibility constraints.

  • Model configuration: GeoPAR uses three encoder layers, eight attention heads, RMS normalization, one communication layer, and a single eight-head sparse geometry cross-attention layer.The geometry branch uses 16-dimensional edge descriptors, no dropout, and zero-initialized residual scaling.
  • Projection-window configuration: Four fixed projection directions with window radius w=8 produce 69 raw cache entries per task.The directions are globally shared and not learned or adapted during training.
  • Conflict-aware assignment: Each agent’s compact candidate pool contains four pointer-logit, four projection-cache, and two savings candidates.Training additionally includes four random feasible candidates.
  • Candidate sources: Savings candidates can add tasks absent from both the highest pointer logits and the local projection-cache neighborhood.The savings source is used for candidate retrieval, while common assignment scores rank pool entries afterward.
  • Geometric scoring: Cached task-pair geometry combines Euclidean distance, depot distances, and normalized projection-window offset.At a depot, the cache score is based on normalized task-to-depot distance.
  • Decoding: The four highest-scoring cache candidates form the cache portion of the pool, and duplicate actions retain only their first occurrence by source order.Conflict-aware decoding lets agents propose top candidates before contested tasks are assigned to the highest-scoring agent.

B.2 Shared Training and Evaluation Protocol

The reported models use a shared reinforcement-learning and deterministic-evaluation protocol, alongside task-specific baselines and solver configurations. Training is conducted on small instances before evaluation under stated timing limits.

  • Shared protocol: GeoPAR training uses online-generated instances, Adam with zero weight decay, and learning-rate milestones at epochs 80 and 95.Unless an ablation specifies otherwise, neural models use deterministic greedy decoding.
  • HCVRP baselines: SISR uses a route-destroy-and-repair heuristic with an iteration budget of 3 × 10^5N.Its reported configuration includes specified removal, temperature, and weighting parameters.
  • HCVRP baselines: GA evolves HCVRP solutions using population-based selection, crossover, and mutation with population size 200 and iteration budget 40N.Mutation and crossover probabilities are 0.8 and 1, respectively.
  • HCVRP baselines: SA combines temperature-controlled search, crossover, and 2-opt refinement with Markov-chain length 20N.The cooling factor is 0.98, with initial and final temperatures 100 and 10^-7.
  • Neural baselines: AM, 2D-Ptr, and DPN use separate small-scale training configurations and greedy or stated decoding for HCVRP evaluation.AM and 2D-Ptr use the N=100, M=7 checkpoint for zero-shot large-scale evaluation where specified.
  • Solver baseline: OR-Tools uses time limits of 30, 60, and 300 seconds for N=50, 100, and 500, and 600 seconds for N≥1000 in OMDCPDP.The solver combines Path Cheapest Arc initialization with Guided Local Search.

B.3 Dataset Details

Evaluation uses fixed HCVRP and OMDCPDP splits, including large-scale zero-shot settings without additional training. Training dynamics and large-scale behavior are reported under deterministic, batch-size-one evaluation where specified.

  • HCVRP: HCVRP uses nine fixed validation and test splits spanning N∈{60,80,100} and M∈{3,5,7}.The zero-shot settings use larger instances without additional training.
  • Protocol: The reported protocol includes training settings for the checkpoints in Table 6.Dataset-specific training and evaluation configurations are separated from the fixed test splits.
  • Training dynamics: Figure 6 evaluates GeoPAR on 128 fixed zero-shot HCVRP instances with N=1000 and M=20.Each checkpoint uses greedy decoding with batch size 1, and lines show means with 95% confidence intervals.
  • OMDCPDP: OMDCPDP uses six fixed splits, with n100_m20 selected for checkpoint selection.Large-scale comparisons use 128 instances per setting with batch size 1 and deterministic greedy decoding.

C.1 Training-Stage Quality–Efficiency Trade-off

GeoPAR learns a more compact construction process before fully refining solution quality, then preserves its rollout advantage while improving the objective over PARCO.

  • C.1 Training-Stage Quality–Efficiency Trade-off: After 10 epochs, GeoPAR reduces average rollout length from 407.5 to 175.9 steps, while its objective value remains 1.67% higher than PARCO.The early result indicates efficiency gains precede full quality refinement.
  • C.1 Training-Stage Quality–Efficiency Trade-off: At epoch 100, GeoPAR achieves objective value 13.686 versus 14.074 for PARCO and requires 125.6 rollout steps versus 599.0.The later checkpoint reverses the initial objective gap while retaining the shorter construction process.
  • C.1 Training-Stage Quality–Efficiency Trade-off: At epoch 100, GeoPAR improves the objective by 2.76% and reduces rollout length by 79.0% relative to PARCO.These simultaneous gains are attributed to progressively reducing redundant and conflicting decisions.

C.2 Test-Time CF Decoding Ablation

Forcing full conflict-aware assignment shortens rollouts consistently, but does not necessarily improve objective values or runtime.

  • C.2 Test-Time CF Decoding Ablation: Full conflict-aware assignment consistently shortens rollouts in HCVRP and OMDCPDP, but does not necessarily improve objective values or runtime.The ablation indicates that unconditional activation is insufficient for reliable overall gains.

C.3 HAM Results on Large-Scale OMDCPDP Instances

HAM degrades sharply on the large-scale zero-shot OMDCPDP settings, with both solution quality and construction efficiency worsening as scale increases.

  • C.3 HAM Results on Large-Scale OMDCPDP Instances: HAM's gap increases from 2958.16% at N=1000 and M=25 to 14744.05% at N=4000 and M=80.These values span the eight large-scale comparison settings reported in Table 8.
  • C.3 HAM Results on Large-Scale OMDCPDP Instances: HAM's rollout steps increase from 834.1 to 3494.0 over the same scale range.The larger gap and longer rollouts indicate simultaneous deterioration in solution quality and construction efficiency.
  • C.3 HAM Results on Large-Scale OMDCPDP Instances: The results indicate that HAM's sequential construction strategy does not generalize reliably to the large-scale scenarios in the comparison.This conclusion follows from the concurrent worsening of its objective gap and rollout length.
Loading 2609.00577v1…