# Learning-Augmented Algorithms for Boolean Satisfiability

arXiv: https://arxiv.org/abs/2505.06146 · HTML: https://mlsanity.com/paper/2505.06146/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 59 references that are in the map.
- First posted on arXiv 9 May 2025.

## Builds on (most cited first, 18 of 18)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Paging with Succinct Predictions](https://mlsanity.com/paper/2210.02775/) (2022)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Learning-Augmented Streaming Algorithms for Approximating MAX-CUT](https://mlsanity.com/paper/2412.09773/) (2024)
- [Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems](https://mlsanity.com/paper/2402.02062/) (2024)
- [Constraint Satisfaction Problems with Advice](https://mlsanity.com/paper/2403.02212/) (2024)
- [Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems](https://mlsanity.com/paper/2502.00841/) (2025)
- [Breaking the PPSZ Barrier for Unique 3-SAT](https://mlsanity.com/paper/1311.2513/) (2013)
- [Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT](https://mlsanity.com/paper/1804.07901/) (2018)
- [PPSZ is better than you think](https://mlsanity.com/paper/2207.11071/) (2022)
- [Tight approximability of MAX 2-SAT and relatives, under UGC](https://mlsanity.com/paper/2310.12911/) (2023)

## Built on by (most cited first, 1 of 1)

- [Learning-augmented smooth integer programs with PAC-learnable oracles](https://mlsanity.com/paper/2602.02505/) (2026)

## Abstract (arXiv)

Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') from a machine-learning oracle, which provides partial information about an optimal solution, and the goal is to design algorithms that leverage this advice to improve worst-case performance. We study the classic Boolean satisfiability (SAT) decision and optimization problems within this framework using two forms of advice. ``Subset advice" provides a random ε fraction of the variables from an optimal assignment, whereas ``label advice" provides noisy predictions for all variables in an optimal assignment. For the decision problem k-SAT, by using the subset advice we accelerate the exponential running time of the PPSZ family of algorithms due to Paturi, Pudlak, Saks and Zane, which currently represent the state of the art in the worst case. We accelerate the running time by a multiplicative factor of 2-c in the base of the exponent, where c is a function of ε and k. For the optimization problem, we show how to incorporate subset advice in a black-box fashion with any α-approximation algorithm, improving the approximation ratio to α + (1 - α)ε. Specifically, we achieve approximations of 0.94 + Omega(ε) for MAX-2-SAT, 7/8 + Omega(ε) for MAX-3-SAT, and 0.79 + Omega(ε) for MAX-SAT. Moreover, for label advice, we obtain near-optimal approximation for instances with large average degree, thereby generalizing recent results on MAX-CUT and MAX-2-LIN.