Research map / Learning theory and algorithms / Prediction and decision losses

Conformal Structured Prediction

ICLR 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Conformal prediction sets · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a general conformal prediction framework for structured outputs that searches over a tau threshold with learn-then-test style tests, yielding marginal or PAC coverage, and instantiates it for DAG-structured prediction sets solved via integer programming.

Problem

Conventional conformal prediction returns label sets that are large and hard to interpret for structured outputs such as text generation or hierarchical labels, and monotonicity-based tau search does not hold for structured prediction sets.

Approach

Replace monotone threshold search with a sequential learn-then-test procedure over candidate thresholds tau that returns the last valid threshold, combined with an optimizer (an integer program for DAG-structured sets) that returns structured prediction sets implicitly representing label sets, with marginal and PAC coverage guarantees.

Key results

• Marginal and PAC guarantees hold empirically: mean coverage stays near or above the 1-epsilon target across the five domains, with PAC coverage above target for almost all seeds.
• Structured prediction sets are smaller than the baseline's sets for almost every parameter setting and significantly so for m=2 and m=4 (per the paper's figures).
• On the question answering task (Llama-3.1-70B-Instruct, about 33.2% accuracy), the method produces interval-based sets such as four intervals at epsilon=0.05, m=4, versus six singleton years in standard conformal prediction in the qualitative example.

Measured effects reported in the paper

Surprising findings

• Prior baseline approaches that prioritize probability mass can achieve coverage as low as 50% or less, whereas the proposed method meets the target coverage.

Limitations

• Integer program solve time can grow with DAG density (e.g., 3-digit MNIST) and some question answering settings with m=2 show drastic runtime increases.
• Guarantees rely on the calibration and test examples being i.i.d. and on the same algorithm being used for calibration and new examples.
• Experiments are limited to a small number of domains and the QA task uses only 262 examples.

Experimental setup

Datasets: MNIST ImageNet SQuAD MBPP GoEmotions

Benchmarks: MNIST ImageNet SQuAD (years 1970-2020) MBPP GoEmotions

Metrics: empirical coverage rate average prediction set size running time

Baselines: PAC prediction set baseline adapted from code-generation conformal work

Builds on: learn-then-test conformal prediction PAC prediction sets

Closest papers by meaning

• Hierarchical Conformal Classification (NeurIPS 2026 · similarity 0.89)
• Conformal Prediction for Deep Classifier via Label Ranking (ICML 2024 · similarity 0.88)
• Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (ICML 2025 · similarity 0.87)
• GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs (NeurIPS 2026 · similarity 0.87)
• Valid Selection among Conformal Sets (NeurIPS 2025 · similarity 0.87)
• Stochastic Online Conformal Prediction with Semi-Bandit Feedback (ICML 2025 · similarity 0.87)