Dependency Learning for QBF

Tomás Peitl, Friedrich Slivovsky, Stefan SzeiderJAIR 2019 · DOI

TL;DR

This paper introduces "dependency learning," a novel technique for Quantified Boolean Formula (QBF) solvers that significantly speeds up solving by dynamically learning variable dependencies. This approach allows solvers to be more flexible in their search strategy, leading to exponential speedups on certain hard instances compared to existing methods.

What Problem Does This Paper Address?

Quantified Boolean Formulas (QBFs) are a powerful tool for encoding complex problems in areas like formal verification and planning. However, solving QBFs (QSAT) is considerably harder than solving propositional satisfiability (SAT) problems, largely due to the inherent dependencies between variables introduced by quantifiers. Standard QBF solvers, like Quantified Conflict Driven Clause Learning (QCDCL), often struggle with these dependencies, forcing them into rigid variable assignment orders. While "dependency schemes" exist to relax these constraints, they can complicate the solver's underlying proof system and are often too coarse, identifying many "spurious" dependencies. This paper addresses the challenge of efficiently exploiting variable independence in QBF solving without sacrificing the solver's core mechanisms or introducing unnecessary complexity.

Methods

The core contribution is dependency learning, a new technique integrated into QCDCL solvers. Instead of relying on pre-computed dependency schemes, dependency learning allows the solver to discover and learn dependencies on the fly during the solving process.

Here's how it works:

  • Dynamic Dependency Set (D): The solver maintains a set D of learned variable dependencies.
  • Modified QBCP: Quantified Boolean Constraint Propagation (QBCP) uses this set D to guide universal and existential reduction. This means a universal variable can be removed from a clause if there's no existential variable it depends on (according to D).
  • Modified Decision Rule: The solver can branch on any variable y as long as there's no unassigned variable x such that (x, y) is in D. This allows for more flexible variable selection.
  • Conflict-Driven Learning: When a conflict occurs, the solver attempts to derive a new clause using Q-resolution. If this fails due to an "illegal merge" (where a universal variable blocks resolution), the solver identifies the involved variables and adds a new dependency (x, y) to D. This learned dependency is crucial for resolving the conflict and potentially avoiding similar issues in the future.
  • Retained Proof System: Crucially, dependency learning retains the standard long-distance Q-resolution proof system, ensuring soundness and enabling efficient strategy extraction.

Datasets

The paper evaluates its approach on benchmark instances from the 2016-2018 QBF Evaluations. These benchmarks include:

  • Prenex non-CNF (QCIR) format: Used in Section 5.2.
  • Prenex CNF (PCNF) format: Used in Section 5.2.
  • CRn instances: A specific family of instances known to be hard for standard QCDCL solvers, used in Section 5.4 and Section 6.

Key Insights and Ideas

  • Learning Dependencies is More Effective than Pre-computing Them: The paper demonstrates that dynamically learning dependencies during the search is more efficient than relying on static dependency schemes. This is because the solver only learns dependencies that are actually hindering its progress, avoiding the overhead of spurious dependencies.
  • Flexibility is Key to Performance: By allowing the solver to branch on a wider range of variables and perform more flexible reductions, dependency learning unlocks significant performance gains, especially on instances with many quantifier alternations.
  • Exponential Speedup on Specific Hard Instances: The technique achieves an exponential speedup on the CRn family of instances, proving that dependency learning can overcome limitations that plague standard QCDCL solvers.
  • Soundness Preserved: A major advantage is that dependency learning is integrated without altering the underlying proof system (long-distance Q-resolution), ensuring correctness and maintaining theoretical guarantees.

Key Results

  • Competitive Performance: The implemented solver, QUTE, with dependency learning, is competitive with state-of-the-art QBF solvers on benchmark sets.
  • Significant Improvement on QCIR: Dependency learning provided a 10% increase in the number of solved instances on the prenex non-CNF (QCIR) benchmark set.
  • Impact on High Alternation Instances: Dependency learning particularly shines on instances with a high number of quantifier alternations (100+), where it enables solving many more instances.
  • Exponential Speedup on CRn: QUTE with dependency learning solves the CRn instances in polynomial time, whereas standard QCDCL solvers require exponential time. This is a key theoretical result demonstrating the power of the learned dependencies.
  • Fewer Learned Dependencies: QUTE typically learns a fraction of dependencies compared to those identified by standard dependency schemes, indicating more efficient exploitation of independence.

Limitations and Future Work

  • Potential for Detrimental Performance: In some cases, particularly with strict temporal or logical dependencies (e.g., in game encodings), the increased freedom from dependency learning might lead to suboptimal search paths and the learning of many useless constraints.
  • Future Work - Decision Heuristics: The authors suggest designing new decision heuristics that consider the quantifier prefix more directly, potentially penalizing out-of-order assignments.
  • Future Work - Initialization: They propose initializing learned dependencies with small sets derived from techniques like Tseitin conversion or implicit variable definitions to guide the search more effectively from the start.
  • Future Work - Dependency Scheme Integration: The paper mentions ongoing research combining dependency learning with dependency schemes, where the solver dynamically queries a scheme to discover independent variables.
  • Future Work - Dependency Management: While not encountered in experiments, the authors suggest that managing learned dependencies (e.g., removing them periodically) might be beneficial for very long solver runs.

Summary updated

BibTeX
@article{peitl2019dependency,
  author = {Tomás Peitl and Friedrich Slivovsky and Stefan Szeider},
  title = {{Dependency Learning for QBF}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  doi = {10.1613/jair.1.11529},
}
Figure