# Conformal Structured Prediction

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 24 references that are in the map.
- First posted on arXiv 8 Oct 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [GoEmotions: A Dataset of Fine-Grained Emotions](https://mlsanity.com/paper/2005.00547/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Distribution-Free Prediction Sets for Two-Layer Hierarchical Models](https://mlsanity.com/paper/1809.07441/) (2018)
- [TRAQ: Trustworthy Retrieval Augmented Question Answering via Conformal Prediction](https://mlsanity.com/paper/2307.04642/) (2023)
- [Confident Object Detection via Conformal Prediction and Conformal Risk Control: an Application to Railway Signaling](https://mlsanity.com/paper/2304.06052/) (2023)
- [Distribution-free inference with hierarchical data](https://mlsanity.com/paper/2306.06342/) (2023)
- [PAC-Wrap: Semi-Supervised PAC Anomaly Detection](https://mlsanity.com/paper/2205.10798/) (2022)
- [PAC Prediction Sets for Large Language Models of Code](https://mlsanity.com/paper/2302.08703/) (2023)
- [Set-valued prediction in hierarchical classification with constrained representation complexity](https://mlsanity.com/paper/2203.06676/) (2022)

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

- [Adaptive Stopping for Multi-Turn LLM Reasoning](https://mlsanity.com/paper/2604.01413/) (2026)
- [Quasar: A Programming Language Specialized for LLM Code Actions](https://mlsanity.com/paper/2506.12202/) (2025)
- [Conformal Graph Prediction with Z-Gromov-Wasserstein Distances](https://mlsanity.com/paper/2603.02460/) (2026)
- [Decomposition-Based Modular Conformal Prediction for Two-Stage Modeling](https://mlsanity.com/paper/2510.04406/) (2025)
- [Enhancing Conformal Prediction via Class Similarity](https://mlsanity.com/paper/2511.19359/) (2025)
- [Reliable Hierarchical Operating System Fingerprinting via Conformal Prediction](https://mlsanity.com/paper/2602.12825/) (2026)
- [Multi-Variable Conformal Prediction: Optimizing Prediction Sets without Data Splitting](https://mlsanity.com/paper/2605.12341/) (2026)
- [SPARC: Single-Pass Scaling for Motion Forecasting with Conformal Bayesian Last Layers](https://mlsanity.com/paper/2608.20802/) (2026)
- [View-Structured Conformal Prediction for 3D Gaussian Splatting](https://mlsanity.com/paper/2609.10307/) (2026)
- [Adaptive Computation with Conformal Certification](https://mlsanity.com/paper/2610.19189/) (2026)

## Abstract (arXiv)

Conformal prediction has recently emerged as a promising strategy for quantifying the uncertainty of a predictive model; these algorithms modify the model to output sets of labels that are guaranteed to contain the true label with high probability. However, existing conformal prediction algorithms have largely targeted classification and regression settings, where the structure of the prediction set has a simple form as a level set of the scoring function. However, for complex structured outputs such as text generation, these prediction sets might include a large number of labels and therefore be hard for users to interpret. In this paper, we propose a general framework for conformal prediction in the structured prediction setting, that modifies existing conformal prediction algorithms to output structured prediction sets that implicitly represent sets of labels. In addition, we demonstrate how our approach can be applied in domains where the prediction sets can be represented as a set of nodes in a directed acyclic graph; for instance, for hierarchical labels such as image classification, a prediction set might be a small subset of coarse labels implicitly representing the prediction set of all their more fine-descendants. We demonstrate how our algorithm can be used to construct prediction sets that satisfy a desired coverage guarantee in several domains.