Black-Box Reliability Certification for AI Agents via Self-Consistency Sampling and Conformal Calibration

Charafeddine Mouzouni

cs.LGFeb 24, 2026

Black-Box Reliability Certification for AI Agents via Self-Consistency Sampling and Conformal Calibration

Authors: Charafeddine Mouzouni

Organizations: OPIT – Open Institute of Technology, and Cohorte AI, Paris, France.

Abstract

Given a black-box AI system and a task, at what confidence level can a practitioner trust the system's output? We answer with a reliability level -- a single number per system-task pair, derived from self-consistency sampling and conformal calibration, that serves as a black-box deployment gate with exact, finite-sample, distribution-free guarantees. Self-consistency sampling reduces uncertainty exponentially; conformal calibration guarantees correctness within 1/(n+1) of the target level, regardless of the system's errors -- made transparently visible through larger answer sets for harder questions. Weaker models earn lower reliability levels (not accuracy -- see Definition 2.4): GPT-4.1 earns 94.6% on GSM8K and 96.8% on TruthfulQA, while GPT-4.1-nano earns 89.8% on GSM8K and 66.5% on MMLU. We validate across five benchmarks, five models from three families, and both synthetic and real data. Conditional coverage on solvable items exceeds 0.93 across all configurations; sequential stopping reduces API costs by around 50%.

Figures & tables

Panel of Figure 1 — Figure 1. Pipeline overview. Step 1 : ask the AI system the same question $K$ times and collect its answers. Step 2 : group identical answers and rank them by frequency. Step 3 : a human checks a small calibration batch; the framework outputs a single reliability level (e.g. $94.6\%$ ) with a formal coverage guarantee. No model internals are needed—only API access.

† Three-term decomposition: agent variance $+$ judge variance $+$ bias variance; does not vanish with more samples.
Method	Bias	Variance	Error $\to 0$ ?	Guarantee
Single sample	$0$	$p^{\star}(1{-}p^{\star})$	No	—
LLM-as-judge	${\mathbb{E}}_{a}[b_{J}]\neq 0$ (irreducible)	Prop. 3.4 †	No (bias persists)	—
Self-consistency (mode)	$0$ if $p^{\star}{>}\tfrac{1}{2}$ ; $\to{-}p^{\star}$ if $p^{\star}{\leq}\tfrac{1}{2}$	$\leq\exp(-2K(p^{\star}{-}\tfrac{1}{2})^{2})$	No (bias if $p^{\star}{\leq}\tfrac{1}{2}$ )	—
Ours (conformal)	Coverage gap $\leq 1/(n{+}1)$		Yes ( $\to 0$ as $n\to\infty$ )	${\mathbb{P}}(Y{\in}S)\geq 1{-}\alpha$

Table 1. Bias–variance profile of evaluation methods (per-query).

K

= number of samples,

n

= calibration set size.

Dataset	$n_{\mathrm{cal}}$ / $n_{\mathrm{test}}$	$M^{\star}$	Coverage	Mode Acc	Judge Acc	Avg. $\|S\|$	Cov $\|$ solv
HumanEval	82 / 82	2	0.707 ( 0.60–0.79 )	0.646 ( 0.54–0.74 )	0.915 †	1.32	0.967
TruthfulQA	408 / 409	1	0.976 ( 0.96–0.99 )	0.976 ( 0.96–0.99 )	0.966 ( 0.94–0.98 )	1.00	0.980
BigBench	125 / 125	2	0.792 ( 0.71–0.85 )	0.768 ( 0.69–0.83 )	0.736 ( 0.65–0.81 )	1.10	1.000
GSM8K	500 / 500	1	0.956 ( 0.93–0.97 )	0.956 ( 0.93–0.97 )	0.986 ( 0.97–0.99 )	1.00	0.980
MMLU	500 / 500	2	0.838 ( 0.80–0.87 )	0.798 ( 0.76–0.83 )	0.962 ( 0.94–0.98 )	1.11	0.988

Table 2. Main results (

T{=}0.7

K{=}10

\alpha=0.10

). Coverage target is

1-\alpha=0.90

. 95% Wilson CIs in parentheses. Results shown for GPT-4.1; see Table 3 for cross-model comparison.

	GPT-4.1		GPT-4.1-mini		GPT-4.1-nano
Dataset	$M^{\star}$	$\bar{\|S\|}$	$M^{\star}$	$\bar{\|S\|}$	$M^{\star}$	$\bar{\|S\|}$
GSM8K	1	1.00	1	1.00	2	1.35
MMLU	2	1.11	2	1.12	2	1.17
	GPT-4.1		Llama 4 Maverick		Mistral Small
Dataset	$M^{\star}$	$\bar{\|S\|}$	$M^{\star}$	$\bar{\|S\|}$	$M^{\star}$	$\bar{\|S\|}$
GSM8K	1	1.00	1	1.00	1	1.00

Table 3. Multi-model comparison at

\alpha=0.10

M^{\star}

and average set size. Top: GPT-4.1 capability ladder on GSM8K and MMLU. Bottom: Open-weight cross-family validation on GSM8K, MMLU, and TruthfulQA.

M^{\star}

and

\bar{|S|}

are non-decreasing with decreasing capability across all model families.

Figure 2. Coverage validation: empirical coverage vs. target

1-\alpha

for

\alpha\in\{0.01,\ldots,0.30\}

across all five benchmarks. Points above the diagonal are consistent with the marginal coverage guarantee (Theorem 6.7 ). Points below the diagonal (HumanEval, BigBench, MMLU) arise when the unsolvable fraction

\beta

exceeds

\alpha

: Theorem 7.5 (3) predicts

M^{\star}=+\infty

in this regime, meaning no finite prediction set can cover unsolvable items. Empirically,

M^{\star}

remains finite (capped by

|\mathcal{C}|

) but the resulting sets still cannot include an acceptable answer for queries that the model fundamentally cannot solve. The under-coverage is thus a diagnosed capability gap, not a calibration failure—conditional coverage on solvable items exceeds

0.96

across all five benchmarks.

Model	Dataset	$M^{\star}$ (mean $\pm$ std)	Coverage (mean $\pm$ std)
GPT-4.1	GSM8K	$1.00\pm 0.00$	$0.951\pm 0.007$
GPT-4.1	MMLU	$2.00\pm 0.00$	$0.979\pm 0.005$
GPT-4.1-mini	GSM8K	$1.00\pm 0.00$	$0.957\pm 0.007$
GPT-4.1-mini	MMLU	$2.00\pm 0.00$	$0.976\pm 0.004$
GPT-4.1-nano	GSM8K	$1.18\pm 0.38$	$0.917\pm 0.023$
GPT-4.1-nano	MMLU	$2.00\pm 0.00$	$0.945\pm 0.007$

Table 4. Bootstrap split stability:

M^{\star}

and coverage across 100 random cal/test partitions (

n_{\mathrm{cal}}=n_{\mathrm{test}}=500

\alpha=0.10

Dataset	$K=1$	$K=2$	$K=5$	$K=10$	$K=20$
HumanEval	.354 ( .26–.46 )	.378 ( .28–.49 )	.366 ( .27–.47 )	.341 ( .25–.45 )	.341 ( .25–.45 )
TruthfulQA	.034 ( .02–.06 )	.044 ( .03–.07 )	.027 ( .02–.05 )	.024 ( .01–.04 )	.022 ( .01–.04 )
BigBench	.248 ( .18–.33 )	.240 ( .17–.32 )	.240 ( .17–.32 )	.240 ( .17–.32 )	.240 ( .17–.32 )
GSM8K	.064 ( .05–.09 )	.058 ( .04–.08 )	.048 ( .03–.07 )	.046 ( .03–.07 )	.046 ( .03–.07 )
MMLU	.212 ( .18–.25 )	.206 ( .17–.24 )	.210 ( .18–.25 )	.204 ( .17–.24 )	.200 ( .17–.24 )

Table 5. Mode error

\widehat{\mathrm{ModeErr}}(K)

as a function of

K

for GPT-4.1. Lower is better. 95% Wilson CIs in parentheses. Results for GSM8K and MMLU add tasks with deterministic canonicalization (numeric extraction and MCQ matching, respectively).

Figure 3. Variance reduction: mode error vs.

K

across all five benchmarks. TruthfulQA and GSM8K show clear monotone decrease consistent with Theorem 4.4 . HumanEval exhibits a counterintuitive increase at low

K

: for items with pass rate

p<0.5

, more samples expose the dominance of the “fail” class, switching the mode from a lucky pass to the more frequent failure—a theoretically predicted effect (Section 11.3 ), not a method failure. BigBench and MMLU show relatively flat error, consistent with theory: variance reduction is most pronounced when

p^{\star}

is far from the decision boundary.

Figure 4. Mean prediction set size vs. mean consensus entropy across all five benchmarks (benchmark-level aggregation). Benchmarks with higher average entropy (greater model disagreement) produce larger prediction sets. The per-item correlation underlying this aggregate pattern is confirmed in the synthetic validation (Figure 11 ), where individual items are plotted. Error bars show 95% bootstrap CIs.

Dataset	Avg. $K$ used	Savings	Seq. Coverage	Seq. Avg. $\|S\|$
HumanEval	11.05 ( 10.3–11.9 )	44.8%	0.720 ( 0.61–0.81 )	1.28
TruthfulQA	9.67 ( 9.4–9.9 )	51.7%	0.980 ( 0.96–0.99 )	1.00
BigBench	9.92 ( 9.4–10.4 )	50.4%	0.792 ( 0.71–0.85 )	1.10
GSM8K	9.85 ( 9.6–10.1 )	50.8%	0.952 ( 0.93–0.97 )	1.00
MMLU	9.98 ( 9.7–10.3 )	50.1%	0.834 ( 0.80–0.86 )	1.11

Table 6. Sequential stopping results for GPT-4.1 (

\delta=0.05

K_{\max}=20

). Coverage and set size are preserved while using fewer samples. 95% CIs in parentheses.

Model	Full budget	Sequential	Single sample	Judge baseline
GPT-4.1	$168.01	$125.13	$4.20	$3.88
GPT-4.1-mini †	$20.80	$10.40	$1.04	$2.40
GPT-4.1-nano †	$1.60	$0.80	$0.08	$2.40
GPT-5 mini	$33.60	$25.03	$0.84	$3.88
Llama 4 Maverick ‡	$7.84	$3.92	$0.39	$2.88
Mistral Small ‡	$2.40	$1.20	$0.12	$2.88

Table 7. Estimated API cost (USD) per evaluation method and model. GPT-4.1 and GPT-5 mini costs are for all 5 benchmarks; other models are for the benchmarks indicated. “Full” =

K_{\max}=20

samples per item; “Sequential” = adaptive stopping; “Single” = 1 sample; “Judge” = 1 judge call per test item.

Dataset	Canonical $\|S\|$	Raw $\|S\|$	Reduction
TruthfulQA	1.00	1.00	0.0%
BigBench	1.10	1.81	39.2%
MMLU	1.11	1.41	21.3%

Table 8. Canonicalization ablation: average prediction set size with and without canonicalization (

\alpha=0.10

, GPT-4.1). Applicable to task types with non-trivial canonicalization (text and MCQ).

Figure 5. Canonicalization effect on average prediction set size. BigBench shows a

39.2\%

reduction (the largest effect), MMLU shows

21.3\%

, and TruthfulQA shows no difference (binary judge labels leave no surface-form variation). GSM8K and HumanEval are excluded (deterministic canonicalization).

		Coverage			Avg. $\|S\|$
Model	Dataset	Rank	LAC	APS	Rank	LAC	APS
GPT-4.1	GSM8K	0.956	0.914	0.908	1.00	1.00	1.15
GPT-4.1	MMLU	0.980	1.000	1.000	1.11	1.13	1.13
GPT-4.1-mini	GSM8K	0.954	0.900	0.902	1.00	1.00	1.12
GPT-4.1-mini	MMLU	0.976	1.000	1.000	1.12	1.13	1.13
GPT-4.1-nano	GSM8K	0.960	0.924	0.894	1.35	1.02	1.61

Table 9. Comparison of nonconformity scores (

K{=}10

\alpha=0.10

). All three scores use identical cached samples. “Cond.” = conditional coverage among solvable items. Best coverage per row in bold .

Model	GSM8K	MMLU	TruthfulQA	BigBench	HumanEval
GPT-4.1	94.6	83.4	96.8	75.4	69.9
GPT-4.1-mini	96.0	81.6	—	—	—
GPT-4.1-nano	89.8	66.5	—	—	—
Llama 4 Maverick	95.4	66.7	85.3	—	—
Mistral Small	93.8	77.8	84.8	—	—

Table 10. Reliability certification: reliability level

1{-}\alpha^{\star}

(%) for each model–task combination. Higher is better. “—” indicates the model was not evaluated on that benchmark. Boldface marks combinations where

M^{\star}{=}1

\alpha{=}0.10

(mode voting alone suffices).

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
${\mathcal{X}}$ , ${\mathcal{A}}$	Query space, answer space
$f_{\theta}$	Agent with parameters $\theta$ ; stochastic map ${\mathcal{X}}\to{\mathcal{A}}$
${\mathcal{A}}^{\star}(x)$	Set of acceptable answers for query $x$
$\mathrm{Canon}(x,a)$	Canonicalization function mapping raw answers to canonical classes
$K$	Number of i.i.d. samples per query
$K_{\max}$	Maximum samples per query (budget)

Appendix

Table 11. Summary of notation.

Figure 6. Synthetic coverage validation: empirical coverage vs. target

1-\alpha

for agents with

p^{\star}\in\{0.6,0.7,0.8\}

. All points lie on or above the diagonal, confirming Theorem 6.7 .

Figure 7. Synthetic variance reduction: mode error vs.

K

for three agents with known

p^{\star}

. Dashed lines show Hoeffding upper bounds. Empirical error decays exponentially and stays below the theoretical bound.

Figure 8. Bias–variance decomposition at

K{=}20

(probability resolution

1/K{=}0.05

). All conformal methods achieve

50

–

200\times

lower MSE than non-conformal baselines. Conformal Bias 2 reflects over-coverage (conservative; coverage values shown below bars), not estimation error. Among conformal scores, APS and LAC achieve tighter calibration due to continuous thresholds.

Figure 9. Bias–variance decomposition at

K{=}10

(probability resolution

1/K{=}0.10

), the regime typical of API-based evaluation. The conformal advantage persists. Rank provides the widest coverage margin (

0.946

vs. APS at

0.901

); on real LLM distributions (Section 11.8 ), this conservatism prevents the coverage violations that affect APS.

Figure 10. Set size

M^{\star}

vs. agent quality

p^{\star}

. Better agents require smaller prediction sets. The step-function shape reflects the discrete nature of

M^{\star}

(the

\lceil(n+1)(1-\alpha)\rceil

-th order statistic of integer-valued scores).

Figure 11. Prediction set size vs. consensus entropy for synthetic agents. The strong positive correlation confirms that set size adapts to per-item uncertainty.

Figure 12. Canonicalization effect: mode error with and without canonicalization for fragmented distributions. Canonicalization consolidates probability mass, reducing mode error exponentially as predicted by Proposition 4.6 .

Explore similar work

Proxy Confidence: Auditing Black-Box LLM Agents with a Surrogate's Log-Probabilities
Oct 2, 2026Yikai Zhao, Saurabh Pandey, Pradeep Kumar MisraLLM Agent Reliability LLM Auditing
Amazon
Measuring Black-Box Confidence via Reasoning Trajectories: Geometry, Coverage, and Verbalization
May 7, 2026Marc Boubnovski Martell, Josefa Lia Stoisser, Kaspar Märtens +4Confidence Estimation in Language Models CoT Reasoning
1Novo Nordisk · University of Oxford
Closing the Consistency Gap: Self-Evolving Agents That Learn to Stay on Course
Sep 8, 2026Evelyn Duesterwald, Benjamin Elder, Lilian Ngweta +2LLM Agent Reliability Self-Evolving Agents
IBM Software Innovation Lab · IBM Research

Oct 2, 2026J/K move · Enter open · S save

Proxy Confidence: Auditing Black-Box LLM Agents with a Surrogate's Log-Probabilities

Yikai Zhao, Saurabh Pandey, Pradeep Kumar Misra

Amazon

LLM Agent Reliability LLM Auditing Confidence Estimation in Language Models

Open paper AskPDF arXiv

A deployed LLM agent emits tool calls, queries, and code that can be silently wrong -- by the time the error surfaces, the action has run. Frontier chat APIs hide the model's token probabilities; the agent's stated confidence barely beats chance on the mistakes that matter; and resampling does not help, since frontier models are highly repetitive, reproducing the same call across samples. We recover the missing signal from a low-cost open-weight surrogate run in parallel. It reads the same context, schema, and proposed action as the agent, then scores the call from its own log-probabilities through a family of complementary readouts: teacher forcing and request-PMI weigh the likelihood of each argument value, a discriminative verdict judges the call as a whole, and tool-choice competition tests the function against its siblings. One principle says which to trust: a generative likelihood localizes wrong argument values, while the verdict catches holistically wrong calls. When the error type is unknown, an ensemble is the low-regret default. The readout is training-free, needs no access to the agent's internals, and costs one prefill pass alongside the tool call. On difficult coding tasks it reaches AUROC 0.825 where the actor's stated confidence is near chance (0.598), and the generative readouts beat it by +0.07 to +0.28 across three further actors. Against self-consistency it gains +0.14 to +0.19 on near-deterministic actors, at 1/K the cost. The signal drives two deployment modes: a real-time gate escalating the least-trustworthy calls for review (+0.05 to +0.30 accepted-action accuracy at 50% coverage), and confidence feedback, returning the tool result with the score so the agent adapts its next step -- lifting task success on live-execution benchmarks (+0.119 and +0.137, p <= 1e-4) and beating a random-value control where step errors are silent (+0.078, p = 0.003).

Abstract

Explore similar work

Proxy Confidence: Auditing Black-Box LLM Agents with a Surrogate's Log-Probabilities

Measuring Black-Box Confidence via Reasoning Trajectories: Geometry, Coverage, and Verbalization

Closing the Consistency Gap: Self-Evolving Agents That Learn to Stay on Course