- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes PID-LD, a training-free discrete Langevin search method for binary combinatorial optimization (MIS, MaxClique, MaxCut). The method runs parallel chains with a momentum (velocity) state that accumulates gradient history and feeds into the bit-flip scores. On top of this sits a “PID-inspired” controller. The P-channel is the clipped gradient. The D-channel tracks sign reversals in the filtered gradient and increases friction when the trajectory oscillates. The I-channel accumulates stagnation and flip-rate history and raises the temperature and noise when progress stalls. The controlled scores are then mapped to independent Bernoulli flip probabilities through a calibration step that fixes the expected number of flips per step, as in RLSA. The authors interpret this calibration as an entropy-regularized allocation problem and give one-step expected-descent bounds plus fixed-score propositions for the D- and I-channels. Empirically, PID-LD is competitive with RLSA and FLD-EG at matched iterations, with small gains on most benchmarks, typically at higher runtime.
Critical strengths
The paper credits its main inherited components to RLSA (the flip budget) and PIDLD (feedback control). I like the transparency. Separating removal of the backbone (momentum) from removal of the controller (D/I channels), and including randomized-control variants as controls, is a good experimental practice. It’s what makes the attribution possible, in the first place. I also like the paired comparisons on matched instances and 95% confidence intervals. The paper exhaustively covers three major problems, graph sizes up to about 11k nodes, and baselines spanning exact solvers, learned methods and sampling methods.
Critical weaknesses
Presentation
The paper’s organization makes it hard to digest. Manuscript jumps from Introduction to Methodology with no related works and preliminaries to build the ramp for the reader. For instance for DLP, on which the method is built, is derived only in Appendix C.7, and all related work is relegated to Appendix A. Section 2.2 uses D_t, I_t and μ_t before they are defined, so the controller cannot be understood from the main text alone. Meanwhile, Fig. 1 occupies roughly 40% of a page with illegible text, and Fig. 2’s panels are too small to read. Not the forget none of these plots have titles. The prose is also heavily defensive at places qualifications such as “should not be interpreted as…” appear throughout, often in place of explanation. I recommend condensing the figures, adding a short preliminaries section on DLP and RLSA, moving related work into the main text, and replacing the central idea with one clear statement of what is claimed and what is not in the intro.
Overall, I feel the paper needs stronger introspective writing. As the manuscript stands, it feels hurried and stitched together without much structure beared in mind.
Novelty
In my view, the novelty stands low. The submission’s core mechanism is using the energy gradient as a feedback signal, adding an accumulated-history (momentum) term and a gradient-change (damping) term, and keeping the procedure training-free is the contribution of PIDLD. The present work places it inside a discrete Langevin proposal with RLSA’s calibrated flip budget. Component wise breakdown
-
Integral term. The “stateful momentum backbone” is PIDLD’s integral term under a new name. PIDLD accumulates past gradients and itself describes the result as a “momentum-like” effect. Unrolling Eq. 15 here gives V_{t+1} = −(η/m) Σ_s (1−ηγ/m)^{t−s} U_s, a leaky integral of the proportional signal. The mechanism is the same; only the label has changed.
-
Derivative term. The D-channel uses the same signal as PIDLD’s derivative term for the same purpose. PIDLD uses the gradient difference s_t − s_{t−1} to damp oscillation and overshoot. The submission’s D-channel is built from Ō_t − Ō_{t−1}, a filtered difference of successive normalized gradients, gated on sign reversals, also to suppress oscillation. The only real change is the actuator: the signal raises friction and lowers velocity–score coupling instead of entering the drift directly.
-
Stabilizing the integral. PIDLD decays its integral gain over time (k_i·γ^t) as a gain schedule so the accumulated term does not destabilize late-stage sampling. Here the same role is filled by the I-state leak λ_I, the burn-in ρ_I, temperature annealing and clipping.
-
Scope and evaluation. Both methods are presented as training-free, plug-in modifications of a Langevin sampler. PIDLD already evaluated discrete reasoning targets (Sudoku, graph connectivity), so moving to MIS, MaxClique and MaxCut is a change of domain, not a change of mechanism. The evaluation follows PIDLD’s ablation template: PIDLD reports P, P+I, P+D and P+I+D, and the submission reports removing D, removing I and removing momentum.
The rest is inherited too. The calibrated Bernoulli flip budget comes from RLSA, which the authors openly acknowledge , and the factorized binary flip kernel comes from DLP. Taken together, the submission is PIDLD’s control structure inside the RLSA/DLP proposal. The only parts it designs itself are the reversal gating and the stagnation/flip-rate inputs that drive friction and temperature.
Having said that, a change of state space can justify a new method/paper when it creates a difficulty the original method cannot handle and the new work resolves it. But I feel that is not the case here. The momentum backbone, which is functionally PIDLD’s integral term, accounts for nearly all of the improvement over RLSA (19.975 to 20.062). The components the authors actually designed adds about 0.014, and randomized schedules recover most of that (Tables 4, 6). What is suprising for me is that appendix statement claims feedback control is not new, but the title, abstract and Fig. 1 present the PID framing as the contribution. I feel the paper should either show that the discrete setting requires the new D/I design: rn its not clear to me \emph{why is this combination needed specifically for CO?} or reposition itself as an empirical study of momentum within RLSA. The former is a positioning issue; maybe use a motivational figure/example in the intro.
Related Works
The related-work discussion omits a substantial line of gradient-based discrete MCMC that directly addresses the problems the D- and I-channels target. Cyclical step-size scheduling for discrete Langevin samplers [1] alternates between exploration and exploitation phases to escape local modes, which is the stated role of the I-channel, and does so without any feedback controller. It is therefore a necessary baseline. Work on adaptive and optimal proposal scaling for locally balanced samplers [2, 3] addresses how many coordinates to move per step, which is central to the expected-flip-budget framing. Path-auxiliary proposals [4] analyze gradient-informed multi-flip moves, relevant to Theorem 1.
Most importantly, the I-channel is closely anticipated by ReSCO [5]. ReSCO identifies the same failure mode that motivates PID-LD: after reaching a plateau, gradient-based discrete samplers keep proposing different solutions of nearly identical objective value (“wandering in contours”). My understanding is it addresses this with the same remedy: detect stagnation along the trajectory and raise the temperature. ReSCO triggers reheating when the objective has not changed for N steps and resets the temperature to an estimated critical temperature. PID-LD’s I-channel accumulates a stagnation counter based on archive improvement (Eqs. 63–67) and raises the temperature through Eq. 71. Functionally, this is stagnation-triggered reheating implemented with a leaky integrator instead of a threshold rule, and without ReSCO’s principled choice of target temperature. ReSCO operates in the same setting (gradient-based discrete samplers for combinatorial optimization, built on iSCO/PAS and DMALA) and reports on largely the same benchmarks: MIS on ER-[700–800] and ER-[9000–11000], MaxClique on RB, and MaxCut on BA. ReSCO is therefore also a necessary baseline. Without it, the paper cannot show that the I-channel offers anything beyond existing stagnation-based reheating. This also sharpens my novelty concern: the momentum backbone and derivative signal follow PIDLD, the I-channel follows ReSCO, and the flip budget follows RLSA.
Finally, the paper builds on and cites DLP, but does not mention its direct extension that targets TSP under CO [6]; this warrants some discussion.
Given how central this prior work is to the paper’s positioning, I strongly encourage the authors to move the related-work discussion from the appendix into the main body and to state explicitly, component by component, what is inherited and what is new, tying it back to novelty.
[1] Pynadath et al. Gradient-based discrete sampling with automatic cyclical scheduling. NeurIPS 2024.
[2] Sun et al. Any-scale balanced samplers for discrete space. ICLR 2023.
[3] Sun et al. Optimal scaling for locally balanced proposals in discrete spaces. NeurIPS 2022.
[4] Sun et al. Path auxiliary proposal for MCMC in discrete space. ICLR 2022.
[5] Li & Zhang. Reheated gradient-based discrete sampling for combinatorial optimization. TMLR 2025.
[6] Mohanty & Zhang. Slithering through gaps: Capturing discrete isolated modes via logistic bridging. AISTATS 2026.
Missing citations.
Several components and baselines are used without attribution. ERDOES and MFA appear in Table 2 without references. The “RMSProp-style” preconditioner (Eqs. 48–49) should ideally cite RMSProp. The momentum backbone (Eq. 15) is underdamped Langevin with friction, yet no work on heavy-ball, Hamiltonian or momentum-based Langevin methods is cited (e.g., Neal 2011; Chen et al. 2014; Shetty et al. 2024), which matters for assessing novelty. The Holm correction should also ideally be used with a citation.
The part that works isn’t new, and the part that’s new doesn’t measurably work.
The momentum backbone (Eq. 15) is a leaky integral of the gradient, i.e., PIDLD’s integral term. Removing it gives 19.975, the same as RLSA (19.97). Removing both D and I leaves about 20.062, only 0.014 below the full method and already above every heuristic baseline. Removing both channels beats removing either one alone (Table 6), so they interfere rather than complement each other. Random schedules come within 0.011–0.015 of the full controller (Table 4). The paper’s contribution is indistinguishable from random perturbation, and this is measured on one small benchmark only.
Does I-channel contradicts itself?
Calibration fixes E[φ̂] = d/N (Eq. 22), so the flip-rate error in Eq. 68 is either noise or a constant that saturates the integral. It isn’t feedback, and φ* is not reported. Proposition 3 says higher temperature increases entropy and helps escape, yet Table 8 shows the I-channel lowers entropy during stagnation (−0.75 nats). Escape improves by +0.58 pp on a 1.26% base rate. Please clarify. I am confused on this part.
Runtime Analysis
We need matched wall-clock time, for fair compute comparison, to gauge evidence of improvement.
The theory never touches the controller.
All results hold at a fixed score. Proposition 2 needs an ordering condition that the D-channel doesn’t enforce. Propositions 3–5 ignore the I-channel’s effect on the noise. Theorem 2’s certificate is never evaluated, and its corollary (Eq. 125) is negative for MIS whenever λ ≥ 2/d (0.1–0.4 for the d used); λ is not reported. Meanwhile FLD, proves polynomial-time escape.
Questions for authors
To be fully transparent, I do not believe an author response phase will change my assessment due to low novelty. Of course, I welcome being corrected by the authors. For now, any meaningful remediation would require a complete rewrite and resubmission from the ground up rather than text revisions ; this would require a structural redesign and repositioning, and a major overhaul of the paper rather than minor text cosmetic fixes. Consequently, I am not recommending a list of author questions.