In modern automated reasoning, solving a complex logical problem is rarely a one-shot event. Whether verifying a neural network, planning a robot's path, or explaining an AI's decision, researchers often face a sequence of nearly identical queries. Traditionally, solvers treated each query as a fresh start, discarding everything they learned about the problem's structure.
The shift toward incremental solving changes this. By retaining internal states—specifically "learned clauses"—solvers can avoid redundant work, transforming tasks that once took hours into processes that finish in seconds.
The Cost of Starting Over
When a solver explores a search space, it doesn't just look for a solution; it learns why certain paths are dead ends. In Boolean Satisfiability (SAT) and related fields, this knowledge is codified as "learned clauses"—logical shortcuts that prune the search tree.
As Cheng et al. note, standard solvers often lack the ability to handle incremental updates, forcing a full re-computation when parameters change. This "cold start" is computationally expensive because the solver must re-discover the same logical implications it found in previous runs. Bjørner et al. argue that maintaining efficiency in iterative optimization requires the ability to reuse these learned clauses across successive steps, as heavy formula transformations often force the system to discard this valuable information.
Learned Clauses as Search Space Maps
To understand why retention works, think of learned clauses as a map of a maze. If you move the exit slightly, you don't need to re-map the entire maze; most of the walls are still in the same place.
Li et al. describe "knowledge-preserving search resets," where a solver periodically restarts its search but maintains a persistent memory of learned clauses. This allows the solver to re-evaluate its decisions using the cumulative constraints discovered across all previous iterations. Similarly, Nieuwenhuis et al. demonstrate that maintaining solver state across multiple satisfying assignments prevents the redundant exploration of the search tree, providing substantial speedups in formal verification.
Mechanisms of Persistence
The research community has developed several architectural patterns to enable this retention:
- Push and Pop Stacks: Barrett et al. describe a stack-based mechanism in the CVC3 solver that allows users to add or remove assumptions while maintaining the solver's state. This allows learned lemmas to be reused across multiple related queries.
- Multi-shot Solving: In Answer Set Programming (ASP), Son et al. highlight "multi-shot" computation, which allows a solver to update constraints and rules without re-initializing. Thomas Eiter explains that this keeps the solver "warm," avoiding the high cost of repeated grounding (the process of turning abstract rules into concrete logic).
- Residual Data: Likitvivatanavong et al. and Lecoutre et al. explore "residual supports"—information left over from previous search steps that allows solvers to skip redundant checks during backtracking.
Assumptions: The Toggle Switch
A key challenge in incremental solving is how to remove a constraint without invalidating the learned clauses that depend on it. The solution often involves "assumption literals."
Instead of permanently adding a constraint, the solver adds a conditional constraint: "If variable $A$ is true, then the constraint must hold." By treating $A$ as a temporary assumption, the solver can "deactivate" the constraint later by simply setting $A$ to false. Kroening et al. show that this allows a solver to treat error properties as temporary, preserving conflict clauses across successive loop unwindings in software verification. Mencía et al. further demonstrate that assumption-based queries allow for testing literals without the overhead of creating new variables for every clause.
Impact on Iterative Reasoning
The ability to build upon previous work has enabled breakthroughs in several domains:
- Explainability: When generating long chains of logical explanations, Gamba et al. show that bootstrapping a solver with previously discovered satisfiable subsets prevents the exponential growth of computational costs.
- Bounded Model Checking: Heljanko et al. utilize incremental encodings that preserve information across increasing search depths, ensuring the cost of extending the search horizon is minimized.
- Optimization: In strip packing problems, Inoue et al. found that carrying over knowledge of impossible configurations from previous iterations significantly reduces the search space.
By treating the solver as a stateful entity rather than a stateless function, this research direction ensures that every second of computation contributes to the final answer, regardless of how many times the underlying problem is refined.
Key Foundational Work
Composition in Hierarchical CLP (1995) — contributed 1 concept elements to this direction.
QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems (2004) — contributed 1 concept elements to this direction.