TL;DR
This paper introduces novel methods for migrating the internal state of SAT solvers, enabling them to be paused and resumed, even across different machines or solvers. This capability offers significant advantages for fault tolerance, efficient resource utilization, and even improved solver performance through "hard restarts."
What Problem Does This Paper Address?
SAT solvers are powerful tools used in various applications, but their execution can be highly variable, sometimes taking hours or days. This unpredictability poses challenges for efficient resource management, especially in cloud environments with time limits (like serverless functions). The paper addresses the problem of how to effectively save and restore the complete internal state of a SAT solver, allowing computations to be paused and resumed later, potentially on different hardware or even using different solvers. This is crucial for applications requiring long-running computations, fault tolerance against hardware failures, and flexible scheduling on constrained resources.
Methods
The authors propose two main approaches for migrating SAT solver state:
- Explicit State Serialization: This method involves saving a "minimum viable subset" of the solver's internal data structures at the end of a run. This subset includes irredundant clauses, redundant clauses with their "literal block distance" (LBD) scores, and a "reconstruction stack" necessary for solution reconstruction. This approach is designed to be largely solver-agnostic and aims to minimize the overhead of storing and restoring state.
- Proof-Based State Migration: This more radical approach leverages the proof trace generated by SAT solvers. Instead of explicitly saving state at the end of a run, the solver continuously writes its state information as part of its proof. The authors introduce "Dual DRAT" (DDRAT), an extension to the standard DRAT proof format, which includes information for solution reconstruction (witnesses for clause deletions) and for distinguishing clause importance (usefulness scores for additions). This allows the state to be reconstructed from the proof log, making it robust against unexpected solver terminations.
Datasets
The experiments were conducted using the full benchmark suite from the SAT Competition 2021, which consists of 400 formulas. No new benchmarks were introduced.
Key Insights and Ideas
- "Hard Restarts" Can Boost Performance: The most surprising insight is that migrating solver state, which essentially acts as a "hard restart" (preserving only clause sets and LBDs, discarding heuristics and phases), can lead to significant performance improvements, particularly for solvers like CaDiCaL. This challenges the conventional wisdom that more preserved state is always better.
- Solver-Agnosticism is Achievable: The "minimum viable subset" approach demonstrates that it's possible to achieve solver-agnostic state migration, reducing brittleness and maintenance overhead associated with solver updates.
- Proof Traces as State Logs: The proof-based approach offers a compelling alternative by using the proof trace as a continuous, fault-tolerant log of the solver's state, eliminating the need for explicit state saving at the end of a run.
- Dual DRAT Extends Proof Utility: The DDRAT format effectively extends the utility of SAT proofs beyond just verifying unsatisfiability, enabling state reconstruction and solution recovery.
Key Results
- CaDiCaL Performance Improvement: For CaDiCaL, migrating state using the explicit serialization method led to a surprising performance increase, solving more instances than the original single-run approach.
- Combinatorial Solvers Excel: Combinations of CaDiCaL and MapleSat, particularly in a multi-run setting where they take turns, achieved the best overall performance, outperforming individual solvers.
- Overhead is Manageable: The time spent on storing and restoring state, while not negligible, was generally found to be a small fraction of the total solving time, especially for the explicit serialization method.
- Proof-Based Approach Robustness: The proof-based approach, while sometimes taking longer to restore state, offers superior robustness against unexpected solver crashes.
- Variance in Performance: Migrating solver state generally increased the variance in solving times, especially for satisfiable instances, where luck plays a larger role.
Limitations and Future Work
- Implementation Complexity: Adding support for DDRAT to solvers like MapleSat was found to be non-trivial, requiring several careful changes.
- Proof-Based Restore Time: Restoring state from proofs can sometimes take significantly longer than explicit state restoration.
- Future Work: The authors suggest extending the approach to support incremental solving, enabling the caching of incremental problems. They also envision this leading to new portfolio approaches, such as "late binding" parallelism and migrating queries to multiple solvers with permuted clauses or different seeds. The paper also hints at the potential for improved proof formats to further facilitate these techniques.
Summary updated