Technical Summary: Conformal Cascade

Problem Statement

Deploying Large Language Models (LLMs) at scale necessitates a trade-off between inference quality and cost. LLM cascades address this by routing queries to a small, inexpensive model first, escalating to a larger, more capable model only when necessary. However, current production cascades rely on confidence thresholds (e.g., softmax probability, self-consistency agreement) to make deferral decisions. These approaches suffer from three critical limitations:

1. Miscalibration: LLM confidence scores are notoriously miscalibrated, particularly on reasoning-heavy tasks, meaning high confidence does not reliably correlate with correctness.
2. Lack of Formal Guarantees: No setting of a confidence threshold $\theta$ provides a formal, distribution-free bound on the cascade's accuracy. The realized error rate depends on the unknown joint distribution of queries and confidences.
3. Tuning Overhead: Practitioners must empirically sweep thresholds for every new model pair, domain, or difficulty distribution to meet a target error rate, as there is no analytical mapping from a desired error budget to a threshold value.

Methodology: Conformal Cascade (CC)

The authors propose Conformal Cascade (CC), a multi-tier inference framework that replaces confidence thresholds with conformal prediction sets. The core mechanism operates as follows:

1. Nonconformity Scoring

Instead of using raw confidence scores, CC utilizes a frequency-based nonconformity score derived from self-consistency decoding. For a given tier $k$ and query $x$, the model generates $N$ independent samples. For each candidate answer $a$ in the finite answer set $A(x)$, the score is defined as:
$$s_k(x, a) = 1 - \frac{|\{i : \hat{y}^{(k)}_i = a\}|}{N}$$
Frequently sampled answers receive low scores (high conformity), while rare answers receive high scores. This approach requires only black-box API access and reuses samples generated for self-consistency.

2. Per-Tier Calibration

Using a held-out calibration set $D_{cal}$, a threshold $\hat{q}_k$ is computed for each tier $k$ to satisfy a user-specified miscoverage level $\alpha$. The threshold is set to the $(1-\alpha)$-quantile of the nonconformity scores on the calibration data. The prediction set for a new query is:
$$C_k(x) = \{a \in A : s_k(x, a) \leq \hat{q}_k\}$$
By the properties of split conformal prediction, this set guarantees that the true answer is contained within $C_k(x)$ with probability at least $1-\alpha$ (marginal coverage).

3. Deferral Rule

The deferral decision is driven by the size of the conformal prediction set, not a confidence value:

• Accept: If the set size $|C_k(x)| \leq \kappa$ (where $\kappa \geq 1$ is an acceptance parameter, default $\kappa=1$), the cascade commits to the most frequent answer in the set.
• Defer: If $|C_k(x)| > \kappa$, the query is escalated to the next tier.
• Fallback: If the final tier fails to produce a set of size $\leq \kappa$, the cascade returns the most frequent answer from the final tier's samples.

Crucially, deferral itself cannot cause an error; errors only occur upon acceptance. This structure allows the per-tier guarantees to compose into a cascade-level guarantee.

Key Contributions

1. Theoretical Framework: The authors formulate CC for arbitrary $K$ tiers and prove a cascade-level coverage bound (Theorem 2). In the worst case, the probability of the cascade accepting a wrong answer is bounded by $K\alpha$. Under a "selection-preservation" condition (Assumption 3), this tightens to $\alpha$.
2. Cost-Accuracy Characterization: The paper derives a closed-form expression for the expected inference cost as a function of $\alpha$ and the calibration-set acceptance rate (Theorem 4). This allows practitioners to explicitly trade off error budget against computational cost.
3. Empirical Validation: Extensive evaluation across 18 multiple-choice benchmarks (covering science, medicine, commonsense, and exams) and four open-weight model families (Llama, Gemma, Ministral, Phi) demonstrates that CC strictly outperforms the strongest calibration-tuned heuristic cascades on the majority of model-benchmark pairs.

Experimental Results

• Accuracy Gains: CC improves over the best heuristic baselines (including agreement, entropy, and random defer strategies) on 49 out of 72 model-benchmark pairs. The most significant gains occur on reasoning-heavy benchmarks (e.g., GPQA-Diamond, MathQA, MedMCQA) where majority vote is unreliable. For instance, on Phi/GPQA-Diamond, CC achieves a +4.3 percentage point gain.
• Efficiency: On easier benchmarks where the small model is reliable, CC commits the vast majority of queries to the small model at no accuracy cost, significantly reducing expected inference cost compared to always-deferring or always-strong baselines.
• Coverage Guarantees: Empirical miscoverage rates generally fall between the strict $\alpha$ and the worst-case $K\alpha$ bounds. For example, with $\alpha=0.10$ and $K=2$, observed miscoverage was often close to 0.10, staying well within the theoretical $0.20$ bound.
• Pareto Frontier: CC dominates heuristic methods on the cost-accuracy Pareto frontier. By adjusting the acceptance parameter $\kappa$, CC can unlock cheaper operating points while maintaining the conformal guarantee, a trade-off not achievable by fixed confidence thresholds.

Significance and Claims

The paper claims that Conformal Cascade provides the first distribution-free, finite-sample accuracy guarantee for multi-tier LLM inference. Unlike previous methods that rely on miscalibrated confidence scores and require extensive tuning per deployment, CC offers:

• Interpretability: The hyperparameter $\alpha$ directly corresponds to the user's error budget.
• Black-Box Compatibility: It requires no model training, no access to log-probabilities, and only standard API sampling.
• Robustness: It effectively handles the calibration problem by bounding set-level coverage rather than attempting to rescale confidence scores.

The authors note that the method is currently limited to tasks with finite, extractable answer sets (e.g., multiple-choice). Extension to open-ended generation via answer clustering is identified as future work. Additionally, the guarantee is marginal (over the data distribution) rather than conditional on query difficulty, and the framework assumes exchangeability between calibration and test data, necessitating online recalibration for covariate shifts.