REVIEW 9 cited by
AutoSAT: Automatically Optimize SAT Solvers via Large Language Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Conflict-Driven Clause Learning (CDCL) is the mainstream framework for solving the Satisfiability problem (SAT), and CDCL solvers typically rely on various heuristics, which have a significant impact on their performance. Modern CDCL solvers, such as MiniSat and Kissat, commonly incorporate several heuristics and select one to use according to simple rules, requiring significant time and expert effort to fine-tune in practice. The pervasion of Large Language Models (LLMs) provides a potential solution to address this issue. However, generating a CDCL solver from scratch is not effective due to the complexity and context volume of SAT solvers. Instead, we propose AutoSAT, a framework that automatically optimizes heuristics in a pre-defined modular search space based on existing CDCL solvers. Unlike existing automated algorithm design approaches focusing on hyperparameter tuning and operator selection, AutoSAT can generate new efficient heuristics. In this first attempt at optimizing SAT solvers using LLMs, several strategies including the greedy hill climber and (1+1) Evolutionary Algorithm are employed to guide LLMs to search for better heuristics. Experimental results demonstrate that LLMs can generally enhance the performance of CDCL solvers. A realization of AutoSAT outperforms MiniSat on 9 out of 12 datasets and even surpasses the state-of-the-art hybrid solver Kissat on 4 datasets.
Forward citations
Cited by 9 Pith papers
-
Agentic MIP Research: Accelerated Constraint Handler Generation
LLM agents in a solver-aware harness recover global constraints from MIP formulations, generate executable propagation-only handlers for SCIP, and solve five additional MIPLIB 2017 instances.
-
IC3-Evolve: Proof-/Witness-Gated Offline LLM-Driven Heuristic Evolution for IC3 Hardware Model Checking
IC3-Evolve evolves IC3 heuristics via offline LLM patches that are admitted only after passing proof or witness validation, yielding standalone improved checkers evaluated on HWMCC and unseen benchmarks.
-
MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources
MiniOpt is an RL framework that decomposes optimization reasoning into modeling and solver generation, achieving top solving accuracy for models under 10B parameters across diverse problem types using OptReward and op...
-
An Information-Theoretic Criterion for Efficient Data Synthesis
Synthetic data improves models only in information-open generation-training loops with external signals, and coarser signals like binary correctness enable better generalization by converging to the most information-e...
-
Discovering heuristics in a complex SAT solver with large language models
LLM-guided evolutionary search over seven modularized SAT solver heuristics yields solvers that beat tuned Kissat and CaDiCaL on most of eleven test families.
-
MiniOpt: Reasoning to Model and Solve General Optimization Problems with Limited Resources
MiniOpt trains LLMs under 10B parameters via RL with OptReward to model and solve general optimization problems, reporting highest average solving accuracy among comparable models.
-
PyVRP$^+$: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems
MEP uses LLMs in a structured reasoning cycle to evolve improved heuristics for HGS on VRPs, achieving up to 2.7% better solution quality and over 45% reduced runtime.
-
A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving
A literature survey that classifies LLM-based optimization research into modeling and solving, with solving divided into LLMs as optimizers, low-level components, and high-level managers.
-
Large Language Models for Operations Research: A Comprehensive Survey
A survey compiling roles, applications, benchmarks, challenges, and future directions for large language models in operations research.
Discussion (0). Sign in to comment.