- 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 with 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.
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 n, not as n2. 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 n2 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 ∞ 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.