acceptodds
Under review as a conference paper at ICLR 2027

Learning a Diffusion-Native Latent Space for Neural Combinatorial Optimization

Abstract

Diffusion-based neural combinatorial optimization requires specifying how combinatorial solutions should be corrupted and subsequently denoised. Generic variable-wise noise ignores the structured geometry of feasible solutions, while search-oriented methods rely on task-specific perturbations such as masking or local-search moves, which can also be difficult to define when solutions lack a meaningful notion of perturbation. We instead learn a targeted space in which diffusion should operate. We introduce LCO-Diff, which uses an instance-conditioned variational autoencoder to transform discrete combinatorial solutions into a diffusion-native latent space. The latent representation is trained to remain sufficient for reconstructing the solution while being regularized toward a Gaussian geometry, so that standard continuous transport becomes native to the learned solution representation rather than being imposed on the original discrete space. In this latent space, we train an instance-conditioned rectified-flow model using a canonical Gaussian interpolation, yielding the same generative dynamics across different combinatorial problem classes. Denoised latents are decoded into solution scores and converted into feasible solutions via constraint-aware decoding and repair. The learned latent geometry also turns the training-time diffusion process into a natural test-time search mechanism. A candidate solution can be re-encoded into the latent space, partially renoised along the same Gaussian path used during training, and denoised again to generate improved candidates, without introducing a separate solution-space perturbation operator. Across problem sizes and inference budgets, our latent-space diffusion achieves state-of-the-art solution quality at low sampling cost and improves further with renoise-based test-time scaling.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Latent Space, Continuous Diffusion Model

Reviews

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

Diffusion-based methods for combinatorial optimization often add noise directly in the discrete solution space. However, combinatorial solutions are discrete and strongly constrained, which does not naturally match the smooth transport of standard continuous diffusion. To address this, LCO-Diff introduces an instance-conditioned variational autoencoder to transform discrete combinatorial solutions into a diffusion-native latent space. The method consists of two stages: the first stage is an instance-conditioned VAE, and the second stage is a latent-space rectified-flow denoiser. At inference time, it starts from standard Gaussian noise, performs a small number of denoising steps, then decodes the result into a heatmap, and repairs it into a feasible solution using lightweight greedy insertion and local search.

Critical strengths

S1. Diffusion-native latent space from an instance-conditioned VAE is used to learn a node-level continuous representation, so that standard Gaussian diffusion/flow can operate directly in this space without designing solution-space corruption for each problem. S2. Problem-specific feasibility is moved to the decoding interface. The generation side is problem-agnostic, while the decoding side handles constraints such as those in TSP, CVRP, and TSPTW using greedy insertion plus local search. S3. The renoise cycle reuses the Gaussian noising from training, requiring no new operators or retraining, and can convert additional test-time computation into quality improvements. S4. Good storytelling, with a clear motivation. S5. Wide experiments cover several CO problems such as TSP, MIS, CVRP, and TSPTW, and can handle routing problems where solution-space noise is hard to define, such as CVRP and TSPTW.

Critical weaknesses

W1. The embedder must be frozen before the denoiser can be trained; switching problems requires retraining both the embedder and the denoiser. Compared with PT-Denoise's no retraining, this implies higher deployment cost. It does not support plug-and-play. W2. Problem-agnostic holds only on the generation side: inference still requires decode-then-repair, with greedy insertion + 2-opt for TSP, capacity-aware 2-opt for CVRP, and time-window-penalized 2-opt for TSPTW; problem-specific repair operators still exist, merely relocated to the decoding interface. W3. Parameter tuning: the renoise factor ρ is still tuned per problem, ρ=0.4 for TSP-500, ρ=0.1 for TSP-1000, ρ=0.75 for MIS, and ρ=0.5 for CVRP/TSPTW. It is not entirely tuning-free.

Questions for authors

See above in Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer Dg5a

Thank you for your thoughtful review and for recognizing how the learned latent space supports both candidate generation and test-time refinement. Your comments help us explain what it takes to apply LCO-Diff to a new problem class and how the solver handles that problem’s constraints during inference.

W1. Two-stage training and deployment cost.

Thank you for pointing us to PT-Denoise. We agree that reusing a pretrained model has a practical advantage when adapting to a new task. We have discussed PT-Denoise in the related work in our revised manuscript and clarify the training requirements of each approach.

In our current setup, a new problem class requires training both the embedder and the denoiser. Freezing the embedder after the first stage gives the denoiser a fixed latent target. Based on our approximate timings, training the embedder takes about 1/10 as long as training the denoiser, or roughly 10% of the combined model training time. This stage provides the representation used for both generation and refinement. The inference gains illustrate the value of that investment. On TSP-500 at C=8C=8, LCO-Diff achieves a 0.0065% gap in 8 seconds, compared with 0.0665% in 10 seconds for the raw-space continuous baseline in Table 5.

W2. Task-specific decoding and repair.

We appreciate the opportunity to clarify the role of post-processing. Our design focuses on improving how the model proposes and refines candidates. Each cycle re-encodes the incumbent and refines it along the Gaussian path used during training. The decoder then constructs a discrete solution, and task-specific local search such as 2-opt can further improve its quality.

The learned refinement can already outperform strong prior solvers with greedy decoding alone. On MIS-RB, LCO-Diff uses greedy decoding with no additional local search. Increasing the number of refinement cycles from 4 to 256 reduces the gap from 1.12% to 0.06%. At 256 cycles, LCO-Diff reaches 0.06% in 13.1 minutes, compared with 0.22% in 35.2 minutes for the best-gap GenSCO setting reported in Table 2. We will clarify that the shared procedure concerns candidate generation and refinement in latent space, and that additional local search can be used where it improves solution quality.

W3. Choice of the renoising strength ρ\rho.

Thank you for pointing out the different values in Table 13. The parameter ρ\rho controls how strongly we perturb the incumbent along the same Gaussian path. A smaller value preserves more information about the current solution, while a larger value allows broader exploration. Since the denoiser is trained across the interpolation path, we can adjust this balance for a task or instance size using the same checkpoint.

Several of our evaluated settings already share a value. CVRP and TSPTW both use ρ=0.5\rho=0.5, and both MIS graph families use ρ=0.75\rho=0.75. With ρ=0.5\rho=0.5 fixed, for example, the CVRP-100 gap falls from 0.49% to 0.11% as CC increases from 8 to 512. We have revised Section 3.3 to make the distinction explicit. The Gaussian renoising rule is shared, and its strength can be chosen at inference time to suit the problem.


Thank you again for your constructive suggestions. We hope the training measurements and the greedy-only MIS results help quantify the cost and benefit of learning the latent representation. We appreciate the opportunity to clarify which parts of generation and refinement are shared across tasks and which choices depend on the problem.

Reviewer_yu4zOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
3
Read review
Paper summary

This paper tackles the problem of learning a generative model to generate solution to combinatorial optimization problems. Their method learns, given a instance description GG and corresponding solution xx a mapping to a latent space zz via a variational autoencoder. A instance conditioned flow model is then learned to reconstruct this latent reprensentation from noise which can then be decoded into a heatmap using the VAE decoder. Through decoding and repair of the headmap a feasible solution of the combinatorial optimization problem can be obtained. At evaluation the authors also use "Test-time scaling" where they iteratively re encode, then noise a generated solution in order to decode it again with the aim at improving the solution even more. The authors evaluate their method on TSP, MIS, CVRP and TSPTW combinatorial optimization tasks and report competitive results at smaller time budgets.

Critical strengths
  1. Method is evaluated on wide variety of combinatorial optimization tasks.
  2. Paper is in terms of language mostly well written and understandable.
  3. The method is sound.
Critical weaknesses
  1. There are serious conflicts in notation and math is not properly introduced which made is difficult to understand the paper. For example in section 3.1 the meaning of qϕq_\phi or AsA_s, ss and xx is never explained. Also it is unclear in equation 3 over what distribution the expectation is defined. Even worse it seems that there are serious conflict between the definitions of these variables in Sec. 3.1 compared to Figure 1. In figure 1, the authors use GG for the problem instance and xx is the solution. In Section 3.1, however, it seems like ss is the solution and xx the problem instance. AsA_s seems to be the encoded instance solution pair. None of this is properly explained in the main text.
  2. Then in Figure 2 it also seems to be unclear to me why μΦ\mu_\Phi receives s and s^* as an input. in the pseudo code \mu would receive an xx and AsA_s. Also suddenly in the Figure \mu depends on Φ\Phi and not as previously written on ϕ\phi. All of these inconsistencies make the paper hard to follow. In my opinion the math should be properly and clearly introduced.
  3. The authors claim to perform latent space diffusion although they use a Rectified Flow which is a flow matching based method.
  4. To me it seems that the novelty of the method is quite limited
Questions for authors
  1. Why do the authors claim to use latent space diffusion although you are using a flow matching method in latent space?
  2. Can you please properly define xx, ss, AsA_s, qq. what is the domain of μ\mu?
  3. To my understanding the decoder would not only decode the proposed solution but also the problem instance. Did the authors also test how well the decoded instance is reconstructed compared to the true instance? When re encoding the currently best solution using "Test-time scaling", to my understanding you have to encode it combined with the problem instance. Do the authors use there the real one or the reconstructed one? How does the prediction quality of the decoded problem instance improve over several "test time scaling" iterations?

Overall, in my opinion the math in this paper should be properly explained and mathematical inconsistencies should be resolved before this paper can be accepted.

5 comments
AuthorsOpenReview ↗

Response to Reviewer yu4z (Part 1/3)

W1 & W2 & Q2. Math issues.

Thank you for the careful reading. We have unified the notation across the text, the equations, the figure captions, and the pseudocode, and every change is marked in blue in the revised manuscript.

Definitions (Q2). A new Notation paragraph at the start of Sec. 3.1 now defines each of these symbols before use:

  • x\mathbf{x}: the given problem instance in its task-specific form, such as node coordinates for TSP; the instance formats of all four tasks are defined in Appendix A.
  • s\mathbf{s}: a discrete solution, and AsA _{\mathbf{s}} the task-specific tensor derived from it (tour adjacency for TSP, route adjacency for CVRP, node-membership vector for MIS).
  • qφ(z∣x,As)q _\varphi(\mathbf{z}\mid\mathbf{x},A _{\mathbf{s}}): the diagonal-Gaussian posterior of the embedder, with mean μφ(x,As)\boldsymbol{\mu} _\varphi(\mathbf{x},A _{\mathbf{s}}) and per-element standard deviation σφ(x,As)\boldsymbol{\sigma} _\varphi(\mathbf{x},A _{\mathbf{s}}), both of shape n×dzn\times d _z with dz=128d _z=128; the sample is zvae=μφ+σφ⊙ε\mathbf{z} _{\mathrm{vae}}=\boldsymbol{\mu} _\varphi+\boldsymbol{\sigma} _\varphi\odot\boldsymbol{\varepsilon}.
  • The decoder Decφ\mathrm{Dec} _\varphi maps a latent to a score tensor supervised by AsA _{\mathbf{s}} (a tour heatmap in Rn×n\mathbb{R}^{n\times n} for TSP and CVRP, a node score vector in Rn\mathbb{R}^{n} for MIS).
  • Three disjoint parameter symbols: φ\varphi for the embedder, ψ\psi for the instance encoder Encψ\mathrm{Enc} _\psi, and θ\theta for the denoiser fθf _\theta, which sees the instance only through c=Encψ(x)\mathbf{c}=\mathrm{Enc} _\psi(\mathbf{x}); the old figure's μΦ\mu _\Phi is gone.
  • The roles of the instance and the solution are stated in the text of Sec. 3.1: the instance is the conditioning input of both stages, while the solution is the datum the encoder embeds and the target the decoder reconstructs, so it reaches the network through the encoder alone; the encoder sees a solution again only in the re-encoding step of the renoise cycle (see the Fig. 2 note below).

The expectation in Eq. (3). The expectation is now written explicitly as E(x,s)∼p^train, ε∼N(0,I)\mathbb{E} _{(\mathbf{x},\mathbf{s})\sim\widehat{p} _{\text{train}},\ \boldsymbol{\varepsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}, where p^train\widehat{p} _{\text{train}} is the empirical distribution of the training pairs and ε\boldsymbol{\varepsilon} is drawn independently of (x,s)(\mathbf{x},\mathbf{s}), and the sentence following the equation states that the KL term is evaluated in closed form for the diagonal Gaussian posterior. Eq. (4), the denoiser objective, was rewritten in the same style, with t∼U(0,1)t\sim\mathcal{U}(0,1) and with c\mathbf{c}, z=μφ(x,As)\mathbf{z}=\boldsymbol{\mu} _\varphi(\mathbf{x},A _{\mathbf{s}}), and zt=t z+(1−t) ε\mathbf{z} _t=t\ \mathbf{z}+(1-t)\ \boldsymbol{\varepsilon} defined alongside.

Fig. 1 versus Sec. 3.1. The submitted figure used G\mathcal{G} for the instance and x\mathbf{x} for the tour, while the text used x\mathbf{x} for the instance. The revision keeps the text convention everywhere: both figures are now redrawn to carry exactly these symbols, and their captions are revised accordingly.

Fig. 2 and the pseudocode. The encoder takes two quantities, the instance and one solution. In the inference figure that solution is the incumbent: the current best candidate s⋆\mathbf{s}^\star is re-encoded as z⋆=μφ(x,As⋆)\mathbf{z}^\star=\boldsymbol{\mu} _\varphi(\mathbf{x},A _{\mathbf{s}^\star}), partially renoised with factor ρ\rho, and denoised again on the interval t∈[1−ρ,1]t\in[1-\rho,1]. Alg. 1 and the full listings in App. C (Alg. 2 and 3) now use the same symbols as the text, for example z←μφ(x,As)\mathbf{z}\leftarrow\boldsymbol{\mu} _\varphi(\mathbf{x},A _{\mathbf{s}}), c←Encψ(x)\mathbf{c}\leftarrow\mathrm{Enc} _\psi(\mathbf{x}), s^←Repair(H^;x)\hat{\mathbf{s}}\leftarrow\mathrm{Repair}(\hat{H};\mathbf{x}), and a cycle loop j=1,…,C−1j=1,\dots,C{-}1. We also fixed the further inconsistencies this review surfaced: arg best⁡\operatorname{arg\ best} is now defined precisely (the better of its two arguments on the given instance, a lower cost on TSP, CVRP and TSPTW and a larger set size on MIS; the submitted pseudocode implied cost minimization on MIS as well, which was an error), one sentence states that the incumbent never worsens, one cycle costs about ρK\rho K denoiser evaluations (the budget counted in Sec. 4.4), the repair restores feasibility everywhere except the small residual time-window violations we report on TSPTW, and the VAE visibility flag is written τ\tau, not tt, so it no longer clashes with the flow time.

AuthorsOpenReview ↗

Response to Reviewer yu4z (Part 2/3)

W3 & Q1. The authors claim to perform latent space diffusion although they use a Rectified Flow which is a flow matching based method.

We agree that your interpretation is mathematically rigorous in the strict SDE-based sense, and we clarify that our use of “latent diffusion” is broad, referring to latent-space generative modeling via iterative noising/denoising or flow-based transport, where Rectified Flow as a flow-matching ODE implementation belongs to the same unified diffusion/flow framework.

In latent diffusion work on images, Stable Diffusion 3 [1] uses rectified flow in latent space but still refers to its architecture as a "transformer-based diffusion backbone". In the domain of CO, GenSCO [2] performs rectified flow in the solution space while also describing itself as "Diffusion-Based Combinatorial Optimization." Such broad usage is therefore accepted in many settings.

If you believe that the mathematical distinction should be emphasized in the current context, we are happy to change "latent space diffusion" to "latent space flow", which does not affect the integrity of our work.

W4. To me it seems that the novelty of the method is quite limited.

We agree that rectified flow and latent diffusion are established tools, and that latent diffusion has been particularly successful in image generation. However, we believe introducing latent diffusion to combinatorial optimization is especially meaningful and the combination is non-trivial. In combinatorial optimization, even a small change to a discrete solution can break global structure, such as tour connectivity, and what constitutes a useful perturbation depends on the task’s constraints. LCO-Diff learns a continuous space that preserves the structure needed to reconstruct a solution and supports Gaussian perturbations, so the solver can reuse its training-time flow to resample from the current best candidate. The state-of-the-art performance also highlights our contributions. We summarize our specific contributions as follows.

  • The contribution is the interface, not the flow. Prior continuous CO solvers inject noise in the solution space, which ties each method to the problems where such a noise is well defined. We instead learn, with an instance-conditioned VAE, a diffusion-native latent space in which one Gaussian prior and one shared corruption rule cover TSP, MIS, CVRP and TSPTW, so the generation side is problem-agnostic. This is where the payoff shows: continuous-diffusion solvers that can handle CVRP are scarce, and LCO-Diff outperforms the prior latent-space solvers there (Table 3); on TSPTW-50 it stays below the LKH-3 reference in both tightness regimes while the constructive baselines remain above it with substantial infeasible rates.
  • Test-time scaling is a property of the representation, not a designed search scheme. The renoise cycle reuses the training Gaussian path: encode the incumbent, partially renoise toward the prior with factor ρ\rho, and denoise on the remaining interval t∈[1−ρ,1]t\in[1-\rho,1]. No new search operator, no retraining, and no per-problem engineering, and the same mechanism converts budget into quality on all four problems. The same formulation is also available in the solution space, but it works noticeably worse there: with the same backbone, training data, and budget, the solution-space gaps stay more than 8×8\times larger at every budget and the advantage grows as CC increases (Table 5).
  • The results confirm the transfer is substantive. On MIS-ER (Table 2), LCO-Diff reaches −0.17%-0.17\% at C=256C=256, a mean set size above the published reference, in 21.3 minutes, while GenSCO remains 1.03%1.03\% short in 21.4 minutes and the discrete diffusion baselines stay above 6.9%6.9\%.
AuthorsOpenReview ↗

Response to Reviewer yu4z (Part 3/3)

Q3.1 How well the decoded instance is reconstructed compared to the true instance?

We first apologize for the confusion caused by our mathematical notation. The VAE encoder receives the given instance x\mathbf{x} together with the tensor AsA _{\mathbf{s}} of a solution s\mathbf{s}. The instance provides context for encoding the solution. The decoder's reconstruction target is AsA _{\mathbf{s}}, so its outputs are scores for solution decisions, such as which edges form a TSP tour or which nodes belong to an independent set.

To measure reconstruction fidelity, we supply the encoder with a test instance and a solution. We convert the decoded scores into a discrete solution using greedy construction and compare it with the input solution. We report overlap over selected nodes for MIS and over tour edges for TSP. In each transfer experiment, we evaluate the VAE trained on the source data directly on the target data.

For MIS, RB-[200-300] and ER-[700-800] involve instance-level shifts in both distribution and size. Specifically, a VAE trained on RB-[200-300] is tested on ER-[700-800], and a VAE trained on ER-[700-800] is tested on RB-[200-300].

train\testRB-[200-300]ER-[700-800]
RB-[200-300]100%100%
ER-[700-800]100%100%

For TSP, TSP-500 and TSP-1000 involve an instance-size shift:

train\testTSP-500TSP-1000
TSP-500100%99.9930%
TSP-1000100%100%

For TSP-100, we trained the VAE on suboptimal data generated by 128-run 2-opt and now test its reconstruction quality when the input is an optimal solution, thereby measuring reconstruction quality under a shift in the solution distribution. The results are as follows.

TSP-100 (test with optimal solution)

Acc.
VAE trained with suboptimal data100%

These results show that reconstruction remains near-perfect even under distribution shifts.

Q3.2 What does the VAE reconstruct, which problem instance does the solver use during test-time refinement, and what improves across iterations?

Thank you for pointing out the ambiguity in our notation. We use an instance-conditioned VAE. The encoder takes the given problem instance x\mathbf{x} and the solution tensor AsA _{\mathbf{s}}. The decoder maps the latent to solution scores, with AsA _{\mathbf{s}} as its only reconstruction target. Instance reconstruction accuracy therefore does not apply.

During test-time refinement, we always re-encode the current best solution together with the same original instance x\mathbf{x}. We partially renoise the resulting latent and denoise it to propose a new candidate for that instance. The quantity that improves across iterations is the quality of the returned solution. For example, on TSP-500, the solution gap falls from 0.0065% to 0.0004% as the number of refinement cycles increases from 8 to 512 (Table 1).


Thank you again for your careful review. We hope the unified notation and the explicit description of training and inference make it easier to follow what LCO-Diff encodes, reconstructs, and updates during refinement. We would appreciate your taking these clarifications, the additional comparisons, and the corresponding manuscript revisions into account when reassessing the paper. We would be happy to clarify any remaining questions.

[1] Scaling Rectified Flow Transformers for High-Resolution Image Synthesis. ArXiv 2024.

[2] Generation as Search Operator for Test-Time Scaling of Diffusion-Based Combinatorial Optimization. NeurIPS 2025.

Reviewer_yoAeOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes LCO-Diff, a diffusion-based neural solver for combinatorial optimization that works in a learned latent space instead of on the discrete solution. Then a variational autoencoder maps each solution to one continuous vector per node. A rectified-flow model learns to generate these vectors from Gaussian noise, and the decoded output is repaired into a legal solution. During inference, the best solution so far is re-encoded, partly re-noised and denoised again.

Critical strengths

The idea is relatively novel in this field. This method does not follow the tradition in diffusion for CO, which works in the discrete solution space, but works in a latent space. The results show that the optimality gap is lowered by more than eightfold on TSP-500 and on RB graphs, compared with diffusion in the raw solution space. The MIS results are better than both GenSCO and the MaskCO results.

Critical weaknesses
  1. The ablation in Table 5 does not fully isolate the latent space. LCO-Diff adds a VAE with 12 transformer layers that the raw-space baseline does not have. Also, no comparisons on the parameter counts are given. The raw-space baseline also uses Gaussian noise, which Section 2.1 itself says is weaker than the discrete noise of DIFUSCO, T2T and Fast T2T. Therefore, it would be more helpful to use a parameter-matched baseline with discrete noise.

  2. Routing is the central problem set for this method, but the evidence for it is thin. The paper says solution-space methods "cannot natively express" routing, but MaskCO and NExCO both report CVRP results. MaskCO even reports up to 1,000 customers. The routing tests stop at 100 customers for CVRP and 50 for TSPTW. The CVRP table also does not include some key neural baselines, such as POMO-based methods, BQ-NCO, LEHD, NeuOpt and MaskCO.

  3. Recent diffusion solvers are not sufficiently discussed. Re-noising a solution and denoising it again is already the test-time search of T2T and Fast T2T. DEITSP (KDD

  1. also alternates noising and denoising, so the major novelty of this method still lies in the learned latent space. Latent Guided Sampling (ICML 2026) also learns an instance-conditioned latent space for routing. There are also some more recent diffusion-based solvers, such as EDISCO (NeurIPS 2026), which builds E(2)-symmetry into the diffusion model for TSP and CVRP and eliminates the need for training data augmentation.
  1. The results reporting is incomplete. The baseline rows in Tables 1 and 2 match GenSCO's published tables exactly, so they appear to be directly quoted. This could be stated, because Appendix F says the repair operators are shared with all neural baselines. Results are averaged over three seeds, but no variance is reported. The training and data generation costs are not given.

  2. The generalization of the method is not sufficiently reported. All routing instances use uniform distribution coordinates. I would be interested to see the performance under different distributions from the one used in training. For example, the explosion and implosion distributions, as reported in GLOP (AAAI 2024) and EDISCO (NeurIPS 2026). Also, every model is tested only at its training size. There are no cross-size or real TSPLIB results, which many existing diffusion-based solvers report. It would also be helpful to show the method’s performance under worse or less training data, since the training label cost is a very important concern for diffusion-based methods.

Questions for authors

How large is the gain from the latent space against a parameter-matched baseline with discrete noise?

How do the results change without 2-opt, with one run instead of eight augmented runs, and with fewer or lower-quality labels?

How often do decoded solutions violate the constraints, and what share of the run time does the repair take?

How do memory and time grow beyond 1,000 nodes? Does the latent space transfer across sizes and distributions?

8 comments
AuthorsOpenReview ↗

Response to Reviewer yoAe (Part 1/6)

Thank you for your careful review and for highlighting the gains from the learned latent space on TSP and MIS. We appreciate your specific suggestions on parameter matching, routing coverage, and generalization. They help us test the contribution of the learned representation against stronger baselines and clarify the scope of our evaluation.

W1 & Q1. Contribution of the continuous latent space under parameter matching.

Thank you for suggesting a parameter-matched baseline with discrete noise. Table 5 compares continuous generation in the original solution space and in the learned latent space using the same denoiser backbone. Appendix G.1 adds two discrete baselines in the original solution space, one matched to the denoiser’s parameter count and the other matched to the full LCO-Diff model, including the VAE.

The VAE adds a training stage devoted to representing and reconstructing given solutions. The denoiser learns to generate new candidates. Matching denoiser parameters therefore compares candidate generators of similar size. Matching total parameters assigns the VAE’s share of the parameter budget to the baseline’s denoiser, giving it a larger candidate generator. We report both comparisons to test whether the gains persist under either way of allocating the parameter budget.

LCO-Diff achieves lower gaps than both discrete baselines on TSP-500 and MIS-RB at all three reported refinement budgets. At C=64C=64, with total parameters matched, the gap drops from 0.0047% to 0.0012% on TSP-500 and from 2.66% to 0.12% on MIS-RB. One possible explanation for the larger gain on MIS is that high-quality independent sets on the same graph can differ substantially in which nodes they select. Improving a candidate can therefore require coordinated changes across several nodes. A continuous representation that preserves solution structure may help the denoiser propose such changes.

TSP-500

C=8C=64C=256
Raw-space Discrete Diffusion (Denoiser-parameter-matched)0.0306%, 9s0.0093%, 56s0.0041%, 3m36s
Raw-space Discrete Diffusion (total-parameter-matched)0.0171%, 11s0.0047%, 1m4s0.0025%, 4m4s
Raw-space continuous diffusion0.0665%, 10s0.0294%, 32s0.0140%, 2.0m
LCO-Diff0.0065%, 8s0.0012%, 38s0.0006%, 2.4m

MIS-RB-[200-300]

C=8C=64C=256
Raw-space Discrete Diffusion (Denoiser-parameter-matched)4.50%, 23s2.84%, 3.1m1.94%, 12.4m
Raw-space Discrete Diffusion (total-parameter-matched)4.41%, 46s2.66%, 6.1m1.83%, 24.3m
Raw-space continuous diffusion7.03%, 23s4.36%, 3.1m3.42%, 12.3m
LCO-Diff0.75%, 26s0.12%, 3.3m0.06%, 13.1m
AuthorsOpenReview ↗

Response to Reviewer yoAe (Part 2/6)

W2. Clarification for that solution-space methods's ability of expressing routing problems & CVRP Baselines.

Thank you for raising these concerns about our routing evaluation and for pointing us to the CVRP results of MaskCO and NExCO. The main question in this work is how a learned continuous latent space can improve candidate generation and test-time refinement for combinatorial optimization. Indeed, we use TSP and MIS as our core benchmarks because they represent edge-selection and node-selection problems, respectively. This pair is also used in representative previous works like DIFUSCO, T2T, and Fast T2T. For other routing problems, we primarily include CVRP and TSPTW to test whether the same latent-space procedure works under capacity and time-window constraints, respectively.

We apologize for the imprecise wording. The phrase "cannot natively express" was a misstatement that appears once, in the experiments section, and it does not reflect our actual position: what we meant is that solution-space continuous diffusion struggles to handle routing problems, which is also how the setup text of Sec. 4 already phrases it ("two problem classes that prior solution-space diffusion solvers struggle to handle"). The sentence has been corrected in the revised manuscript, and the statement in Table 3/4 now reads: "Tables 3 and 4 evaluate routing, the problem class that solution-space continuous diffusion struggles to handle." This is also consistent with our motivation to improve continuous diffusion for CO problems via learned latent space.

For CVRP baselines, we have added POMO, POMO+PO [3], BQ-NCO, LEHD, NeuOpt, and MaskCO to Table 3 of the revised manuscript, each under the recommended setting of its original paper, evaluated on the same CVRP-100 test set and the same HGS reference as the existing rows; App. G.2 lists the configurations and the full budget ladders. For your convenience, we also reproduce the results below.

Obj.GapTime
POMO (augx8)15.7411.231%7s
POMO+PO (augx8)15.8231.753%11s
BQ-NCO (bs16)15.7901.544%1.2m
LEHD (RRC 100)15.6750.808%1.7m
LEHD (RRC 1000)15.6170.431%15.4m
NeuOpt (D2A=5, T=10k)15.5820.208%1h46m
MaskCO (T=640)15.5860.231%40s
MaskCO (T=1280)15.5780.182%1.3m
MaskCO (T=2560)15.5720.139%2.6m
MaskCO (T=5120)15.5670.109%5.2m

W3. Discussion on recent diffusion solvers (DEITSP, LGS-Net, EDISCO).

Thank you for bringing these works to our attention. All three are now discussed in the Related Work of the revised manuscript.

  • DEITSP. Alternating noise addition and removal is a mechanism shared with our renoise cycle, but the space matters: under the same backbone, data, and budget, running it in the solution space leaves gaps more than 8×8\times larger at every budget (Table 5). This isolates the gain that the learned latent space brings to continuous diffusion.
  • LGS-Net. Its instance-conditioned latent is in line with our instance-conditioned VAE, but it searches the latent with an external MCMC procedure, whereas we let the learned denoiser itself model and sample the latent distribution.
  • EDISCO. Its E(2)-equivariant backbone is an architecture-level contribution, orthogonal to our work on the diffusion space, and could be adopted in our method to scale to larger Euclidean instances.
AuthorsOpenReview ↗

Response to Reviewer yoAe (Part 3/6)

W4. More complete report.

Thank you for the suggestions. The requested details are supplemented in the revised manuscript.

  • Quoted baselines. The baseline rows in Tables 1 and 2 that are taken directly from GenSCO's published tables are now marked with a dagger (†\dagger) and explained in the table captions, and the shared-operators sentence of App. F now states explicitly that the daggered rows are quoted from GenSCO and use that paper's post-processing. This does not affect the fairness of the comparison: our evaluation and GenSCO's evaluation both run on a single NVIDIA RTX 4090.
  • Variance. App. H now reports the per-seed results behind every reported objective (Table 16, seeds 0/1/2) together with the sample standard deviation. The across-seed standard deviation stays below 0.01% of the mean on TSP-500, TSP-1000, CVRP-100, and TSPTW-50, and below 0.25% on the MIS instances.
  • Training cost. Measured on a single NVIDIA RTX 4090 (App. H), the embedder stage takes 2.9h on TSP-500 and 3.5h on TSP-1000, against 27.7h and 31.0h for the denoiser, so the embedder is about one tenth of the denoiser stage; it also does not start from scratch at every size, thanks to the warm starts of Table 11.
  • Data generation cost. Most of the datasets we use are public and can be found in the GenSCO repository. Only a small fraction of the experiments introduced during the rebuttal requires data generation, such as generalization on the explosion and implosion distributions. Generating the corresponding test sets took 2.9 min and 7.9 min, respectively, on a machine with a 64-core Intel(R) Xeon(R) Platinum 8468.

W5. Explosion and Implosion distributions. Cross-scale generalization. TSPLIB. Worse or less training data.

Thank you for suggesting these evaluations. We tested LCO-Diff under shifts in the instance distribution and problem size, on real-world TSPLIB instances, and with fewer or lower-quality training labels.

Explosion and Implosion Distributions. We conducted this experiment on TSP-500, using the data-generation scripts provided by EDISCO [4] to generate 128 test instances for each test distribution. The generalization results of LCO-Diff remain highly compatitive.

TSP-500 (explosion)TSP-500 (implosion)
C=320.0087%0.368%
C=1280.0058%0.276%
C=5120.0043%0.230%

Cross-scale generalization.

We conducted cross-scale generalization experiments on TSP-500 and TSP-1000 (C=512). At C=512C=512, LCO-Diff achieves a gap of 0.0747% when trained on TSP-500 and tested on TSP-1000, and 0.0034% in the reverse direction. Both are much lower than the corresponding published Fast T2T gaps of 0.33% and 0.58%.

Test\TrainTSP-500TSP-1000
TSP-5000.0004%0.0034%
TSP-10000.0747%0.0080%

TSPLIB. On the evaluated TSPLIB instances with 200–1,000 nodes, LCO-Diff achieves the lowest aggregate gap among the compared methods. Its 0.207% gap is about 42% lower than GenSCO’s and 78% lower than Fast T2T’s. The per-instance results are given in Appendix I.1.

TSPLIB-[200-1000]
DIFUSCO2.86%
T2T1.51%
Fast T2T0.96%
GenSCO0.36%
LCO-Diff0.207%

Worse or less training data.

For less training data, we conducted experiments on MIS-RB-[200-300] using 1/2 (45,000 instances) and 1/4 (22,500 instances) of the dataset, with results as follows.

MIS-RB-[200-300]

C=4C=16C=64
1/4 dataset2.07%0.97%0.43%
1/2 dataset1.35%0.55%0.18%
Full dataset1.12%0.43%0.12%

As can be seen, halving the dataset leads to only a slight decrease in performance, and even with one quarter of the data the model still delivers reasonable results, indicating that the method is reasonably robust to a reduction in labeled data.

For worse training data, we trained on TSP-100 using a dataset labeled by 128-run 2-opt, following the setting in Table 3 of GenSCO. This data-generation algorithm achieves 1.920% on the test set.

TSP-100 with suboptimal training data

C=32C=128C=512
LCO-Diff0.0191%0.0051%0.0009%

Notably, at C=512 on TSP-100, LCO-Diff achieves a gap of 0.0009%, which is far better than the quality of the data source. We note that GenSCO reports 0.014% under this setting.

Comments on the paper

2 comments

Dear Reviewers, The authors have now submitted their responses to the reviews. There is only a limited amount of time left for you to review their replies and provide any further comments.

Your feedback is crucial to ensure that the review process proceeds smoothly. We would greatly appreciate it if you could share your reactions before the discussion period closes.

Thank you very much for your work. Best regards.

AuthorsOpenReview ↗

General Response

We thank the chairs and all reviewers for their time and constructive suggestions, and we are encouraged that the reviewers find the idea "relatively novel in this field" (yoAe) and the method "sound" (yu4z), applied to a "wide variety of combinatorial optimization tasks" (yu4z), with a renoise cycle that requires "no new operators or retraining" (Dg5a) and gaps "lowered by more than eightfold on TSP-500 and on RB graphs" (yoAe). The primary concerns are whether the gains come from the learned latent space rather than from the extra parameters or from the generic flow machinery, and how much novelty this adds. The table below summarizes each concern, the evidence we added, and where the change sits in the revised manuscript.

All changes in the revised manuscript are marked in blue.

Main concernResponse: what we added or clarifiedFinding: what the evidence showsReviewer comments addressed, and location in the revised manuscript
1. Attribution of the gains to the learned latent spaceTable 5 changes only the space, with the backbone, data, budget, and decoding interface fixed. App. G.1 adds raw-space discrete diffusion matched to the denoiser or to the total parameters.With the parameter counts matched, the latent space still gives the lower gaps: more than 8×8\times smaller at every budget than raw-space continuous diffusion, and lower than the discrete baselines matched to the total parameter count, 0.0047% to 0.0012% on TSP-500 at C=64C{=}64.yoAe: W1, Q1. Sec. 4.2 (Table 5), App. G.1 (Table 14).
2. Notation, figures, and pseudocodeDefined x\mathbf{x}, s\mathbf{s}, AsA_{\mathbf{s}}, and qφq_\varphi before use, wrote out the expectations in Eqs. (3) and (4), separated φ\varphi, ψ\psi, and θ\theta, redrew both figures, and aligned Alg. 1 to 3.Reviewer yu4z confirmed that the notational problems are resolved.yu4z: W1, W2, Q2, Q3.2. Sec. 3.1, Eqs. (3) and (4), Figs. 1 and 2, Alg. 1, App. C.
3. Generalization across distributions, sizes, and labelsAdded the shifted distributions, cross-scale and TSPLIB tests, training with half, a quarter, and lower-quality labels, reconstruction transfer tests, and scaling beyond 1,000 nodes.The model stays accurate outside its training distribution and at unseen sizes: gaps of 0.0043 to 0.230% on the shifted distributions, 0.0747% and 0.0034% across sizes, and 0.208% on TSPLIB-[200-1000] at C=256C{=}256. With a quarter of the labels, or labels 1.92% off optimal, the gap reaches 0.0009%, and the VAE reconstruction transfers at near 100%.yoAe: W5, Q4.1 and Q4.2; yu4z: Q3.1. App. I.1 (Tables 17 to 19), App. I.2 (Tables 20 and 21), App. L, App. M.
4. Routing coverage and baselinesCorrected the wording on routing, and added six neural baselines to Table 3, each under the recommended setting of its paper.LCO-Diff reaches 0.11% at C=512C{=}512 in 8.2 min on CVRP-100, comparable to the strongest neural baseline, while previous latent-space solvers stay at 0.53% and above.yoAe: W2. Sec. 4.1 (Table 3), App. G.2 (Table 15).
5. Novelty and the problem-agnostic claimClarified that the contribution is the interface, not the flow machinery, discussed DEITSP, LGS-Net, EDISCO, and PT-Denoise, defined latent-space diffusion (Sec. 2.2) with rectified flow as its concrete instantiation, and reported the cost of each training stage.A single Gaussian prior and one corruption rule cover the edge-, node-, and routing-structured problems, test-time scaling needs no new operator and no retraining, and ρ\rho is left as an inference-time choice; the embedder adds about a tenth of the denoiser training time, 2.9h against 27.7h on TSP-500.yu4z: W3, W4, Q1; yoAe: W3; Dg5a: W1 and W3. Sec. 2.1, Sec. 2.2, Sec. 3.3, App. E (Table 13), App. H.

Furthermore, we reported per-seed results with sample standard deviations, marked the baseline rows quoted from GenSCO, and gave the training and data generation costs (yoAe: W4; Tables 1 and 2 captions, App. F, App. H, Table 16). We added runs with 2-opt disabled, single-run evaluations against eight augmented runs at matched budgets and cycles, and the constraint-violation rates with and without repair (yoAe: Q2 and Q3; Dg5a: W2; Sec. 3.3, App. J, App. K).

We are pleased that the reviewers find the work valuable, and that all three scores now stand at 3. We thank the chairs and the reviewers for the careful reading and the constructive comments, which have strengthened the paper. We hope the additional experiments, clarifications, and revisions summarized above help address the concerns raised, and we sincerely appreciate the time and thought devoted to our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.