- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces Edge-BFN (EBFN), a non-autoregressive neural combinatorial optimization solver that applies Bayesian Flow Networks (BFNs) to the Traveling Salesman Problem (TSP). EBFN represents each directed edge as a binary variable and maintains a probabilistic belief over whether the edge belongs to the target tour. A graph neural network predicts edge-selection probabilities at each flow step, and these probabilities are used to iteratively update the edge beliefs.
Critical strengths
S1: The proposed idea is novel and explores a relatively under-studied direction.
S2: Edge-BFN is clearly described overall.
Critical weaknesses
W1: The manuscript mainly compares against relatively old baselines and lacks comparisons with more recent state-of-the-art methods, such as [1–4]. Moreover, the comparison in Table 1 may not be fully fair, as EBFN employs a sampling-based decoding strategy, whereas the other diffusion-based baselines are evaluated using greedy decoding.
W2: The experimental evaluation is limited to relatively small-scale TSP instances and does not assess the scalability of the proposed method on much larger problems, such as TSP-10K.
W3: The experiments are limited to TSP, making it difficult to assess the generality of EBFN. Evaluations on other variants, such as the Asymmetric Traveling Salesman Problem [5], are needed.
[1] Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization. NeurIPS 2024.
[2] Generation as Search Operator for Test-Time Scaling of Diffusion-based Combinatorial Optimization. NeurIPS 2025.
[3] MaskCO: Masked Generation Drives Effective Representation Learning and Exploiting for Combinatorial Optimization. ICLR 2026.
[4] NExCO: Native Solution Expansion for Diffusion-based Combinatorial Optimization. ICLR 2026.
[5] UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP. ICLR 2025.
Questions for authors
see Weaknesses.
2 comments
I thank the authors for their response. However, after carefully considering their clarifications, I believe that Edge-BFN still has inherent design limitations, and my main concerns have not been adequately addressed. Therefore, I will maintain my original rating.
Response to Reviewer 1X6P
Weakness 1: The manuscript mainly compares against relatively old baselines and lacks comparisons with more recent state-of-the-art methods, such as [1–4]. Moreover, the comparison in Table 1 may not be fully fair, as EBFN employs a sampling-based decoding strategy, whereas the other diffusion-based baselines are evaluated using greedy decoding.
Response: We thank the reviewer. We agree that the current comparison is not fully fair: EBFN uses multi-candidate sampling while the diffusion baselines are evaluated with greedy decoding, and several recent methods are not included. A fair comparison should match the decoding budget (greedy vs sampling, number of candidates/forward passes), and we will adopt such an equal-budget comparison in future work. We also agree that recent methods such as Fast T2T, Generation-as-Search, MaskCO, and NExCO should be included, and we will add them in future experiments.
Weakness 2: The experimental evaluation is limited to relatively small-scale TSP instances and does not assess the scalability of the proposed method on much larger problems, such as TSP-10K.
Response: We thank the reviewer. We agree that the current evaluation stops at TSP-500 and does not assess TSP-10K. EBFN uses a dense N×N edge representation, whose memory and compute grow as O(N²); at N=10K this requires on the order of 10⁸ edge variables per instance, which is infeasible on a single GPU with the current implementation. We acknowledge this scalability limitation. Extending EBFN to large N would require a sparse or hierarchical edge representation (e.g., k-NN candidate graphs or multi-resolution edge sets), and we will explore this in future work.
Weakness 3: The experiments are limited to TSP, making it difficult to assess the generality of EBFN. Evaluations on other variants, such as the Asymmetric Traveling Salesman Problem [5], are needed.
Response: We thank the reviewer. We agree that the current evaluation is limited to symmetric Euclidean TSP. EBFN takes node coordinates as input and uses a coordinate-based GNN; ATSP instances are typically given as asymmetric cost matrices (often without coordinates), so the current architecture cannot directly consume them. Extending EBFN to ATSP would require a matrix encoder (e.g., a cost-matrix GNN in the spirit of UniCO [5]) and retraining on ATSP; we have not evaluated this setting and do not claim generality beyond TSP. We will explore ATSP and other problem variants in future work.