- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes a self-supervised framework for constrained neural combinatorial optimization using the LMOs in parallel. Instead of sequentially decomposing a neural prediction into feasible vertices, the network generates multiple query directions , which are independently passed through LMOs to obtain feasible candidates . The mean query $ x_\theta=\frac{1}{m}\sum_{i=1}^m q_i$ is then associated (but not decomposed) with a probability vector over the generated candidates by solving a regularized simplex-constrained quadratic program. Gradients are obtained from the corresponding KKT system without differentiating through the discrete LMO.
Critical strengths
-
Simple but useful parallelization idea: Independent LMO calls remove an important sequential bottleneck of previous decomposition-based methods. The inference procedure is especially efficient: generate feasible solutions in parallel and directly select the best candidate.
-
Broad empirical applicability: The framework is demonstrated on several structurally different combinatorial optimization problems. The reported experimental results are promising.
Critical weaknesses
-
The loss is not naturally a global function of alone: The actual state is the full query tuple , since and . Two query collections can have the same mean while generating completely different candidate sets . Therefore, the more faithful formulation seems to be , rather than a globally well-defined function . Proposition 1 establishes local gradient correctness when remains fixed, but this is weaker than establishing a globally meaningful extension over .
-
The mean aggregation introduces a large local nullspace and weak query-specific credit assignment: Within a region where is fixed, the loss depends on the queries only through . Therefore, for every . Any perturbation satisfying is thus locally invisible to the gradient. This defines an -dimensional nullspace. However, such zero-mean perturbations can substantially change individual queries and eventually move them across different LMO regions, thereby changing the generated candidates. Hence, the directions that control candidate diversity can be precisely the directions that receive no first-order training signal. So I think using some different aggregations may be important.
-
The geometric and probabilistic interpretation is weaker than in previous decomposition-based methods: In previous geometric approaches, the coefficients describe a probability distribution arising from a decomposition of the neural output itself. Here, the candidates are generated independently first, and the QP subsequently projects onto their restricted convex hull. There is no guarantee that is close to . If is far from this hull, the QP still returns a probability vector , but its interpretation becomes less convincing: it is merely the best regularized projection onto a potentially unrelated candidate set. This may weaken both interpretability and reliability of the training signal. I would like to see the residual reported and analyzed empirically.
Some Minor Suggestions:
-
The theoretical assumptions and some experimental oracle choices are not fully aligned: Proposition 1 assumes a deterministic, locally stable LMO with fixed tie-breaking, while the framework also allows approximate LMOs and some experiments use heuristic or approximate oracle procedures. It would be helpful to state clearly which experimental settings satisfy the assumptions of Proposition 1 and which fall outside the current theoretical guarantee.
-
In line 44, the "both..and" seems confusing, I guess it's a typo?
-
State the representation power of the method directly, i.e., share the same optimal solution as the original problem.
Questions for authors
-
How do the authors interpret the -dimensional zero-mean nullspace induced by ? In particular, what mechanism provides query-specific credit assignment for changing candidate diversity? (Randomness? different aggregations?)
-
How large is the projection residual during training? Is this quantity correlated with training stability or solution quality?
-
I would like to increase my score if two of the critical weaknesses above are addressed. I think it serves as a good empirical framework and would like to recommend acceptance if the weaknesses are addressed.
6 comments
Response to Reviewer 2USD - II
The mean aggregation introduces a large local nullspace and weak query-specific credit assignment: Within a region where is fixed, the loss depends on the queries only through . Therefore, for every . Any perturbation satisfying is thus locally invisible to the gradient. This defines an -dimensional nullspace. However, such zero-mean perturbations can substantially change individual queries and eventually move them across different LMO regions, thereby changing the generated candidates. Hence, the directions that control candidate diversity can be precisely the directions that receive no first-order training signal. So I think using some different aggregations may be important. How do the authors interpret the -dimensional zero-mean nullspace induced by ? In particular, what mechanism provides query-specific credit assignment for changing candidate diversity?(Randomness? different aggregations?)
We agree that mean aggregation introduces a local nullspace. However, this does not imply that the network receives a zero gradient or that different queries cannot explore distinct candidate regions. When remains locally fixed, the chain rule gives
and consequently,
\frac{1}{m}\sum_{i=1}^{m} \left(\frac{\partial q_i}{\partial\theta}\right)^\top \nabla_{x_\theta}F_V(x_\theta).$$ Thus, **although the gradients with respect to individual queries are identical, their contributions to the network parameter gradient can differ through their respective Jacobians**. Moreover, Gaussian sampling and Sobol directions encourage exploration of different LMO regions, allowing diverse feasible candidates to be generated. Importantly, **the mean is a design choice, not a restriction of our framework**. As noted in Section 3, any differentiable aggregation rule $x_\theta=g(q_1,\ldots,q_m)$ can be used. For instance, a weighted aggregation $x_\theta=\sum_i w_iq_i$ would provide different gradient weights to individual queries. More generally, reducing $m$ query vectors to a single $n$-dimensional representation necessarily introduces a local nullspace, regardless of the aggregation rule. In practice, **simple averaging already achieves strong empirical results across our benchmarks**, without additional complexity. We have updated the manuscript to clarify these points and discuss alternative aggregations as a direction for improving query-specific credit assignment. To further assess the reliability of these design choices, we conducted additional controlled experiments examining the effects of removing Gaussian sampling and changing the aggregation rule. We implement a direct variant of our method, in which the neural network directly outputs the query vectors without Gaussian sampling. This variant tests whether the learned query generator itself can maintain candidate diversity without relying on injected Gaussian noise. For learnable aggregation, a shared scoring network assigns a scalar score to each query based on its normalized statistics. Softmax converts these scores into weights, giving $x=\sum_i w_i(Q)q_i$. The scorer adds 96 trainable parameters and is initialized to uniform weights, so training starts from mean aggregation. It is optimized jointly with the query generator, introducing query-dependent gradient paths through both the weights and the queries. | Query generation | Aggregation | MC coverage ↑ | QAP mean class gap (%) ↓ | |---|---|---:|---:| | Gaussian | Mean | 29932.85 | 26.39 | | Gaussian | Learned | **30045.10** | **25.84** | | Direct | Mean | 29950.36 | 26.61 | Learnable aggregation improves MC coverage by 0.375% and reduces the QAP gap by 0.550% relative to mean aggregation. Direct variant achieves slightly higher MC coverage than Gaussian generation, But scored a worse QAP gap. These results demonstrate the practicality of alternative aggregations. We favor Gaussian query generation for its scalability and flexible candidate budget. Once the network predicts the distribution parameters, additional queries can be generated through parallel sampling while reusing those parameters and the encoded instance representation. This allows the candidate budget to grow without adding a separate learned output for every additional query, making the approach well suited to large instances and large candidate pools. We retain mean aggregation as a practical trade-off between solution quality and time. Mean aggregation requires only a simple reduction, whereas learnable aggregation adds a scoring network. Given the modest quality gains observed here, mean aggregation provides an efficient default.Response to Reviewer 2USD - III
The geometric and probabilistic interpretation is weaker than in previous decomposition-based methods: In previous geometric approaches, the coefficients describe a probability distribution arising from a decomposition of the neural output itself. Here, the candidates are generated independently first, and the QP ... that is close to . If is far from this hull, the QP still returns a probability vector , but its interpretation becomes less convincing: it is merely the best regularized projection onto a potentially unrelated candidate set. This may weaken both interpretability and reliability of the training signal. I would like to see the residual reported and analyzed empirically.
Our approach constructs a probability distribution over feasible candidates generated in parallel, without requiring an exact decomposition of . The coefficients remain valid probabilities since , regardless of whether lies inside . Moreover, Proposition 1 does not require the projection residual to be small.
This also removes a restriction of previous decomposition-based methods, such as Karalias et al. (2025), which require the neural network output to lie within the feasible polytope. Enforcing this condition can require additional, problem-specific constructions, particularly for more complex polytopes such as matroid and spanning-tree polytopes. Our framework avoids this requirement while preserving feasibility through the LMOs.
Importantly, the projection residual is not necessarily indicative of solution quality. For an exact LMO, scaling all queries by leaves the generated candidates unchanged, i.e., , while the residual can grow arbitrarily large. Conversely, a small residual does not guarantee high-quality candidates. Our method directly optimizes a surrogate over the generated solutions during training and selects the best feasible candidate at inference.
We have updated the manuscript to clarify this interpretation and the role of the projection residual in our framework.
An aggregate far from the candidate hull can still correspond to queries that lead the LMO to high-quality feasible solutions. Likewise, an aggregate close to or inside the hull can correspond to solutions with different objective values. The geometric position of therefore provides limited information about the optimization outcomes associated with the queries.
To assess whether training guides the queries toward better feasible solutions, we track the mean objective value of their LMO solutions together with our combinatorial loss. Let . We compute
The mean LMO objective gives each query equal weight and measures the average quality of the generated feasible solutions. The loss weights these same solutions using the coefficients returned by the QP. Tracking both quantities allows us to examine how optimizing the weighted objective translates into improvements in the quality of the query set.
Figures 6 and 7 in the updated draft show these quantities together with the projection residual throughout training. For MC, MaxCut, and DkS, the plotted weighted objective corresponds to the negative combinatorial loss, so higher values indicate better solutions. For QAP, it corresponds to the combinatorial loss itself, with lower values indicating better solutions. Across these experiments, the mean LMO objective quality improves alongside the weighted objective under different residual behaviors. This provides empirical evidence that the training updates guide the queries toward better feasible solutions, including when the projection residual remains large or fluctuates.
- MC: Mean coverage and the negative combinatorial loss increase and then stabilize, while the projection residual increases before leveling off.
- MaxCut: The mean normalized cut and the negative combinatorial loss improve overall, while the projection residual decreases toward zero.
- DkS: Mean density and the negative combinatorial loss increase, while the projection residual also increases overall.
- QAP: Both mean cost and the combinatorial loss decrease, while the projection residual shows a substantial overall increase.
These observations provide empirical support that the training signal improves the objective quality of the solutions associated with the network's queries. Such improvements occur across different residual behaviors, consistent with the theoretical result accommodating aggregates both inside and outside the polytope.
Response to Reviewer 2USD - I
We thank the reviewer for the thoughtful feedback and positive assessment of our work. We updated the manuscript significantly and address the reviewer's concerns in detail below.
We thank the reviewer for this observation. We agree that the full training objective is more precisely written as L(Q)=FV(Q)(x(Q)). This dependence is already reflected in our notation FV(xθ) in Eq. (4), and Section 3 explicitly describes our construction as a local surrogate extension. We do not claim a globally defined extension depending only on xθ.
Importantly, under the local stability assumption in Proposition 1, V(Q) remains constant in a neighborhood almost everywhere. Therefore, the gradient of the full objective satisfies ∇qiL(Q)=m1∇xFV(Q)(x(Q)). Hence, our KKT-based computation gives the exact gradient of the actual training objective almost everywhere, without requiring a global extension over xθ.
We have updated the manuscript to explicitly state the query-dependent objective and clarify the scope of Proposition 1.