acceptodds
Under review as a conference paper at ICLR 2027

Bayesian Flow Networks for Combinatorial Optimization: An Edge-based Approach to the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is a fundamental combinatorial optimization problem, and non-autoregressive generative models have recently demonstrated strong solving capabilities on this problem. Diffusion-based solvers generate tours by iteratively denoising sampled edge configurations, but they do not retain the probabilities of alternative edge selections as the state is progressively refined. However, many locally plausible edge selections in the TSP continue to compete before their global compatibility becomes clear, creating a need for a generation state that can explicitly represent and progressively update such uncertainty. To address this, we introduce Bayesian Flow Networks (BFNs), which use probabilistic beliefs over alternative edge selections as the generative state and progressively refine these beliefs during generation, and propose Edge-BFN (EBFN), a non-autoregressive solver operating in the edge space. EBFN continuously maintains probabilistic beliefs throughout the iterative process, allowing competing edge selections to be progressively distinguished as global information accumulates, and uses the beliefs to generate and select multiple candidate solutions. Experiments on multiple TSP benchmarks under different test-time search budgets show that EBFN achieves competitive results and outperforms recent diffusion-based solvers in some settings, suggesting that directly refining probabilistic confidence over edge selections holds substantial potential for exploring competing decision alternatives.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian Flow Networks, Combinatorial Optimization, Traveling Salesman Problem, Neural Combinatorial Optimization, Non-Autoregressive Generation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1X6POpenReview ↗
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
AuthorsOpenReview ↗

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.

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.

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

This paper tackles the problem that non-autoregressive neural solver is hard to achieve both high solution quality and small computational time. It proposed Edge-Baysian Flow Networks, which uses probabilistic belief. Numerical experiments shows its generalization performance on real-world TSP instances.

Critical strengths

EBFN shows good performance for small-sized TSP instances.

Figure 2 effectively demonstrates proposed method procedure.

Critical weaknesses

PointFormer seems to be better than EBFN in terms both of quality and computational budget.

The advantage of using probabilistic relief is not clear. Its ablation study seem to be missing.

The idea of edge-focused neural solver with prior knowledge is not innovative and it is recently studied such as DIFU-Ada*.

(DIFU-Ada: Haoyu LEI et al., Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation)

Questions for authors

Would it possible to provide the result of Pointformer for Table3 experiment?

For TSP200 and 500, Is it possible to compare the performance among DEITSP, Pointformer and EBFN under same computational time?

Would you show the advantage of probabilistic relief through ablation study with uniform probabilistic relief?

Number of edges is not always same even instances share the number of nodes. Can EBFN handle different number of edges across instances? If yes, how does it tackle?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 1La7 [1/2]

Weakness 1: PointFormer seems to be better than EBFN in terms both of quality and computational budget.

Response: We thank the reviewer. Pointerformer is faster; if latency is the priority, it is preferable on TSP50, where both methods are essentially optimal. However, quality dominance does not hold at larger sizes, as summarized below.

SettingPointerformerEBFN
TSP500.0007% @49s−0.006% @106s
TSP1000.168% @61s0.108% @311s
TSP2001.439% @27s0.562% @129s
TSP50012.560% @85s2.637% @1130s

On TSP100, Pointerformer is faster (61s vs 311s) but EBFN has the lower gap (0.108% vs 0.168%); on TSP200/500, EBFN is slower (129/1130s vs 27/85s) but has a much lower gap (0.562/2.637 vs 1.439/12.560). This is a time–quality trade-off (Pareto), not uniform dominance: Pointerformer wins on budget, EBFN wins on quality, and neither dominates the other.

Weakness 2: The advantage of using probabilistic relief is not clear. Its ablation study seem to be missing.

Response: We agree the ablation was missing. With the same 21 forwards, 168 candidates, and 2-opt on the same 1280 test set (TSP50/TSP100):

ConfigurationTSP50TSP100
initial-only pO−0.00880.0388
no-update (c=0)−0.00780.0626
full deployed (c=0.0125)−0.00580.0632
final-only0.1550.235
uniform heatmap0.1061.732

The learned heatmap is essential (the uniform control is far worse), but the iterative update does not outperform the initial prediction at the same candidate budget and acts as a diversity/compute knob. With c=1.0, per-state best@K improves with k (1.75% → 0.40% on TSP100, τ=2.5), but the final low-budget gap is worse (0.177 vs 0.108). We agree that the paper should report this ablation and state the advantage of the probabilistic belief accordingly.

Weakness 3: The idea of edge-focused neural solver with prior knowledge is not innovative and it is recently studied such as DIFU-Ada*.

Response: We thank the reviewer for pointing us to DIFU-Ada*. We agree that an edge-focused neural solver alone is not novel, and that this related work should be discussed explicitly. DIFU-Ada* focuses on inference-time adaptation for cross-problem generalization of diffusion-based solvers; in contrast, EBFN uses a Bayesian flow over edge beliefs as the generative state and combines it with multi-stage edge heatmaps and multi-candidate Gumbel/2-opt decoding. Our contribution is therefore the edge-belief BFN with an anytime decoder and its empirical analysis, not the edge-focused formulation per se; the positioning relative to DIFU-Ada* needs to be made explicit.

Question: Would it possible to provide the result of Pointformer for Table3 experiment?

Response: Yes. We report Pointerformer on the same real-world instances used in Table 3:

DatasetPointerformer
USA17.02%
JA10.84%
BM15.14%
TSPLIB26n/a (fixed-size only)

128 instances each, same protocol as the table. TSPLIB26 is not applicable because Pointerformer requires a fixed graph size and cannot handle the variable-length TSPLIB instances. Pointerformer was not included in the original Table 3; this omission needs correction.

AuthorsOpenReview ↗

Response to Reviewer 1La7 [2/2]

Question: For TSP200 and 500, is it possible to compare the performance among DEITSP, Pointformer and EBFN under the same computational time?

Response: Yes. On the same 128-instance TSP200/500 test sets, the gap–time points are:

DatasetMethodTimeGap
TSP200Pointerformer27s1.44%
TSP200DEITSP (16-iter)73s0.48%
TSP200EBFN (168 candidates)129s0.56%
TSP200EBFN at ~73s (K=1–2)~70s2.6–3.3%
TSP500Pointerformer85s12.56%
TSP500DEITSP (16-iter)419s2.15%
TSP500EBFN (168 candidates)1130s2.64%
TSP500EBFN at ~419s (K=1)~423s5.0%

At equal computational time, DEITSP is better than EBFN on both sizes; Pointerformer is faster but has a much worse gap. We therefore do not claim an advantage over DEITSP at TSP200/500. EBFN’s dense N² representation is the main limitation at these scales.

Question: Would you show the advantage of probabilistic relief through ablation study with uniform probabilistic relief?

Response: Yes. With a uniform heatmap (0.5) and the same 168 candidates and 2-opt:

ConfigurationTSP50TSP100
uniform heatmap0.1061.732
full model−0.0060.063
initial-only−0.0090.039

The uniform control is one to two orders of magnitude worse, so the learned edge probabilities are clearly advantageous over an uninformative prior. However, the gain comes from the learned initial heatmap rather than from the iterative update: initial-only is comparable to (slightly better than) the full model, and the belief update acts as a diversity/compute knob.

Question: Number of edges is not always same even instances share the number of nodes. Can EBFN handle different number of edges across instances? If yes, how does it tackle?

Response: EBFN does not take an instance-specific edge list; it operates on a dense N×N directed edge grid, so for a fixed N the number of potential edges is always N(N−1), independent of the instance. For standard TSP the graph is complete, so this is well-defined. If an instance has fewer edges (a non-complete graph), absent edges can be masked—their belief/score is fixed to 0 (or −inf) before merge and 2-opt—so the same architecture can represent a variable number of present edges without a variable-length input. We have not trained or evaluated EBFN on non-complete graphs, so we do not claim zero-shot performance there; this is a limitation and a natural extension (masking plus training on sparse instances).

Reviewer_1La7OpenReview ↗

Comment by reviewer

Thanks for detailed explanation. I understand the positive aspects to introduce relief based on the additional experiments. However, its performance under same computational budget is not shown as author mentioned. Considering these things, I keep my original score.

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

This paper proposes Edge-BFN, a non-autoregressive TSP solver that adapts Bayesian Flow Networks to edge-based generation. It iteratively refines edge beliefs through a GNN and uses intermediate heatmaps, Gumbel sampling, and 2-opt to construct candidate tours. Experiments demonstrate competitive performance on synthetic TSP benchmarks and promising generalization under distribution shifts.

Critical strengths
  • Novel application of BFNs. Adapting Bayesian Flow Networks to edge-based TSP generation is an interesting idea and provides a reasonable alternative to diffusion-based solvers.

  • Strong generalization. The model demonstrates promising zero-shot generalization on the real-world benchmarks in Table 3.

Critical weaknesses

W1. Insufficient evidence for the contribution of Bayesian belief refinement.

The very small inference step size raises concerns about whether meaningful belief refinement actually occurs. Specifically, the two-logit update in the released code, together with ∑tαt=β1=20\sum_t \alpha_t=\beta_1=20, implies

$ |\operatorname{logit}\pi_{ij,1}^{(t)}|\leq 2c\beta_1=0.5, $

which strictly bounds the edge beliefs to [0.3775,0.6225][0.3775,0.6225] throughout inference (c=0.0125)(c=0.0125). This appears inconsistent with the belief concentration illustrated in Figure 2, if the figure represents actual belief states.

Moreover, Eq. (10) produces much more concentrated training beliefs at later flow times (e.g., the training log-odds have mean ±10\pm10 at t=0.5t=0.5), suggesting a substantial training–inference distribution mismatch.

Without matched-budget ablations using the initial prediction P0P_0 or disabling belief updates (c=0)(c=0), it remains unclear whether the performance gains primarily come from Bayesian refinement or from multi-stage Gumbel sampling and 2-opt.

W2. Incomplete and potentially inconsistent baseline comparisons.

The experiments omit relevant recent methods, such as Fast T2T and DISCO. Furthermore, the reported TSP100 results for DEITSP and T2TCO are noticeably worse than those in their original papers, raising concerns about the fairness and reliability of the comparisons.

W3. Paper–code discrepancies and limited reproducibility.

The supplementary material provides inference-only code, without the training implementation. Several implementation details also differ from the manuscript, including the number of GNN layers and the edge input features. These discrepancies make it difficult to fully verify the reported method and results.

Questions for authors

Q1. Belief refinement:

How does EBFN perform when sampling the same number of candidates directly from P0P_0, or when disabling belief updates (c=0)(c=0)? How does the limited range of edge beliefs align with Figure 2?

Q2. Baseline comparisons:

Could the authors explain why the reproduced DEITSP and T2TCO results are weaker than their originally published values? Could comparisons with Fast T2T and DISCO be included?

Q3. Implementation and reproducibility:

Could the authors clarify the discrepancies between the manuscript and the released code?

3 comments
AuthorsOpenReview ↗

Response to Reviewer vj5a

W1 (belief refinement). We thank the reviewer for this careful analysis; we agree that the inference step size and the train/inference belief gap are real issues. With c=0.0125 and β1=20, the two-logit update implies |log-odds| ≤ 2cβ1 = 0.5, so the inference belief stays near-uniform (θ∈[0.378,0.603]); training true-edge log-odds at t=1 are ≈20 (effective inference time ≈sqrt(2c)≈0.16). Figure 2 was generated with the earlier c=1.0 configuration; at the deployed c=0.0125 the sharp quantity is the network output pO (|log-odds|≈13), not the belief state.

Configuration (21 forwards, 168 candidates, 2-opt)TSP50TSP100
initial-only pO−0.00880.0388
no-update (c=0)−0.00780.0626
full deployed (c=0.0125)−0.00580.0632
final-only0.1550.235
uniform heatmap0.1061.732

With c=1.0, per-state best@K improves with k (1.75% → 0.40% on TSP100, τ=2.5), but the final low-budget gap is worse (0.177 vs 0.108). The results show that the gains come primarily from the learned initial heatmap, multi-candidate Gumbel sampling, and 2-opt; the iterative belief update acts as a diversity/compute knob. We agree that the current claims and Figure 2 need correction; the belief refinement is not the primary source of the reported gains.

W2 (baselines). We thank the reviewer; we agree the comparison needs to be protocol-consistent. The re-run numbers on the same 1280 test set are:

MethodProtocolTSP50TSP100
T2TCOrewrite 0.25, 50 steps, 2-opt 10000.1100.259
T2TCOrewrite 0.4, same0.1180.282
T2TCOno-rewrite (original table)0.0870.284
DEITSP16-iter pow, greedy+2opt, TSP-100 ckpt0.0340.155

The original T2TCO paper reports a lower TSP100 value (≈0.06) on its own benchmark; the residual difference is due to the test split and the guided/2-opt schedule. The DEITSP TSP100 value matches the earlier table (0.156); the remaining difference from the original paper is the test split/2-opt budget. We agree the current entries need correction/annotation; the discrepancies are test-split/protocol effects, not code errors. Recent methods (Fast T2T, DISCO) will be added in future experiments.

W3 (reproducibility). We thank the reviewer; we agree the supplementary material was inference-only and the manuscript description did not fully match the implementation. The actual implementation is:

ItemValue
Encoder5 GNN layers, hidden 384 (5.23M)
Edgesdense directed N×N
Edge input2θ−1 (θ = BFN belief)
BFNβ1=20, n_flow=25, θ-dropout 0.25
OptimizerAdamW, lr 2e-4, wd 1e-4, cosine
Trainingbatch 64, 50 epochs (75.1M samples)

We agree that the manuscript’s layer count and edge-feature description need correction to match this. We will release the full training code and exact configuration in the future.

Q1. Please see W1. With the same 21 forwards and 168 candidates, initial-only pO gives −0.0088/0.0388 and no-update (c=0) −0.0078/0.0626 (TSP50/TSP100); the gains come from the initial heatmap + Gumbel + 2-opt. Figure 2 was generated with the earlier c=1.0 configuration and does not represent the deployed c=0.0125 belief (θ∈[0.378,0.603]).

Q2. Please see W2. On the 1280 test, DEITSP gives 0.034/0.155 and T2TCO (rewrite) 0.110/0.259; the differences from the original papers are consistent with test-split/2-opt effects, and Fast T2T/DISCO will be added in future experiments.

Q3. Please see W3. The implementation uses 5 GNN layers, hidden 384, and edge input 2θ−1; the manuscript’s layer/feature description needs correction, and the training code will be released in the future.

Thanks for the clarifications and additional ablations. The explanations of Figure 2 and the implementation differences are helpful.

My main concern is still what belief refinement adds. On TSP100, P0P_0-only performs better than the full method, while disabling the updates gives almost the same result as the full method. This does not rule out the value of BFN training, but it leaves the benefit of iterative refinement unclear. Given how central this is to the paper’s motivation, how do these findings change your view of the main contribution?

The baseline comparison also remains a concern. As you acknowledge, EBFN uses multi-candidate sampling while the diffusion baselines use greedy decoding. This makes it difficult to tell whether the reported advantage comes from BFN modeling or the search procedure.

I appreciate the additional analysis, but these two concerns remain, so I am keeping my original rating.

AuthorsOpenReview ↗

Response to Reviewer vj5a

We thank the reviewer for the follow-up and for the candid assessment. We agree with both points, and they change our view of the contribution.

Belief refinement

The matched-budget results show that initial-only is slightly better than the full model, and that disabling updates gives nearly the same result. We therefore no longer view iterative belief refinement as the main contribution. The BFN training is still valuable in that it produces the learned edge heatmap—removing it (uniform heatmap) is far worse—but the benefit of iterating the belief is not established: at the deployed step size it mainly provides diversity, and at c=1.0 it improves per-state candidates but not the final low-budget gap. The original motivation overstates the role of refinement; the contribution should be reframed as a learned edge heatmap with an anytime multi-candidate decoder, with the BFN belief as a diversity/compute knob.

Baseline fairness

We also agree that the current comparison conflates BFN modeling with the search procedure. The advantage in Table 1 is primarily due to multi-candidate sampling; at an equal sampling budget the advantage is small or reverses. We therefore do not claim that the reported advantage comes from BFN modeling. A controlled comparison should use the same decoder and matched budgets.

Next steps

Going forward, we will continue to investigate why iterative refinement is ineffective—e.g., the train/inference belief mismatch, the update scale, and the lack of a refinement objective—and aim to make the belief state itself discriminative, so that the method relies less on multi-candidate Gumbel sampling. We see this as the key next step for the method.

We appreciate the reviewer’s careful reading and understand the decision to keep the rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions

We thank all reviewers. We summarize the main analyses and corrections.

1. Belief refinement and the core claim. Matched-budget ablations (21 forwards / 168 candidates / 2-opt): initial-only pO −0.0088/0.0388, no-update −0.0078/0.0626, full deployed −0.0058/0.0632, final-only 0.155/0.235, and uniform heatmap 0.106/1.732 (TSP50/TSP100). The gains come primarily from the learned initial heatmap, multi-candidate Gumbel sampling, and 2-opt; the iterative belief update acts as a diversity/compute knob. Figure 2 was generated with the earlier c=1.0 configuration and does not represent the deployed c=0.0125 belief (θ∈[0.378,0.603]); with c=1.0, per-state best@K improves (1.75%→0.40%) but the final low-budget gap is worse (0.177 vs 0.108). We agree that the current claims and Figure 2 need correction.

2. Baselines and fairness. We re-ran T2TCO with the original rewrite protocol (TSP50 0.110 / TSP100 0.259 at ratio 0.25; 0.118/0.282 at 0.4) and DEITSP with the official 16-iteration protocol (0.034/0.155) on the full 1280 test; the residual differences from the original papers are consistent with test-split and 2-opt/guided-schedule effects. We agree that Table 1 is not a like-for-like comparison (EBFN uses multi-candidate sampling while the diffusion baselines use greedy decoding); a fair comparison should match the decoding budget, and we will adopt it and add Fast T2T, DISCO, Generation-as-Search, MaskCO, and NExCO in future experiments.

3. Pointerformer and equal-time comparison. Pointerformer is faster, but this is a time–quality trade-off: on TSP50 both are near-optimal; on TSP100 EBFN has the lower gap (0.108% vs 0.168%); on TSP200/500 EBFN is slower but has much lower gaps (0.562/2.637 vs 1.439/12.560). At equal time, DEITSP is better than EBFN at TSP200/500; we do not claim uniform dominance. Pointerformer on Table 3: USA 17.02%, JA 10.84%, BM 15.14% (TSPLIB26 n/a, fixed-size only); this omission needs correction.

4. Scalability and generality. The evaluation stops at TSP-500; the dense N×N representation grows as O(N²) (~10⁸ edge variables at N=10K), which is infeasible on a single GPU. Extending to large N requires sparse or hierarchical edges. The evaluation is limited to symmetric Euclidean TSP; ATSP requires a matrix encoder (UniCO-style) and retraining; non-complete graphs can be handled by masking but were not evaluated. We do not claim zero-shot performance in these settings.

5. Reproducibility and positioning. The implementation uses 5 GNN layers, hidden 384 (5.23M), dense directed N×N edges, and edge input 2θ−1; training uses β1=20, n_flow=25, θ-dropout 0.25, AdamW (lr 2e-4, wd 1e-4, cosine), batch 64, and 50 epochs (75.1M). The full training code and exact configuration will be released in the future. An edge-focused solver alone is not novel; DIFU-Ada* is inference-time adaptation, whereas EBFN is an edge-belief BFN with an anytime decoder, and the positioning needs to be made explicit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.