# Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 54 references that are in the map.
- First posted on arXiv 24 May 2024.

## Builds on (most cited first, 30 of 32)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Verisig: verifying safety properties of hybrid systems with neural network controllers](https://mlsanity.com/paper/1811.01828/) (2018)
- [Distribution-free binary classification: prediction sets, confidence intervals and calibration](https://mlsanity.com/paper/2006.10564/) (2020)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Few-shot Conformal Prediction with Auxiliary Tasks](https://mlsanity.com/paper/2102.08898/) (2021)
- [Neurosymbolic Reinforcement Learning with Formally Verified Exploration](https://mlsanity.com/paper/2009.12612/) (2020)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [PAC Prediction Sets Under Covariate Shift](https://mlsanity.com/paper/2106.09848/) (2021)
- [HOUDINI: Lifelong Learning as Program Synthesis](https://mlsanity.com/paper/1804.00218/) (2018)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [PAC Confidence Predictions for Deep Neural Network Classifiers](https://mlsanity.com/paper/2011.00716/) (2020)
- [PAC Prediction Sets for Meta-Learning](https://mlsanity.com/paper/2207.02440/) (2022)
- [Rekall: Specifying Video Events using Compositions of Spatiotemporal Labels](https://mlsanity.com/paper/1910.02993/) (2019)
- [TerpreT: A Probabilistic Programming Language for Program Induction](https://mlsanity.com/paper/1608.04428/) (2016)
- [Neurosymbolic Transformers for Multi-Agent Communication](https://mlsanity.com/paper/2101.03238/) (2021)
- [When Does Uncertainty Matter?: Understanding the Impact of Predictive Uncertainty in ML Assisted Decision Making](https://mlsanity.com/paper/2011.06167/) (2020)
- [Web Question Answering with Neurosymbolic Program Synthesis](https://mlsanity.com/paper/2104.07162/) (2021)
- [Data Extraction via Semantic Regular Expression Synthesis](https://mlsanity.com/paper/2305.10401/) (2023)

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

- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Quasar: A Programming Language Specialized for LLM Code Actions](https://mlsanity.com/paper/2506.12202/) (2025)
- [Conformal Risk-Averse Decision Making with Action Conditional Guarantee](https://mlsanity.com/paper/2606.05551/) (2026)
- [Concise and Logically Consistent Conformal Sets for Neuro-Symbolic Concept-Based Models](https://mlsanity.com/paper/2605.18202/) (2026)

## Abstract (arXiv)

Machine learning has become an effective tool for automatically annotating unstructured data (e.g., images) with structured labels (e.g., object detections). As a result, a new programming paradigm called neurosymbolic programming has emerged where users write queries against these predicted annotations. However, due to the intrinsic fallibility of machine learning models, these programs currently lack any notion of correctness. In many domains, users may want some kind of conservative guarantee that the results of their queries contain all possibly relevant instances. Conformal prediction has emerged as a promising strategy for quantifying uncertainty in machine learning by modifying models to predict sets of labels instead of individual labels; it provides a probabilistic guarantee that the prediction set contains the true label with high probability. We propose a novel framework for adapting conformal prediction to neurosymbolic programs; our strategy is to represent prediction sets as abstract values in some abstract domain, and then to use abstract interpretation to propagate prediction sets through the program. Our strategy satisfies three key desiderata: (i) correctness (i.e., the program outputs a prediction set that contains the true output with high probability), (ii) compositionality (i.e., we can quantify uncertainty separately for different modules and then compose them together), and (iii) structured values (i.e., we can provide uncertainty quantification for structured values such as lists). When the full program is available ahead-of-time, we propose an optimization that incorporates conformal prediction at intermediate program points to reduce imprecision in abstract interpretation. We evaluate our approach on programs that take MNIST and MS-COCO images as input, demonstrating that it produces reasonably sized prediction sets while satisfying a coverage guarantee.