💻 computer science

Understanding CDCL Solvers via Scalability Studies and Proofdoors

This paper addresses the lack of systematic scaling studies on industrial SAT instances by analyzing a large BMC benchmark, demonstrating that the recently proposed "proofdoor" parameter—representing a sequence of interpolants—successfully explains solver performance scalability where traditional structural parameters fail.

Original authors: Shimin Zhang, Yechuan Xia, Chunxiao Li, Jianwen Li, Moshe Y. Vardi, Vijay Ganesh

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shimin Zhang, Yechuan Xia, Chunxiao Li, Jianwen Li, Moshe Y. Vardi, Vijay Ganesh

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

The Big Mystery: Why Do Computers Get Good at Hard Puzzles?

Imagine you have a giant, impossible jigsaw puzzle. In theory, solving it should take longer than the age of the universe. This is what computer scientists call an "NP-complete" problem. It's supposed to be a nightmare for computers.

Yet, in the real world, computers (specifically a type called CDCL SAT solvers) are solving massive industrial puzzles—like checking if a car's braking system is safe—in seconds. This is the "gap between theory and practice." We know the math says it should be impossible, but the machines do it anyway.

For decades, researchers tried to figure out why these computers are so good. They looked at the shape of the puzzle (how the pieces connect) and tried to find a rule that predicts when a puzzle will be easy or hard. But their old rules didn't work.

The New Experiment: A Race Against Time

The authors of this paper decided to run a massive experiment. Instead of looking at one puzzle at a time, they created 766 families of puzzles. For each family, they made versions that got bigger and bigger (from 1 step deep to 100 steps deep).

They timed how long it took a modern computer to solve each version. They discovered that the puzzles fell into three distinct groups:

The Linear Runners: As the puzzle got bigger, the time to solve it grew slowly and steadily (like walking up a gentle hill).
The Polynomial Hikers: The time grew faster, but still manageable.
The Exponential Runners: As the puzzle got slightly bigger, the time to solve it exploded (like a snowball turning into an avalanche).

The mystery was: What makes the "Linear Runners" easy and the "Exponential Runners" impossible?

The Failed Clues: Old Maps Didn't Work

The researchers tried to use the old "maps" (structural parameters) that everyone else used to explain this:

The "Tangle" (Treewidth): How knotted the connections are.
The "Ratio" (Clause-Variable Ratio): How many rules there are compared to how many variables.
The "Community" (Community Structure): How the puzzle pieces cluster into groups.

The Result: These maps failed. Both the easy puzzles and the impossible puzzles looked exactly the same on these maps. They had the same "tangles" and the same "communities." So, these old clues couldn't explain why the computer was fast on one and slow on the other.

The New Clue: The "Proofdoor"

The authors introduced a new concept called a Proofdoor.

The Analogy:
Imagine you are walking through a long, dark hallway with many doors. You need to find the exit.

The Old Way: You try to memorize the entire hallway at once. If the hallway is long, your brain explodes.
The Proofdoor Way: You walk through the hallway one room at a time. After you leave a room, you write a tiny note (an interpolant) on the wall that summarizes only what you need to remember to get through the rest of the hallway. You don't need to remember the whole room, just the note.

A Proofdoor is a sequence of these notes.

If the notes are short and simple, the computer can write them quickly and solve the puzzle fast.
If the notes are long and complicated, the computer gets overwhelmed, and the puzzle becomes impossible to solve in a reasonable time.

What They Found

The researchers tested this "Proofdoor" idea on their 766 families of puzzles:

On the Easy (Linear) Puzzles: The computer naturally figured out how to write these tiny, simple notes as it solved the puzzle. It was "memoizing" its work, step-by-step. The notes stayed small, so the computer stayed fast.
On the Hard (Exponential) Puzzles: The computer tried to write notes, but the notes kept growing huge. It couldn't summarize the problem efficiently. The notes became so big that the computer got stuck.

The "Scramble" Test:
To prove this wasn't just luck, they took an "Easy" puzzle and scrambled it (shuffled the order of the rooms and the notes).

Result: The computer suddenly got much slower. Why? Because the scrambling forced the computer to write huge, messy notes instead of the tiny, clean ones it used to write. The "Proofdoor" got bigger, and the performance crashed.

The Conclusion

The paper concludes that the secret to why computers are so good at these industrial puzzles isn't the shape of the puzzle itself (like how knotted it is). Instead, it's about how the computer breaks the problem down.

If the computer can find a way to break the problem into small, manageable chunks and write simple "notes" (Proofdoors) for each chunk, it solves it instantly. If it can't find that path, the notes get too big, and the computer fails.

In short: The difference between a puzzle that takes a second and one that takes a lifetime isn't the puzzle's shape; it's whether the computer can find a "shortcut note" to summarize its progress. The authors call this shortcut a Proofdoor, and it's the first tool that successfully explains why some industrial puzzles are easy and others are hard.

Technical Summary: Understanding CDCL Solvers via Scalability Studies and Proofdoors

Problem Statement

Despite the theoretical intractability of SAT (NP-complete), Conflict-Driven Clause Learning (CDCL) solvers have demonstrated remarkable efficiency on large industrial formulas, particularly in SAT-based Bounded Model Checking (BMC). While extensive empirical research exists on solver performance over benchmarks and random/crafted families, there is a significant gap in systematic scaling studies over families of large industrial instances. Specifically, it remains unclear how solver performance scales with problem size (e.g., unfolding depth in BMC) and which structural parameters can explain the observed spectrum of behaviors (linear, polynomial, or exponential scaling). Previous attempts to explain this via structural parameters like treewidth, clause-variable ratio (CVR), and community structure have failed to distinguish between linearly-scaling and exponentially-scaling industrial instances.

Methodology

The authors conducted a comprehensive scaling study and structural analysis using the following approach:

Benchmark Collection and Scaling Study:
- Dataset: A collection of 76,600+ CNF instances derived from 766 BMC families from the HWMCC benchmark suite.
- Generation: Instances were generated at unfolding depths $K = 1, \dots, 100$ using simpleCAR.
- Solver Configuration: A modern CDCL solver (CaDiCaL) was used with inprocessing, preprocessing, and clause deletion disabled to isolate pure CDCL behavior.
- Classification: Solving times were smoothed using a running-maximum envelope to remove parity oscillations. Families were classified as linear, polynomial, exponential, or unclassified based on the best fit of linear, polynomial, and exponential regression models.
Structural Parameter Analysis:
- The study evaluated previously proposed parameters: Clause-Variable Ratio (CVR), Treewidth, and Community Structure (including Hierarchical Community Structure).
- Proofdoor Analysis: The authors investigated the recently proposed "proofdoor" parameter. A proofdoor is a sequence of interpolants between chunks of a formula, representing the solver's memoization of reasoning effort.
- Computation: Three types of interpolants were computed for each cut in the formula decomposition: the strongest ( $I_s$ $I_{s}$ ), the weakest ( $I_w$ $I_{w}$ ), and a McMillan interpolant ( $I_m$ $I_{m}$ ).
  - BVESPC: Used bounded variable elimination to compute strongest proofdoors.
  - IPCCP: Used iZ3 to compute McMillan interpolants.
- Absorption Testing: The authors tested whether CDCL solvers "incrementally absorb" these proofdoors. A clause is absorbed if unit propagation derives its consequences without explicitly learning the clause. Incremental absorption implies the solver is effectively computing the proofdoor sequence step-by-step.
Perturbation Experiments:
- Linearly-scaling instances were "scrambled" by permuting iterations or clauses to disrupt the natural variable ordering. The impact on proofdoor size and solver performance was measured.

Key Contributions and Results

1. Spectrum of Scaling Behaviors

The study revealed a diverse spectrum of scaling behaviors within the same benchmark suite, with no obvious syntactic distinction between regimes:

Linear: 333 families
Polynomial: 268 families
Exponential: 148 families
Unclassified: 17 families

2. Failure of Traditional Structural Parameters

The authors empirically demonstrated that traditional parameters fail to discriminate between linear and exponential regimes:

CVR: Remained constant across both regimes.
Treewidth: BMC formulas generally have small treewidth, but this parameter predicts linear scaling for all BMC families (via dynamic programming), failing to explain the observed exponential cases.
Community Structure: Modularity was uniformly high in both linear and exponential families, rendering it ineffective as a discriminator.

3. Success of the Proofdoor Parameter

The proofdoor parameter successfully distinguished the regimes:

Linear Instances: CDCL solvers were observed to incrementally absorb small proofdoors. The computed strongest proofdoors satisfied the "smallness" conditions (bounded interpolant size $c$ , bounded chunk pathwidth $w$ , and bounded dependency $s$ ) required by the Small Proofdoor Theorem.
Exponential Instances: Sampled proofdoors (strongest, weakest, and McMillan) scaled exponentially with formula size. Furthermore, these proofdoors were typically not incrementally absorbed by the solver, indicating a failure to memoize reasoning locally.

4. Impact of Scrambling (Variable Ordering)

Scrambling linearly-scaling instances disrupted the solver's ability to find small proofdoors:

Performance Drop: Scrambling increased solving time by an average of 12% (iteration permutation) and 256% (clause permutation).
Proofdoor Growth: The size of the McMillan interpolant ( $I_m$ ) increased dramatically (average 4590% for iteration scrambling, 7400% for clause scrambling).
Correlation: This establishes a link between poor branching orders (induced by scrambling), larger proofdoor sizes, and degraded solver performance.

Significance and Claims

The paper claims that the proofdoor is the first structural parameter that:

Admits a polynomial proof-size theorem (linking small proofdoors to polynomial resolution proofs).
Empirically tracks the behavior of CDCL solvers on industrial formulas, successfully separating linear from exponential scaling regimes.

The authors argue that while traditional parameters describe the static graph structure of formulas, proofdoors capture the semantic reasoning behavior of the solver (localized analysis and memoization). The results support the hypothesis that CDCL solvers achieve efficiency on linear BMC instances by incrementally computing small proofdoors, whereas they fail to do so on exponential instances.

The paper remains modest in its claims, acknowledging that:

The labeling of scaling regimes is statistical (based on regression fits) rather than formal complexity proofs.
The proofdoor computation pipeline times out on many exponential instances due to the NP-hard nature of the problem.
The theoretical results regarding CDCL and proofdoors rely on idealized models (e.g., non-deterministic branching), whereas the experiments use a real-world solver.
The study did not cover polynomial families in depth, focusing primarily on the linear vs. exponential endpoints.

The work concludes that understanding and optimizing the discovery of small proofdoors (e.g., via branching heuristics that prioritize interface variables) is a promising direction for improving BMC solvers.