PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization

We sincerely thank the reviewer for their valuable and detailed feedback. We are happy to provide below extensive answers to highlight the significance and originality of our approach.

W1 & Q1: about the formulation of multi-agent CO

We appreciate the opportunity to clarify these important concepts.

In conventional CO, "agents" are indeed mathematical entities without the interactive properties we model. Our approach differs fundamentally in how we conceptualize and solve these problems.

In our formulation, we model problems where multiple distinct entities must coordinate to construct a complete solution as multi-agent systems. Each "agent" corresponds to a physical entity (e.g., vehicle, machine, robot) that can independently take actions to build parts of the overall solution. This is formalized through our parallel multi-agent MDP in Section 4.1, where agents operate in a joint action space $A_1 \times ... × A_M$ rather than a single action space.

The key distinctions are:

• Multi-agent CO (PARCO): Multiple coordinating entities construct solution parts simultaneously with communication and conflict resolution.
• Single-agent CO: One entity constructs the entire solution sequentially.
• Conventional CO: Mathematical optimization without explicit agent modeling or coordination mechanisms.

Regarding nodes, these represent the discrete decision points or locations in the problem space (customers in VRP, jobs in scheduling). The relationships between nodes are problem-specific (distances in routing, precedence in scheduling) and captured in our encoder representations and through masking in the decoder.

Our decision variables are the actions taken by each agent at each time step, forming joint actions $\mathbf{a}_t = (a^1_t, ..., a^M_t)$. The optimization objective remains minimizing the original CO cost function, but achieved through coordinated parallel construction rather than centralized sequential planning.

This formulation enables the communication layers and conflict resolution mechanisms that are central to our contribution, allowing agents to coordinate during solution construction rather than operating independently.

W2: About literature review

Thank you for raising this important point about our literature review and motivation. We appreciate your feedback and would be happy to expand our literature review in specific directions if you could suggest particular areas you would like us to focus on. Regarding the definition of multi-agent CO, we intentionally keep it broad because our approach is general-purpose and does not restrict to any single problem class; we view this generality as a key advantage of PARCO, allowing it to tackle diverse optimization scenarios with a unified framework.

Your example of ride-hailing with polynomial-time algorithms like the KM algorithm is well-taken for certain task assignment problems. However, this does not apply to the significantly more complex problems we address. The combinatorial optimization problems we consider - particularly OMDCPDP and FFSP - are much harder computational challenges where traditional methods struggle considerably. Our experimental results demonstrate that PARCO not only finds substantially better solutions than existing approaches but does so more efficiently and with superior scalability. For instance, in FFSP, traditional solvers like Gurobi cannot even find feasible solutions for problems with $N > 20$ within reasonable time limits, while PARCO consistently outperforms all baselines across all tested scales. This highlights that while polynomial-time solutions may exist for some specific assignment problems, the broader class of multi-agent CO problems we target requires the sophisticated coordination and parallel decision-making capabilities that PARCO provides.

W3 & Q2: About the effectiveness of the conflict handler

Thank you for your detailed question about the conflict handler. We appreciate your concern about the fallback mechanism and would like to clarify several key points about its design and effectiveness.

First, we want to emphasize that the fallback mechanism is only applied to actions that are in conflict and not selected as priority and not to every action. This selective application guarantees feasibility of construction while maintaining the parallel decision-making benefits. The priority-based selection uses learned probabilities from the model output (as shown in Fig. 3c, where "learned" priorities consistently outperform heuristic alternatives), making it an adaptive mechanism that leverages the neural network's learned representations rather than being purely fixed. The fallback actions (staying at current position for routing, keeping machine idle for scheduling) are domain-appropriate "do nothing" operations that maintain feasibility without disrupting solution quality, as agents can reconsider their choices in subsequent decoding steps.

Regarding your question about more sophisticated conflict resolution methods, we acknowledge this as an interesting direction for future work. However, our empirical results demonstrate that the current approach already works quite well in practice: PARCO achieves state-of-the-art performance across all tested problems while maintaining computational efficiency. The simplicity of the fallback mechanism is actually a strength, as it provides reliable constraint satisfaction without adding computational overhead or training complexity. We chose this approach following the principle of using the simplest effective solution, similar to how masking is used in neural combinatorial optimization to guarantee feasible solution construction. The learned priority mechanism already provides the adaptive component you mentioned, while the fallback ensures robustness.

W4 & Q3: About lack of training curve plots

Thank you for pointing this out. While we cannot add figures or any other media due to the rebuttal policy, we will provide the below table with PARCO's convergence evaluated on the validation dataset (training budgets refer to the percentage of the total training epochs):

We can observe that PARCO is robust and yields consistent improvements.

Q4: What is the practical significance of the approach?

Thanks for asking this question, as it gives us an opportunity to further emphasize the strength of our approach. PARCO yields substantial imporvements over multiple problems, scales, and number of agents. In most problems we tested, it yields SOTA results even against heuristic approaches and a fraction of the cost.

To further strengthen our results, we have tested PARCO for even larger scales in both number of nodes and number of agents during the rebuttal. We generated 16 new instances for $N=5000$ nodes and 3 different values of $M$ agents total of 48 instances of OMDCPDP and evaluate OR-Tools with 1 hour of runtime and greedy performance for HAM and PARCO. The results are in the table below:

As we can see from the results, PARCO excels at generalization in extremely large scales with $50\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools -- at a $10,000\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications.

Thank you for your constructive feedback and for your time reviewing our paper. We greatly appreciate your acknowledgment of PARCO's strengths, including our model's efficacy across multiple settings and the thorough experimental design.

We will address your concerns and questions in the following.

W1: About fair efficiency comparison

This is a crucial point that highlights a core contribution of our work. The reformulation from a sequential to a parallel decision-making process is an intentional innovation designed to find higher-quality solutions more efficiently.

The comparison is fair for two key reasons:

• Shared Objective: All models are ultimately judged on the quality of the final, complete solution (e.g., the total makespan or the longest route) for the same underlying optimization problem. The method of constructing that solution is what differs.

• Efficiency as a Contribution: PARCO's ability to construct this solution in parallel is precisely the source of its efficiency advantage. It drastically reduces the number of sequential decoding steps required to build a valid solution (see figure 3b), leading to significant speedups in both training and inference without sacrificing - and often improving - the final solution quality.

Therefore, the efficiency gain isn't an artifact of an unfair comparison; it's the direct result of a more advanced and arguably more realistic solution construction methodology.

W2: About training curves and clarification of figure 3b

Thanks for pointing us to missing information and training details. Regarding the convergence analysis, while note that we cannot add figures or any other media due to the rebuttal policy, we will provide the below table with PARCO's convergence evaluated on the validation datasets of the respective problems (Training budgets refer to the percentage of the total training epochs):

We can observe that PARCO is robust and yields consistent improvements.

To clarify, the "Time per Epoch (s)" metric on the right y-axis of Figure 3b represents the wall-clock training time in seconds. This is a standard measure of computational throughput, indicating how long it takes to complete one full training epoch on the FFSP dataset. The figure illustrates that PARCO's parallel architecture allows it to process an entire epoch of training data significantly faster than the sequential MatNet baseline, demonstrating its superior training efficiency.

Q1: Learning stability and computational complexity

The learning stability and computational complexity with growing number of agents is one of the greatest strengths of PARCO. PARCO's design directly confronts the challenge of a large joint action space via:

• Factorization of joint action space: PARCO does not compute a probability distribution over the entire joint action space of size $N^M$. Instead, PARCO leverages the fact that all agents share the same action space, generating a joint logit space of dimension $N \times M$. In addition, our method generates this joint logit space in parallel (one forward pass) via our multiple-pointer mechanism enabling efficient scaling to multi-agent settings without combinatorial explosion.
• Coordination through communication layers: The attention-based coordination layer effectively helps to coordinate even a large (and as we show in the result table below also an unseen) number of agents
• Intelligently resolving decision conflicts (e.g., two agents selecting the same customer) using learned priorities

The effectiveness of these components is also demonstrated in Figure 3a, 3b, and 3c of the paper. While 3a and 3c show the effectiveness of our communication layer and conflict handler respectively, figure 3b demonstrates that PARCO requires fewer forward passed of the neural policy to construct a solution, when the number of agents increases, leading to much shorter training and inference times.

Q2: Is the agent embedding also used in the decoding process?

Yes, after the communication layer, which sends the agent embeddings as well as context information (like remaining workload) through a transformer layer, the resulting query vectors q are used in the decoding process in order to generate the score matrix $\mathbf{u} \in \mathbb{R}^{M \times N}$ (i.e. one score for each agent-node pair).

Q3: About the overestimation bias

Thank you for the insightful question. While priority is derived from the policy, our method does not introduce overestimation bias, due to the structure of the REINFORCE + POMO update and our deterministic fallback mechanism.

Gradient-Based Analysis:

In case of conflict (i.e., multiple agents selecting the same node), only the agent with the highest action probability $g_{\theta} (a_t^m | a_{<t}, \mathbf{h})$ is allowed to proceed; the others fall back to a deterministic "do-nothing" action (with $\log p_\theta (a_t^m) = 0$ and zero gradient). We apply REINFORCE with a POMO-style baseline. The policy gradient for solution $\tau_i$ is:

$$\nabla_\theta J(\theta) \propto \nabla_\theta \log \pi_\theta(\tau_i|x) \cdot (R(\tau_i) - \bar{R})$$

where $R$ is the return the $i$-th POMO rollout and $\bar{R}$ is the mean return across multiple POMO rollouts.

Case 1: Agent $m$ wins in a conflict and executes $a_t^m$ in solution $\tau_i$:

• If $R_i > \bar{R}$: the update is positive → the action is reinforced and the chances of agent $m$ winning increase.
• If $R_i < \bar{R}$: the update is negative → the action is penalized and the chances of agent $m$ winning decrease. Thus, high-priority agents are not blindly reinforced; they are only updated in proportion to actual performance.

Case 2: The agent looses and is forced into a deterministic fallback action with probability 1:

• $\log \pi(\text{fallback}) = 0$
• $\nabla_\theta \log \pi = 0$

Hence, the gradient update is zero, and no reinforcement occurs, even if the original action had high $\pi$. Therefore, no overestimation bias is introduced. The priority mechanism acts only as a selection filter and the gradient remains aligned with actual performance outcomes.

Q4: Is PARCO used in an untrained number of agents?

Yes! We also tested PARCO in not only a new number of agents $M$ , but also new number of nodes $N$. This is the result of Table 2.

Moreover, we have further tested PARCO for even larger scales in both number of nodes and number of agents during the rebuttal. We generated 16 new instances for $N=5000$ nodes and 3 different values of $M$ agents total of 48 instances of OMDCPDP and evaluate OR-Tools with 1 hour of runtime and greedy performance for HAM and PARCO. The results are in the table below:

As we can see from the results, PARCO excels at generalization in extremely large scales with $50\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools at a $10,000\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications.

We sincerely thank you for your time and for highlighting the strengths of our paper. We appreciate the insightful feedback, which has helped us further improve our work. Below, we address each of your concerns and questions.

W1 & W2: Comparison with Decentralized and Graph-Based Communication Methods

Thank you for this valuable suggestion. We agree that comparing PARCO with decentralized methods and alternative communication models like Graph Neural Networks (GNNs) provides a more complete picture. During the rebuttal period, we conducted new experiments on the min-max traveling salesman problem (mTSP), benchmarking PARCO against notable decentralized methods like GNN-DisPN [1], DAN [2], and GNN-based communication models like ScheduleNet [3].

The results, shown in the table below (where g. stands for greedy and s. for sampling), demonstrate that PARCO consistently outperforms these methods in solution quality.

Centralized training with parallel decoding, as used in PARCO, offers distinct advantages by enabling global coordination and highly efficient solution construction. For example, GNN-based communication in models like ScheduleNet incurs significantly higher computational overhead, making our approach much faster.

W3: Clarification on Figure 2 and Dynamic Node Features

Thank you for pointing out this inconsistency. Figure 2 was simplified for visual clarity, but your interpretation of Equation (5) is correct. Dynamic node features ($\xi_t$) are indeed a part of our model. While these features are not used in the routing problems (where $\xi_t$ is zero), they are critical for the Flexible Flow Shop Problem (FFSP). In FFSP, $\xi_t$ encodes the time a job becomes available at a new stage, which is essential dynamic information for the machines (agents) to make correct scheduling decisions. We will update Figure 2 in the final version to fully reflect Equation (5).

Q1: Scalability

This is a valid concern. While self-attention complexity is quadratic with the number of agents, our experiments show that PARCO's performance remains robust and stable even at extreme scales. During the rebuttal, we stress-tested PARCO on the OMDCPDP with up to 5000 nodes and 1000 agents, 50 times larger than the training distributions.

As we can see from the results, PARCO excels at generalization in extremely large scales with $50\times$ the number of nodes and agents seen during training and up to a whopping $1,000$ agents. Thanks to its massively parallel structure, PARCO can solve such instances in a fraction of a second, with better results than OR-Tools at a $10,000\times$ speedup. This makes our PARCO ideal for real-world, real-time, large-scale complex applications.

Q2: Two Stages of Communication

This is an excellent observation. You are correct that one can view the model as having two stages of "communication":

• Static Communication (Encoder): The encoder processes the initial agent and node features, establishing a baseline understanding of the problem structure and static agent-node relationships.
• Dynamic Communication (Decoder): The Communication Layers provide a second, crucial stage of coordination that happens at every step of the decoding process. This allows agents to react to the dynamically changing state of the problem and each other's actions.

Our ablation study in Figure 3a, which removes the explicit Communication Layers but keeps the same encoder, confirms that this second stage of dynamic collaboration is essential for achieving high-quality solutions.

---

References

[1] Hu, Yujiao, Yuan Yao, and Wee Sun Lee. "A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs." Knowledge-Based Systems 204 (2020): 106244.

[2] Cao, Yuhong, Zhanhong Sun, and Guillaume Sartoretti. "Dan: Decentralized attention-based neural network for the minmax multiple traveling salesman problem." International Symposium on Distributed Autonomous Robotic Systems. Cham: Springer Nature Switzerland, 2022.

[3] Park, Junyoung, Changhyun Kwon, and Jinkyoo Park. "Learn to Solve the Min-Max Multiple Traveling Salesmen Problem with Reinforcement Learning." AAMAS. Vol. 22. 2023.

We sincerely thank you for your time and for providing a positive and encouraging review, acknowledging the design choices of our PARCO method, our empirical results, as well as the clear writing. We will answer your concern below:

W1: About guarantee on optimality

Regarding the lack of an optimality guarantee, we agree with the reviewer's observation. This is a common and accepted trade-off for heuristic and learning-based methods designed to tackle NP-hard problems. Our primary objective is to produce high-quality solutions in the shortest possible time, which is a critical requirement for many real-world applications where exact methods are computationally infeasible. In this sense, PARCO can produce a high-quality solution at a fraction of the cost of traditional methods while outperforming all learning-based ones. This is validated across numerous benchmarks and ablation studies in the paper. While PARCO does not offer an optimality guarantee, it successfully provides a state-of-the-art, scalable, and efficient solver for practical use.