Incremental Solving for Efficient Formal Reasoning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 266 papers100 conceptsfrozen 2026-10-04

In traditional automated reasoning, a solver is often treated as a "black box." You provide a complex logical formula, the solver works in isolation, and it returns a result: "Satisfiable" or "Unsatisfiable." Once the answer is delivered, the solver’s internal state is typically discarded.

However, real-world problems—ranging from verifying software to planning robot trajectories—rarely consist of a single, isolated query. Instead, they involve a sequence of closely related questions. If you add one new constraint to a problem you just solved, should you really have to start the entire search from scratch?

Incremental solving is the paradigm shift that treats the solver as a stateful machine. By preserving learned information across a sequence of queries, incremental techniques allow solvers to "remember" why certain paths were dead ends, transforming exponential search tasks into manageable computations.

The Cost of Forgetting

To understand why incremental solving is necessary, consider Bounded Model Checking (BMC). In BMC, we check if a system property holds for a path of length $k$. If no bug is found, we increase the depth to $k+1$ and try again.

As Daniel Kroening and colleagues point out in their work on Incremental Bounded Model Checking, traditional tools that "start from scratch" at each depth perform massive amounts of redundant work. The solver is forced to repeatedly rediscover the same logical implications and conflict clauses it already found at depth $k$. This lack of state retention is a primary bottleneck in verifying complex software.

The Mechanism of Persistence

The "magic" of modern solvers like CVC3, developed by Clark Barrett and Cesare Tinelli, lies in their ability to maintain an internal state. This is achieved through two primary mechanisms:

1. Learned Clause Reuse

When a SAT or SMT solver encounters a contradiction, it performs "conflict analysis" to learn a new clause—a rule that explains why a specific combination of variables is impossible. In an incremental setting, these learned clauses are kept in memory. When the next query arrives, the solver already knows large sections of the search space are off-limits, significantly pruning the tree.

2. Stack-Based State Management

To allow users to add and remove constraints flexibly, solvers implement a push/pop mechanism. A "push" command saves the current state of the solver (including all learned lemmas), and a "pop" command reverts to that saved state. This allows for "assumption-based" queries, where a base model is tested against varying sets of additional conditions without re-initializing the entire system.

Multi-Shot Solving and Grounding

In Answer Set Programming (ASP) and other high-level logic frameworks, the challenge is even steeper. Before a solver can search for a solution, it must "ground" the program—translating high-level rules into a massive Boolean formula.

Thomas Eiter and others have pioneered multi-shot computation to address this. As seen in Large-Neighbourhood Search for ASP, multi-shot solving preserves the "warm" state of the solver, including grounded rules and internal heuristics. This is essential for iterative tasks like industrial scheduling or real-time emergency planning, where the solver must react to new observations within milliseconds.

Applications Across the Research Landscape

The intuition of "reusing work" manifests in several specialized algorithms:

  • Diagnostic Tools: Ulrich Junker’s QUICKXPLAIN uses a recursive strategy to find minimal sets of conflicting constraints. By reusing "witnesses" (partial solutions) from previous consistency checks, it avoids redundant evaluations in interactive configuration.
  • Neural Network Explanation: Algorithms like FaVeX by Greta Dolcetti accelerate the generation of verified explanations for AI decisions. By caching internal search trees and bounds across correlated queries, the system avoids re-proving the same properties for different parts of a neural network.
  • Optimization: In MaxSAT solving, Mikolás Janota and colleagues demonstrate that reusing unsatisfiable cores—high-level explanations of why a formula is unsolveable—allows solvers to maintain progress even as the underlying formula evolves.
  • Local Verification: Even as far back as 1992, Kim Guldstrand Larsen showed that memoization in local correctness checking could reduce complexity from exponential to polynomial by preventing the re-exploration of previously visited states.

The Bottom Line

Incremental solving works because logical problems are rarely random; they have structure that persists even when small changes are made. By treating the solver's internal knowledge as a reusable asset rather than a disposable byproduct, researchers have enabled formal reasoning to scale from small puzzles to the verification of industrial-scale autonomous systems and complex software.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 47 papers
  2. Version 1 · 2026-10-04 · 66 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_learned_clause_retention_a006baf0,
  title = {learned clause retention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/learned-clause-retention/rdr_a006baf0c3e14574974fb3a69b140fc5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_incremental_solving_for_efficient_formal_a006baf0_v1,
  title = {Incremental Solving for Efficient Formal Reasoning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-solving-for-efficient-formal-reasoning/rdr_a006baf0c3e14574974fb3a69b140fc5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}