Abstract
Quantified Boolean Formula (QBF) solving is a PSPACE-complete problem that often suffers from exponential search space explosions. This paper presents QFUN, a solver that integrates machine learning—specifically decision tree induction—into the refinement-based RAReQS algorithm. By learning general strategies from specific counter-examples, QFUN can prune search spaces more effectively than traditional enumeration methods. Experimental results from the 2017 QBF Competition demonstrate that QFUN achieves state-of-the-art performance, solving more instances with significantly fewer iterations.
Introduction
While Boolean Satisfiability (SAT) has seen immense progress, Quantified Boolean Formulas (QBF) remain a significant challenge due to the addition of universal ($\forall$) and existential ($\exists$) quantifiers. Proving a formula like $\forall X \exists Y. \phi$ requires finding a strategy for $Y$ that holds for every possible assignment of $X$. Traditional solvers typically rely on refinement or search, effectively enumerating specific assignments. This approach often leads to an exponential bottleneck.
The core insight of this work is that humans often solve such problems by identifying patterns or functional dependencies. If a solver can automatically discover a strategy—a function mapping $X$ to $Y$—it can "generalize" from a few samples to cover a vast portion of the search space simultaneously.
Methodology: Learning Strategies with QFUN
QFUN builds upon the RAReQS (Recursive Abstraction Refinement QBF Solver) framework. In standard RAReQS, the solver maintains an abstraction of the formula and refines it by adding point-wise constraints derived from counter-moves found during the search.
QFUN enhances this process through a machine learning loop:
- Sample Collection: The solver tracks pairs of moves and counter-moves during the refinement process.
- Decision Tree Induction: Every $K$ iterations (where $K$ is a configurable parameter, typically 64 or 128), the solver uses the ID3 algorithm to train a decision tree on the collected samples.
- Generalization: The learned decision tree is converted into a symbolic Boolean formula representing a candidate strategy.
- Refinement with Strategies: Instead of adding a single assignment, the solver plugs the entire learned strategy into the abstraction. This strengthens the abstraction much faster than individual points.
- Strategy Accumulation: To maintain progress, the solver retains previously learned strategies as long as they remain consistent with new incoming data, allowing for the construction of increasingly complex winning conditions.
Experimental Evaluation
The solver was evaluated on the non-CNF suite from the 2017 QBF Competition, which includes 320 instances. These instances are represented as And-Inverter Graphs (AIGs), which preserve structural information conducive to functional recovery.
As shown in the performance plot above, QFUN variants (qfun-64 and qfun-128) outperform the baseline RAReQS and other top-tier solvers like Quabs. Specifically, QFUN-64 solved 111 instances, surpassing RAReQS's 105.
A key driver of this performance is the drastic reduction in the number of refinement iterations required. By generalizing from samples, QFUN can bypass thousands of individual search steps.
The scatter plot illustrates that for many hard instances, the number of iterations drops by several orders of magnitude. For example, instances requiring 100,000 iterations in RAReQS were solved in fewer than 1,000 iterations by QFUN-64.
Discussion and Future Work
The success of QFUN highlights the potential of integrating machine learning into symbolic reasoning. The "ShouldLearn" trade-off is a critical factor; learning too frequently introduces unnecessary overhead, while learning too rarely misses optimization opportunities. The current study suggests a fixed interval of 64-128 iterations is effective, but dynamic triggers could offer further improvements.
Future research directions include exploring more expressive ML models, such as neural networks, provided they can be efficiently translated into symbolic logic. Additionally, applying these generalization techniques to search-based (CDCL) QBF solvers remains a promising open question.
Summary updated