- 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
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=7 | N=1000,M=70 | |||
|---|---|---|---|---|
| Metric | Obj. | Gap | Obj. | Gap |
| DiffPtr | 4.57 | 2.66% | 4.16 | 0.00% |
| PARCO | 4.58 | 2.92% | 5.51 | 32.37% |
| None-Diffusion | 4.58 | 3.02% | 5.40 | 29.90% |
| None-Diffusion(with noisy) | 4.59 | 3.18% | 5.39 | 29.48% |
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 , we practically approximate the expected distribution of multimodal expert actions through repeated sampling of 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 time | GPU Memory | |
|---|---|---|
| DiffPtr | 21.2h | 12.59GB |
| DiffPtr (explicit consistency training) | 28.3h | 20.67GB |
Table R5. In-distribution Performance Comparison Between DiffPtr and DiffPtr with Explicit Consistency Training.
| In-distribution | M=3,N=60 | M=5,N=60 | M=7,N=60 | M=3,N=100 | M=5,N=100 | M=7,N=100 |
|---|---|---|---|---|---|---|
| DiffPtr | 6.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-distribution | M=30,N=500 | M=50,N=500 | M=70,N=500 | M=30,N=1000 | M=50,N=1000 | M=70,N=1000 |
|---|---|---|---|---|---|---|
| DiffPtr | 4.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.
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.
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}, defined as follows: APD=B(B−1)2∑i<jD(Si,Sj) AMD=B1∑imini=jD(Si,Sj) Here, D(Si,Sj)∈[0,1] denotes the Jaccard distance between the directed graphs corresponding to solutions Si and Sj, 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).
Table R2. Diversity and solution quality for DiffPtr and PARCO on HCVRP (Out-of-distribution).
[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.