acceptodds
Under review as a conference paper at ICLR 2027

Autoregressive Differentiable Method for Integer Programming

Abstract

We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
differentiable integer programming, transformers, Gumbel-softmax, quantum-inspired algorithms

Reviews

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

The paper proposes ADIP, a two-phase method for improving a feasible solution of a 0-1 quadratic integer program, tested on the quadratic knapsack problem (QKP). It works per instance rather than amortized over a dataset. Phase 1 runs an open-source solver (SCIP, HiGHS, CP-SAT or CBC) for 500 seconds to get a feasible incumbent, then trains a two-layer causal transformer under teacher forcing to reproduce that incumbent, using smoothed targets of 0.001 and 0.999 to avoid logit saturation. Phase 2 takes the shared transformer weights themselves as the optimization variables. A relaxed binary vector is generated autoregressively with Gumbel-softmax at fixed temperature 0.5 using a straight-through estimator, and the penalized objective, meaning the relaxed quadratic objective minus lambda times the summed ReLU constraint violation, is maximized with Adam for at most 2000 steps. Every step also hard-decodes the relaxed vector, tests feasibility, and keeps the best feasible solution seen. Claimed contributions are four. First, the autoregressive reparametrization itself. Second, the ADIP pipeline. Third, theory: NP-completeness of incumbent improvement (Theorem 1), combinatorial expressivity of the parametrization (Proposition 1 and Corollary 1), a sufficient penalty for binary feasibility (Proposition 2), low-temperature Gumbel-softmax asymptotics (Proposition 3), an induced decision-space gradient kernel equal to the Jacobian times its transpose (Theorem 2), and a rescaling symmetry showing that functionally identical transformers can induce different dynamics (Theorem 3). Fourth, experiments on random QKP instances at n equal to 400, 1000 and 10000 under matched wall-clock budgets (Table 1), plus a tunneling-like barrier-crossing diagnostic (Table 2, Figure 3). Validation as presented is a single benchmark family, random dense QKP, on a single CPU-only laptop, with improvement reported as a percentage relative to the matched solver objective at 1000 seconds, using 100 runs at n = 400 and 10 runs at n = 1000 and 10000.

Critical strengths

Strength 1, the central reframing is novel and worth stating. Making the shared parameters of an autoregressive model, rather than the relaxed decision vector, the variables of the optimization is a real conceptual move, and the clean expression of the induced flow x~˙=Kθ∇x~Fλ(x~)\dot{\tilde{x}} = K_\theta \nabla_{\tilde{x}} F_\lambda(\tilde{x}) with Kθ=JθJθ⊤⪰0K_\theta = J_\theta J_\theta^\top \succeq 0 in Theorem 2 is the right formal object for it. This matters to my assessment because it is the only part of the paper that would survive a rejection: a reader can take the kernel view and ask, separately, whether it buys anything empirically. I would encourage the authors to keep this framing and build a defensible empirical study around it. Strength 2, the positioning against the closest prior work is unusually well done. Sections 2 and A.1 distinguish ADIP from DiffILO (an explicit Gumbel-softmax relaxation rather than a surrogate loss containing a discontinuous indicator) and from constrained tensor networks (no architectural feasibility encoding, hence no exponential parameter blow-up in the number of linear constraints), and they correctly attribute the QKP benchmark and the tunneling analogy to Lopez Piqueres and Chen (2025) and Leng et al. (2023) rather than claiming them. This matters because it means the contribution claim is not inflated by misattribution: the problem here is the evidence, not the credit assignment.

Critical weaknesses

W1, fatal. The experiments cannot have been run as described. With a 500 second cap, up to 2000 steps and all runs CPU-only single-threaded, each step needs a full rollout of n bits plus backpropagation and about n squared penalty work. At n = 10000 that is roughly 100 million operations at every step, so hours per instance, not 500 seconds. W2, fatal. The improvement metric divides by the matched solver objective, which is zero in five of eight rows of Table 1. Those rows carry the "infinity" and "100 percent of runs" claims, so the headline result rests on a ratio against zero. W3, fatal. The objective values contradict the stated generator. With Q entries uniform on minus 5 to 5 and capacity at one quarter of total weight, a random feasible solution already has expected objective about 31000 at n = 400, while Table 1 reports about 2100, one to two orders of magnitude lower. W4, major. The control that would isolate the claimed mechanism is missing: no direct relaxed gradient ascent at equal budget, no standard primal heuristics such as local branching or RINS, and no control for the tunneling diagnostic. W5, major. The theory does not apply to the algorithm run. Theorem 2 assumes continuous-time gradient flow but the implementation is Adam with a straight-through estimator and injected noise; Proposition 2 needs a penalty above 250 million at n = 10000 while 500 is used, and Proposition 3 assumes zero temperature while 0.5 is used. W6, major. The statistics are too thin. Win rates of 100 and 90 percent rest on 10 runs with no confidence interval or paired test, and Figure 2 uses a broken axis and transformed time scale that make it uninterpretable. W7, moderate. The artifact cannot be verified: every request to the anonymous repository returned HTTP 401, so no code or results could be inspected.

Questions for authors

Q1. Were the n = 10000 rows of Table 1 and the five "infinity" entries produced by the exact protocol of Section 5.1 and Appendix A.2, that is one process on one M4 Max laptop with solver threads, BLAS and OpenMP pinned to 1, a 500 second training cap and at most 2000 steps? If yes, please give the measured time per step, the number of steps actually achieved, and a profiling log for one n = 10000 instance. If not, please say exactly which parts were run differently.

Q2. Each Phase-2 step forms the constraint products and the quadratic objective and hard-decodes and checks an n-vector, which is about n squared work, that is 100 million operations at n = 10000, repeated up to 2000 times, plus a sequential rollout of 10000 steps with a backward pass, all CPU-only and single-threaded. Please report the FLOPs and wall-clock time you measured, or explain how the budget closes.

Q3. Equation 12 divides by the matched solver objective, which is zero in five of eight rows. What do the "infinity" entries and the 100 percent win-rate statements communicate about solution quality? Please report absolute per-instance objectives for ADIP and the matched solver in those rows, with best-known or optimal values.

Q4. With Q entries in minus 5 to 5 the objective can be negative and the all-zero vector is feasible with value zero. In how many n = 10000 runs was the matched solver's 0.00 actually optimal, or better than what ADIP returned? Please report the fraction of instances whose optimum is at most zero.

Q5. Under the identical 500 second and 2000 step budget, what does ADIP achieve when the same computation goes to: (a) direct projected gradient ascent in the relaxed variables; (b) a standard primal heuristic such as local branching, RINS, polishing or random restart with repair; (c) simply running the solver beyond 1000 seconds. Without this, the distinction between the Jacobian kernel and the identity is untested.

Q6. On instances with Q entries uniform on minus 5 to 5 and capacity at one quarter of total weight, a uniformly random feasible solution has expected objective about 0.1 n, roughly 31000 at n = 400, yet Table 1 reports about 2100. Please explain the gap: were the Q entries rescaled, was only a subset used, were only diagonal or block terms optimized, or were the instances different from those described?

Q7. You define tunneling as a relaxed iterate whose direct-gradient endpoint lies in a different basin from the incumbent's. On a non-convex landscape almost any large perturbation does this. What fraction of random perturbations, matched in norm to your iterates, also land in a different basin, and does a basin change correlate with a better hard-decoded objective? Please also give the selection rule for the four representative trajectories in Table 2.

Q8. Proposition 2 needs a penalty larger than about 2.5 n squared, that is 400000 at n = 400 and 250 million at n = 10000, but you use 100 and 500, and the proposition covers binary points only. What then keeps relaxed iterates feasible, and what fraction of your hard-decoded candidates were infeasible, and by how much?

Q9. The temperature is fixed at 0.5 with no annealing, while Proposition 3 concerns the zero-temperature limit. What temperature is used at decoding time, how is the straight-through estimator combined with the injected Gumbel noise, and what fraction of relaxed values over a run lie within 0.1 of zero or one?

Q10. Theorem 2 concerns continuous-time gradient flow, but you run Adam with a straight-through estimator, injected noise and plateau early stopping. Can you state any guarantee that survives this, and does anything you prove constrain the finite-step trajectory that produced your results?

Q11. Theorem 3 rescales the query matrix by c and the key matrix by 1 over c. What are the observed scales of those two matrices before and after Phase 2 in your trained models? Is the trajectory actually moving along such directions, or is Theorem 3 about a symmetry the optimizer never approaches?

Q12. Proposition 1 is proved by approximating a constant map, and the step claiming that some input initiates an autoregressive rollout close to the target does not follow from the cited universal approximation theorem. Please give a construction for a causal autoregressive model over the alphabet zero and one that represents an arbitrary target under threshold decoding, or restate the proposition.

Q13. Corollary 1 asserts NP-hardness of finding parameters whose hard-decoded output beats a threshold while remaining feasible. Since Proposition 1 only guarantees representability, please clarify that the reduction needs the hard-decoded map to be surjective onto the feasible set, with no approximation error at the threshold.

Q14. HiGHS, CBC and CP-SAT receive a Fortet or McCormick model with about n squared auxiliary binaries, roughly one million at n = 1000 and 100 million at n = 10000. Is it fair to report relative improvements against solvers handicapped this way, and is linearization time included in their budget? Please also justify single-threaded solver baselines when the summary claim concerns state-of-the-art open-source solvers in general.

Q15. The paper attributes the advantage to the room for improvement the solver leaves. What happens with a seed budget of 3600 seconds, or with a target-gap stopping rule, at n = 400 and n = 1000? If the advantage disappears once the seed solver has a realistic budget, the conclusion changes qualitatively.

1 comment

We have carefully reviewed your comments, and we believe the extent of your criticisms does not warrant such a low rating. We give more details below by addressing and/or discussing each of your concerns.

"W1, fatal. The experiments cannot have been run as described. ": The method is autoregressive so it has a fixed network size and goes through the sequence of bits autoregressively, plus it uses sparse attention as stated l. 792 in both the revised and the initial submission, so each gradient update scales as nn, not as n2n^2. We do not see what you may mean by "about n squared penalty work", but if you see another component of our method where a n2n^2 dependence may arise, please let us know and we would be happy to clarify why it is not the case.

"W2, fatal. The improvement metric divides by the matched solver objective, which is zero in five of eight rows of Table 1.": the objective is zero in 3 out of 9 rows (not 5 out of 8 rows), and the ∞\infty convention is explicitly explained and acknowledged l. 787 in both the revised and the initial submission.

"W3, fatal. The objective values contradict the stated generator. With Q entries uniform on minus 5 to 5 and capacity at one quarter of total weight, a random feasible solution already has expected objective about 31000 at n = 400, while Table 1 reports about 2100, one to two orders of magnitude lower. ": With Q entries uniform between -5 and 5, a random feasible solution has expected objective 0 because the distribution is centered. Could you please clarify where your number 31,000 comes from ?

"W4, major. The control that would isolate the claimed mechanism is missing: no direct relaxed gradient ascent at equal budget, no standard primal heuristics such as local branching or RINS, and no control for the tunneling diagnostic.", we wish to draw your attention on the primary contribution and scope of our paper. We claim to have developed a method that beats state-of-the-art open-source integer-programming solvers on a non-trivial problem class (non-convex quadratic knapsack). To someone who is familiar with the practice of integer programming, we would argue that this is already a strong claim. We have therefore focused our evaluation on state-of-the-art open-source integer-programming solvers to establish a rigorous baseline. Methods such as "direct relaxed gradient" and "standard primal heuristics" are superseded by the advanced heuristics already integrated into modern solvers, which include sophisticated local search techniques starting from feasible incumbents. In our opinion, there is no need to re-establish that non-convex quadratic knapsack is a hard problem that weak/trivial baselines cannot solve.

All in all, we have discovered a method that outperforms state-of-the-art open-source integer-programming solvers on a non-trivial problem class. The method is an autoregressive reparameterization and the paper investigates why it helped. We think the autoregressive aspect plays a role here (and this was the motivation for using it) because it allows one to scale to larger instances without changing the size of the input space, a property that standard integer-programming solvers do not leverage: this is well-known and does not require to be re-established. We have added a sentence to clarify this l. 35 in the revised submission. Neural reparameterization changes the loss landscape and therefore offers new dynamics which can explain why we are able to outperform solvers, which we are conveying in our theoretical analysis.

"W5, major. The theory does not apply to the algorithm run." this is a fair statement, and we have included a sentence to acknowledge this l. 296 in the revised submission. However, we note that idealizing the setting of the experiments to derive theoretical results is customary, e.g. gradient flow dynamics is believed to still capture non-trivial insights about actual stochastic gradients, e.g. Du et al. (2018), Jacot et al. (2018), Chizat and Bach (2020).

"W6, major. The statistics are too thin. Win rates of 100 and 90 percent rest on 10 runs with no confidence interval or paired test, and Figure 2 uses a broken axis and transformed time scale that make it uninterpretable.": Win rates of 100% and 90% are large enough to already be statistically significant with 10 independent runs to establish a non-trivial improvement. For example the probability of obtaining 100% win rate if the actual probability of win was below 50 % is already well within the 95% confidence interval. Could you please clarify what you mean by "broken axis and transformed time scale make it uninterpretable"?

"W7, moderate. The artifact cannot be verified: every request to the anonymous repository returned HTTP 401, so no code or results could be inspected.": Please double check, the anonymous repo is available.

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

The paper proposes ADIP, a per-instance primal-improvement method for binary quadratic programs max xᵀQx s.t. Ax ≤ b. A conventional solver (SCIP, HiGHS, CP-SAT, CBC) runs for T_seed = 500 s to produce an incumbent x^inc. In Phase 1, a small causal transformer is trained by teacher forcing to reproduce x^inc, using ε-smoothed targets. In Phase 2, the transformer weights are optimized directly on a Lagrangian-penalized relaxed objective, with x̃ produced by an autoregressive straight-through Gumbel-softmax rollout; every hard-decoded candidate is checked for feasibility and the best feasible one is returned. The theoretical results cover:

  • hardness of incumbent improvement (Thm 1);
  • surjectivity of the parametrization (Prop 1, Cor 1);
  • a sufficient penalty for binary feasibility (Prop 2);
  • low-temperature Gumbel-softmax gradient statistics (Prop 3);
  • the induced decision-space kernel K_θ = J_θJ_θᵀ (Thm 2);
  • a W_Q/W_K rescaling symmetry showing that the kernel depends on the parametrization (Thm 3).

Experiments on random dense, indefinite QKP instances (n ∈ {400, 1000, 10000}) compare ADIP with the same solver run for a matched 1000 s (Table 1) and examine "tunneling-like" basin changes (Section 5.3).

Critical strengths
  1. The paper separates feasibility discovery (the solver) from neural improvement (ADIP). This modest positioning, as a primal-improvement add-on rather than an end-to-end solver, is sensible.
  2. Solvers run single-threaded, thread counts are controlled, and the matched baseline continues the same solver for T_seed + T_train (App. A.2).
  3. This covers Prop 3's moments, the Jacobian scaling in the proof of Thm 3, and the gradient-realization construction. Thm 2 is a clean way to state how parameter-space optimization changes the decision-space dynamics.
Critical weaknesses
  1. The paper's stated question is whether the autoregressive parametrization "exposes useful optimization directions that differ from direct coordinate-wise movement" (Section 1).

    • Table 1. No experiment uses the same x^inc, straight-through Gumbel-softmax, λ, optimizer and budget with per-variable logits optimized directly (DiffILO-style), or a simple 1-flip/tabu local search from x^inc. The gains in Table 1 therefore cannot be attributed specifically to the transformer, as opposed to generic stochastic local improvement around the incumbent.
    • Tunneling (Section 5.3). A dense indefinite QP has very many local maxima, so any sufficiently large perturbation of x^inc would be expected to reach "distinct endpoints" (Table 2). A random-perturbation control at matched Hamming distance is needed. Thm 3 is a generic overparametrization symmetry: it shows the dynamics are parametrization-dependent, not that they are beneficial.
  2. The headline results overstate scalability and consistency.

    • n = 10,000. The abstract claims "consistent improvement … up to 10,000 binary variables". At n = 10,000, however, SCIP reports an objective of 0.00, the value of the trivially feasible solution x = 0, and ADIP reaches 60.21 ± 26.01 (Table 1). SCIP values are ≈2.1k at n = 400 and ≈5.1k at n = 1,000, which suggests that good solutions at n = 10,000 are orders of magnitude above 60. The "∞ %" improvement therefore reflects an empty baseline rather than solution quality.
    • Linearized solvers. The same applies to HiGHS/CBC at n = 1,000. The very large percentages at n = 400 (77–848 %) are relative to reformulations with O(n²) auxiliary product variables, which the paper itself notes become impractical as n grows.
    • "Consistent." ADIP beats matched SCIP in only 58 % of n = 400 runs (Section 5.2).
    • Statistics. n ≥ 1,000 uses only 10 instances each, without confidence intervals.
  3. The most closely related work is missing. Optimizing per-instance network weights on a relaxed QUBO-type objective and then rounding is established. Examples:

    • Schuetz et al., Nature Machine Intelligence 2022 (PI-GNN), and its critical follow-ups (Angelini & Ricci-Tersenghi 2023; Boettcher 2023). These show that such methods can lose to simple greedy heuristics.
    • Neural reparametrization of optimization variables (Hoyer et al. 2019).
    • Overparametrization as implicit preconditioning (Arora et al., ICML 2018), which is closely related to the mechanism behind Thm 2's K_θ.

    The novelty statement in Section 2 should be positioned against these works, ideally with a non-autoregressive network baseline.

  4. The theory does not match the experimental regime.

    • Prop 2. It requires λ > U_Q − f_inc, where U_Q ≈ n²·15/11 (≈2.2×10⁵ at n = 400), whereas the experiments use λ = 100/500. It also assumes integer b, whereas C = ¼Σwᵢ is generally not an integer. Yet Section 4.5 uses Prop 2 to explain why decoded solutions "remain feasible".
    • Other results. Thm 2 assumes gradient flow, not Adam. Prop 3 analyzes the soft sample, not the straight-through estimator. Prop 1 relies on the universal approximation result of Yun et al. (unbounded depth, full attention, deterministic outputs), not on the 2-layer banded-sparse model with Gumbel noise that is actually used.

    These gaps should at least be stated explicitly.

Questions for authors
  1. With the same x^inc, Gumbel/straight-through settings, λ, optimizer and budget, how does ADIP compare with directly optimized per-variable logits and with 1-flip/tabu local search? Do random perturbations at matched Hamming distance also produce many distinct basin endpoints?
  2. At n = 10,000, what objective does a simple greedy-plus-local-search heuristic reach? How many Phase-2 steps does ADIP actually complete within 500 s, and is the Phase-1 time included in T_train?
  3. In Fig. 4, the caption says "matched SCIP" while the title says "warm SCIP". Which baseline is used, and what are the win/tie/loss counts against matched SCIP at n = 400? Are the identical HiGHS/CBC n = 1,000 rows due to both starting from x^inc = 0?
  4. What fraction of hard-decoded Phase-2 candidates are infeasible, and how were λ and η₂ chosen for each n?
1 comment

We have carefully reviewed your comments, and we believe the extent of your criticisms does not warrant such a low rating. We give more details below by addressing and/or discussing each of your concerns.

On your concern "the gains in Table 1 therefore cannot be attributed specifically to the transformer, as opposed to generic stochastic local improvement around the incumbent.", we wish to draw your attention on the primary contribution and scope of our paper. We claim to have developed a method that beats state-of-the-art open-source integer-programming solvers on a non-trivial problem class (non-convex quadratic knapsack). To someone who is familiar with the practice of integer programming, we would argue that this is already a strong claim. We have therefore focused our evaluation on state-of-the-art open-source integer-programming solvers to establish a rigorous baseline. Methods such as "generic stochastic local improvement" are superseded by the advanced heuristics already integrated into modern solvers, which include sophisticated local search techniques starting from feasible incumbents. In our opinion, there is no need to re-establish that non-convex quadratic knapsack is a hard problem that weak/trivial baselines cannot solve.

Similarly, there is no point in comparing with "a random-perturbation control at matched Hamming distance". We agree with your assessment that "Thm 3 is a generic overparametrization symmetry: it shows the dynamics are parametrization-dependent, not that they are beneficial.", the goal of the tuneling analogy is to provide insights as to why our neural reparameterization is even a candidate for improving SOTA solvers. We indeed do not have a theorem that demonstrates why this particular method is superior to open-source integer-programming solvers, and we think that deriving such a theorem amounts to giving a precise characterization of the dynamics of overparameterized neural models, which is a notoriously difficult (and more general) open research question.

All in all, we have discovered a method that outperforms state-of-the-art open-source integer-programming solvers on a non-trivial problem class. The method is an autoregressive reparameterization and the paper investigates why it helped. We think the autoregressive aspect plays a role here (and this was the motivation for using it) because it allows one to scale to larger instances without changing the size of the input space, a property that standard integer-programming solvers do not leverage: this is well-known and does not require to be re-established. We have added a sentence to clarify this l. 35 in the revised submission. Neural reparameterization changes the loss landscape and therefore offers new dynamics which can explain why we are able to outperform solvers, which we are conveying in our theoretical analysis.

"The headline results overstate scalability and consistency.". We are not trying to overclaim here: we never claimed that at n=10,000 our methods finds a good quality of solution in comparison with a NP-oracle returning the optimal solution immediately, instead the claim is that open-source integer-programming solvers are unable to find a better solution within the time budget, whereas our method is. Furthermore, the consistency of the reported improvements is correlated with the size of the instance, which supports our scalability claim "suggesting that ADIP is stronger when the solvers leave greater room for improvement (at large problem sizes)." (l. 373 in the revised submission and l. 374 in the initial submission).

"The most closely related works is missing": we thank the reviewer for sharing these extra references, which we have added to our Related works section l. 129 in the revised submission. However, we note that none of these works claim to have developed a method that outperforms SOTA open-source integer-programming solvers on a non-trivial problem class, which is why we may have missed them initially. In that regard, the most closely related work is the ICLR 2025 Spotlight paper DiffILO, which we have discussed at length. Indeed, Schuetz et al. (2022) studies QUBO objectives (whereas we study standard constrained integer programs) and does not compare to integer-programming solvers (they compare with different heuristics and relaxation techniques). Hoyer et al. 2019 and Arora et al. 2018 are related to the neural parameterization idea, but do not even treat of combinatorial optimisation.

"The theory does not match the experimental regime": this is a fair statement, and we have included a sentence to acknowledge this l. 296 in the revised submission. However, we note that idealizing the setting of the experiments to derive theoretical results is customary, e.g. gradient flow dynamics is believed to still capture non-trivial insights about actual stochastic gradients, e.g. Du et al. (2018), Jacot et al. (2018), Chizat and Bach (2020).

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

This paper introduces ADIP, an instance-specific primal-improvement method for binary integer programs. An autoregressive Transformer is first trained to reproduce a feasible incumbent from a conventional solver using smoothed targets. Its parameters are then optimized against the problem objective and a constraint-violation penalty using Gumbel-softmax and straight-through gradients, while retaining the best feasible hard-decoded solution. The paper analyzes representational capacity, a sufficient penalty condition for binary solutions, and the decision-space geometry induced by idealized parameter-space gradient flow. Experiments on random quadratic knapsack problems report improvements over open-source solvers under a stated matched-time protocol, together with a study of trajectories reaching different relaxed-optimization endpoints.

Critical strengths
  1. The incumbent-improvement setting is well motivated. Starting from an existing feasible solution and retaining the best feasible hard candidate gives the neural procedure a clear role as a complement to a conventional solver. The separation between incumbent imitation and subsequent improvement is also easy to understand.

  2. The paper attempts to connect neural reparameterization with optimization behavior rather than presenting only an empirical heuristic. The induced-kernel analysis provides a useful interpretation of how shared parameters can couple decision-space updates, and the experiments examine both solution quality and trajectories. These are valuable directions, although the connection to the implemented algorithm and the experimental evidence need strengthening.

Critical weaknesses
  1. The geometric interpretation is not sufficiently connected to the implemented algorithm, and the endpoint experiment does not establish the claimed basin interpretation. The analysis studies Euclidean parameter-space gradient flow through a smooth map. The experiments instead use hard forward decisions, a soft straight-through backward estimator, stochastic Gumbel draws, and Adam. These differences mean that the stated gradient-flow dynamics are an idealization rather than a characterization of the actual updates. In addition, Section 5.3 allows direct relaxed optimization to stop when the feasible boundary prevents further movement. Reaching that boundary does not certify constrained stationarity or local optimality, so distinct stopping points are not enough to demonstrate distinct attraction basins of a valid constrained local optimizer. The experiment needs an appropriate constrained solver and projected-gradient or KKT residuals, together with clarification of whether any inputs are binarized before endpoint analysis. These issues weaken the proposed explanation for why the autoregressive parameterization helps.

  2. The main empirical evidence needs reconciliation and stronger controls. For the SCIP n=400 row of Table 1, the reported objective and percentage-improvement statistics appear incompatible with Eq. (12) if they use the same instances and matched-time baseline. Let B be the baseline objective, A the ADIP objective, and r=(A-B)/B for positive B. Then mean(A-B)=mean(B)mean(r)+Cov(B,r). The table gives mean(A-B)=64.94 and mean(B)mean(r)=118.80, requiring covariance about -53.86. However, the reported standard deviations bound its magnitude by approximately 339.71 x 0.0457=15.52; using sample rather than population standard deviations cannot explain this discrepancy. The percentages may use a different reference time, subset, or convention, but that needs to be made explicit. Beyond this reporting issue, solver-only comparisons do not isolate the benefit of autoregression from stochastic sampling or generic neural reparameterization. Feasible local search, frozen-network sampling, independent logits, alternative network parameterizations, and direct relaxation optimization from the same incumbent are important controls. At n=10,000, improving on a zero-objective solver baseline is particularly weak evidence of solution quality, especially because the generator permits many zero-weight variables.

Questions for authors
  1. Could you release the per-instance 500-second seed objective, 1,000-second solver objective, final ADIP objective, and percentage improvement for Table 1? Please reconcile the SCIP n=400 statistics and specify any filtering, clipping, zero-denominator handling, or use of different sample sets or reference times.

  2. Does the stated total budget include Phase 1 imitation, model initialization, all Phase 2 computation, decoding, and feasibility checks? Appendix A.2 describes a 500-second Phase 2 cap; please clarify how the additional work is counted in the matched-time comparison.

  3. Which conclusions of the geometric analysis are intended to apply to the implemented straight-through/Adam algorithm? Can the contribution of autoregressive coupling be isolated while matching the optimizer, Gumbel noise, temperature, incumbent, and initialization procedure?

  4. What are the exact stopping and preprocessing rules in the endpoint experiment? Can the results be reproduced using a constrained local solver, retaining continuous initial points and reporting projected-gradient or KKT residuals at every endpoint?

  5. How does ADIP compare, at the same total time and from the same incumbent, with feasible local search, frozen-network sampling, independent logits, another neural parameterization, and direct relaxed optimization? For the largest instances, please include a simple structure-aware baseline that exploits zero-weight variables.

4 comments

We have carefully reviewed your comments, and we believe the extent of your criticisms does not warrant such a low rating. We give more details below by addressing and/or discussing each of your concerns.

We agree with your assessment that "the stated gradient-flow dynamics are an idealization rather than a characterization of the actual updates". It is customary for theoretical results in deep learning to prove something about gradient flow and perform experiments with actual stochastic gradient updates, e.g. Du et al. (2018), Jacot et al. (2018), Chizat and Bach (2020). Gradient flow is believed to still capture non-trivial insights about practical deep learning. We have included a sentence to clarify this in the paper (l.296 in the revised submission).

We have investigated the discrepancy you identified and realised that the table was reporting percentage improvement conditionally on strictly positive improvement (i.e. discarding the non-improving instances, while separately reporting the number of runs with no improvements l. 373 in the initial submission and l. 372 in the revised submission). We apologise for this reporting issue which we have now flagged l. 380 in the revised submission. We had already released the detailed outputs of the runs in the anonymous repo (file results/gap_improvement_sweep_scip_n400_s40_k100.json, from which the percentage improvements can be recomputed). We note that we had also already released detailed output of the SCIP n=400 run in the paper as a figure (Figure 4 in the Appendix).

On your concern "solver-only comparisons do not isolate the benefit of autoregression from stochastic sampling or generic neural reparameterization", we wish to draw your attention on the primary contribution and scope of our paper. We claim to have developed a method that beats state-of-the-art open-source integer-programming solvers on a non-trivial problem class (non-convex quadratic knapsack). To someone who is familiar with the practice of integer programming, we would argue that this is already a strong claim. We have therefore focused our evaluation on state-of-the-art open-source integer-programming solvers to establish a rigorous baseline. Methods such as "feasible local search, frozen-network sampling, independent logits, and direct relaxation optimization" are superseded by the advanced heuristics already integrated into modern solvers, which include sophisticated local search techniques starting from feasible incumbents. In our opinion, there is no need to re-establish that non-convex quadratic knapsack is a hard problem that weak/trivial baselines cannot solve. Furthermore, finding an "alternative network parameterizations" that also beats SOTA open-source integer-programming solvers is not a control experiment, it would be another separate research result in itself. In our continued research on the topic, we are indeed working on alternative network parameterizations to try to beat our own baseline and improve the solutions, but this is outside of the scope of this rebuttal.

All in all, we have discovered a method that outperforms state-of-the-art open-source integer-programming solvers on a non-trivial problem class. The method is an autoregressive reparameterization and the paper investigates why it helped. We think the autoregressive aspect plays a role here (and this was the motivation for using it) because it allows one to scale to larger instances without changing the size of the input space, a property that standard integer-programming solvers do not leverage: this is well-known and does not require to be re-established. We have added a sentence to clarify this l. 35 in the revised submission. Neural reparameterization changes the loss landscape and therefore offers new dynamics which can explain why we are able to outperform solvers, which we are conveying in our theoretical analysis.

Your assessment reports "1: I learned little or nothing new from this paper". Could you please clarify why this is the case ? We are under the impression that you had not fully appreciated that a method outperforming state-of-the-art open-source integer-programming solvers on a non-trivial problem class is a strong claim, but please elaborate and we would be happy to try to clarify our contribution. For example, you write "At n=10,000, improving on a zero-objective solver baseline is particularly weak evidence of solution quality, especially because the generator permits many zero-weight variables", however the claim is not good quality of solution in comparison with a NP-oracle returning the optimal solution immediately, the claim is that open-source integer-programming solvers are unable to find a better solution within the time budget, whereas our method is.

Thank you for clarifying the conditional improvement statistics, which is now resolved. However, I retain my score of 2 because the cited artifact does not clearly substantiate the claimed matched computational budget, and the endpoint diagnostic does not establish constrained stationarity. The main remaining issues are whether the timing and baseline data can be reconciled and whether controlled comparisons would demonstrate a benefit attributable to the proposed autoregressive parameterization.

Apologies for not addressing these comments upfront, following the guidelines for rebuttal we had focused on what we felt were the strongest concerns, in order to keep the rebuttal short.

Matched computational budget:

We can confirm that we have run the experiments with matched computational budgets as this is the main claim of the paper. Here are more details on how the experiments were performed. For each instance, we run a 500 seconds solver warm-start and collect the best feasible incumbent. Then we run Phase 1 as described l. 793 in the paper (in the SCIP experiment for instance, this can take 200+ seconds). Then we run Phase 2 as described l. 795 in the paper with a time limit of 500 s. It has an early stopping criterion so sometimes it takes less than 500 seconds and sometimes it does reach the time limit. In any case, we then take the total time of the run "wall_total_s" in the artifact we pointed to in the rebuttal, and run the solver for this time.

In Figure 2 "Representative objective value trajectory", for illustrative purpose we had actually removed the Phase 1 (which is why there is a bar labeled "Phase 2 starts" at 500 seconds), as Phase 1 is is a phase where the objective does not move, to have a cleaner visualisation. We realise this was likely the source of the confusion. We have now flagged this in the paper l. 809 in the revised submission.

To make it very concrete, we provide in the comment below a simple script that the reviewer can inspect, and run on any seed ("base_seed" in the artifact provided). It uses the code from the anonymous repo. So cloning the repo and running the script after poetry install is an independent way to verify the results. Running each seed takes about 40 mins under the stated budgets, so it may not be feasible to run all 100 seeds, but choosing one or even a few arbitrary seeds where our artifact claims an improvement and finding consistent results should lend confidence in our claimed results.

"Endpoint diagnostic does not establish constrained stationarity": We have not claimed to have reached KKT points, nor is this required for the purpose of these experiments. As described l. 427 in the paper, we perform direct gradient ascent in the relaxed decision variables and "we iterate until convergence or until the feasible boundary prevents further improvement". What we wanted to observe with these experiments is that the points on the ADIP trajectory are exploring different regions of the relaxed landscape than that of the solver incumbent. Reaching different endpoints with direct gradient ascent is enough to conclude that, and provides a nice visualisation of the phenomenon (Figure 3 in the paper). Establishing KKT stationarity is an additional requirement that is not necessary for the conclusion we draw from this diagnostic, and that we have not claimed in the paper.

"whether controlled comparisons would demonstrate a benefit attributable to the proposed autoregressive parameterization": on this last point, we would like to re-iterate the argument we have been making throughout the rebuttal. The comparison with SOTA open-source solvers is the control experiment. Outperforming SOTA open-source solvers is already a strong signal, so what else would we attribute the benefit to?

SEEDS="${SEEDS:-41 103}" poetry run python - <<'PY'
import os, time
from dataclasses import replace

from adip.pipeline import (
    AdipPipelineConfig,
    _apply_reproducibility,
    _derive_torch_run_seed,
    _merge_scip_params_with_seed_shift,
    _parse_scip_param_kv_list,
    run_adip_pipeline,
    sample_qkp_instance,
    solve_max_qkp_scip_with_incumbent_x_trace,
)

N, EXP_ID, Q_KIND = 400, 0, "indefinite"
SEEDS = [int(s) for s in os.environ.get("SEEDS", "40 41 42").split()]
scip_params = _merge_scip_params_with_seed_shift(
    _parse_scip_param_kv_list(["timing/clocktype=wall"]), 424267
)

cfg0 = AdipPipelineConfig(
    pipeline_name="adip_scip_gumbel_ste",
    use_gurobi_warm_start=False,
    device="cpu",
    base_seed=0,
    q_kind=Q_KIND,
    ar_lr=0.001,
    ar_d_model=64,
    ar_nhead=4,
    ar_nlayers=2,
    ar_sparse_attn_prev_fraction=0.1,
    ar_sparse_attn_pattern="band",
    scip_time_limit=500.0,
    unused_gurobi_time_limit=500.0,
    scip_warm_start_seed_shift=424267,
    gurobi_warm_start_seed=424267,
    gurobi_license=None,
    scip_extra_params=scip_params,
    phase1_ce_target_prob=0.999,
    phase1_ce_max_steps=150,
    phase1_ce_plateau_patience=12,
    phase1_ce_plateau_min_delta=1e-5,
    phase2_max_steps=2000,
    phase2_w_soft=1.0,
    phase2_tau=0.5,
    phase2_lambda=100.0,
    phase2_q_weight=1.0,
    phase2_plateau_patience=45,
    phase2_plateau_min_delta=1e-5,
    phase2_time_limit_s=500.0,
    gumbel_use_ste=True,
    phase2_lr=None,
    reproducible=True,
    train_show_progress=False,
    warm_solver="scip",
    warm_threads=1,
)

print(
    f"{'seed':>6}  {'warm':>8}  {'ADIP':>8}  {'SCIP_matched':>12}  "
    f"{'ADIP_wall':>10}  {'SCIP_wall':>10}  {'imp_vs_matched%':>15}"
)
for seed in SEEDS:
    inst = sample_qkp_instance(N, EXP_ID, base_seed=seed, q_kind=Q_KIND)
    _apply_reproducibility(_derive_torch_run_seed(seed, N, EXP_ID, Q_KIND), device="cpu")
    cfg = replace(cfg0, base_seed=int(seed))

    t0 = time.perf_counter()
    out = run_adip_pipeline(inst, cfg=cfg, t_instance_start=t0)
    adip_wall = time.perf_counter() - t0

    res, snaps, meta = solve_max_qkp_scip_with_incumbent_x_trace(
        inst, time_limit_sec=float(adip_wall), quiet=True, scip_params=scip_params
    )
    warm = float(out.warm_xTQx or 0.0)
    adip = float(out.rounded_xTQx or warm)
    if not out.rounded_feasible:
        adip = warm
    adip = max(adip, warm)
    scip_m = float(res.obj_value) if res.obj_value is not None else float("nan")
    imp = (100.0 * (adip - scip_m) / abs(scip_m)) if abs(scip_m) > 1e-15 else float("nan")
    print(
        f"{seed:6d}  {warm:8.1f}  {adip:8.1f}  {scip_m:12.1f}  "
        f"{adip_wall:10.1f}  {float(res.wall_time_s):10.1f}  {imp:15.3f}"
    )
PY

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.