# CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 16 Jul 2026.

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

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [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)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Approximation Algorithms for Combinatorial Optimization with Predictions](https://mlsanity.com/paper/2411.16600/) (2024)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut](https://mlsanity.com/paper/2402.02328/) (2024)
- [Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems](https://mlsanity.com/paper/2502.00841/) (2025)
- [Max-Cut with ε-Accurate Predictions](https://mlsanity.com/paper/2402.18263/) (2024)
- [Competitive strategies to use "warm start" algorithms with predictions](https://mlsanity.com/paper/2405.03661/) (2024)
- [Improved Approximations for Hard Graph Problems using Predictions](https://mlsanity.com/paper/2505.23967/) (2025)

## Abstract (arXiv)

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from tilde O(varepsilon-2log K) samples (K the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread R, none below Omega(R/varepsilon2). Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to 26% of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.