💻 computer science

Generalizing CDCL with Graph Backtracking

This paper introduces graph backtracking, a novel and sound CDCL-based SAT solving scheme that generalizes chronological and non-chronological backtracking by using implication graphs and user-defined weight functions to minimize unassigned literals, thereby reducing propagations and improving runtime as demonstrated in the NapSAT solver.

Original authors: Robin Coutelier, Thomas Hader, Laura Kovács

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Robin Coutelier, Thomas Hader, Laura Kovács

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 trying to solve a massive, complex puzzle where every piece must fit perfectly, or the whole picture falls apart. In the world of computer science, this is called SAT solving (Boolean Satisfiability). The computer tries to assign "True" or "False" to thousands of variables to make a logical formula work.

When the computer makes a mistake and hits a dead end (a "conflict"), it has to go back and change its mind. This paper introduces a new, smarter way to do that "going back," called Graph Backtracking.

Here is the breakdown using simple analogies:

1. The Old Ways: The "Undo" Button vs. The "Backtrack" Button

Before this paper, computers used two main ways to fix mistakes:

Non-Chronological Backtracking (NCB): This is like a very aggressive "Undo" button. If you make a mistake at step 10, the computer looks at the logic and says, "Oh, step 3 was the root cause." It jumps back to step 3 and erases everything that happened between step 3 and step 10. It's fast, but it's wasteful. It throws away steps 4 through 9 even if those steps were actually fine and didn't cause the problem.
Chronological Backtracking (CB): This is more like a standard "Back" button. It only goes back to the very last thing you did (step 10) and tries again. It's safer because it doesn't throw away good work, but it can be slow because it might have to re-do the same work many times.

The Problem: Both methods are rigid. They follow a strict "stack" order (like a stack of plates: you can only take the top one off). They can't say, "Let's keep the top 5 plates, but swap out the 3rd one."

2. The New Idea: Graph Backtracking (The "Surgical" Approach)

The authors propose Graph Backtracking, which treats the puzzle not as a stack of plates, but as a web of dependencies (a graph).

The Web: Imagine every decision you made is a node in a web, connected by strings to the things it caused.
The Weight: The user can assign a "weight" to every piece of the puzzle. Some pieces are "heavy" (expensive to move or change), and some are "light" (easy to change).
The Strategy: When a conflict happens, instead of blindly erasing the top of the stack, the computer looks at the web. It calculates: "Which specific group of connected pieces can I remove to fix the error while keeping the 'heavy' pieces in place?"

The Analogy:
Imagine you are building a house of cards.

Old Way: You knock over the whole tower because one card at the bottom is wobbly, even if the top 10 floors are perfectly stable.
Graph Backtracking: You look at the structure. You see that the wobbly card is connected to a specific branch. You carefully remove only that branch and the cards directly above it, leaving the rest of the house standing. You might even choose to remove a different branch if it's lighter and easier to rebuild.

3. How It Works in Practice

The paper describes a system where the computer:

Maps the Dependencies: It draws a map of which decisions led to which other decisions.
Chooses the Cheapest Fix: It looks at all the possible groups of cards it could remove. It picks the group that costs the least (based on the user's "weights") to undo.
Preserves the Good Stuff: It keeps the "heavy" decisions (the ones the user wants to keep) assigned, even if they are high up in the decision chain.

4. The Results

The authors built a prototype solver called NapSAT to test this.

The Test: They used "3-coloring" problems (a classic puzzle where you try to color a map with only three colors so no touching areas share a color).
The Outcome: Graph Backtracking made fewer mistakes (fewer "propagations") than the old methods. Because it didn't waste time undoing and redoing things that didn't need to change, the solver finished the puzzles about 30% faster in their best tests.

5. Why This Matters

This isn't just about being slightly faster. It gives the user control.

In the old days, the computer decided what to forget.
With Graph Backtracking, you can tell the computer: "Don't touch this specific variable; it's too expensive to change. Find a different way to fix the error."

Summary

Think of Graph Backtracking as upgrading from a blunt hammer (which breaks everything to fix one thing) to a scalpel (which removes only the exact tissue needed to heal the patient). It allows the computer to be more precise, keep more of its good work, and solve logical puzzles more efficiently by respecting the "weight" or importance of different parts of the problem.

Note: The paper specifically mentions this is useful for SAT solving and has potential applications in "Model Counting," "AllSAT," and "MaxSAT." It also mentions ongoing work to integrate this into "Vampire," a tool for first-order logic proofs.

Technical Summary: Generalizing CDCL with Graph Backtracking

Problem Statement

The Conflict-Driven Clause Learning (CDCL) algorithm is the dominant approach in propositional satisfiability (SAT) solving. Current solvers primarily rely on Non-Chronological Backtracking (NCB) or, more recently, Chronological Backtracking (CB) for conflict repair.

NCB aggressively backjumps to the highest decision level in a learned clause (typically the second-highest), unassigning all subsequent decisions and their consequences. While efficient, this approach imposes a strict top-down order that may force the unassignment of literals the user wishes to keep assigned, potentially leading to unnecessary backtracking and reduced search locality.
CB is less restrictive, backtracking only to the highest decision level minus one, preserving some assignments. However, it still adheres to a rigid temporal order based on decision levels.

Both methods abstract the implication graph into decision levels, creating a coarse over-approximation of dependencies. This abstraction restricts the solver's ability to perform fine-grained repairs, potentially undoing "heavy" (expensive or preferred) literals that are not strictly necessary to resolve a conflict.

Methodology: Graph Backtracking (GB)

The authors propose Graph Backtracking (GB), a novel scheme that utilizes the implication graph directly to determine which literals to unassign, rather than relying solely on decision levels.

Core Concepts

Chunks: Instead of grouping literals by decision level, GB clusters them into chunks. A chunk $ck_\ell$ is defined as the set of all literals in the implication graph that depend on a specific decision literal $\ell$ . An implied literal may belong to multiple chunks if it depends on multiple decisions.
User-Defined Weight Function: GB introduces a weight function $\zeta: \mathcal{L} \to \mathbb{R}$ that maps literals to real numbers. This allows users to assign higher weights to literals they prefer to keep assigned (e.g., "heavy" literals).
Chunk Selection Strategy: Upon detecting a conflict clause $C$ $C$ , GB identifies the set of chunks $\gamma(C)$ $γ (C)$ involved in the conflict. It selects a set of chunks $\Gamma^*$ $Γ^{*}$ to undo such that:
- Exactly one chunk from $\gamma(C)$ is undone (to ensure the learned clause becomes unit).
- The total weight of the undone literals is minimized.
- Termination Safeguards: To prevent infinite loops (where the same conflict recurs without learning new clauses), the selection is restricted to "terminating backtrack candidates." A candidate is valid if it either leads to learning a new clause or involves the most recent chunk in the conflict.

Algorithmic Adjustments

Conflict Analysis: The standard 1-UIP (Unique Implication Point) analysis is adapted to operate on chunks. The algorithm resolves clauses until exactly one literal belonging to the selected chunk $\Gamma^*$ remains, generating a learned clause that implies a flipped literal.
Backtracking: Unlike NCB/CB which unassigns a contiguous suffix of the trail, GB unassigns specific chunks. This requires recalculating decision levels for remaining literals and managing the trail structure dynamically.
Watched Literals & Invariants: The standard two-watched-literal scheme relies on a stack-like invariant where watchers are unassigned before other literals. GB breaks this ordering. To maintain soundness, the authors introduce cross-chunks ( $\eta(\ell)$ ), a set of chunks that, if undone, require literal $\ell$ to be repropagated. This leads to a revised invariant (Invariant 2) ensuring that if a watcher is unassigned, the other watcher is either satisfied or will be repropagated.

Key Contributions

Generalization: GB is proven to be a generalization of both NCB and CB. By defining specific weight functions, GB can simulate the behavior of NCB (backjumping to the second-highest level) and CB (backtracking to the highest level minus one).
Fine-Grained Control: The approach allows for "surgical" conflict repair, minimizing the number of unassigned literals based on user preferences (weights) rather than just decision order.
Theoretical Guarantees: The paper provides proofs for the soundness, completeness, and termination of the GB algorithm.
Implementation: The authors implemented GB in the experimental solver NapSAT, including optimizations such as:
- Blockers: Adapted for GB with cross-chunks.
- Chunk Merging: Both Eager (ECM) and Lazy (LCM) strategies to handle missed implications and avoid redundant backtracking.
- Best Chunk Selection (BB): A heuristic to balance the trade-off between minimizing unassignments and ensuring progress.

Empirical Results

The authors evaluated GB against NCB, CB, and LSCB (Lazy Strong Chronological Backtracking) on 1,000 satisfiable 3-coloring instances.

Propagations: GB variants consistently required fewer literal propagations than standard approaches. The best configuration (GB+ECM) achieved 47% fewer propagations than NCB.
Runtime: The reduction in propagations translated to a runtime improvement of approximately 30% for the best configuration.
Trade-offs: While GB reduces the number of unassignments, the per-propagation cost is higher due to the overhead of maintaining chunks and cross-chunks. However, the net effect on difficult instances was positive.
Restarting: The authors noted that standard restarts penalize GB performance, as they conflict with GB's goal of minimizing unassignments. GB performs best in single-shot solving or scenarios where decision reordering is less critical than preserving specific assignments.

Significance and Claims

The paper claims that Graph Backtracking offers a more flexible and user-guided approach to SAT solving. By challenging the abstraction of decision levels, GB enables solvers to preserve "heavy" literals that would otherwise be discarded by aggressive backtracking schemes.

The authors position GB not as a replacement for all existing strategies, but as a general framework that subsumes NCB and CB while offering superior performance on specific benchmarks (like graph coloring) where minimizing the scope of backtracking is beneficial. They highlight its potential applicability in AVATAR-based frameworks and SMT solving, where the rigid stack structure of traditional CDCL may be a limitation, though they acknowledge that scaling to a massive number of decisions and integrating with theory solvers remains an open challenge.