Target-Aware Data Augmentation for SAT Prediction

• URL: http://arxiv.org/abs/2605.06931v1
• Date: Thu, 07 May 2026 20:45:08 GMT
• Title: Target-Aware Data Augmentation for SAT Prediction
• Abstract summary: In domains such as Boolean satisfiability (SAT), standard pipelines rely on solver-in-the-loop labeling.<n>This bottleneck hinders the broader goal of leveraging machine learning to capture structure in hard problems.<n>We propose a target-aware, solver-free data generation framework for SAT that produces correctly labeled SAT and UNSAT instances by construction.
• Score: 5.288977149942441
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• How LLMs Fail and Generalize in RTL Coding for Hardware Design? [56.361436215029045]
  We introduce a new error taxonomy grounded in problem solvability, inspired by cognitive theory.<n>Our taxonomy categorizes failures into syntactic, semantic, solvable functional, and unsolvable functional types.
  arXiv  Detail & Related papers  (2026-04-26T14:34:49Z)
• Towards Neural Graph Data Management [48.66793294452754]
  We introduce NGDBench, a unified benchmark for evaluating neural graph database capabilities across five diverse domains.<n>NGDBench supports the full Cypher query language, enabling complex pattern matching, variable-length paths, and numerical aggregations.<n>Our evaluation of state-of-the-art LLMs and RAG methods reveals significant limitations in structured reasoning, noise robustness, and analytical precision.
  arXiv  Detail & Related papers  (2026-02-27T08:59:25Z)
• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• RV-Syn: Rational and Verifiable Mathematical Reasoning Data Synthesis based on Structured Function Library [58.404895570822184]
  RV-Syn is a novel mathematical Synthesis approach.<n>It generates graphs as solutions by combining Python-formatted functions from this library.<n>Based on the constructed graph, we achieve solution-guided logic-aware problem generation.
  arXiv  Detail & Related papers  (2025-04-29T04:42:02Z)
• DPFAGA-Dynamic Power Flow Analysis and Fault Characteristics: A Graph Attention Neural Network [0.19439126568870457]
  We propose the joint graph attention neural network (GAT) and clustering with adaptive neighbors (CAN) for dynamic power flow analysis and fault characteristics.<n>We then evaluate the proposed framework in the use-case application in smart grid and make a fair comparison to the existing methods.
  arXiv  Detail & Related papers  (2025-03-19T03:17:11Z)
• DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment [57.62885438406724]
  Graph neural networks are recognized for their strong performance across various applications. BP has limitations that challenge its biological plausibility and affect the efficiency, scalability and parallelism of training neural networks for graph-based tasks. We propose DFA-GNN, a novel forward learning framework tailored for GNNs with a case study of semi-supervised learning.
  arXiv  Detail & Related papers  (2024-06-04T07:24:51Z)
• EPIC: Effective Prompting for Imbalanced-Class Data Synthesis in Tabular Data Classification via Large Language Models [39.347666307218006]
  Large language models (LLMs) have demonstrated remarkable in-context learning capabilities across diverse applications.<n>We introduce EPIC, a novel approach that leverages balanced, grouped data samples and consistent formatting with unique variable mapping to guide LLMs in generating accurate synthetic data across all classes, even for imbalanced datasets.
  arXiv  Detail & Related papers  (2024-04-15T17:49:16Z)
• Quadratic Binary Optimization with Graph Neural Networks [20.497024298986883]
  We investigate a link between Graph Neural Networks (GNNs) and Quadratic Unconstrained Binary Optimization (QUBO) problems.<n>We propose QUBO-GNN, an architecture that integrates graph representation learning techniques with QUBO-aware features to approximate solutions efficiently.
  arXiv  Detail & Related papers  (2024-04-07T08:38:35Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  We train oracles using Graph Neural Networks and evaluate them on two SLS solvers on random SAT instances of varying difficulty. We find that access to GNN-based oracles significantly boosts the performance of both solvers.
  arXiv  Detail & Related papers  (2023-09-20T16:27:52Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  We analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We show that augmenting the structural representation of problems with Distance is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.
  arXiv  Detail & Related papers  (2022-01-03T14:14:28Z)
• Adaptive Anomaly Detection for Internet of Things in Hierarchical Edge Computing: A Contextual-Bandit Approach [81.5261621619557]
  We propose an adaptive anomaly detection scheme with hierarchical edge computing (HEC) We first construct multiple anomaly detection DNN models with increasing complexity, and associate each of them to a corresponding HEC layer. Then, we design an adaptive model selection scheme that is formulated as a contextual-bandit problem and solved by using a reinforcement learning policy network.
  arXiv  Detail & Related papers  (2021-08-09T08:45:47Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNF-based SAT and MaxSAT solvers are central to logic synthesis and verification systems. In this work, we propose a one-shot model derived from the Transformer architecture to solve the MaxSAT problem.
  arXiv  Detail & Related papers  (2021-07-15T04:47:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.