Probabilistic-bit Guided CDCL for SAT Solving using Ising Consensus Assumptions

• URL: http://arxiv.org/abs/2605.04033v1
• Date: Tue, 05 May 2026 17:54:42 GMT
• Title: Probabilistic-bit Guided CDCL for SAT Solving using Ising Consensus Assumptions
• Abstract summary: This paper studies a hybrid SAT-solving framework in which a probabilistic-bit (p-bit) Ising sampler proposes high-agreement literals that are passed to CDCL as temporary assumptions.<n>On selected controlled-backbone random 3-SAT benchmarks, the hybrid method reduces median conflicts by 80.8-85.5% and median propagation by 80.2-84.6% relative to pure CDCL.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Boolean satisfiability (SAT) solvers are widely used in hardware verification, cryptanalysis, automatic test-pattern generation, and side-channel reasoning workflows. Modern conflict-driven clause-learning (CDCL) solvers are highly effective, but satisfiable instances may still require substantial conflict analysis and Boolean propagation before identifying productive regions of the search space. This paper studies a hybrid SAT-solving framework in which a probabilistic-bit (p-bit) Ising sampler proposes high-agreement literals that are passed to CDCL as temporary assumptions. The goal is not to replace CDCL, but to evaluate whether stochastic low-violation samples can reduce CDCL internal search effort while retaining correctness through CDCL fallback. On selected controlled-backbone random 3-SAT benchmarks, the hybrid method reduces median conflicts by 80.8-85.5% and median propagations by 80.2-84.6% relative to pure CDCL. The observed benefit is distribution-sensitive, suggesting that p-bit guidance is effective only for certain instance classes. We further report exploratory machine-learning gates that estimate when hybrid solving is likely to help. On the selected run, a random-forest gate retains 94.8% of hybrid wins, indicating that lightweight gating may help avoid unproductive hybrid calls.

Related papers

• Non-Clifford Benchmarking via Ensemble Feature Selection [0.0]
  We propose an Ensemble Feature Selection (EFS) method for fast estimation of process infidelity of involutory multi-qubit gates.<n>The method selects a compact set of experimentally executable circuit measurements from a candidate pool through offline training.<n>The training ensemble is an explicit and tunable component of the protocol, incorporating prior knowledge about dominant hardware noise mechanisms.
  arXiv  Detail & Related papers  (2026-07-01T17:11:26Z)
• Efficient Conditioning Why Pseudo Observation Batch Bayesian Optimization Works When It Does not [0.0]
  Constant Liar (CL), Kriging Believer (KB), and fantasy models are widely used for batch selection in parallel Bayesian Optimization.<n>We identify efficient conditioning as the key surrogate property the ability to update predictions in closed form when data is augmented.<n>We unify CL, KB, and fantasy models as instances of a single conditioning mechanism differing only in lie value distribution.
  arXiv  Detail & Related papers  (2026-05-12T13:14:24Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• Learnable Chernoff Baselines for Inference-Time Alignment [64.81256817158851]
  We introduce Learnable Chernoff Baselines as a method for efficiently and approximately sampling from exponentially tilted kernels.<n>We establish total-variation guarantees to the ideal aligned model, and demonstrate in both continuous and discrete diffusion settings that LCB sampling closely matches ideal rejection sampling.
  arXiv  Detail & Related papers  (2026-02-08T00:09:40Z)
• Conflict-Driven Clause Learning with VSIDS Heuristics for Discrete Facility Layout [0.0]
  This paper studies the use of Conflict-Driven Clause Learning (CDCL) withDSs as a computational engine for discrete facility layout problems.<n>We develop a CNF-based formulation for layout feasibility and compare CDCL-based SAT solving against CPSAT and MILP formulations.
  arXiv  Detail & Related papers  (2025-12-19T20:03:37Z)
• SafeBench-Seq: A Homology-Clustered, CPU-Only Baseline for Protein Hazard Screening with Physicochemical/Composition Features and Cluster-Aware Confidence Intervals [26.81598226089532]
  We introduce SafeBench-Seq, a metadata-only, reproducible benchmark and baseline classifier built entirely from public data.<n>To approximate "never-before-seen" threats, we homology-cluster the combined dataset at =40% identity and perform cluster-level holdouts.<n>We report discrimination (AUROC/AUPRC) and screening-operating points (TPR@1% FPR; FPR@95% TPR) with 95% bootstrap confidence intervals (n=200)<n>We quantify probability quality using Brier score, Expected Error (ECE); 15 bins, and reliability diagrams.
  arXiv  Detail & Related papers  (2025-12-19T12:51:31Z)
• Kolmogorov Arnold Networks in Fraud Detection: Bridging the Gap Between Theory and Practice [3.692410936160711]
  This study evaluates the applicability of Kolmogorov-Arnold Networks (KAN) in fraud detection, finding that their effectiveness is context-dependent. We propose a quick decision rule using Principal Component Analysis (PCA) to assess the suitability of KAN: if data can be effectively separated in two dimensions using splines, KAN may outperform traditional models; otherwise, other methods could be more appropriate.
  arXiv  Detail & Related papers  (2024-08-15T18:58:21Z)
• Sample-Efficient "Clustering and Conquer" Procedures for Parallel Large-Scale Ranking and Selection [3.913403111891027]
  We modify the commonly used "divide and conquer" framework in parallel computing by adding a correlation-based clustering step.<n>This seemingly simple modification yields an $mathcalO(p)$ reduction in sample complexity for a widely used class of sample-optimal R&S procedures.<n>In large-scale AI applications such as neural architecture search, our methods demonstrate superior performance.
  arXiv  Detail & Related papers  (2024-02-03T15:56:03Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Actor-Critic based Improper Reinforcement Learning [61.430513757337486]
  We consider an improper reinforcement learning setting where a learner is given $M$ base controllers for an unknown Markov decision process. We propose two algorithms: (1) a Policy Gradient-based approach; and (2) an algorithm that can switch between a simple Actor-Critic scheme and a Natural Actor-Critic scheme.
  arXiv  Detail & Related papers  (2022-07-19T05:55:02Z)
• Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
  Predict then Interpolate (PI) is an algorithm for learning correlations that are stable across environments. We prove that by interpolating the distributions of the correct predictions and the wrong predictions, we can uncover an oracle distribution where the unstable correlation vanishes.
  arXiv  Detail & Related papers  (2021-05-26T15:37:48Z)
• Semi-supervised Contrastive Learning with Similarity Co-calibration [72.38187308270135]
  We propose a novel training strategy, termed as Semi-supervised Contrastive Learning (SsCL) SsCL combines the well-known contrastive loss in self-supervised learning with the cross entropy loss in semi-supervised learning. We show that SsCL produces more discriminative representation and is beneficial to few shot learning.
  arXiv  Detail & Related papers  (2021-05-16T09:13:56Z)

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.