Hard Examples for Common Variable Decision Heuristics

Marc VinyalsAAAI 2020 · DOI

Abstract

Conflict-Driven Clause Learning (CDCL) solvers are the industry standard for solving massive Boolean Satisfiability (SAT) problems. While theoretical models suggest CDCL can polynomially simulate the resolution proof system, this simulation assumes optimal branching choices. This research identifies a fundamental gap by proving that common variable decision heuristics—such as VSIDS and LRB—can be systematically lured into exponential-time traps. By constructing a family of "pitfall formulas," the authors demonstrate that these heuristics prevent CDCL solvers from achieving their full theoretical potential on problems that possess short, polynomial-time proofs.

Introduction

In the realm of automated reasoning, the efficiency of CDCL solvers is largely attributed to their "brain": the heuristics used to decide which variables to branch on next. Heuristics like VSIDS (Variable State Independent Decaying Sum) and CHB (Conflict History-Based) prioritize variables involved in recent conflicts. While effective in practice, this paper investigates whether these heuristics preserve CDCL's ability to simulate resolution. The findings provide a definitive "No," showing that the greedy nature of these heuristics creates a bottleneck that adversarial formulas can exploit.

Adversarial Engineering: Pitfall Formulas

The authors prove their thesis through the construction of Pitfall Formulas. These formulas are specifically engineered to exploit the "recency" bias of modern heuristics. A pitfall formula consists of three main components:

  1. An Easy Part: A set of clauses with a very short resolution proof.
  2. A Hard Part: A "Tseitin formula," which is a classic hard problem for resolution requiring exponential time.
  3. Pitfall and Pipe Gadgets: These traps ensure that as soon as a solver begins the "easy" part, a cascade of unit propagations triggers variables in the "hard" part.

Because heuristics reward variables involved in recent conflicts, the solver becomes hyper-focused on the hard variables, ignoring the easy path to a solution and trapping itself in an exponential search space.

Experimental Validation

To validate the theoretical proof, the authors tested several state-of-the-art solvers, including CaDiCaL, Glucose, and MapleCOMSPS, against these engineered instances. The results highlight a stark contrast between heuristic-driven search and fixed-order search.

Comparison of solver runtimes (in seconds) on Tseitin (Ts) and Pitfall (Φ) formulas.

As shown in the data, standard solvers frequently timed out (reaching the 3,600-second limit) when facing the pitfall formulas ($\Phi$). However, when these same solvers were forced to use a simple static variable order (labeled "Fix" in the table), they bypassed the heuristic traps and solved the instances in less than one second. This empirical evidence confirms that the heuristics themselves, rather than the underlying CDCL mechanism, are responsible for the exponential slowdown.

Key Insights and Future Directions

The study formalizes the "Rewards Conflicts" property common to modern heuristics. While prioritizing recent conflicts is generally beneficial for industrial benchmarks, it creates a blind spot. Interestingly, the research notes that introducing randomness can sometimes help solvers escape these traps, though it increases runtime variance.

Future work in SAT solver design may need to move beyond pure recency-based heuristics. To overcome these limitations, solvers might require mechanisms that actively seek out "ignored" variables to ensure they do not become permanently stuck in local, hard sub-problems. This research underscores that even with perfect clause learning, a flawed decision mechanism can render a solver exponentially slower than the proof system it implements.

Summary updated

BibTeX
@inproceedings{vinyals2020hard,
  author = {Marc Vinyals},
  title = {{Hard Examples for Common Variable Decision Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5527},
}
Figure