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

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.