acceptodds
Under review as a conference paper at ICLR 2027

DiffPtr: Diffusion Pointer Networks for Multi-Agent Combinatorial Optimization

Abstract

Combinatorial Optimization problems in Multi-Agent systems are particularly challenging due to the combination of NP-hardness, agent coordination, and exponentially large joint action space. Existing Constructive (or AutoRegressive) methods such as PARCO typically rely on pointers to deterministically model the joint action distribution, from which multiple trajectories are sampled to explore the solution space. Although these methods have achieved significant progress, they still suffer from issues such as limited generation diversity and poor generalization capability. In this work, we propose the Diffusion Pointer Networks (DiffPtr), which incorporates diffusion models into the pointer generation process, to capture the diverse multimodal distributions over multi-agent joint actions and trajectories. DiffPtr introduces an independence assumption between arbitrary agent–action pairs and defines a discrete diffusion process based on binary action variables, consisting of a forward noising process and a state-conditioned reverse denoising process. By iteratively generating diffusion pointers under different noise levels, DiffPtr progressively refines the joint actions, thereby enhancing inter-agent coordination, promoting solution diversity, and improving robustness under out-of-distribution generalization. Experimental results show that DiffPtr outperforms existing methods in both solution quality and generalization, highlighting the potential of diffusion-based policies for complex Multi-agent Combinatorial Optimization problems.

Primary area:
optimization
Keywords:
Multi-Agent Combinatorial Optimization, Diffusion Models, Pointer Networks, Solution Diversity, Out-of-Distribution Generalization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_vR9iOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes DiffPtr, a diffusion-based pointer network for multi-agent combinatorial optimization. DiffPtr formulates joint action generation as a state-conditioned discrete denoising process and is trained via imitation learning using trajectories generated by existing solvers. The method is evaluated on HCVRP and OMDCPDP under both in-distribution and larger-scale zero-shot generalization settings.

Critical strengths

1.DiffPtr introduces a meaningful modeling perspective by incorporating diffusion into the pointer-generation process of a constructive multi-agent solver, enabling state-conditioned generation of joint actions in variable-size action spaces.

2.The experiments provide solid evidence for the large-scale generalization benefit, and the comparable-budget and teacher-quality studies help rule out increased computation or stronger demonstrations as simple explanations.

Critical weaknesses

1.The mechanistic claims are stronger than the current evidence. The paper attributes the gains to improved multimodal modeling, diversity, and coordination, while the experiments mainly establish better solution quality and generalization rather than directly isolating these mechanisms.

2.The justification of the consistency-based inference is not fully clear: the training procedure does not explicitly impose cross-timestep consistency, while Eq. (14) presents such consistency as a property. The paper should clarify the status and scope of this claim.

Questions for authors

1.Could the authors provide more direct evidence or clarification for the claim that DiffPtr’s gains arise from better modeling of multimodal joint-action distributions, rather than more generally from noise-conditioned training or architectural differences?

2.Could the authors clarify how the training procedure establishes the cross-timestep consistency stated in Eq. (14), given that each training sample uses only one diffusion timestep and no explicit consistency loss is imposed?

6 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We appreciate the reviewer’s valuable feedback and constructive suggestions. We have carefully revised the manuscript in response to all the comments and provided a point-by-point response below. The updated manuscript has been uploaded, with all revisions highlighted in blue for easy identification.


W1 and Q1

Following your suggestion, we conducted additional experiments to further demonstrate the multimodal modeling capability of DiffPtr.

We provide a visual comparison of the top-5 solution sets generated by PARCO and DiffPtr in Appendix D.5 of the revised manuscript. As shown in Figs. 6 and 7, DiffPtr captures a noticeably wider variety of solution patterns than PARCO. Specifically, for a randomly selected HCVRP instance, all five top-5 solutions generated by PARCO are identical, while for OMDCPDP, three of the top-5 solutions are identical. In contrast, DiffPtr produces more diverse solution patterns for both instances, providing qualitative evidence of its stronger capability to capture multiple modes in the solution space.

Furthermore, we quantitatively evaluate the diversity of the solution sets generated by DiffPtr and PARCO, with the results reported in Tables R1 and R2. Specifically, we adopt two metrics, Average Pairwise Distance (APD) and Average Minimum Distance (AMD), to measure the diversity of a sampled solution set {S1,S2,⋯ ,SB}\{S_1,S_2,\cdots,S_B\}, defined as follows: APD=2B(B−1)∑i<jD(Si,Sj)APD = \frac{2}{B(B-1)} \sum_{i<j} D(S_i,S_j) AMD=1B∑imini≠jD(Si,Sj)AMD = \frac{1}{B}\sum_{i} min_{i\neq j}D(S_i,S_j) Here, D(Si,Sj)∈[0,1]D(S_i,S_j)\in[0,1] denotes the Jaccard distance between the directed graphs corresponding to solutions SiS_i and SjS_j, which is commonly used to measure solution dissimilarity in VRPs [1,2]. APD and AMD characterize the overall dispersion and local diversity of a solution set, respectively, with higher values indicating greater diversity.

As shown in Table R1, DiffPtr achieves substantially higher APD and AMD values than PARCO in in-distribution (ID) settings, confirming its ability to generate more diverse solutions. More notably, we further evaluate both methods on large-scale OOD instances with 1,000 nodes, as reported in Table R2. Interestingly, the diversity metrics of both methods approach saturation, with PARCO even achieving slightly higher values. However, this increased diversity does not translate into better solution quality for PARCO, which instead suffers from substantial performance degradation. In contrast, DiffPtr maintains considerably better solution quality despite exhibiting similarly high diversity. This suggests that DiffPtr can better preserve solution quality while generating diverse solutions under distribution shifts, demonstrating more robust multimodal solution generation.

Table R1. Diversity and solution quality for DiffPtr and PARCO on HCVRP (In-distribution).

In-distributionM=3,N=60M=5,N=60M=7,N=60
MetricsObj.APDAMDObj.APDAMDcostAPDAMD
DiffPtr6.77210.81460.23864.13470.88100.32833.02150.89710.4141
PARCO6.82030.70360.14484.17380.73970.19093.05790.76280.2490

Table R2. Diversity and solution quality for DiffPtr and PARCO on HCVRP (Out-of-distribution).

out-of-distributionM=30,N=1000M=50,N=1000M=70,N=1000
MetricsObj.APDAMDObj.APDAMDObj.APDAMD
DiffPtr9.14990.98830.98025.61410.98910.98104.16010.98900.9809
PARCO10.48850.99450.98986.85920.99480.99015.50500.99550.9910

[1] Jastrzab T, Myller M, Tulczyjew L, et al. Standardized validation of vehicle routing algorithms: T. Jastrzab et al[J]. Applied Intelligence, 2024, 54(2): 1335-1364.

[2] Li H, Zhang M, Zeng C. Circular Jaccard distance based multi-solution optimization for traveling salesman problems[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4458-4480.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 2)

Regarding the effects of ”noise-conditioned training“ and ”architectural differences“, we would like to clarify that we have already conducted an architectural ablation in the left panel of Fig.4. Specifically, the Non-Diffusion variant retains exactly the same network architecture and IL training paradigm as DiffPtr, with the only difference being the removal of the diffusion process.

Furthermore, to investigate whether the performance gains could be attributed simply to noise injection during training, we conducted an additional experiment. Specifically, while retaining the same network architecture and IL training paradigm, we removed the diffusion process and instead injected Gaussian noise into the action and agent embeddings during training. The results are reported in Table R3.

As shown in Table R3, Gaussian noise injection brings only marginal improvements over the Non-Diffusion baseline on OOD instances, while slightly degrading ID performance. More importantly, this variant remains substantially inferior to DiffPtr on OOD instances (5.39 vs. 4.16 in objective value). These results suggest that the performance gains of DiffPtr cannot be simply attributed to architectural differences or noise injection, but rather benefit from its diffusion-based generative modeling mechanism.

Table R3. Ablation study on architectural differences and noise-conditioned training.

N=100,M=7N=1000,M=70
MetricObj.GapObj.Gap
DiffPtr4.572.66%4.160.00%
PARCO4.582.92%5.5132.37%
None-Diffusion4.583.02%5.4029.90%
None-Diffusion(with noisy)4.593.18%5.3929.48%
AuthorsOpenReview ↗

Rebuttal by Authors (Part 3)

W2 and Q2

We would like to clarify that Eq.(14) represents an ideal optimization objective derived from Optimization Consistency [1]. However, since expert-generated trajectories follow a distribution rather than correspond to a fixed A0A^0, we practically approximate the expected distribution of multimodal expert actions through repeated sampling of A0A^0 and training across different diffusion steps. This approach also implicitly achieves consistency alignment across different diffusion steps. We revise the relevant wording (Appendix A.2, P14-15) in the manuscript to avoid potential misunderstandings.

In fact, we opted for implicit rather than explicit consistency training to balance training costs and performance gains. Tables R1–R3 provide a comprehensive comparison on HCVRP between DiffPtr and its variant with explicit consistency training, which follows the original paper by explicitly sampling different diffusion steps and introducing an additional consistency loss.

As shown in Table R4, explicit consistency training increases the training time from 21.2h to 28.3h (33.5%) and GPU memory consumption from 12.59GB to 20.67GB (64.2%). However, as shown in Tables R5 and R6, the resulting performance differences are marginal. For ID, the two approaches achieve nearly identical results across all settings. For OOD, explicit consistency training provides slight improvements in some settings while leading to marginal performance degradation in others. Overall, these results suggest that the additional computational costs of explicit consistency training do not translate into consistent performance gains. In contrast, implicit consistency training achieves comparable ID and OOD performance with substantially lower training costs, making it a more favorable trade-off in our setting.

Table R4. Training Cost Comparison Between DiffPtr and DiffPtr with Explicit Consistency Training.

Training timeGPU Memory
DiffPtr21.2h12.59GB
DiffPtr (explicit consistency training)28.3h20.67GB

Table R5. In-distribution Performance Comparison Between DiffPtr and DiffPtr with Explicit Consistency Training.

In-distributionM=3,N=60M=5,N=60M=7,N=60M=3,N=100M=5,N=100M=7,N=100
DiffPtr6.77 (3.08%)4.13 (3.35%)3.02 (3.82%)10.59 (2.88%)6.34 (2.74%)4.57 (2.66%)
DiffPtr(explicit consistency training)6.77 (3.07%)4.13 (3.36%)3.02 (3.80%)10.59 (2.89%)6.34 (2.74%)4.57 (2.71%)

Table R6. Out-of-distribution Performance Comparison Between DiffPtr and DiffPtr with Explicit Consistency Training.

Out-of-distributionM=30,N=500M=50,N=500M=70,N=500M=30,N=1000M=50,N=1000M=70,N=1000
DiffPtr4.85 (0.00%)3.23 (0.00%)2.57 (0.00%)9.15 (0.00%)5.61 (0.00%)4.16 (0.00%)
DiffPtr(explicit consistency training)4.86 (0.04%)3.19 (-0.98%)2.54 (-0.91%)9.17 (0.20%)5.61 (-0.03%)4.13 (-0.76%)

[1] Li Y, Guo J, Wang R, et al. Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization[J]. Advances in Neural Information Processing Systems, 2024, 37: 30179-30206.


We sincerely appreciate the reviewer’s time and effort. We would be happy to address any further questions or concerns the reviewer may have.

Reviewer_GGhUOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces DiffPtr, a diffusion-based framework for multi-agent combinatorial optimization. The proposed method employs a diffusion decoder consisting of a noisy action extractor, a communication layer, and a pointer output head to generate joint actions through a denoising process. The method is evaluated on Heterogeneous Capacitated Vehicle Routing Problem and the Open Multi-Depot Capacitated Pickup and Delivery Problem.

Critical strengths
  1. The paper is generally well-organized and easy to follow.

  2. The paper provides relatively comprehensive experimental evaluations across two multi-agent combinatorial optimization tasks, including comparisons with various existing methods under both in-distribution and out-of-distribution settings.

Critical weaknesses

1. Limited methodological novelty.

The methodological novelty of this paper is rather limited. The proposed method mainly incorporates an existing discrete diffusion model into multi-agent combinatorial optimization framework. In the decoder part, the paper introduces several neural network layers like noisy action extractor, self-attention-based communication layer. But most components follow standard diffusion formulations and conventional neural network architectures. The paper does not introduce substantial methodological innovations beyond combining these existing techniques.

2. Unclear motivation for the MDP formulation.

The problem formulation is unclear and misleading. Section 3.1 introduces the MDP formulation, but the proposed method is trained entirely through imitation learning. In particular, the reward function RR introduced in the problem formulation does not appear to be used in the subsequent methodology or training objective. It is therefore unclear what role the MDP formulation plays in the proposed approach beyond describing the sequential decision-making process. The authors should better justify the necessity of this formulation and clarify its relationship to the proposed diffusion-based IL framework. Also, in Appendix B.1, the RiR_i is used again to represent the route rather than reward.

3. Redundant methodology presentation.

The overall presentation of the methodology is unnecessarily lengthy and redundant. A substantial portion of the methodology section is devoted to explaining standard diffusion processes and conventional neural network components. In particular, many details regarding the encoder-decoder architecture and standard attention mechanisms could be briefly summarized or moved to the appendix. This would allow the authors to focus more on the actual methodological contributions and their motivations.

4. Unconvincing experimental analysis.

Although the experimental comparisons are relatively comprehensive, the analysis is not sufficiently convincing, particularly regarding the substantial improvements in out-of-distribution (OOD) generalization. The proposed method is trained entirely through imitation learning using trajectories generated by PARCO, an RL-based teacher model. However, DiffPtr significantly outperforms its teacher under OOD settings despite relying on demonstrations from the same model. Since imitation learning can be sensitive to distribution shifts and may suffer from compounding errors when encountering unseen states, this result deserves further investigation. Moreover, several existing VLM/VLA-based approaches employing diffusion policies still face challenges with OOD generalization [1],[2], while various RL-based methods have specifically explored ways to address these limitations. In this context, it would be helpful for the authors to provide a more detailed explanation of why the proposed diffusion-based imitation learning framework achieves such substantial generalization improvements.

[1] Adapting by Analogy: OOD Generalization of Visuomotor Policies via Functional Correspondence Gupta, Admoni, and Bajcsy — CoRL 2025

[2] Dreaming the Unseen: World Model-regularized Diffusion Policy for Out-of-Distribution Robustness Hu et al. — arXiv 2026

5. Minor Comments

Several abbreviations are repeatedly introduced throughout the paper. For example, "Imitation Learning (IL)" is defined multiple times in Sections 1, 3.4, and 4.2.

Some definitions are unnecessarily repeated. For instance, the joint action space is introduced in Section 3.1 and then described again in Section 3.2. These explanations could be consolidated to improve readability and conciseness.

  • Section 1: "NP-hardess" should be "NP-hardness".
  • Section 3.2: "tow optional classical approaches" should be "two optional classical approaches".
Questions for authors

Binary action representation and class imbalance.

The proposed method represents joint actions using a binary matrix A0∈{0,1}M×NA^0 \in \{0,1\}^{M \times N}, where each agent typically selects only one action. Consequently, the positive labels are considerably outnumbered by negative labels, particularly as the action space grows. Could the authors clarify whether any class balancing or weighting strategies are applied during training?

Diffusion-based modeling and methodological novelty.

Could the authors further clarify the specific advantages of introducing diffusion into the multi-agent pointer network? Since conventional stochastic pointer networks can also generate diverse actions through sampling, what additional modeling capabilities does the proposed diffusion framework provide? In particular, is there direct evidence that DiffPtr captures multimodal joint-action distributions more effectively than conventional pointer-based policies?

Explanation of OOD generalization improvements.

Could the authors futher clarify why DiffPtr performs much better in OOD settings even only with IL?

9 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We are grateful to the reviewer for the thoughtful comments and helpful suggestions. We have carefully considered each point and revised the manuscript accordingly. A detailed point-by-point response is provided below, and the revised manuscript has been uploaded with all modifications highlighted in blue.


Q1

We acknowledge that the binary action representation leads to a significant class imbalance, with negative labels substantially outnumbering positive labels. In our implementation, no explicit class-balancing or weighting strategies are applied, and we directly optimize the standard discrete diffusion objective. We agree that the potential impact of this imbalance deserves further investigation and will explore effective balancing strategies in future work.

Q2 and W1

We would like to clarify that DiffPtr is proposed to address the limitations of existing methods in modeling multimodal solution distributions, particularly in terms of solution diversity and stability.

First, our approach differs fundamentally from existing pointer networks such as PARCO in how solution diversity is modeled. Although methods like PARCO can also generate different solutions through action sampling, their reliance on a fixed softmax pointer distribution limits their expressive capacity, potentially resulting in insufficient solution diversity and a unimodal solution distribution. In contrast, DiffPtr can generate different pointer distributions through stochastic denoising trajectories, offering greater expressive capacity for modeling multimodal solution distributions. To facilitate understanding, Fig. 5 in Appendix D.5 illustrates the conceptual difference between unimodal and multimodal solution distributions.

Second, to the best of our knowledge, this is the first attempt to explore diffusion-based policies in multi-agent combinatorial optimization (multi-agent CO). Unlike existing diffusion policy methods, which typically operate in fixed and continuous action spaces, multi-agent CO involves variable-sized, discrete joint action spaces with problem size (e.g. the customer number). Moreover, the multimodal nature of multi-agent CO solutions makes it particularly important to capture diverse joint action patterns. To address these challenges, we redesign the diffusion formulation over independent binary action variables and develop a corresponding conditional denoising process, ensuring that the diffusion process does not depend on the problem size. We further propose Diffusion decoder for denoising to accommodate these formulations, where the NAE component, an attention mechanism incorporating a soft negative bias, is designed to extract information from noisy actions.

To further validate the multimodal modeling capability of DiffPtr, we provide a visual comparison of the top-5 solution sets generated by PARCO and DiffPtr in Appendix D.5 of the revised manuscript. As shown in Fig. 6 and Fig.7 ( Appendix D.5, P22,P23 ) , DiffPtr captures a noticeably wider variety of solution patterns than PARCO. Specifically, for a randomly selected HCVRP instance, all five top-5 solutions generated by PARCO are identical, while for OMDCPDP, three of the top-5 solutions are identical. In contrast, DiffPtr produces more diverse solution patterns for both instances, providing qualitative evidence of its stronger capability to capture multiple modes in the solution space.

In addition, we quantitatively evaluate the diversity of the solution sets generated by DiffPtr and PARCO, with the results reported in Tables R1 and R2. Specifically, we adopt two metrics, Average Pairwise Distance (APD) and Average Minimum Distance (AMD), to measure the diversity of a sampled solution set {S1,S2,⋯ ,SB}\{S_1,S_2,\cdots,S_B\}, defined as follows: APD=2B(B−1)∑i<jD(Si,Sj)APD = \frac{2}{B(B-1)} \sum_{i<j} D(S_i,S_j) AMD=1B∑imini≠jD(Si,Sj)AMD = \frac{1}{B}\sum_{i} min_{i\neq j}D(S_i,S_j)

Here, D(Si,Sj)∈[0,1]D(S_i,S_j)\in[0,1] denotes the Jaccard distance between the directed graphs corresponding to solutions SiS_i and SjS_j, which is commonly used to measure solution dissimilarity in VRPs [1,2]. APD and AMD characterize the overall dispersion and local diversity of a solution set, respectively, with higher values indicating greater diversity.

[1] Jastrzab T, Myller M, Tulczyjew L, et al. Standardized validation of vehicle routing algorithms: T. Jastrzab et al[J]. Applied Intelligence, 2024, 54(2): 1335-1364.

[2] Li H, Zhang M, Zeng C. Circular Jaccard distance based multi-solution optimization for traveling salesman problems[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4458-4480.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 2)

As shown in Table R1, DiffPtr achieves substantially higher APD and AMD values than PARCO in in-distribution (ID) settings, confirming its ability to generate more diverse solutions. More notably, we further evaluate both methods on large-scale OOD instances with 1,000 nodes, as reported in Table R2. Interestingly, the diversity metrics of both methods approach saturation, with PARCO even achieving slightly higher values. However, this increased diversity does not translate into better solution quality for PARCO, which instead suffers from substantial performance degradation. In contrast, DiffPtr maintains considerably better solution quality despite exhibiting similarly high diversity. This suggests that DiffPtr can better preserve solution quality while generating diverse solutions under distribution shifts, demonstrating more robust multimodal solution generation.

Table R1. Diversity and solution quality comparison between DiffPtr and PARCO on HCVRP (In-distribution).

In-distributionM=3,N=60M=5,N=60M=7,N=60
MetricsObj.APDAMDObj.APDAMDcostAPDAMD
DiffPtr6.77210.81460.23864.13470.88100.32833.02150.89710.4141
PARCO6.82030.70360.14484.17380.73970.19093.05790.76280.2490

Table R2. Diversity and solution quality comparison between DiffPtr and PARCO on HCVRP (Out-of-distribution).

out-of-distributionM=30,N=1000M=50,N=1000M=70,N=1000
MetricsObj.APDAMDObj.APDAMDObj.APDAMD
DiffPtr9.14990.98830.98025.61410.98910.98104.16010.98900.9809
PARCO10.48850.99450.98986.85920.99480.99015.50500.99550.9910
AuthorsOpenReview ↗

Rebuttal by Authors (Part 3)

Q3 and W4

Following your suggestion, we have conducted a more comprehensive analysis of the generalization capability of DiffPtr and incorporated the corresponding discussions into Appendix D.6 of the revised manuscript.

First, we would like to clarify that the improved generalization of DiffPtr does not originate from imitation learning (IL) itself, but rather from its diffusion-based pointer generation mechanism. This is supported by the ablation study in Fig. 4 of our manuscript. Specifically, the Non-diffusion variant, which employs the same network architecture but is trained via IL without the diffusion denoising process, fails to exhibit the generalization capability of DiffPtr and instead inherits the distribution shift issue observed in PARCO. Notably, its performance under multiple sampling (5.40) is even worse than that of PARCO's single greedy decoding (4.44). This comparison suggests that IL alone is insufficient to account for the generalization improvement, highlighting the importance of the diffusion-based generation process.

Regarding the two RL-based generalization methods you mentioned[1,2], we would like to point out an important distinction between their target domains and multi-agent CO. Existing RL-based methods in domains such as robotic control primarily address generalization across different states, while typically operating in fixed-dimensional continuous action spaces. In contrast, multi-agent CO involves discrete joint action spaces whose dimensions and structures vary with the problem scale. Therefore, effective generalization in our setting requires handling variations in both states and action spaces.

We believe that the generalization improvement of DiffPtr over RL-based PARCO can be attributed to two complementary aspects:

  • First, although PARCO is trained based on RL, it learns a direct mapping from the current state ss (or latent representations UU and VV ) to a deterministic pointer distribution PP. Such direct parameterization can be sensitive to representation shifts when the problem scale increases, because changes in the latent state distribution may directly propagate to the generated pointer distribution. In contrast, DiffPtr models pointer generation as a conditional denoising process, where the final pointer distribution is derived from noisy states via denoising. This design enables a more robust generation pathway and reduces the dependency on an exact state-to-pointer mapping, which helps alleviate the distribution shift encountered in large-scale OOD scenarios.

  • Second, PARCO generates solutions via sampling actions from a fix softmax pointer , which may suffer from significant distribution shift as the action space changes (see Fig.4). On the contrary, DiffPtr shifts the random part to the denoising process to generate different pointers P0P^0, with each P0P^0 corresponding to a specific joint action. This action generation method may be more stable in a varying action space.

[1] Adapting by Analogy: OOD Generalization of Visuomotor Policies via Functional Correspondence Gupta, Admoni, and Bajcsy

[2] Dreaming the Unseen: World Model-regularized Diffusion Policy for Out-of-Distribution Robustness Hu et al.

W2

We thank the reviewer for the careful comments. We use the MDP framework to formally describe the external sequential decision-making process, where the state ss, action aa, and transition function T\mathcal{T} are used to condition the internal denoising process, define the multi-agent joint action space, and characterize the progression of the problem, respectively.

Actually, MDPs are also commonly used to formulate imitation learning problems, as in [1] and [2]. In our setting, although the reward function RR does not directly appear in the IL objective, reward maximization is implicitly pursued by training the policy to imitate high-quality expert behaviors. We sincerely thank the reviewer for pointing out this potential confusion. In the revised manuscript, we have further clarified the relationship between the diffusion policy, imitation learning, and the MDP in Section 3.1. We have also addressed the symbol reuse issue in Appendix B.1 by replacing RR with Γ\Gamma.

[1] Rajaraman N, Yang L, Jiao J, et al. Toward the fundamental limits of imitation learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 2914-2924.

[2] Kim K, Gu Y, Song J, et al. Domain adaptive imitation learning[C]//International Conference on Machine Learning. PMLR, 2020: 5286-5295.

Reviewer_P4McOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

DiffPtr uses a discrete diffusion policy within an autoregressive multi-agent construction process. Joint actions are represented as binary agent–node matrices. A state-conditioned decoder combines noisy-action extraction, agent communication, masking, and a pointer head; argmax decoding and conflict handling produce actions. The model is trained by imitation of PARCO trajectories and uses few-step inference. Experiments on HCVRP and OMDCPDP evaluate in-distribution solution quality, scale generalization, decoder components, inference budgets, and teacher-data choices.

Critical strengths
  1. State-conditioned diffusion at each constructive decision is a useful design for multi-agent problems with changing constraints. The HCVRP scale-generalization improvement is meaningful: at N=1000 and M=70, DiffPtr obtains 4.16 versus 5.51 for PARCO sampling and 4.37 for 2D-Ptr (Table 1, p. 8). Figure 4 (p. 9) also shows an improvement over PARCO greedy, so the benefit is not solely a comparison against a weak sampling configuration.

  2. The ablations address several plausible alternative explanations. There is a non-diffusion imitation-learning comparison (Section 4.2, pp. 8–9), a comparable-time HCVRP experiment (Appendix D.1, pp. 18–19), and teacher quantity/quality studies (Table 5, p. 19). In particular, Table 4 (p. 19) compares objective/time of 4.16/10.41 seconds for DiffPtr with 5.29/12.89 seconds for PARCO using 20 times as many samples. Decoder-removal and training-cost comparisons are also provided (Tables 3, 6–7, pp. 9, 20). These strengthen the practical case beyond equal-sample-count comparisons.

Critical weaknesses
  1. The consistency interpretation should distinguish an optimization target from an achieved probabilistic identity. Section 3.4 gives random-timestep cross-entropy training (p. 7); Appendix A.2 explicitly says paired timesteps are not sampled within one training step and motivates implicit alignment from repeated training (pp. 13–14). Algorithm 1 already specifies the denoise/re-noise sampler (p. 14), and Figure 4 compares it with DDIM (p. 9); these are not missing. My narrower concern is Eq. (14)'s equality to a Dirac distribution. Where the expert policy is multimodal for a fixed state and terminal noise is independent of the clean action, cross-entropy's population optimum is a conditional posterior, or its elementwise marginals under the stated factorization, rather than every example's particular clean-action point mass. An ideal per-example target need not be an attained identity or a proof of pathwise consistency. This challenges the explanation, not the existence or measured effectiveness of the sampler. Separately, direct algebra on the flip matrix in Section 3.2 (p. 4) gives a residual-bias factor of product_t(1−2β_t), not product_t(1−β_t). The latter alone is not sufficient for uniform mixing; I have not established that the implemented cosine schedule fails to mix.

  2. The empirical mechanism claims go beyond the directly reported measurements. Section 4.2 already has a same-data, same-training-settings non-diffusion IL comparison, and the decoder communication ablations support a role for agent interaction (pp. 8–9, 20). I do not claim these controls are absent. However, their objective values do not directly measure output diversity, and a deterministic pointer parameterization does not by itself imply a unimodal action distribution (the motivating claims are in Sections 1–2, pp. 2–3). Conversely, conditional factorization does not rule out marginal dependence through noise and communication. A narrower mechanism interpretation would be reasonable without additional diversity experiments. The remaining comparison uncertainty is specific: Appendix D.1's comparable-time study covers HCVRP, while the small OMDCPDP in-distribution difference of 42.96 versus 43.08 at N=100, M=20 (Table 2, p. 8) has no reported paired uncertainty. Appendix C.2.3 explicitly sets OOD inference to K=1 (p. 18), so that particular result supports stochastic diffusion-pointer prediction but cannot establish a benefit from multiple refinement steps. Figure 4 does already study inference-step sensitivity; this is a limit on attributing the K=1 result, not a claim that step ablations are missing.

Questions for authors
  1. Given the training explanation in Appendix A.2 and the existing sampler in Algorithm 1, does Eq. (14) denote an ideal per-example training target rather than an attained equality? Can the authors qualify the consistency interpretation for multimodal expert actions and correct the uniform-mixing condition for the stated flip matrix?

  2. Can the authors report paired objective differences/uncertainty and a quality–time comparison including both greedy and sampling PARCO for the key OMDCPDP settings? This would clarify whether the smaller gains are stable at matched effort.

  3. Beyond the existing IL, communication, and step-count ablations, is there a direct diversity statistic supporting the claimed increase in solution diversity? If not, can that claim be limited to the observed solution-quality gains, and can the K=1 OOD result be distinguished from evidence for multi-step refinement?

4 comments
AuthorsOpenReview ↗

Rebuttal by Authors

We sincerely thank the reviewer for the constructive and insightful comments, which have helped us improve the manuscript. We have carefully addressed each comment point by point and uploaded the revised manuscript. All changes in the revised manuscript are highlighted in blue for clarity.

W1 and Q1

Following your suggestion, we identify that the expression ∏t=1T(1−βt)≈0\prod_{t=1}^{T}(1 - \beta^t) \approx 0 is a typographical error caused by an oversight on our part. We correct it in the revised manuscript (P4, in blue) to ∏t=1T(1−2βt)≈0\prod_{t=1}^{T}(1 - 2\beta^t) \approx 0.

Furthermore, regarding the "uniform-mixing condition" and the "cosine noise schedule" you mention, our implementation follows the same approach as [1] and is based on the right expression, i.e., ∏t=1T(1−2βt)≈0\prod_{t=1}^{T}(1 - 2\beta^t) \approx 0. Therefore, the forward diffusion process can indeed achieve an approximately uniform distribution at the final diffusion step. The corresponding implementation can be found at DiffPtr/IL/models/diffusion_shedulers.py in our anonymized code repository.

For Eq. (14) and the “multimodal expert actions”, we would like to clarify that Eq.(14) represents an ideal optimization objective derived from Optimization Consistency [2]. However, since expert-generated trajectories follow a distribution rather than correspond to a fixed A0A^0, we practically approximate the expected distribution of multimodal expert actions through repeated sampling of A0A^0 and training across different diffusion steps. This approach also implicitly achieves consistency alignment across different diffusion steps. We revise the relevant wording (Appendix A.2, P14-15, in blue) in the manuscript to avoid potential misunderstandings.

In fact, we opted for implicit rather than explicit consistency training to balance training costs and performance gains. Tables R1–R3 provide a comprehensive comparison on HCVRP between DiffPtr and its variant with explicit consistency training, which follows the original paper by explicitly sampling different diffusion steps and introducing an additional consistency loss.

As shown in Table R1, explicit consistency training increases the training time from 21.2h to 28.3h (33.5%) and GPU memory consumption from 12.59GB to 20.67GB (64.2%). However, as shown in Tables R2 and R3, the resulting performance differences are marginal. For ID, the two approaches achieve nearly identical results across all settings. For OOD, explicit consistency training provides slight improvements in some settings while leading to marginal performance degradation in others. Overall, these results suggest that the additional computational costs of explicit consistency training do not translate into consistent performance gains. In contrast, implicit consistency training achieves comparable ID and OOD performance with substantially lower training costs, making it a more favorable trade-off in our setting.

Table R1. Training Cost for DiffPtr and DiffPtr with Explicit Consistency Training.

Training timeGPU Memory
DiffPtr21.2h12.59GB
DiffPtr (explicit consistency training)28.3h20.67GB

Table R2. ID Performance for DiffPtr and DiffPtr with Explicit Consistency Training.

In-distributionM=3,N=60M=5,N=60M=7,N=60M=3,N=100M=5,N=100M=7,N=100
DiffPtr6.77 (3.08%)4.13 (3.35%)3.02 (3.82%)10.59 (2.88%)6.34 (2.74%)4.57 (2.66%)
DiffPtr(explicit consistency training)6.77 (3.07%)4.13 (3.36%)3.02 (3.80%)10.59 (2.89%)6.34 (2.74%)4.57 (2.71%)

Table R3. OOD Performance for DiffPtr and DiffPtr with Explicit Consistency Training.

Out-of-distributionM=30,N=500M=50,N=500M=70,N=500M=30,N=1000M=50,N=1000M=70,N=1000
DiffPtr4.85 (0.00%)3.23 (0.00%)2.57 (0.00%)9.15 (0.00%)5.61 (0.00%)4.16 (0.00%)
DiffPtr(explicit consistency training)4.86 (0.04%)3.19 (-0.98%)2.54 (-0.91%)9.17 (0.20%)5.61 (-0.03%)4.13 (-0.76%)

[1] Nichol A Q, Dhariwal P. Improved denoising diffusion probabilistic models[C]//International conference on machine learning. PmLR, 2021: 8162-8171.

[2] Li Y, Guo J, Wang R, et al. Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization[J]. Advances in Neural Information Processing Systems, 2024, 37: 30179-30206.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 2)

Q2

Following your suggestion, we conducted a quality–time comparison between DiffPtr and PARCO on OMDCPDP. The results are reported in Tables R4 and R5. Specifically, we increased the number of parallel samples generated by PARCO by 5×, such that PARCO incurred a longer inference time than DiffPtr. Even under this setting, DiffPtr consistently outperforms PARCO, with particularly pronounced improvements in out-of-distribution (OOD) scenarios, demonstrating its stronger solution generation capability and generalization ability.

Table R4. Performance under comparable inference times on OMDCPDP (In-distribution).

In-distributionN=50,M=5N=50,M=7N=50,M=10
MetricObj.GapTimeObj.GapTimeObj.GapTime
PARCO(s.1280 × 5)35.500.04%0.12s28.870.09%0.11s23.820.11%0.11s
DiffPtr(s.1280)35.480.00%0.07s28.840.00%0.08s23.790.00%0.08s

Table R5. Performance under comparable inference times on OMDCPDP (Out-of-distribution).

Out-of-distributionN=1000,M=100N=1000,M=150N=1000,M=200
MetricObj.GapTimeObj.GapTimeObj.GapTime
PARCO(s.1280 × 5)516.082.01%4.19s403.351.52%4.88s359.581.14%5.61s
DiffPtr(s.1280)505.910.00%3.97s397.310.00%4.85s355.540.00%5.17s

Furthermore, we report the paired objective differences between DiffPtr and both PARCO and PARCO (greedy) on OMDCPDP, as shown in Table R6. DiffPtr exhibits a more pronounced advantage in OOD scenarios, while its advantage is relatively smaller in ID scenarios. Nevertheless, it still achieves win rates of 70.4% and 100% against PARCO and PARCO (greedy), respectively, in ID scenarios, further demonstrating its consistent performance advantage.

Table R6. Paired objective comparison between DiffPtr and PARCO on OMDCPDP.

OMDCPDPIn-distribution(N=100,M=20)Out-of-distribution(N=1000,M=200)
Δ\Delta (DiffPtr vs. PARCO)−0.1194 ± 0.2322−5.3031 ± 1.4019
wining rate (DiffPtr vs. PARCO)70.4%100%
Δ\Delta (DiffPtr vs. PARCO greedy)-1.5068 ± 0.6056-4.5505 ± 1.9470
wining rate (DiffPtr vs. PARCO greedy)99.7%100%

Q3 and W2

Following your suggestion, we conducted additional experiments to report the diversity statistics of the generated solution sets. Specifically, we introduce two diversity metrics, Average Pairwise Distance (APD) and Average Minimum Distance (AMD), to quantify the diversity of a sampled solution set {S1,S2,⋯ ,SB}\{S_1,S_2,\cdots,S_B\}. They are defined as follows: APD=2B(B−1)∑i<jD(Si,Sj)APD = \frac{2}{B(B-1)} \sum_{i<j} D(S_i,S_j) AMD=1B∑imini≠jD(Si,Sj)AMD = \frac{1}{B}\sum_{i} min_{i\neq j}D(S_i,S_j) Here, D(Si,Sj)∈[0,1]D(S_i,S_j)\in[0,1] denotes the Jaccard distance between the directed graphs corresponding to solutions SiS_i and SjS_j, which is commonly used to quantify solution dissimilarity in VRPs[1,2]. APD and AMD characterize the overall dispersion and local diversity of a solution set, respectively. Higher values of both metrics indicate greater solution diversity.

AuthorsOpenReview ↗

Rebuttal by Authors (Part 3)

We evaluate the diversity of DiffPtr and PARCO on HCVRP, with the results reported in Tables R7 and R8. As shown in Table R7, DiffPtr achieves substantially higher diversity than PARCO in in-distribution (ID) settings, while also obtaining better solution quality across all tested configurations. More notably, in large-scale OOD settings with 1,000 nodes, as shown in Table R8, the diversity metrics of both methods approach saturation. However, this high diversity comes at the cost of a substantial degradation in solution quality for PARCO. In contrast, DiffPtr maintains considerably better solution quality despite achieving similarly high diversity. These results suggest that DiffPtr can generate diverse solutions while better preserving solution quality, demonstrating a more favorable balance between diversity and generation stability.

Table R7. Diversity and solution quality for DiffPtr and PARCO on HCVRP (In-distribution).

In-distributionM=3,N=60M=5,N=60M=7,N=60
MetricsObj.APDAMDObj.APDAMDcostAPDAMD
DiffPtr6.77210.81460.23864.13470.88100.32833.02150.89710.4141
PARCO6.82030.70360.14484.17380.73970.19093.05790.76280.2490

Table R8. Diversity and solution quality for DiffPtr and PARCO on HCVRP (Out-of-distribution).

out-of-distributionM=30,N=1000M=50,N=1000M=70,N=1000
MetricsObj.APDAMDObj.APDAMDObj.APDAMD
DiffPtr9.14990.98830.98025.61410.98910.98104.16010.98900.9809
PARCO10.48850.99450.98986.85920.99480.99015.50500.99550.9910

Furthermore, we provide a visual comparison of the top-5 solution sets generated by PARCO and DiffPtr in Appendix D.5 of the revised manuscript. As shown in Figs. 6 and 7, DiffPtr captures a noticeably wider variety of solution patterns than PARCO. Specifically, for a randomly selected HCVRP instance, all five top-5 solutions generated by PARCO are identical, while for OMDCPDP, three of the top-5 solutions are identical. In contrast, DiffPtr produces more diverse solution patterns for both instances, providing qualitative evidence of its stronger capability to capture multiple modes in the solution space. The corresponding visualizations and experimental results have been included in Appendix D.5 and highlighted in blue.

Regarding K=1K=1, this is in fact the best configuration for OOD settings. As illustrated in the right panel of Fig. 4, ID performance can benefit from an appropriate number of denoising steps, i.e., it initially improves as KK increases, but eventually deteriorates. Our analysis further attributes this phenomenon to exposure bias. Specifically, during training, the noisy input AtA^t is obtained by adding noise to the clean A0A^0, whereas during inference, A^t\hat{A}^t is predicted by DiffPtr and therefore deviates from the training distribution. This discrepancy introduces additional prediction errors in subsequent denoising steps, leading to error accumulation. In OOD settings, this effect becomes even more pronounced because the initial input state (s) already differs from the training distribution, which further exacerbates exposure bias and error accumulation, making it difficult to benefit from multi-step refinement. Nevertheless, even with K=1K=1, DiffPtr still achieves substantially better OOD performance than its teacher PARCO. For example, on HCVRP with N=1000N=1000 and M=70M=70, DiffPtr achieves costs of 4.07, 4.12, and 4.16 with K∈{1,2,3}K\in\{1,2,3\}, respectively, all substantially outperforming PARCO (5.51). We leave addressing exposure bias and the resulting error accumulation to future work.

[1] Jastrzab T, Myller M, Tulczyjew L, et al. Standardized validation of vehicle routing algorithms: T. Jastrzab et al[J]. Applied Intelligence, 2024, 54(2): 1335-1364.

[2] Li H, Zhang M, Zeng C. Circular Jaccard distance based multi-solution optimization for traveling salesman problems[J]. Mathematical Biosciences and Engineering, 2022, 19(5): 4458-4480.


We sincerely thank the reviewer for the constructive feedback and hope that our responses have clarified the raised concerns. We remain open to providing any further clarification if needed.

Dear Reviewer P4Mc,

We would like to sincerely thank you for your insightful comments and constructive suggestions throughout the review process. Your feedback has been very helpful in improving the quality and clarity of our work.

In our rebuttal, we carefully revisit the issues you raised and provide detailed explanations, additional experiments, and clarifications. We hope that our responses have addressed your concerns.

With the discussion period coming to a close, we would greatly appreciate any further feedback you may have regarding our responses. Should any concerns remain unresolved, we would be more than happy to offer additional explanations or answer further questions.

Thank you once again for your time, effort, and thoughtful evaluation of our work.

Best regards,

Submission 40564 Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.