acceptodds
Withdrawn from ICLR 2027

Observe Then Control: PID-Inspired Discrete Langevin Search for Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Discrete Langevin proposals provide a training-free approach to combinatorial optimization by converting local energy information into parallel bit flips. We study how trajectory feedback can regulate such proposals under a prescribed expected flip budget. We introduce PID-LD, a hierarchical closed-loop discrete Langevin search framework for finite-horizon binary optimization. Bounded stochastic momentum provides a stateful dynamical backbone, while PID-inspired feedback regulates this backbone and the resulting proposal distribution: the proportional channel forms the instantaneous oriented drive, the derivative channel adjusts damping and velocity coupling using gradient-reversal observations, and the integral channel adjusts temperature and noise using accumulated stagnation and past flip-rate information. Calibrated Bernoulli centering then maps the controlled score to bit-flip probabilities while preserving the prescribed expected flip budget. We characterize this calibration as entropy-regularized score allocation and derive a conditional one-step energy bound, an oracle comparison, and mechanism-level results under explicit assumptions. Experiments on maximum independent set, maximum clique, and maximum cut show instance-dependent quality–runtime trade-offs. Ablations further distinguish the role of the stateful momentum backbone from the incremental role of closed-loop feedback on top of that backbone. Together, the formulation and analysis provide a structured view of how stateful dynamics, trajectory feedback, and budget-preserving proposal calibration interact in adaptive discrete Langevin search.

Primary area:
optimization
Keywords:
PID-Inspired Discrete Langevin, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_1PqeOpenReview ↗
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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

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

The paper proposes PID-LD, a training-free sampler for binary combinatorial optimisation. It builds on discrete Langevin proposals and RLSA/FLD-style solvers. The methodology is broken into four componenets:

Proportional drive - Form a drive from the gradient. Momentum backbone - Updates a clipped, damped auxiliary velocity. Controller channels - A “D-channel”, based on sign reversals of a filtered gradient, then modulates the damping and velocity-score coupling. An “I-channel”, which is a leaky integral of stagnation and past flip rate, modulates temperature and velocity noise. Calibration - Maps the resulting scores to independent Bernoulli flip probabilities via a shifted, clipped sigmoid. The shift is found by bisection so that the expected number of flips equals a prescribed budget dd.

The authors make the following claims:

Theory: a variational characterisation of the calibrated proposal as entropy-regularised allocation over the capped simplex (Lemma 1); a one-step expected-descent bound for independent multi-bit flips (Thm 1); an a posteriori descent certificate with comparison to a budgeted one-bit oracle (Thm 2); propositions on undo mass and temperature-induced anti-concentration and escape (Props 2–5).

Experiments: comparisons on RB/ER MIS, RB MaxCl and BA MaxCut against OR, learning-based and sampling baselines; ablations, one-factor sensitivity and paired tests against RLSA and FLD-EG, all on the single benchmark MIS RB-[200–300].

Critical strengths

The paper shows consistent, competitive results from a training-free method. PID-LD seems to exceed the strongest sampling baseline, FLD-EG, in seven of eight configurations at matched iteration count. On MIS RB, this is supported by a paired, multiplicity-corrected test. This seems to establish the method as a viable member of the RLSA/FLD family of training-free solvers. However, this strength is still quite modest. The margins are often 0.06 or less and they come at higher runtime in every configuration, and variability is reported for only one benchmark.

A clean separation of move size from move allocation. The budget-preserving calibration ensures that adaptive changes to temperature, noise or damping redistribute flip probability across coordinates without altering the expected Hamming step. Its characterisation as the unique maximiser of ⟨S,p⟩+τH(p)\langle S,p\rangle+\tau H(p) over the capped simplex makes this separation precise. It is the most transferable idea in the paper. Its weight as a novel contribution is limited, however: the variational result follows from a standard KKT calculation, and expected-move regularisation is inherited from RLD/RLSA, as the authors acknowledge.

Critical weaknesses

My biggest concern with this paper is that the method is poorly motivated and presented, and the PID framing does not hold together. The paper reads as an accumulation of heuristics rather than a design derived from a clear principle. In a PID controller, the proportional, integral and derivative terms act on a single error signal relative to a setpoint and are combined into one control input. Here they share neither. The P-channel is simply the preconditioned gradient, with no setpoint. The D-channel is the 0.7-quantile of a sigmoid-gated, clipped increment of an EMA of normalised gradients. The I-channel is a leaky integral of a stagnation counter and a flip-rate error. Each channel observes a different signal and drives a different actuator: the drive, the damping and coupling, and the temperature and noise respectively. No closed-loop property, such as stability, setpoint tracking or disturbance rejection, is defined or analysed. "PID", therefore, seems to function as an organising metaphor rather than a control design.

In one place the loop is structurally incoherent. Under exact calibration, E[ϕ^t]=d/N\mathbb{E}[\hat\phi_t]=d/N irrespective of the controller (Eq. 22). The flip-rate error in Eq. 68 is therefore either zero-mean noise, if ϕ⋆=d/N\phi^\star=d/N, or a constant offset that drives the leaky integrator to a fixed point, which amounts to a constant rescaling of τ\tau. Appendix C.4 acknowledges this but retains the term without explaining what purpose it serves.

Many functional forms are introduced without justification. These include the multiplicative gain in Eq. 12, the exponential in Eq. 13, and the factor of one half in Eq. 16. The role of a continuous velocity in a binary state space is never explained intuitively. A plausible reading is that, because χi\chi_i changes sign when bit ii flips, the −νV⊙χ-\nu V\odot\chi term penalises undoing recent flips. On this reading, the "momentum" acts as a soft memory, which may well be the paper’s real story, but it is never articulated.

Notation is frequently undefined or inconsistent. The quantities aγ,aν,aτ,aσa_\gamma, a_\nu, a_\tau, a_\sigma in Eqs. 12–13 and as,aϕa_s, a_\phi in Eq. 69 are never defined or reported. The parameter β\beta in Tables 5 and 7 takes values between 1.001 and 1.10, so it cannot be any of the EMA rates in the text, and it is never identified. The noise law μt\mu_t is never specified, and the S$\alpha$S variant in Table 4 is undefined. The pairs ν0\nu_0 and λv\lambda_v, γ0\gamma_0 and γ\gamma, and KPK_P and kpk_p are used interchangeably. KK denotes both the number of chains and the controller gains. YtY_t appears in the main text but is defined only in Appendix C.1. The "decoded objective" is never described, and neither is the procedure that turns penalised-energy states into feasible solutions. The caption of Table 5 even refers to code variable names.

The central claim, that closed-loop feedback improves the search, is not supported empirically or theoretically. The paper’s own numbers attribute most of the gain to the velocity term rather than to the controller. On MIS RB-[200–300], PID-LD beats RLSA by 0.106. It beats the variant with both D- and I-channels removed by only 0.014 (Table 6), so roughly 87% of the improvement over RLSA is present without any feedback at all. Removing momentum gives 19.975, essentially RLSA’s 19.97. In that variant the D-channel has no actuator, since γ\gamma and ν\nu act only through the velocity. The remaining I-channel temperature control therefore adds almost nothing over RLSA.

Questions for authors

Decoding and feasibility: How are final states mapped to feasible independent sets and cliques? Is the same procedure applied to RLSA and FLD-EG? How often is the best-energy state infeasible, and what penalty λ\lambda was used for each benchmark?

Baselines and compute: Were RLSA, FLD-EG and iSCO re-run on the same hardware with the same KK, TT and decoding, or are their objectives and times taken from [10, 23]? Please report a matched-wall-clock comparison, giving the baselines the extra iterations that PID-LD’s runtime allows. With margins of 0.01–0.06, this is decisive.

Variability: Please give standard errors or paired tests for all configurations in Tables 1–2.

Hyperparameter selection: Which data were used to choose the Table 5 values, given that the benchmarks provide training and validation splits?

Theory in practice: Do you evaluate Eq. 29, or the exact Eq. 190, along trajectories, and how often is it positive? What does Eq. 32 add, given that it is never tighter than Eq. 29?

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

This work proposes a novel Langevin-based search method for combinatorial optimization, based on the PID-control adapted from traditional control domain. Using a stateful searching operator (from trajectory feedback), PID-control outperforms prior SOTA on 3 QUBO problems: MIS, Max Clique and Max Cut.

Critical strengths
  1. This paper validates the effectiveness of integrating the trajectory feedback as part of the search (explicitly with PID-control) in combinatorial optimization, as opposite to prior Langevin methods, which could be a valuable insight for future design.
  2. The effort to adapt the traditional PID-control for combinatorial optimization is also meaningful.
Critical weaknesses
  1. The empirical evaluation is limited. The problems used in this work are almost saturated --- some baselines can be further improved by simply running more iterations (which I also hope authors could do a more controlled study by comparing the performance under the same time budget). The advantage of the current method may be in question given the tiny improvement and the increased solving time.
  2. The more general picture for the existing Langevin methods on CO---the reliance on the differentiable objective for a gradient---is not considered in this work. Prior studies at least try to integrate such an idea to the neural solvers, but this part is totally missing. How would you extend your framework to non-differentiable CO problems like those globally constrained ones (TSP, CVRP)?
Questions for authors

Since you use H100 for your own method, have you reproduced the baseline results, especially in time, on the same machine? At least from what I see, some results are taken directly from prior papers evaluated in less powerful GPUs.

Following my above suggestion, I would like to see a more controlled study by fixing the time budget during the comparison. Since PID involves more operations, you could run the fast baselines for more iterations.

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

Related papers

Discussion (0)

Sign in to comment.