Streamlining Variational Inference for Constraint Satisfaction Problems

Aditya Grover, Tudor Achim, Stefano Ermon

Introduction Constraint Satisfaction Problems (CSPs), such as Boolean Satisfiability (SAT), are foundational to computer science, underpinning applications from hardware verification to AI planning. While modern solvers are highly capable, they often falter on "hard" random instances near the phase transition—the critical threshold where a problem is just barely satisfiable.

A state-of-the-art method for tackling these hard instances is Survey Propagation (SP), a variational inference scheme that estimates the marginal probability of a variable being True or False in a satisfying assignment. Traditionally, solvers use these marginals in a process called decimation: they select the variable with the most confident marginal and permanently fix its value. However, SP marginals are only approximations. A single incorrect hard assignment early in the process can lead to an unrecoverable contradiction.

This paper introduces Survey Inspired Streamlining (SIS), a more robust, risk-averse alternative that replaces the "all-or-nothing" decimation approach with flexible multi-variable constraints. By doing so, the authors shrink the gap between empirical solver performance and theoretical limits by 16.3% on average.

The Streamlining Approach Instead of fixing a single variable to a specific value (a unary constraint), streamlining adds a disjunction constraint (a clause) between two or more variables.

  • Survey Inspired Streamlining (SIS): Fixing one variable reduces the search space by 50%. In contrast, a length-2 streamlining constraint (e.g., $x_i \lor x_j$) reduces it by only 25%, eliminating only the scenario where both variables are assigned incorrectly. This allows the solver to "hedge its bets."
  • Disjunction Pairing: To scale effectively, the algorithm identifies the top $2R$ most confident variables. It then pairs the most confident variable with the least confident one within that set. This balancing act ensures that the strong signal from one variable guides the weaker signal of another without over-constraining the problem.
  • Hybrid Strategy: The solver runs streamlining for a set number of iterations to narrow the search space toward a specific "cluster" of solutions. Once the problem is sufficiently simplified, it switches back to standard decimation.

Key Insights * The "Safety Net" Property: The authors mathematically demonstrate that if a standard decimation step preserves satisfiability, a streamlining step is guaranteed to do the same. Crucially, streamlining can maintain satisfiability even when decimation would have forced a contradiction. * Guiding Toward Clusters: Analysis of the Hamming distance between solutions reveals that streamlining gracefully guides the solver into a specific cluster of valid assignments rather than blindly searching the entire space. * Confidence Calibration: As streamlining constraints are added, the calibration of the remaining marginals improves, making the solver increasingly certain about which variables are safe to branch on later.

Empirical Results The authors evaluated SIS on random $k$-SAT instances ($k=3, 4, 5, 6$) with up to 50,000 variables, as well as XORSAT problems. They also integrated the method into Dimetheus, a high-performance ensemble solver.

Comparison of SIS and SID success rates across different k-SAT problems
  • Closing the Performance Gap: SIS reduced the gap between the best-known algorithmic thresholds and theoretical satisfiability limits by an average of 16.3% across the tested $k$-SAT instances.
  • Higher Success Rates: In head-to-head comparisons, SIS consistently solved instances at higher constraint densities where Survey Inspired Decimation (SID) failed completely.
  • Healthier Downstream Search: The percentage of failures caused by local search timeouts dropped from 36% (with decimation) to 24% (with streamlining). This indicates that the simplified formulas produced by streamlining are easier for downstream search algorithms to process.

Limitations and Future Work While highly effective, streamlining does have limitations. Adding constraints increases the number of edges in the problem's factor graph, making it more "loopy" and occasionally hindering the convergence of the Survey Propagation algorithm. Furthermore, the current approach is greedy; once a constraint is added, it cannot be removed. Future work could explore backtracking mechanisms to delete problematic streamlining constraints, or utilize joint marginals for clusters of variables to make even smarter pairing decisions.

Summary updated

Abstract

Several algorithms for solving constraint satisfaction problems are based on survey propagation, a variational inference scheme used to obtain approximate marginal probability estimates for variable assignments. These marginals correspond to how frequently each variable is set to true among satisfying assignments, and are used to inform branching decisions during search; however, marginal estimates obtained via survey propagation are approximate and can be self-contradictory. We introduce a more general branching strategy based on streamlining constraints, which sidestep hard assignments to variables. We show that streamlined solvers consistently outperform decimation-based solvers on random k-SAT instances for several problem sizes, shrinking the gap between empirical performance and theoretical limits of satisfiability by 16.3% on average for k = 3, 4, 5, 6.
BibTeX
@inproceedings{grover2018streamlining,
  author = {Aditya Grover and Tudor Achim and Stefano Ermon},
  title = {{Streamlining Variational Inference for Constraint Satisfaction Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJZcJd-uWH},
}
Figure