🤖 machine learning

PASC: Pipeline-Aware Conformal Prediction with Joint Coverage Guarantees for Multi-Stage NLP and LLM Pipelines

The paper introduces PASC, a pipeline-aware conformal prediction method that ensures finite-sample joint coverage guarantees for multi-stage NLP and LLM systems by reducing the problem to a single scalar quantile computation, thereby significantly outperforming independent calibration and conservative Bonferroni bounds in both accuracy and efficiency.

Original authors: Varun Kotte

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Varun Kotte

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: The "Broken Chain" of AI

Imagine you are building a complex machine to sort mail. It has three steps:

Step A: A robot scans the envelope and finds the address.
Step B: A second robot looks up that address in a database to find the zip code.
Step C: A third robot puts the letter in the correct bin based on that zip code.

In the world of AI (specifically NLP and LLMs), these are called pipelines. The paper points out a big problem: if you make sure Step A is 90% accurate, and Step B is 90% accurate, and Step C is 90% accurate, the entire machine is not 90% accurate.

Because the steps happen one after another, errors pile up. If Step A makes a tiny mistake, Step B gets the wrong input, and Step C fails completely. By the time the letter reaches the bin, the whole system might only be working 73% of the time, even though every individual robot was "90% reliable."

The Old Solutions: Guessing or Over-Protecting

The paper says existing methods to fix this are flawed:

The "Independent" Method: This treats each robot separately. It says, "I'm 90% sure Step A is right, and 90% sure Step B is right."
- The Flaw: It ignores the fact that if Step A fails, the whole chain breaks. It gives a false sense of security about the final result.
The "Bonferroni" Method: This is the "paranoid" approach. To guarantee the whole chain works 90% of the time, it forces each robot to be 99% accurate (dividing the error budget equally).
- The Flaw: It's too conservative. It makes the easy steps (like finding an address) work way harder than necessary, which slows everything down and makes the system less efficient, even though the final result is safe.

The New Solution: PASC (The "Weakest Link" Strategy)

The authors introduce PASC (Pipeline-Aware Split Conformal Prediction).

The Core Idea:
Instead of checking if Robot A is good, Robot B is good, and Robot C is good separately, PASC asks a single question: "Is the worst mistake in the whole chain small enough?"

Think of a chain made of metal links. The strength of the chain isn't the average of all links; it's determined by the weakest link.

If Link 1 is strong, Link 2 is strong, but Link 3 is weak, the whole chain breaks at Link 3.
PASC focuses entirely on that weakest link (the "maximum error") across the whole process.

How it works:

The system runs the pipeline on a bunch of practice examples.
For every example, it calculates the "error score" for every step.
It picks the highest error score from that specific run (the "worst link").
It sets a single safety threshold based on those "worst link" scores.

If the "worst link" in a new, real-world example is below that threshold, the system says, "We are safe!" If the worst link is too high, it says, "Don't trust this result."

Why is PASC Better?

The paper claims PASC is a "Goldilocks" solution—it's just right.

It's Safer than the "Independent" method: It actually guarantees that the whole pipeline works 90% of the time (or whatever target you set), not just the individual parts.
It's Smarter than the "Paranoid" method: It doesn't force the easy steps to be perfect. It realizes that if Step A is easy and Step C is hard, the system's safety depends on Step C. PASC adjusts automatically to the hardest part of the chain, whereas the old "Paranoid" method wasted effort making the easy parts super-duper perfect.

The Results (The "Proof")

The authors tested this on a real-world text-processing pipeline (finding names, linking them to facts, and categorizing them).

Accuracy: PASC achieved 96.4% success rate for the whole pipeline. The "Paranoid" method got 93.4%, and the "Independent" method only got 86.5%.
Efficiency: PASC was just as efficient as the others (it didn't produce huge, useless lists of guesses).
Speed: Because PASC only needs to calculate one safety number instead of three separate ones, it is 1.7 times faster to set up.
Robustness: When the data changed (e.g., moving from news articles to Twitter posts), PASC stayed reliable, while the "Independent" method crashed and failed to protect the user.

The Bottom Line

PASC is a new way to trust AI systems that have multiple steps. Instead of trusting each step individually or being overly cautious about every single step, it looks at the entire chain and ensures the weakest link is strong enough. This gives users a mathematically guaranteed safety net for the final result without slowing the system down.

Technical Summary: PASC (Pipeline-Aware Conformal Prediction)

1. Problem Statement

Modern NLP and Large Language Model (LLM) systems are increasingly deployed as multi-stage pipelines (e.g., Named Entity Recognition $\to$ Entity Disambiguation $\to$ Entity Typing, or Planner $\to$ Tool $\to$ Critic chains). A critical challenge in these systems is End-to-End (E2E) Uncertainty Quantification.

While individual stages can be calibrated to provide marginal coverage guarantees (e.g., $P(\text{stage}_k \text{ covered}) \ge 1-\alpha$ ), these guarantees do not translate to the pipeline as a whole.

Independent Calibration: Calibrating each stage at level $1-\alpha$ independently results in a joint coverage probability of at most $(1-\alpha)^K$ (under independence), which degrades significantly as the number of stages $K$ increases. For $K=3$ and $\alpha=0.1$ , joint coverage drops to $\approx 72.9\%$ , far below the target $90\%$ .
Bonferroni Correction: Applying a union bound by calibrating each stage at $1-\alpha/K$ guarantees joint coverage ( $\ge 1-\alpha$ ) but is overly conservative. It allocates error budgets uniformly regardless of stage difficulty, leading to unnecessarily large prediction sets (over-coverage) on easy stages without proportional gains in joint reliability.
Existing Alternatives: Methods like MC Dropout or Deep Ensembles provide heuristic uncertainty estimates but lack finite-sample, distribution-free guarantees and often ignore cross-stage dependencies.

The core problem is the lack of a method that provides a formal, finite-sample, distribution-free joint coverage guarantee for the entire pipeline while maintaining efficiency (i.e., not inflating prediction set sizes unnecessarily).

2. Methodology: PASC

The authors propose PASC (Pipeline-Aware Split Conformal), a method that reduces the multi-stage joint calibration problem to a standard scalar conformal prediction problem.

Key Insight

The event "all $K$ stages are simultaneously covered" is mathematically equivalent to the event "the maximum nonconformity score across all stages does not exceed a threshold."
$\bigcap_{k=1}^K \{s_k \le q\} \iff \left\{ \max_{k} s_k \le q \right\}$
where $s_k$ is the nonconformity score of stage $k$ .

Algorithm

Score Definition: For a pipeline sample, compute per-stage nonconformity scores ( $s_1, \dots, s_K$ $s_{1}, \dots, s_{K}$ ).
- NER: $s_{NER} = \max_t (1 - p_{BIO, t})$ (softmax probability).
- NED: $s_{NED} = 1 - \text{score}(e^*)$ (top-ranked entity score).
- Entity Typing: $s_{typing} = 1 - \max_c \min_{\text{span}} p_{RoBERTa}$ .
Joint Maximum Score: Compute the scalar maximum score for each sample: $s_{\max} = \max_k s_k$ .
Calibration: Using a calibration set, compute the conformal quantile $\hat{q}$ of the distribution of $s_{\max}$ at level $1-\alpha$ .
Prediction: For a test input, compute per-stage scores. The pipeline is accepted if $s_{\max} \le \hat{q}$ . The prediction set for each stage $k$ is $C_k(x) = \{y_k : s_k(x, y_k) \le \hat{q}\}$ .

Theoretical Guarantee

Under the assumption of exchangeability between calibration and test data, PASC provides a finite-sample, distribution-free guarantee:
$P\left( \bigcap_{k=1}^K \{s_k(x_{n+1}, y_{k,n+1}) \le \hat{q}\} \right) \ge 1 - \alpha$
The guarantee is nearly tight, bounded by $1 - \alpha + \frac{1}{n+1}$ . Unlike Bonferroni, which uses a worst-case union bound, PASC adapts to the empirical joint distribution of the scores, automatically assigning tighter budgets to "easy" stages (low scores) and looser budgets to "hard" stages.

3. Key Contributions

PASC Algorithm: A pipeline-aware calibration procedure that reduces multi-stage joint coverage to a single scalar quantile computation on the joint maximum nonconformity score.
Formal Guarantee: A theorem proving finite-sample, distribution-free joint coverage ( $\ge 1-\alpha$ ) under exchangeability, with a near-tightness result.
Comprehensive Evaluation: Experiments across three shift scenarios (in-distribution, Twitter NER, Wikipedia NER), varying calibration sizes, and scaling from $K=1$ to $K=6$ stages.
Sanity Checks: Permutation tests and negative controls confirming that the validity is not an artifact of implementation errors, data leakage, or overly broad thresholds.

4. Experimental Results

The authors evaluated PASC on a three-stage pipeline (NER $\to$ NED $\to$ Entity Typing) using CoNLL-2003, WNUT-17, and WikiNEuRal datasets.

Coverage vs. Efficiency: At $\alpha=0.1$ $α = 0.1$ with $K=3$ $K = 3$ :
- PASC: Achieved 96.4% E2E coverage.
- Bonferroni: Achieved 93.4% E2E coverage.
- Independent CP: Achieved 86.5% E2E coverage.
- Crucially, all methods maintained an identical average prediction set size of 1.083, demonstrating PASC's superior efficiency in converting coverage probability into set size.
Distribution Shift: When calibrated on CoNLL-2003 and tested on shifted domains (WNUT-17, WikiNEuRal):
- Independent CP collapsed to 59.0% coverage.
- PASC and Bonferroni maintained 100% coverage (due to conservative thresholds providing a buffer against shift).
Scaling to $K$ Stages: In synthetic experiments scaling to $K=6$ $K = 6$ :
- Independent CP coverage dropped to 0.53 (multiplicative collapse).
- PASC remained near the target coverage, avoiding the multiplicative decay.
Conditional Coverage: PASC showed significant advantages on "hard" subpopulations (e.g., the hardest NER confidence quintile), achieving 82.0% coverage compared to 67.0% for Bonferroni and 30.0% for Independent CP.
Runtime: PASC calibration is 1.7 $\times$ faster than Bonferroni and Independent CP because it requires computing only one quantile instead of $K$ .

5. Significance and Claims

The paper claims that PASC addresses a fundamental gap in the deployment of multi-stage NLP systems:

Direct Certification: Unlike Independent CP (which certifies local stages but fails globally) or Bonferroni (which guarantees globally but pays a "conservatism tax"), PASC certifies the exact deployed event of interest (joint acceptance) directly.
Minimal Reduction: The reduction from a multi-stage problem to a scalar problem is mathematically simple (using the maximum) but represents the minimal sufficient monotone scalarization for the joint acceptance event.
Practical Applicability: The method is immediately applicable to any multi-stage pipeline (including compound LLM systems and agent workflows) without requiring model modification or heavy inference overhead.
Robustness: While theoretical guarantees rely on exchangeability, empirical results suggest PASC maintains coverage under distribution shift better than Independent CP, though the authors note that extending to weighted CP for robust shift handling is future work.

The authors position PASC not as a replacement for stage-specific calibration but as the necessary aggregation layer that ensures the reliability of the entire pipeline output, which is the metric that matters for downstream decision-making in high-stakes applications.