💻 computer science

Solving QBF with Counterexample Guided Refinement

This paper introduces two novel Counterexample-Guided Abstraction Refinement (CEGAR) approaches for Quantified Boolean Formula (QBF) solving—a recursive CEGAR-driven algorithm and a DPLL-based learning enhancement—both of which demonstrate improved performance on specific problem families compared to existing solvers.

Original authors: Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke

Published 2026-08-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a massive, multi-layered mystery where the clues are hidden inside a giant, tangled ball of string. This isn't just any mystery; it's a game played between two invisible opponents: one who wants to prove a statement is true, and another who desperately wants to prove it's false. In the world of computer science, this is called a Quantified Boolean Formula (QBF). Think of it as a super-charged version of a logic puzzle where you have to figure out if there's a way to win no matter how your opponent plays. These puzzles are incredibly hard—so hard that they power everything from checking if a self-driving car's software is safe to planning complex robot missions. For decades, computers have tried to solve them using a method called DPLL, which is like a detective trying every single door in a mansion one by one until they find the exit. It works, but for the biggest, most tangled mysteries, the detective gets lost in the sheer number of doors, running out of time and energy before finding the answer.

Enter a new strategy called CEGAR, which stands for Counterexample-Guided Abstraction Refinement. If DPLL is a detective checking every door, CEGAR is a detective who starts with a rough sketch of the mansion. They guess a path, and if their opponent says, "No, you can't go there because of this specific trap," the detective doesn't give up. Instead, they use that specific trap (the "counterexample") to update their sketch, making it more accurate. They repeat this process—guess, get corrected, refine the sketch—until the sketch is perfect enough to solve the mystery without ever needing to check every single door. This paper introduces two clever ways to use this "guess-and-refine" trick to solve these logic puzzles faster and smarter than before.

The authors, a team of researchers from Portugal, Ireland, and the USA, propose two distinct ways to bring this CEGAR magic into the world of QBF solvers. The first approach is a brand-new solver they named RAReQS. Instead of trying to solve the whole puzzle at once or expanding the entire ball of string into a massive, unwieldy mess (a problem known as "memory blowup" that plagues older methods), RAReQS plays the game in layers. It starts by making a simple guess about the first layer of variables. It then asks a helper (a SAT solver) if this guess works. If the helper finds a flaw—a specific way the opponent could win against this guess—RAReQS uses that flaw to tighten its rules for the next guess. It's like playing a video game where you don't need to see the whole map; you just need to know where the walls are so you don't walk into them. By only expanding the parts of the puzzle that are absolutely necessary, RAReQS avoids the memory explosion that crashes other solvers.

The second approach is a bit more like a software upgrade. The authors took an existing, popular solver called GhostQ, which uses the traditional "check every door" DPLL method, and gave it a new learning tool. They taught GhostQ to use the same "guess-and-refine" logic. When GhostQ finds a path that looks good but turns out to be a dead end, instead of just backtracking, it learns a powerful lesson: "Never take this path again." This new learning technique allows the solver to prune the search space much more aggressively, cutting out huge chunks of impossible scenarios that the old method would have wasted time exploring.

When the team tested these new methods on a massive collection of real-world logic puzzles (from the QBF-LIB benchmark suite), the results were striking. Their new solver, RAReQS, solved significantly more puzzles than the competition—about 33% more than the second-best solver. It particularly excelled at families of problems related to formal verification (checking if hardware designs are correct) and planning (figuring out how robots should move). For some specific types of puzzles, like "incrementer-encoder" and "trafficlight-controller," RAReQS solved almost every single instance, while other solvers struggled or failed completely. The upgraded GhostQ also showed improvements, solving more puzzles than its un-upgraded version, though it sometimes paid a small price in speed or memory usage.

The paper makes it clear that while these methods are powerful, they aren't a magic wand that solves everything instantly. The authors note that if a puzzle does require a full expansion of the string to solve, RAReQS might end up doing the same amount of work as the older methods, just with a little extra overhead for the refinement steps. However, for the vast majority of practical problems they tested, the "partial expansion" strategy was a game-changer. It proved that you don't need to see the whole picture to solve the mystery; you just need to refine your understanding of the parts that matter, using the mistakes you make along the way to guide you to the truth. This opens up two exciting new paths for the future: building solvers that rely entirely on this refinement loop, and teaching old-school solvers to learn from their counterexamples in a whole new way.

Technical Summary: Solving QBF with Counterexample Guided Refinement

Problem Statement
Quantified Boolean Formulas (QBFs) extend the SAT problem to PSPACE-complete problems, finding applications in formal verification and planning. While the DPLL procedure dominates non-random SAT solving, it has proven insufficient as a universal solution for QBF. Existing QBF solvers generally fall into two categories: DPLL-based approaches and expansion-based approaches. Expansion-based solvers (e.g., Quantor, Nenofex) eliminate quantifiers by expanding the formula into a propositional one, but this often leads to memory blowup as the formula size grows rapidly. DPLL-based solvers struggle with the complexity of the search space in QBF. This paper addresses the need for more efficient QBF solving techniques that can mitigate memory issues while effectively pruning the search space.

Methodology
The authors propose two distinct approaches utilizing the Counterexample-Guided Abstraction Refinement (CEGAR) paradigm:

RAReQS (Recursive CEGAR-based Algorithm):
- Core Concept: RAReQS is a recursive algorithm that treats QBF solving as a game between a universal player and an existential player. Instead of fully expanding the formula, it builds a partial expansion (abstraction) driven by counterexamples.
- Mechanism: The algorithm attempts to find a "winning move" (an assignment to a block of variables that satisfies the formula for the existential player or falsifies it for the universal player) for an abstraction of the formula.
  - It starts with an empty set of counterexamples ( $\omega = \emptyset$ ), representing a trivial abstraction.
  - In each iteration, it solves the current abstraction to find a candidate winning move.
  - It then verifies if this candidate is a winning move for the original formula. This verification involves solving a sub-QBF.
  - If the candidate fails verification, a counterexample (a winning move for the opposing player) is generated.
  - The abstraction is refined by adding this counterexample to the set $\omega$ , effectively strengthening the abstraction to exclude the failed candidate.
- Optimization (Multi-games): To address the high memory consumption caused by the recursive nature of the algorithm (where abstraction size can grow exponentially with recursion depth), the authors introduce the concept of "multi-games." A multi-game allows the solver to handle multiple sub-formulas simultaneously. The abstraction is maintained as a set of subgames, and refinement adds new subgames rather than blindly expanding the formula size. This allows the solver to terminate before a full expansion is required.
- Implementation: A prototype was implemented in C++ using the MiniSat 2.2 SAT solver, supporting the QDIMACS format. It employs standard QBF preprocessing techniques like unit propagation and pure literal rules.
CEGAR as a Learning Technique in DPLL:
- Core Concept: This approach integrates CEGAR as an additional learning mechanism within an existing DPLL-based solver (specifically GhostQ).
- Mechanism: When the DPLL solver assigns values to variables such that the existential player wins (the formula evaluates to true), the assignment is split into a candidate part ( $\pi_{cand}$ ) and a counterexample part ( $\pi_{cex}$ ).
- Learning: The solver learns from this by modifying the input formula. If the last decision literal was owned by the winning player, the solver substitutes the relevant quantified subformula with a disjunction (for existential) or conjunction (for universal) involving the counterexample assignment. Specifically, $\exists X. \Phi$ is replaced by $(\exists X. \Phi) \lor \Phi[\pi_{cex}]$ , ensuring the specific counterexample assignment is avoided in future searches.
- Trade-off: This technique allows for more aggressive pruning of the search space than standard clause learning but incurs higher memory consumption.

Key Contributions

RAReQS Algorithm: The development of a novel, recursive, CEGAR-driven QBF solver that avoids the memory blowup inherent in traditional expansion-based solvers by performing careful, counterexample-driven partial expansions.
Multi-game Abstraction: The introduction of the multi-game concept to manage the complexity and memory usage of recursive CEGAR, allowing the solver to handle formulas with arbitrary numbers of quantifier levels efficiently.
CEGAR Learning for DPLL: The proposal and implementation of a new learning technique for DPLL-based QBF solvers that leverages counterexamples to strengthen the search space pruning.
Empirical Validation: Extensive experimental evaluation on the QBF-LIB benchmark suite, demonstrating that CEGAR-based techniques are effective for a wide range of problem families.

Experimental Results
The authors evaluated the prototypes on 4,669 instances from the QBF-LIB, focusing on families from formal verification and planning.

RAReQS Performance: RAReQS outperformed existing solvers (QuBE7.2, Quantor, Nenofex, GhostQ) on a significant number of families. It solved approximately 33% more instances than the second-best solver (QuBE7.2). Notably, RAReQS solved all instances for families like blackbox-01X-QBF and trafficlight-controller, and solved nearly all instances for incrementer-encoder and RobotsD2.
Memory Efficiency: Out of 801 aborted runs, only 50 were due to memory exhaustion, indicating that RAReQS successfully mitigates the memory blowup issues common in expansion-based solvers.
DPLL Learning: The integration of CEGAR learning into GhostQ (GhostQ-CEGAR) generally improved performance, particularly on families like irqlkeapclte (where it was the only solver to find solutions) and incrementer-encoder. However, in some families, the added memory overhead slightly worsened performance.

Significance and Claims
The paper claims to open two promising avenues in QBF solving:

CEGAR-driven solvers as an alternative: RAReQS demonstrates that a CEGAR-driven approach can serve as a viable alternative to existing DPLL and full-expansion methods, particularly by avoiding the memory blowup of expansion-based solvers while maintaining soundness and completeness.
Novel learning in DPLL: The paper establishes that CEGAR can be effectively utilized as an additional learning technique within DPLL-based solvers, offering a more powerful pruning mechanism than standard clause learning, albeit with a memory cost.

The authors conclude that while RAReQS shares similarities with expansion-based solvers, its step-by-step, counterexample-driven expansion allows it to stop early if a winning move is not found in the partial expansion, a crucial advantage for large formulas. They modestly note that if a full expansion is eventually required, RAReQS performs the same expansion as traditional solvers but with the overhead of intermediate tests. Future work involves refining the DPLL learning to mitigate speed penalties and integrating preprocessing techniques from other solvers into RAReQS.

More like this