Target-Aware Data Augmentation for SAT Prediction

Eshed Gal, Uri Ascher, Eldad Haber · 2026

Read Target-Aware Data Augmentation for SAT Prediction by Eshed Gal, Uri Ascher, Eldad Haber (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06931.txt.

Introduction

Eshed Gal, Uri Ascher, and Eldad Haber attack the data choke point in learning to predict Boolean satisfiability. Machine learning for hard combinatorial problems needs labeled cases, but tagging satisfiability instances needs costly solver runs, which scales badly. Their target-aware framework builds correctly labeled satisfying and unsatisfying instances by construction, with no solver in the loop, while matching the structural traits of a chosen target benchmark.

A paired graph network feeds constraint-violation leftovers into its message passing, using the optimization structure of the problem. Together the pieces yield far faster data generation, and the synthetic, benchmark-aligned data usefully augments solver-labeled sets for graph-based satisfiability guessing. The authors argue data design matters as much as model design here.

Catalog record

CREATOREshed Gal, Uri Ascher, Eldad Haber
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06931

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Target-Aware Data Augmentation for SAT Prediction Eshed Gal, Uri Ascher, Eldad Haber Abstract Learning-based approaches to NP-hard problems have shown increasing promise, but their progress is fundamentally constrained by the high cost of generating labeled training data. In domains such as Boolean satisfiability (SAT), standard pipelines rely on solver-in-the-loop labeling, which scales poorly with problem size and limits the amount of usable supervision. This bottleneck hinders the broader goal of leveraging machine learning to capture structure in hard combinatorial problems. In this work, we propose a target-aware, solver-free data generation framework for SAT that produces correctly labeled SAT and UNSAT instances by construction, eliminating the need for expensive solver calls. Our method aligns generated instances with the structural properties of a target benchmark, making synthetic data effective for downstream learning. We further develop a linear-programming-aware graph neural network (LPGNN) architecture that incorporates constraint-violation residuals into message passing, enabling the model to exploit underlying optimization structure. Together, these contributions support a data-centric paradigm for learning on NP-hard problems, where scalable, task-aligned data generation is as critical as model design. Our approach yields orders-of-magnitude speedups in data generation, demonstrating that benchmark-aligned synthetic data can effectively augment solver-labeled datasets for GNN-based SAT prediction. 1 Introduction Boolean satisfiability (SAT) is a canonical NP-complete problem ( 8 ) . This is a core primitive in formal verification ( 3 ) , combinatorial optimization ( 22 ) , and cryptanalysis ( 31 ) . Despite the worst-case NP-hardness of SAT, modern conflict-driven clause-learning (CDCL) solvers such as CaDiCaL ( 4 ) can approximately solve many large practical instances efficiently. At the same time, solver performance remains highly sensitive to instance structure, and the design of effective heuristics remains difficult and domain-specific. This has motivated increasing interest in machine learning methods for SAT, with the broader goal of using learned structure to improve performance on hard combinatorial problems. Recent works have shown that Graph Neural Networks (GNNs) can learn useful representations of SAT formulas from graph-based encodings. One major thread explores alternative graph constructions and literal-incidence encodings to better capture the underlying community and algebraic structure of formulas ( 2 ; 7 ; 24 ) . Another focuses on providing learned search guidance, ranging from local search heuristics to improving CDCL solver decisions ( 34 ; 32 ) . Some works focus on optimization-aware architectures that incorporate algebraic feasibility signals, such as linear programming residuals or energy-based functions, directly into message passing ( 19 ; 13 ; 6 ) . Together with comprehensive benchmark suites such as G4SATBench ( 21 ) , these advances have established SAT as a primary testbed for scaling machine learning methods on NP-hard problems. A basic premise of machine learning is that performance depends jointly on the architecture, the size of the model, and the quality and scale of the training data. The recent history of language modeling illustrates this point: progress accelerated once next-token prediction provided a scalable self-supervised objective, allowing increasingly large architectures to be trained on massive corpora ( 18 ; 17 ; 25 ; 5 ) . Without a scalable source of supervision, however, architectural improvements alone are difficult to exploit. For SAT learning, recent work has focused on graph representations and GNN architectures, and we also introduce architectural improvements below. However, SAT does not naturally come with a next-token-prediction analogue: supervision is typically obtained by generating formulas and then calling a complete SAT solver to determine whether each instance is SAT (satisfiable formula) or UNSAT (unsatisfiable formula). As formulas become larger and harder, this solver-in-the-loop labeling process becomes increasingly costly, limiting the amount of usable supervision and tying learning progress to exact solver runtime. Recent works have begun to highlight this issue explicitly ( 29 ) , and we discuss additional related literature in Appendix A . In this work, we address this data bottleneck directly. We propose a target-aware, solver-free data-generation framework that constructs SAT and UNSAT formulas with certified labels by construction while matching structural properties of a target benchmark. The goal is not merely to generate more data, but to generate data that is useful for downstream learning. In particular, we show that synthetic SAT data can be generated with meaningful benchmark-aligned structure. Such data, when combined with GNN architectures, improves predictive performance. This supports a data-centric view: progress depends not only on better architectures, but also on scalable mechanisms for producing informative training data. Although synthetic data augmentation carries an inherent risk of introducing distributional bias, prior work suggests it can act as an effective regularizer, often improving model robustness and downstream generalization ( 11 ; 30 ) . The starting point of our approach is a simple asymmetry. While solving SAT is NP-hard, that is, finding a satisfying assignment for a given formula is difficult in the worst case; constructing a formula around a known assignment is easier. This is analogous in spirit to the method of manufactured solutions in numerical partial differential equations, where one first chooses an exact solution and then constructs a problem for which that solution is known ( 27 ) . We exploit the same inverse viewpoint for SAT data generation: rather than sampling a formula and then invoking a solver to determine its label, we first construct a certificate, a satisfying assignment for SAT instances or an explicit contradiction for UNSAT instances, and then generate a CNF formula consistent with that certificate. Our generation method is therefore CNF-native and solver-free. For SAT instances, we construct clauses around a planted assignment. For UNSAT instances, we embed a certified contradiction and add benchmark-aligned filler clauses. In both cases, the label is known by construction, avoiding repeated calls to a complete solver during data generation. At the same time, target-aware matching reduces the distributional mismatch that would arise from generic planted constructions. In addition, we connect this data pipeline to an optimization-aware model design. Using the standard binary linear encoding of CNF formulas, we represent SAT as a feasibility problem and derive a Linear Programming (LP)-aware residual mechanism that injects constraint-violation information into message passing. This exposes algebraic feasibility structure to the GNN and complements the proposed generation framework, following the general direction of optimization-aware graph learning ( 13 ; 19 ) . Overall, this work advances a simple claim: for machine learning on NP-hard problems, scalable and task-aligned data generation can be as important as model architecture. Contributions. • We propose a target-aware solver-free data-generation framework for SAT learning, motivated by the broader challenge of scaling machine learning methods for NP-hard problems. • We introduce a CNF-native formula-generation strategy that produces correctly labeled SAT and UNSAT formulas by construction, avoiding repetitive solver calls during data generation. • We develop a benchmark-aligned augmentation approach that matches generated formulas to structural and algebraic properties of a target distribution, making synthetic data more useful for downstream learning than generic generated instances. • We formulate the learning pipeline through a binary linear feasibility view that connects CNF formulas, generated instances, and graph-based learning in a common algebraic framework. • We introduce an LP-aware residual GNN architecture that incorporates feasibility-related signals into message passing, complementing the proposed data-generation framework with an optimization-aware model component. 2 Related Work Graph representations for SAT. A central

Read the complete text