🤖 AI

Modal CEGAR-tableaux with RECAR and resolution-based SAT-shortcuts

This paper presents CEGARBox++, a C++ implementation that integrates modal resolution (KSP) as SAT-shortcuts into CEGAR-tableaux, demonstrating superior performance over both standalone KSP and RECAR-enhanced CEGAR-tableaux, particularly on large satisfiable modal problems.

Original authors: Rajeev Goré (Faculty of Information Technology, Monash University, Australia), Cormac Kikkert (Cormac Kikkert Research)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rajeev Goré (Faculty of Information Technology, Monash University, Australia), Cormac Kikkert (Cormac Kikkert Research)

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 complex mystery: Is a specific logical puzzle possible to solve, or is it a contradiction? In the world of computer science, this is called "modal satisfiability." The puzzle involves rules about what must happen, what might happen, and how different scenarios connect to one another.

For a long time, detectives (computer algorithms) used three different, competing toolkits to solve these puzzles:

SAT-Solvers: Great at checking if a simple list of facts fits together.
Tableaux: A method that builds a "tree" of possibilities, branching out to see if a valid story can be told.
Resolution: A method that aggressively combines rules to find contradictions, like a bulldozer clearing a path.

The authors of this paper, Rajeev Goré and Cormac Kikkert, wanted to build a "Super Detective" that could use the best parts of all three toolkits. They created a system called CEGARBox++ and tested two new ways to make it faster.

The Problem: The "Model Building" Trap

Their original detective, CEGARBox, was already very good at solving "unsolvable" puzzles (proving a story is a lie). However, it struggled with "solvable" puzzles (proving a story is true).

Why? Because to prove a story is true, CEGARBox had to build the entire story from scratch.

The Analogy: Imagine trying to prove a maze has an exit. CEGARBox would try to draw every single possible path through the maze. If the maze is huge and has many branching paths, the drawing takes forever, and the detective runs out of time (a "timeout") before finishing the picture, even though the exit exists.

They needed a way to say, "We don't need to draw the whole maze; we just need to know an exit exists." This is called an ESAT-shortcut.

Attempt 1: The "Optimistic Architect" (RECAR)

The first new approach they tried was called RECAR.

The Analogy: This approach is like an optimistic architect who says, "Instead of building two separate rooms for two different ideas, let's try to build one big room that fits both." If it works, we save space. If it fails, we split them apart and try again.
The Result: The authors found this didn't work well. The "optimism" often led to wasted effort. The system spent too much time trying to force things to fit together, only to realize later they couldn't, and then having to start over. It was slower than the original method.

Attempt 2: The "Bulldozer Oracle" (KSP)

The second approach was a total game-changer. They partnered with a different, very aggressive detective called KSP (a Resolution-based solver).

The Analogy: Imagine CEGARBox is building a house room by room. KSP is a bulldozer that runs ahead, smashing through walls and checking the foundation of the entire neighborhood at once.
How they worked together:
1. CEGARBox starts building the house (the logical model).
2. KSP runs in parallel, aggressively checking if the rules of the house are consistent.
3. The Magic Moment: If KSP finishes checking a section and says, "This section is solid; no contradictions found," it sends a signal back to CEGARBox.
4. CEGARBox hears this and says, "Great! I don't need to build the rest of this room. I know a valid house exists here." It skips the heavy lifting and moves on.
The Result: This was a massive success. By letting the "bulldozer" (KSP) do the heavy lifting of checking consistency, CEGARBox could skip the expensive step of building huge models. On large, solvable puzzles, this new team (CEGARBox++(KSP)) was much faster than either detective working alone.

The Big Picture

The paper claims that this is the first time these three distinct methods (SAT, Tableaux, and Resolution) have been successfully combined into one system that performs better than any of them could on their own.

The Old Way: You had to pick a detective based on the puzzle type. If it was a "no" puzzle, pick CEGARBox. If it was a "yes" puzzle, pick KSP.
The New Way: The new hybrid system is a "Swiss Army Knife" detective. It uses the careful, step-by-step building of CEGARBox for complex unsolvable puzzles, but it uses the fast, aggressive checking of KSP to instantly confirm solvable puzzles without building the whole thing.

The Catch

The authors admit their current version isn't perfect. Because the two detectives communicate by writing notes to files (like passing notes in a classroom), there is some delay. Also, the "bulldozer" (KSP) sometimes creates too much paperwork (clauses) for very large, complex puzzles, which slows things down.

However, the core idea—using one method to detect "fixpoints" (safe zones) so the other method doesn't have to waste time building them—is a breakthrough. It proves that combining these different logical strategies creates a super-tool that is greater than the sum of its parts.

Technical Summary: Modal CEGAR-tableaux with RECAR and Resolution-based SAT-shortcuts

Problem Statement

The paper addresses the challenge of efficiently deciding satisfiability in multi-modal logic $K_n$ (also known as ALC). While Counter-Example Guided Abstraction Refinement (CEGAR) tableaux have proven highly effective for unsatisfiable problems and many satisfiable ones, they struggle with large satisfiable instances. Specifically, the authors' previous implementation, CEGARBox, outperformed other solvers on standard benchmarks but lost to the modal resolution prover KSP on the MQBF benchmark set. The core issue identified is that CEGAR-tableaux explicitly construct satisfying models; for problems with high branching factors, this can lead to the generation of exponentially large models, causing timeouts. Unlike resolution-based methods (like KSP) which can determine satisfiability via saturation without explicitly building a full model, CEGAR-tableaux lack an effective "ESAT-shortcut" (a mechanism to quickly confirm satisfiability without full model construction).

Methodology

The authors investigate two distinct approaches to integrating ESAT-shortcuts into CEGAR-tableaux, implemented in a new C++ system called CEGARBox++. Both approaches utilize a Trie data structure to store modal clauses in Separated Modal Clausal Normal Form (SNFmc).

1. The RECAR Approach (RECARTAB)

This method adapts the RECAR (Recursive Explore and Check Abstraction Refinement) framework, originally proposed by Lagniez et al. for general CEGAR.

Mechanism: Instead of creating a separate world for every fired diamond clause (which leads to exponential branching), RECARTAB attempts to group multiple diamond clauses into a single successor world using an over-approximation. It annotates diamond clauses with labels and tries to satisfy a conjunction of their targets in one world.
Refinement: If a conflict arises involving multiple diamonds, the algorithm separates them by assigning fresh labels and restarts the search.
Goal: To find a smaller model (fewer worlds) than the standard CEGAR approach, thereby avoiding the exponential blowup in world generation.

2. The Resolution-based Oracle Approach (CEGARBox++(KSP))

This novel approach integrates the modal resolution theorem prover KSP as an oracle to detect "fixpoints" in the CEGAR search.

Mechanism: The system runs CEGARBox++ and KSP in parallel (multithreaded). KSP operates on a linear Trie (SNFml) and performs resolution from the deepest modal layer up to the root.
Fixpoint Detection: When KSP fully saturates a specific modal layer $l$ with respect to layer $l+1$ , it outputs learned classical clauses. CEGARBox++ imports these clauses. If a layer is saturated (a "fixpoint" is reached), CEGARBox++ infers that no further refinement (learning of new clauses) is possible for that layer.
Shortcut: Upon detecting a fixpoint, CEGARBox++ skips the expensive process of generating successor worlds (the "jump" rule) for that layer and immediately returns Satisfiable, relying on the lemma that if the under-approximation is a fixpoint, the full modal formula is satisfiable.

Key Contributions

Implementation of CEGARBox++: A new C++ implementation of CEGAR-tableaux that serves as the baseline for the experiments.
RECARTAB Algorithm: A sound and complete extension of CEGAR-tableaux incorporating RECAR-style ESAT-shortcuts to attempt model minimization.
CEGARBox++(KSP) Integration: The first effective integration of SAT, tableaux, and resolution methods for modal satisfiability. It uses KSP not just as a portfolio partner, but as an internal oracle to detect fixpoints and trigger early termination for satisfiable problems.
Theoretical Analysis: Formal proofs of soundness, completeness, and termination for both the RECAR-based and Resolution-based approaches.

Experimental Results

The authors evaluated their approaches on the standard K-benchmarks (LWB-K, 3CNF, and MQBF) using an Intel i7-11700F CPU.

RECAR Performance: The RECARTAB (RECARBox) approach was found to be not competitive. It generally performed worse than the standard CEGARBox++. The authors attribute this to the overhead of searching for smaller models; if a smaller model does not exist or is hard to find, the extra computation is wasted.
Resolution-based Performance: CEGARBox++(KSP) demonstrated superior performance:
- It significantly outperformed both the standalone CEGARBox++ and the standalone KSP on the MQBF benchmarks (which are dominated by satisfiable problems).
- It achieved speedups of up to 100x on certain satisfiable instances compared to KSP alone.
- On the 3CNF benchmarks, it performed equivalently to CEGARBox++.
- On the LWB-K benchmarks, it was slightly outperformed by CEGARBox++ alone, likely due to the overhead of KSP's normal form generation producing more clauses for massive formulas.
Synergy vs. Parallelism: The authors ruled out the possibility that the performance gains were merely due to parallelism (doubling resources). CEGARBox++(KSP) solved satisfiable problems that KSP alone could not, proving that the CEGAR component actively contributed to the solution by providing the resolution prover with necessary context or by pruning the search space via the fixpoint detection.

Significance and Claims

The paper claims that CEGARBox++(KSP) represents the first effective integration of SAT, tableaux, and resolution methods for modal satisfiability that performs better than its individual components.

Overcoming Limitations: The work addresses the fundamental weakness of CEGAR-tableaux in handling large satisfiable problems by introducing a mechanism to detect when a model exists without explicitly constructing it.
Complementary Strengths: The results highlight that while SAT-based, tableaux-based, and resolution-based solvers have traditionally been competing methods with different strengths (e.g., tableaux for unsatisfiable, resolution for satisfiable), their integration can yield a solver that is "greater than the sum of its parts."
Future Outlook: The authors modestly note that their current implementation is naive (using file I/O for communication and KSP's specific normal form). They suggest that a more polished integration, potentially using CEGAR's own normal form generation and better communication protocols, could allow this hybrid approach to outperform existing solvers across all benchmark sets, including the LWB-K benchmarks where it currently lags slightly.

The paper concludes that while the RECAR approach was unsuccessful in this context, the fixpoint detection strategy using a resolution oracle is a promising direction for recursive CEGAR algorithms, particularly those involving branching.