Conformal Prediction with Paraphrase-Aware Scoring for LLM Uncertainty Quantification

1 Introduction

• LLM confidence can be poorly calibrated and vary substantially across superficial rewordings, limiting the practical usefulness of uncertainty estimates.This creates a gap between conformal prediction’s statistical guarantees and stability across semantically equivalent inputs.Source: §1 · pp. 1–2
• The method aggregates predictions across paraphrases using a lightweight proxy, then integrates the resulting scores with conformal prediction when exchangeability conditions hold.The learned proxy accounts for most set-size reduction, while paraphrase-augmented training and test-time aggregation contribute to wording stability.Source: §1 · p. 2
• Across five general and two medical QA benchmarks, prediction sets shrink by up to 2–4× versus raw-probability baselines, with empirical coverage generally near nominal.The analysis also finds that scores preserve exchangeability under paraphrased inputs and under transformations satisfying a distributional closedness condition.Source: §1 · p. 2

2 Related Work

• Conformal prediction offers finite-sample marginal coverage under exchangeability, and existing language-model applications include language modeling, multiple-choice QA, and API inference.Prior work also adapts scores and thresholds to task structure.Source: §2 · p. 2
• Prior perturbation-based uncertainty estimation and conformal coverage leave open the design of label-wise nonconformity scores stable under meaning-preserving rewording.This paper distinguishes its focus on per-option conformal decisions from SPUQ’s instance-level uncertainty value.Source: §2 · p. 3
• Semantically equivalent queries can produce different prediction sets even when marginal coverage is maintained.The paper frames its contribution as a unified treatment of score methodology, evaluation, and validity analysis.Source: §2 · p. 3

3 Preliminaries

• The objective is to construct small prediction sets containing the correct label at prescribed coverage under matched calibration and test distributions, as well as test-only rewording shifts.Coverage under test-only rewording requires additional assumptions formalized later in the paper.Source: §3 · p. 3
• Split CP includes a candidate label when its nonconformity score is at most the empirical (1 − α) calibration quantile, using one global threshold.The global threshold can be overly conservative across heterogeneous inputs.Source: §3 · p. 3
• QCCP fits a quantile regressor to calibration scores and adapts thresholds to input features, unlike split CP’s global threshold.The feature mapping ϕ determines the threshold adaptation.Source: §3 · p. 3

4 Paraphrase-Aware Nonconformity Scores for Conformal Prediction

• The pipeline generates paraphrases, extracts their embeddings, predicts calibrated probabilities with the proxy, aggregates them into scores, then applies split CP or QCCP.The framework uses a collection of paraphrase embeddings for each input question.Source: §4 · p. 4
• A lightweight proxy classifier maps LLM hidden-state embeddings to predictive probabilities, using task and calibration-aware losses.The main variant requires hidden-state access and labeled proxy-training data.Source: §4 · p. 4
• The PA score remains robust across tested embedding variants, including different token-representation pooling and model-layer choices.Its motivation is to address the single-prompt scores’ failure to capture variability across semantically equivalent rewordings.Source: §4 · pp. 3–4
• Mean scores average across paraphrases, weighted scores favor semantically closer variants, and worst-case scores take the maximum.The weighted variant uses inverse embedding distance, assigning larger weights to paraphrases closer to the original input.Source: §4 · p. 5, Table 1 · p. 5
• For QCCP, the class function groups semantically similar questions using SBERT embeddings and K-means fitted on calibration embeddings.Test inputs are assigned to their nearest centroid, without requiring manual question-type annotations.Source: §4 · p. 5

• Distributional closedness requires the paraphrase distribution to remain unchanged after rewording, supporting the stated guarantees when test inputs undergo paraphrasing.Under Assumption 5.1, this invariance extends to the joint distribution of paraphrase samples.Source: §5 · pp. 5–6
• Although rewording only the test input may break exchangeability with original calibration data, applying the transformation across all inputs restores data exchangeability under Assumption 5.1.The proposition describes compatibility between transformed calibration and test samples under the stable paraphrase distribution.Source: §5 · p. 5
• The proposed Mean, Weighted, and Worst scores are exchangeable with their calibration counterparts, supporting the corresponding CP marginal and QCCP quasi-conditional coverage guarantees.The reworded-test guarantee requires the stated score conditions and, for QCCP, its joint feature–score assumptions.Source: §5 · p. 6
• A total-variation bound controls the coverage change caused by departures from exact distributional closedness under the stated assumptions.An empirical diagnostic also examines score-distribution shift and its effect on coverage.Source: §5 · p. 6

6 Empirical Performance

• The evaluation uses seven multiple-choice QA benchmarks, a 40/30/30 training-calibration-test split, and a nominal target coverage of 90%.The benchmarks include five general and two medical datasets; reworded inputs are generated with stochastic decoding and filtered for validity.Source: §6 · p. 6

6.1 Stable Coverage and Compact Sets under Rewording

• Across normal and fully reworded settings, PA produces the smallest sets while maintaining coverage near 90%; in the semi-reworded setting, it is usually most compact with competitive coverage.In normal and fully reworded settings, PA coverage ranges from 89.90% to 95.63%, while APS ranges from 93.10% to 100.00%; fixed-α comparisons can yield different coverage across methods.Source: Table 3 · p. 7, §6.1 · pp. 7–8, Table 4 · p. 8
• On MMLU with Llama-3.1-8B-Instruct and Phi-3-small-8k-Instruct, PA consistently yields the most compact sets with coverage near the nominal target across all three settings.APS tends to over-cover, while LAC, SPUQ, and TRON can be closer to nominal coverage but generally require larger sets.Source: Table 5 · p. 8, §6.1 · p. 8
• On the remaining two medical MCQA datasets, PA likewise produces smaller sets with coverage closer to target than competing methods.API-only scenarios, factuality verification, and image modalities are discussed as extensions.Source: §6.1 · p. 8

Proxy Model Improves Accuracy and Calibration

• The proxy consistently outperforms raw LLM logits across benchmarks on accuracy, Brier score, and NLL; examples include DS accuracy 0.597→0.944 and RC Brier 0.075→0.039.The proxy is a lightweight two-layer MLP trained on frozen LLM hidden states with a calibration-aware loss.Source: §7 · p. 8, Figure 3 · p. 9

Where Do the Gains Come From?

• The hidden-state proxy accounts for most compactness, reducing Semi SS from 2.8929 to 1.3725; six-view aggregation cuts set change by 15.8% and Semi SS from 1.3587 to 1.3331.Augmentation improves rewritten-input accuracy from 79.80% to 80.38% and reduces true-label score drift from 0.0596 to 0.0574; aggregation changes coverage from 89.96% to 89.81%.Source: §7 · p. 9, Table 6 · p. 9

Better Class-conditional Coverage

• PA tracks the 90% target across semantic clusters, while LAC and APS overshoot and TRON/SPUQ show larger per-cluster swings.Figure 4 evaluates CosmosQA and HaluDial; additional datasets appear in Figure 9.Source: §7 · p. 9, Figure 4 · p. 9

Effect of Coverage Levels

• At α = 0.05, PA achieves approximately 95% coverage with average set size 2.9, versus 4.8 for LAC and 4.7 for APS.Across α values, PA tracks nominal coverage and yields the most compact sets; APS reaches 95% coverage at α = 0.2 against an 80% target.Source: §7 · p. 10, Figure 5 · p. 10

Larger Paraphrase Budgets Yield Smaller Prediction Sets

• Increasing the paraphrase budget from 2 to 4 to 6 yields higher coverage and smaller prediction sets on MMLU.The reported comparison uses Qwen3-8B under split CP and QCCP.Source: §7 · p. 10, Table 7 · p. 10

Comparison of Different Scores

• Under QCCP, Mean and Weighted average 91.7%/90.1%/90.7% and 91.7%/90.6%/90.8% coverage across normal/semi-/fully-reworded prompts, with average set sizes around 1.9–2.0.Worst is mildly conservative at 92.1%/93.0%/90.9% and yields average set sizes around 2.0–2.2; split CP gives near-identical averages.Source: §7 · p. 10, Figure 6 · p. 10

8 Conclusion

• Paraphrase-aware nonconformity scores are integrated with split CP and quasi-conditional CP to produce compact prediction sets under stated exchangeability conditions.The conclusion attributes most compactness gains to the learned proxy and wording-stability improvements to paraphrase training and inference-time aggregation.Source: §8 · p. 10

A Detailed Related Work

• Unlike prior perturbation-based uncertainty work focused on instance-level estimates, this work studies label-wise scores and prediction-set stability within CP.The related work frames its approach as combining semantic perturbations with conformal guarantees.Source: A Detailed Related Work · p. 17

B Brief Introduction to the Conformal Framework

• Split CP provides finite-sample marginal coverage under exchangeability, while QCCP offers a middle ground between marginal and full conditional coverage.QCCP learns an input-dependent threshold from calibration scores using quantile regression.Source: B Brief Introduction to the Conformal… · p. 17

C.1 Proofs for Score Exchangeability

• Under distributional closedness, applying the same fixed score rule to augmented inputs yields exchangeable calibration and test scores in the semi-reworded setting.The score must depend only on the internally generated paraphrases and label, unless an additional joint-invariance assumption supports input-anchored weights.Source: §C.1 · p. 19

C.2 Formal Coverage Results

• Split CP with the PA score has coverage between 1 − α and 1 − α + 1/(n + 1); QCCP’s stated bound requires exchangeability of its features paired with PA scores.For QCCP in the semi-reworded setting, the stated feature condition is that its feature is essentially T(U_i).Source: §C.2 · pp. 20–21

C.3 Approximate Distributional Closedness

• If paraphrase distributions are ε-approximately closed, the coverage gap is at most mε, up to finite-sample effects.Here m is the number of internally generated paraphrases; the deviation scales linearly with that number.Source: §C.3 · p. 21

D.1 Dataset Details

• The evaluation uses five general and two medical multiple-choice QA datasets, each with 10,000 questions; all are cast into a six-option label space.The medical datasets are restricted to single-answer items, and the MedQA subset uses the US portion.Source: §D.1 · p. 22

D.2 Paraphrase Generation for Full/Semi-Paraphrase Settings

• Full- and semi-reworded evaluation inputs are generated with sampled templates, cleaned and validated, then retried or rewritten by rules when generation fails.The prompt pool contains seven templates; generation uses temperature 0.7 and top_p 0.9.Source: §D.2 · pp. 22–23

D.3 Baseline Score Adaptations

• The SPUQ-adapted and TRON-adapted controls use per-option scores; mean-probability averaging matches Smean only when using the same proxy probabilities and paraphrase views as Full PA.That identity does not extend to weighted, worst-case, or negative-log scores.Source: §D.3 · p. 23

D.4 Experimental Implementation Details

• The proxy is a two-layer MLP trained on LLM embeddings, with cross-entropy plus soft-binned ECE loss; PA scores use proxy predictions on six paraphrases, not the original-question embedding.Paraphrases share their parent question’s label; hidden states come from the LLM’s final layer.Source: §D.4 · pp. 23–24

D.5 Hyperparameters for Reproducibility

• Appendix tables list framework and proxy-model hyperparameters for the general and medical datasets.Tables 8–11 provide these reproducibility settings.Source: §D.5 · p. 24

E.1 Better Performance on Medical MCQA Datasets

• On all 12 medical-domain settings, PA achieves the smallest set sizes, 2.02 to 3.61, with coverage ranging from 89.57% to 91.77%.The comparison uses Qwen3-8B on MedMCQA and MedQA under normal, semi-reworded, and fully reworded conditions.Source: §E.1 · p. 24

E.2 Finite-Sample Behavior of Class-Conditional Coverage

• 1 − α ≤ cluster coverage ≤ 1 − α + slack at the population level; finite-sample empirical coverage may fluctuate around 0.90 because of sampling variability and nonzero slack.The slack decreases with effective cluster sample size, and moderate empirical deviations are not by themselves violations of the population guarantee.Source: §E.2 · p. 25
• WCD was lowest for PA on QA, CI, and DRS at K = 20 with Qwen3-8B, indicating more uniform alignment with the 0.9 target.Table 13 compares methods under QCCP in the semi-reworded setting.Source: Table 13 · p. 27, §E.2 · p. 27
• 0.8963, 0.9025, and 0.9059 were average coverages for the smallest, middle, and largest calibration-size terciles, respectively, though some large clusters still deviated.The share of clusters with coverage ≤0.85 fell from approximately 10.7% in the smaller two terciles to 1.8% in the largest.Source: §E.2 · p. 27

E.3 Robustness under the Semi-Reworded Setting

• 89.97% (CosmosQA) and 90.27% (HellaSwag) coverage: PA’s split-CP sets were smallest at SS ≈1.41–2.03 in the semi-reworded setting.Under QCCP, PA also had coverage closest to 90% while maintaining compact sets.Source: Table 14 · p. 28, §E.3 · p. 28

E.4 Quantifying Coverage Deviations in the Semi-Reworded Setting

• r = 0.983 (95% CI [0.935, 0.985]) linked cutoff-local shift with semi-reworded coverage deviation; HaluDialogue’s largest global KS distance did not imply the largest coverage error.MMLU’s local shift and coverage error were both approximately 4.5 points, whereas HaluDialogue’s were 2.7 and 2.4 points.Source: §E.4 · p. 29

E.5 Semantic Consistency of Generated Paraphrases

• 0.61–0.87 SBERT cosine similarity across CosmosQA and MedMCQA, with Qwen3-8B above 0.81; HellaSwag scores were lower at 0.37–0.59.BLEU and ROUGE-L followed the same dataset and scenario pattern; the authors conclude the paraphrase sets largely preserve semantics.Source: §E.5 · p. 30

E.6 End-to-End Runtime

• 22.7–83.4× slower than raw single-input inference, online Full PA with m = 6 spent 67–97% of its time generating paraphrases.With paraphrases and hidden representations cached, scoring, aggregation, and set construction took at most 0.20 ms per question.Source: §E.6 · p. 30

F Analysis of the Proxy Model

• Without the proxy, set sizes inflate substantially while coverage remains close to 90% under both split CP and QCCP.The same pattern appears in the Qwen3-8B proxy-removal figures.Source: F Analysis of the Proxy Model · p. 30, Figure 7 · p. 31, Figure 8 · p. 32
• On CosmosQA under split CP, Full PA yields set size 1.17 versus 1.77 for paraphrase-only; on HaluDial under QCCP, it yields 1.39 versus 4.86.The variants are close to nominal coverage in the fully reworded setting, and Full PA matches or slightly improves Aug-Proxy Single on nearly every dataset.Source: F Analysis of the Proxy Model · p. 32, Table 18 · p. 32

F.1 Different Class-Conditional Levels for QCCP

• Under QCCP, PA tracks the 90% target across class clusters, while LAC and APS overshoot and TRON and SPUQ show larger per-cluster swings.Under split CP, PA tracks nominal coverage across α levels (79.7% at α=0.2, 95.1% at α=0.05, and 99.2% at α=0.01) and keeps sets compact (1.63, 2.67, and 3.48, respectively); TRON and SPUQ produce larger sets at every level.Source: §F.1 · p. 33, §F.2 · pp. 33–34, Figure 9 · p. 34

F.3 Different Paraphrase Generators

• With Llama-3.1-8B generating paraphrases and Qwen3-8B supplying embeddings, PA maintains near-90% coverage and smaller sets across three datasets; its scores also remain stable across pooling and layer choices.The generator comparison covers normal and fully reworded settings, while the representation sensitivity analysis uses CosmosQA under split CP.Source: §F.3 · p. 34, Table 23 · p. 35, §F.4 · p. 35

F.5 Different Proxy Training and Calibration Budgets

• At full calibration, increasing proxy-training fraction from 0.01 to 1.00 shrinks set size by 16.5% on RC (1.602 →1.338) and 9.4% on CI (1.848 →1.674).A 5–10% proxy-training fraction nearly matches the full-budget reference, while reducing calibration fraction from 1 to 0.05 increases set size by 9.9–24.9%.Source: §F.5 · p. 36

F.6 Different Aggregation Scoring Rules

• Across five general QA benchmarks, Worst has higher mean and standard deviation than Mean and Weighted, whose scores are lower and more stable.The authors link high nonconformity on a hard paraphrase to brittle predictions, while Mean and Weighted smooth variation across paraphrases.Source: §F.6 · p. 37, Table 27 · p. 37

G.1 Extension to Black-Box / API-Only Settings

• In semi-reworded QCCP, API-only PA substantially reduces set size versus LAC and APS on all five datasets, but coverage is below 90% on QA, RC, and CI.This option uses only option log-probabilities, without hidden states or a proxy classifier, and is presented as a partial rather than parity extension.Source: §G.1 · p. 37, Table 28 · p. 37

G.2 Extension to Larger Backbone LLMs

• With Qwen3-14B and Qwen3-32B, PA produces substantially smaller sets than LAC and APS across CosmosQA and HellaSwag while generally maintaining near-target coverage.The reported set-size range falls from roughly 1.3–6.0 to about 1.0–1.3; on HellaSwag in the semi-reworded setting, coverage is 91.27% with 14B and 91.33% with 32B.Source: §G.2 · p. 38, Table 29 · p. 38

G.3 Extension to Factuality Verification Tasks

• For factuality verification, open-ended generations are decomposed into atomic claims labeled True or False, and PA scores are integrated into conformal prediction.The pipeline generates claim paraphrases, scores them with the proxy, and calculates PA scores across the paraphrases.Source: §G.3 · p. 38
• On FEVER, PA is most stable across settings; in the fully reworded case it reaches 90.5% under Split CP and 90.3% under QCCP, while LAC, TRON, and SPUQ dip below 90%.The experiment uses Qwen3-8B; all non-APS methods yield essentially singleton sets, so coverage is the main distinction.Source: §G.3 · p. 39, Table 30 · p. 39, Table 31 · p. 39
• The FEVER experiment is a preliminary step toward open-ended applications; full long-form treatment still requires claim decomposition and aggregation back to response-level guarantees.The reported evaluation is at the claim-verification level.Source: §G.3 · p. 39

G.4 Extension to Image Modality

• For image–question inputs, the proposed extension uses semantic-preserving visual perturbations and VLM hidden representations to compute variant-aware scores within the conformal framework.The paper describes this as an extension in principle, not as an evaluated experiment.Source: §G.4 · pp. 39–40

H Limitations and Broader Impacts

• The strongest variant requires hidden states and labeled proxy-training data, while six-view inference takes 22.7–83.4 times longer than raw single-input inference on a B200.The black-box extension demonstrates applicability but does not match the white-box model.Source: H Limitations and Broader Impacts · p. 40
• Coverage guarantees do not extend to arbitrary test-only rewriting; effectiveness may also degrade with semantic drift or limited paraphrase diversity.The framework focuses on paraphrase-preserving changes rather than topic drift, temporal changes in factual knowledge, or adversarial perturbations.Source: H Limitations and Broader Impacts · p. 40
• Experiments are primarily on English multiple-choice QA, leaving multilingual and free-form generation settings for future work; prediction sets are decision support, not guarantees of correctness.The caution particularly applies in high-stakes applications.Source: H Limitations and Broader Impacts · p. 40