Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network

Abdolvahab Khalili Sadaghiani; Jose Nunez-Yanez

cs.LGSep 28, 2026

Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network

Authors: Abdolvahab Khalili Sadaghiani, Jose Nunez-Yanez

Abstract

Graph neural networks (GNNs) need to exploit improved message passing without surrendering control over predictions already trusted in deployment. We introduce Reference-Tail Trust (RTT), a framework that admits learned updates inside a frozen GNN and certifies the prediction actually served. RTT couples graph-based proposal states with a constrained internal optimizer: each displacement is charged for its worst-case terminal cross-entropy increase through the incumbent's remaining message-passing layers. A trajectory-validated tube and an independent checker enforce per-node probability floors, $p^{\mathrm{s}}_{ic} \ge e^{-H_{\mathrm{row}}} p^{\mathrm{r}}_{ic}$ , and a call-level budget, $\sum_i w_i D_\infty(p^{\mathrm{r}}_i \| p^{\mathrm{s}}_i) \le H^+$ , uniformly over labels. Calls whose adapted outputs pass certification require no separate full incumbent rollout; failed certificates trigger whole-call fallback. We derive the exact probability-floor frontier by water-filling, characterize architecture-constrained efficiency, and establish conditions under which internal propagation exploits evidence unavailable to restricted output correctors. In the reported ogbn-arxiv audit, RTT achieves $6.5\times 10^{-3}$ nats of mean gain per call, with a one-sided 95% regression-rate upper bound of 0.95% and a 95% negative-flip upper bound of 0.51% on the uninspected part of the reserved node population. Its mean gain is 61% of a cross-fitted posterior-based frontier estimate and exceeds the strongest matched one-pass corrector by $+0.9\times 10^{-3}$ nats. Reported experiments span eight proposals, six graph-incumbent families, structural and temporal graph shifts, and molecular prediction, with additional image and tabular evaluations. RTT makes GNN adaptation a budgeted, certifiable inference decision rather than an unconditional model replacement.

Figures & tables

	Statement about the served prediction $p^{\rm s}$	Type	Unit	Assumptions
G1	$p^{\rm s}_{ic}\geq e^{-H_{\rm row}}p^{\rm r}_{ic}$ for every node $i$ and class $c$	deterministic	node	valid continuation enclosures and sound arithmetic; none on proposal quality or labels
G2	$\sum_{i}w_{i}D_{\infty}(p^{\rm r}_{i}\\|p^{\rm s}_{i})\leq H^{+}$ , hence $d^{\rm own}\leq H^{+}$ for every label vector	deterministic	call	as G1
G3	every class is capped, $p^{\rm s}_{ic}\leq 1-e^{-H_{\rm row}}(1-p^{\rm r}_{ic})$ (Proposition 1 (iv))	deterministic	node	as G1
G4	$\Pr(d^{\rm own}>\zeta)\leq u$ for the mixture, each component and the stress test	statistical	call	i.i.d. episodes of the registered generator
G5	$\mathbb{E}[-d^{\rm own}]\geq{\rm LB}$ (anytime-valid); negative-flip rate $\leq u_{\rm node}$	statistical	call, node	as G4; uniform inspection of reserved nodes
G6	slope coverage $\Rightarrow d^{\rm own}\leq 0$ , and $\Pr(d^{\rm own}>0)\leq\delta_{\rm cov}$	design	call	exchangeable episodes; a fixed member or selection-valid calibration

Table 1: Guarantees for the served prediction ( 1 ). G1–G3 require valid continuation bounds and sound certificate arithmetic, but no deployment labels or assumptions on proposal quality. G4–G5 concern the audited generator. G6 separates a pathwise coverage implication from a probability statement requiring selection-valid calibration (Section 3.5 ).

Panel of Figure 1 — Figure 1: RTT execution and certification. (a) Internal steps leave the incumbent trajectory; validated tubes enclose the reference continuations and bound terminal row damage. (b) Proposal features and learned heads choose a displacement inside the candidate hull. (c) The checker recomputes the executed trajectory’s tube, factors, charges, and descent predicates before release; a persistent failure triggers whole-call fallback. Blue modules determine utility, while the red certificate path determines deterministic validity. Labels are used offline, not by the deployed admission decision.

Policy	$-\mathbb{E}[d^{\rm own}]$ [95% CI]	$\Delta$ to RTT	$N_{\zeta}$	$u$	$u_{\rm node}$	LB	Lat.	FLOPs
RTT, registered ( $H^{+}{=}$ $25\zeta$ , $H_{\rm row}{=}1$ )	6.5 [6.3, 6.7]	–	12	0.95%	0.51%	6.2	1.42	1.36
RTT $+$ corrector on the unused budget	6.7 [6.5, 7.0]	$-$ 0.2 [ $-$ 0.4, $-$ 0.1]	12	0.95%	0.51%	6.4	1.49	1.40
One-pass corrector, 2-hop head $+$ rows	5.6 [5.4, 5.8]	+0.9 [+0.8, +1.1] †	14	1.07%	0.56%	5.3	1.25	1.22
One-pass corrector, 2-hop head	5.1 [4.8, 5.3]	+1.4 [+1.3, +1.6]	14	1.07%	0.56%	4.8	1.07	1.05
One-pass corrector, per-row head	4.5 [4.3, 4.7]	+2.0 [+1.9, +2.2]	13	1.01%	0.54%	4.2	1.02	1.01
Adaptive mixing, $\varepsilon_{i}\leq\varepsilon_{\max,i}$ (2 rollouts)	5.1 [4.9, 5.3]	+1.4 [+1.2, +1.6]	15	1.13%	0.61%	4.8	2.18	2.18

Table 2: Primary arxiv comparison on 2,048 final-audit mixture episodes; gain and its intervals are in

10^{-3}

nats.

\Delta

is RTT minus the row method;

\dagger

marks the primary comparison.

N_{\zeta}

is the regression count,

u

the one-sided call-level Clopper–Pearson bound,

u_{\rm node}

the reserved-node bound, and LB the betting lower bound on mean gain. Latency and FLOPs are relative to one incumbent pass. The oracle row is a cross-fitted posterior estimate, not a deployable method or a certified true-Bayes optimum.

Figure 2: Floor geometry and its empirical frontier. (a) The row floor at $h=0.45$ : the Bayes-posterior projection gains 0.256 nats; mixing toward the raw update gains 0.187 at its largest feasible weight and 0.145 at the universal weight $1-e^{-h}$ . The RTT point is schematic, not an additional measured result. (b) Water-filling equalizes marginal gains across unsaturated rows. (c) The arxiv budget sweep compares RTT, one-pass correction, two-rollout rules, matched TR, and symmetric pricing; the dashed frontier uses the cross-fitted posterior.

Figure 3: Mechanism diagnostics. (a) Planted partitions with a known label law: the analytic output frontier and the reported numerical reachability, certification, and policy levels. The numerical internal levels are optimization diagnostics, not proofs that their global suprema were attained. (b) Posterior-based frontier shares on arxiv. (c) Architecture-constrained efficiency by depth, together with cap placement and certified-to-exact price ratios. (d) Contributions from near-cancellation, beyond-two-hop, and remaining rows. Appendix E defines the groups and the limitations of the numerical gap calculation.

Panel of Figure 4 — Figure 4: Deployment trade-offs. (a–b) Final-audit mean gain against the call-level regression bound and relative latency. Equal-bound markers are offset for visibility; Table 2 gives exact values. The tolerance point is a deterministic statement. (c–d) Development-set effects of call size and row budget, including members reselected per call size and observed fallback rates.

Proposal	raw	raw $u$	TR	corrector	RTT	RTT $u$	RTT $-$ corrector	Lat. RTT	Lat. 2 roll.
bank prior + signed attention (ours)	3.9	8.81% ×	5.8	5.6	6.5	0.95%	+0.9 [+0.8, +1.1]	1.42	2.18
GPR-GNN (adapter)	3.2	6.99% ×	5.5	5.4	6.2	0.95%	+0.8 [+0.6, +1.0]	1.53	2.29
Co-GNN (adapter)	2.7	8.19% ×	5.2	5.2	5.9	1.01%	+0.7 [+0.5, +0.9]	1.62	2.38
AMP (adapter)	3.0	7.67% ×	5.4	5.3	6.0	1.01%	+0.7 [+0.5, +0.9]	1.59	2.35
GTrans (test-time adaptation)	2.3	6.00% ×	4.3	4.4	4.9	0.89%	+0.5 [+0.3, +0.7]	3.42	3.19
Matcha (test-time adaptation)	2.9	5.21% ×	4.6	4.6	5.2	0.95%	+0.6 [+0.4, +0.8]	2.63	2.39

Table 3: Proposal breadth on arxiv. Gain is in

10^{-3}

nats and

u

is the call-level regression-rate upper bound. Raw proposals are norm-trimmed but not admitted by RTT. The corrector receives each proposal’s rows; paired intervals compare RTT with that corrector. Latencies include the proposal and are relative to one incumbent pass.

Proposal	Native full	Native + floor	Matched TR	Matched corrector	RTT derived	$\Delta$
TSA	8.0	6.5	6.0	6.2	7.2	+1.0
STEM	8.4	6.8	6.3	6.4	7.4	+1.0

Table 4: TSA/STEM mean gains in

10^{-3}

nats per scored call under the common evaluation law specified here. These are results of the present comparison, not results quoted from the cited papers. “Native” retains the complete method; “floor” projects its output onto RTT’s budgets. TR, corrector, and RTT receive the same exported proposal.

\Delta

is RTT minus the matched corrector. Native gain can exceed certified gain: protection is not claimed to be free.

Quantity	TSA-derived + RTT	STEM-derived + RTT
Observed regressions $N_{\zeta}$	12	10
Pointwise call bound $u$	0.95%	0.83%
First-pass / re-certified releases	2,030 / 10	2,028 / 10
Whole-call fallbacks / fraction	8 / 0.39%	10 / 0.49%
Per-node negative-flip criterion	$\leq 0.60\%$	$\leq 0.60\%$
Adjusted paired gain criterion	lower CI endpoint $>0$	lower CI endpoint $>0$

Table 5: Event counts and pre-specified criteria for the two RTT-derived policies. Each audit contains

N=2{,}048

independent scored episodes;

u

is the one-sided 95% Clopper–Pearson bound from the regression count. The lower panel lists pre-specified thresholds; the intervals, bounds, and cost measurements needed to evaluate them are not reported for this comparison.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Family	transport	tube factor	window	last depth	global factor
tanh diffusion ( $T{=}32$ )	$\tanh(PHW)$	interval (Lemma 1 ), rank-8	second-order envelope	exact $C^{+}$	$(1{-}\alpha)(1{-}\tau{+}\tau\\|W\\|_{2})$
APPNP	$\alpha H_{0}+(1{-}\alpha)PH$	exact (linear)	exact $C^{+}$	exact $C^{+}$	$1-\alpha$
GCNII	$\mathrm{ReLU}(\tilde{X}\tilde{W})$	interval Clarke (Lemma 2 )	first-order enclosure	exact $C^{+}$	$(1{-}\alpha)\\|\tilde{W}\\|_{2}$
GRAND	smooth diffusion	interval	second-order envelope	exact $C^{+}$	per-step bound
GraphSAGE-2, GCN-3	2–3 layers	interval	covers the whole tail	exact $C^{+}$	$\\|W\\|_{2}$ per layer
ResNet-50, last 4 blocks	$x+f(x)$ , ReLU, $P{=}I$	interval Clarke	first-order enclosure	exact $C^{+}$	block Lipschitz

Appendix

Table 6: Primitive decomposition of every implemented incumbent family: the transport, where it is certified, how the window and the last depth are charged, and the factor used when a tube saturates.

Symbol	meaning	value	enters	effect of moving it
$T$ , $\alpha$ , $\tau$	horizon, skip weight, step size of the incumbent	32, 0.1, 0.9	( 9 )	fixed by the incumbent
$H^{+}$	per-call one-sided budget (selected member)	$25\zeta=0.05$	G2, charges	oracle frontier concave; executed curve empirical (Fig. 2 c)
$H_{\rm row}$	per-node floor	1 nat	G1, row trim	gain and fallback (Fig. 4 d)
$\zeta$	regression tolerance (registered choice)	0.002 nats	G4	rate statements only
$\delta$ , $p^{\star}$	statistical level, rate target	0.05, 2%	Thm. 3	bound widths
$\delta_{\rm cov}$	nominal fixed-member trajectory allocation	0.1	Thm. 1 (iii)	radii

Appendix

Table 7: Factors, parameters and variables behind the reported values: symbol, meaning, registered value or observed range, where it enters, and what moving it does. The lower block reports properties of the trained checkpoint and of the record.

Operation per training episode	count	forward passes	backward passes	memory
policy pass: incumbent steps and proposal at open depths	1	1.18	–	6.9 GB
counterfactual tails for full-loss slopes, one per open depth	16	3.75	3.75	checkpointed every 4 steps
field, covariance and posterior heads	1	0.04	0.05	0.3 GB
implicit differentiation through the solver (KKT systems)	16	–	0.03	small
total		4.97	3.83	18.4 GB peak

Appendix

Table 8: Training cost of one episode (operation counts; A100 80GB).

(a) Outcome	calls	share	by predicate
first-pass release (R1)	2,035	99.37%	–
failed the first pass: damage / row / descent	13	0.63%	2 / 4 / 7
released after re-certification (R2)	6	0.29%	1 / 3 / 2
whole-call fallback (F)	7	0.34%	1 / 1 / 5

Appendix

Table 9: Final audit of the registered member: (a) release ledger (integer counts of 2,048 calls); (b) the ten statements, pointwise at

\delta

and simultaneous at

\delta/10

, with the component means of the separate 4,096-episode audits, which are independent samples and differ from the mixture’s component means within sampling error.

(a) Implementation	half-width	certified mean
registered bets tuned to $N$	0.295	6.20
horizon-free sequence	0.316	6.18
approximate Kelly	0.352	6.15
hedged capital ( $\delta/2$ )	0.328	6.17
normal interval (not finite-sample valid)	0.204	6.30
Gaussian first-order width $\sqrt{2\sigma^{2}\log(1/\delta)/N}$	0.304	–

Appendix

Table 10: Statistics: (a) lower bounds on the mean gain by implementation at

N=2{,}048

against the Gaussian first-order width; (b) transfer to the reserved 2020 cohort, audited directly (the pass/fail column tests

u\leq p^{\star}

, not the principal audit’s minimum-mean requirement); (c) the conditional robustness curve for laws within KL radius

\rho

of the audit law.

Figure 5: Statistical machinery on the audit record. (a) Half-widths of lower bounds against $N$ with the Gaussian first-order width. (b) Running bounds: the registered bets at every $t$ (anytime-valid) and the horizon-free sequence. (c) The ten statements with the observed rate, the bound at $\delta$ and the simultaneous bound. (d) Per-node bound against the inspected flip rate; circle: RTT, square: the one-pass corrector. (e) The conditional robustness curve, and the 2020 cohort’s own audit (band). (f) Worst-case regression rate over reweightings of the components.

(a) Population	$\widehat{U}_{\rm out}$	$\widetilde{U}_{\rm reach}$	$\widetilde{U}_{\rm cert}$	$\widehat{U}_{\rm RTT}$	share	corrector
clean	2.6	2.1	1.8	1.3	50%	1.5
degree	8.9	7.4	6.4	5.3	60%	4.6
cache	17.2	14.6	12.9	10.8	63%	8.6
noise	12.6	10.6	9.4	7.7	61%	6.8
dropout	11.8	10.0	8.8	7.4	63%	6.4
mixture	10.6	8.9	7.9	6.5	61%	5.6

Appendix

Table 11: Reported frontier and internal-optimization diagnostics (

10^{-3}

nats per call). (a) Arxiv with a cross-fitted posterior. (b) Planted-partition diagnostics:

I

denotes information,

E

estimation,

\chi

uncertainty conservatism, and

\Upsilon

execution suboptimality. Tildes denote achieved numerical levels, hats denote empirical or posterior-based estimates, and the unmarked planted-law output frontier is analytic. These internal levels need not attain the exact suprema. The last column is the reported surrogate expression

\widetilde{U}_{\rm cert}-I-\chi-\frac{1}{2}(\sqrt{2E}+\sqrt{2\Upsilon})^{2}

; without the additional identifications discussed above, it is not a proved global lower bound on RTT’s gain. The rounded component values do not uniquely determine this nonlinear expression; reproducing it requires the unrounded records.

Figure 6: Separation diagnostics for Proposition 2 . (a–b) The cancellation instance is computed analytically. (a) Cancellation: probability of class 1 per node under the raw update and under RTT, which admits only the helpful candidate. (b) Gains at the scored node. (c) Planted graphs: share of the oracle gain against the distance of the evidence, for RTT and a two-hop corrector.

Policy	$-\mathbb{E}[d^{\rm own}]$ [95% CI]	$\Delta$ to RTT	$N_{\zeta}$	$u$	$u_{\rm node}$	LB	Lat.	FLOPs	Holm $p$
RTT
RTT (registered)	6.5 [6.3, 6.7]	–	12	0.95%	0.51%	6.2	1.42	1.36	–
RTT $+$ one-pass corrector on the unused budget	6.7 [6.5, 7.0]	$-$ 0.2 [ $-$ 0.4, $-$ 0.1]	12	0.95%	0.51%	6.4	1.49	1.40	–
RTT, tolerance point ( $H^{+}{=}\zeta$ )	2.0 [2.0, 2.1]	+4.5 [+4.3, +4.7]	0	0 (det.)	0.22%	1.9	1.42	1.36	–
One-pass floor correctors (one incumbent pass; same floor, labels, capacity, proposal rows)
One-pass corrector, 2-hop head $+$ rows	5.6 [5.4, 5.8]	+0.9 [+0.8, +1.1] †	14	1.07%	0.56%	5.3	1.25	1.22	–

Appendix

Table 12: Complete frontier on arxiv (final audit, as Table 2 ); Holm-adjusted

p

-values for the secondary comparisons.

Mechanism	swap	gain	$u$	what changes
Per-node budget	none $\to$ $H_{\rm row}{=}1$ nat	6.69 $\to$ 6.50	0.95% $\to$ 0.95%	per-node floor becomes deterministic; fallback 0.34% $\to$ 0.34%
Radii	per depth $\to$ sequential, trajectory-valid	6.86 $\to$ 6.50	1.01% $\to$ 0.95%	trajectory statement of Theorem 1 (iii); selection caveat applies
Placement	spend-based $\to$ certified efficiency	6.17 $\to$ 6.50	0.95% $\to$ 0.95%	trust moves to depths with high $\eta_{\ell}$
Window	envelope only $\to$ two branches	6.45 $\to$ 6.50	0.95% $\to$ 0.95%	optimum over the union of both feasible sets
Features	mean pooling $\to$ support functions	6.39 $\to$ 6.50	1.01% $\to$ 0.95%	executed step exactly invariant (Table 18 )
Slopes	probe loss $\to$ full loss	6.16 $\to$ 6.50	1.13% $\to$ 0.95%	accounting identity closes

Appendix

Table 13: What each mechanism buys: one swap at a time on the registered configuration (final audit;

10^{-3}

nats; alternative

\to

registered). Swaps are order-dependent comparisons, not an additive decomposition.

(a) Neighbor	gain	$u$	Lat.
WiSE-FT (incumbent $\leftrightarrow$ v2), $\alpha$ by learn-then-test	3.4	2.15% ×	1.00
LoRA scaling $\alpha$ by learn-then-test	3.2	2.20% ×	1.00
EATA (anti-forgetting test-time adaptation)	2.6	3.51% ×	2.10
RDumb (periodic reset)	2.2	2.86% ×	2.05
$D_{\infty}$ -regularized fine-tuning (floor trained, not enforced)	3.4	1.81%	1.00

Appendix

Table 14: Neighboring methods, and test-time adaptation under a batch-shift collapse (20 streams of 600 calls, a separate experiment from Figure 8 , shift at call 150; damage in

10^{-3}

nats on the shifted segment; positive is a loss). Part (a) reports the neighboring methods themselves; proposal-specific RTT comparisons are given in Table 3 . These rows do not establish an RTT wrapper experiment for each neighboring method.

Dataset / shift	incumbent	$\zeta$	$\hat{U}_{\rm out}$	RTT	corr.	TR	share	$u$	$u_{\rm node}$	verified	Lat.	metric
ogbn-arxiv, registered mixture	tanh diffusion, $T{=}32$ (tube)	2	10.6	6.5	5.6	5.8	61%	0.95%	0.51%	99.37%	1.42	acc. 75.7 $\to$ 76.1
ogbn-arxiv, registered mixture	APPNP (linear tail, exact)	2	9.4	6.0	5.4	5.3	64%	0.89%	0.46%	100.00%	1.22	acc. 75.5 $\to$ 75.9
ogbn-arxiv, registered mixture	GraphSAGE, 2 layers (shallow)	2	8.1	5.2	5.0	4.6	64%	0.83%	0.46%	100.00%	1.52	acc. 72.1 $\to$ 72.4
ogbn-arxiv, registered mixture	GCN, 3 layers (shallow)	2	8.4	5.4	5.2	4.8	64%	0.89%	0.46%	100.00%	1.47	acc. 71.8 $\to$ 72.2
ogbn-arxiv, 2020 cohort (temporal)	tanh diffusion (tube)	2	2.9	1.9	1.6	1.3	66%	1.18%	–	99.51%	1.42	acc. 74.1 $\to$ 74.2
GOOD-Arxiv, degree (covariate)	GCNII (ReLU, interval Jacobians)	2.3	9.7	5.8	5.1	4.9	60%	1.13%	0.61%	99.22%	1.43	acc. 63.8 $\to$ 64.1

Appendix

Table 15: Breadth under one protocol (final audits, 2,048 episodes;

10^{-3}

nats per task unit;

\zeta

10^{-3}

\hat{U}_{\rm out}

: estimated oracle frontier; share: RTT gain over

\hat{U}_{\rm out}

; verified: calls released on the first pass; the last column gives the task metric of the incumbent and of RTT on the audited episodes.

Official test split (audited once)
Reference family	AP ref.	AP TR	AP RTT	gain ( $10^{-3}$ )	RTT $-$ TR (AP)
Contractive diffusion	26.4	27.8	28.5	1.52	+0.7 [+0.4, +1.0]
Centered GIN-style	27.3	28.2	28.4	1.03	+0.2 [0.0, +0.4]
Incumbent GIN-style (deployed)	27.7	28.2	28.6	0.88	+0.4 [+0.1, +0.7]
GIN-style $+$ virtual node	28.4	28.8	29.2	0.79	+0.4 [+0.2, +0.6]
Incumbent GIN-style (deployed)	27.7	–	28.5	–	–

Appendix

Table 16: ogbg-molpcba on four reference families: the reserved scaffold halves define a custom finite-population protocol with exact empirical test-half AP. The separately reported official-test evaluation uses the full official test population and is not independent of any custom split drawn from that same population.

Panel of Figure 7 — Figure 7: Robustness on the development half. (a) Three incumbents $\times$ eight training seeds: gain of every passing seed for RTT (red circles) and the one-pass corrector (blue squares); crosses: failed selections, deployed as the incumbent (gain 0, plotted at zero). (b–e) Gain against the row trim, the safety factor, the number of support-function probes and the trajectory miscoverage budget (circle: registered value).

Panel of Figure 8 — Figure 8: Reported monitored-service traces and alarm-delay counts from the 20-stream study (held-out corruption family begins at call 200): (a) trailing gain of the fixed and the monitored policy; (b) cumulative regressions; (c) alarm delays, including streams that never alarm.

(a) Proposal	its cost (ms)	RTT	2 rollouts, sequential	2 devices
bank prior + signed attention (ours)	7.5	1.42	2.18	1.18
GPR-GNN (adapter)	12.1	1.53	2.29	1.29
Co-GNN (adapter)	16.0	1.62	2.38	1.38
AMP (adapter)	14.6	1.59	2.35	1.35
GTrans (test-time adaptation)	91.0	3.42	3.19	2.19
Matcha (test-time adaptation)	58.0	2.63	2.39	1.39

Appendix

Table 17: Costs: (a) latency ratios by proposal, with two rollouts sequential and on two devices; (b) episode-evaluation and compute ledger of the reported study. Part (a) contains no separate FLOP column; relative FLOPs for the primary comparison are in Table 2 .

Test	result	verdict
planted violations, hidden margins $10^{-7}$ – $10^{-3}$ nats	10,000 of 10,000 rejected	test passed
50-digit re-evaluation of certificates	1,000 certificates; float64 enclosure above the high-precision reference value, by at most $3.1\times 10^{-10}$	test passed
exact endpoint cost (offline second rollout)	0 violations on 2,048 calls; certified / exact median 1.61	test passed
adversarial directions within the trim	released 41%; released damage mean 29, max 49 ( $10^{-3}$ ); over all calls 11.9	bound met; audit fails
provisional factors under-estimated by 30%	214 of 214 violating calls caught (fallback)	test passed
outward rounding switched off	3 of 2,048 certificates below the exact cost by $\leq 10^{-6}$	diagnostic

Appendix

Table 18: Checker and stress-test results: planted violations, high-precision re-evaluation, endpoint costs, adversarial directions, corrupted inputs, and displacement invariance. A passing finite test is evidence about the tested instances, not a proof of universal numerical soundness.

Figure 9: The certificate. (a) Toy contractive incumbent, computed exactly: distance of every incumbent continuation started on an executed segment from the executed state, against the tube radius of Lemma 7 . (b) Certified charge against the offline endpoint cost for the 2,048 candidate trajectories, including trajectories subsequently rejected by the selector; no trajectory lies below the diagonal. A fallback serves the incumbent and therefore has zero served loss contrast. (c) Distribution over served nodes of the certified per-node bound $\Gamma_{\Delta}r_{T,i}$ (red) and of the exact one-sided damage $h_{i}=D_{\infty}(p^{\rm r}_{i}\|p^{\rm s}_{i})$ (grey). (d) Certified-to-exact charge ratio by depth, median and 5–95% band; shaded: the window.

Figure 10: Mechanism. (a) Per-step factors by depth: interval factors on the tube, the factor recorded along the incumbent’s own trajectory, and the global factor. (b) Contract growth $\Pi_{\ell}$ with the admissibility cap $\Pi_{\max}$ ; the open depths must be admissible. (c) Generic verifiers on the same executed interventions (64-node calls, last eight depths): certified-to-exact ratio and time per call.

Line	check	changes	guarantee	reference run	updates
Differential verification ( Paulsen et al., 2020a ; Paulsen et al., 2020b ; Teuber et al., 2025 )	offline	a second network	bounds on the difference	yes	any fixed pair
Certified upgrades ( Zhang et al., 2026 ; Balachandran, 2026 )	offline audit	replacement model	statistical non-regression	yes	replacement
Conformal policy control ( Prinster et al., 2026 ) ; LTT, CALM ( Angelopoulos et al., 2025 ; Schuster et al., 2022 )	calibration	policy or exit	risk control	yes / partly	policies, exits
CPI, PPO ( Kakade and Langford, 2002 ; Schulman et al., 2017 )	training	policy	CPI: model-based improvement; PPO: clipped surrogate	–	policies
Weight interpolation ( Wortsman et al., 2022 )	offline	weights	none per call	–	weight deltas
Safe / graph TTA ( Niu et al., 2022 ; Press et al., 2023 ; Bao et al., 2025 ; Hsu et al., 2026 )	online	states or weights	none per call	–	test-time updates

Appendix

Table 19: Positioning on explicit axes: when the check happens, what is changed, what is guaranteed, whether the reference prediction is computed, and which updates are supported.

Symbol	meaning
$p^{\rm r},\ p^{\pi},\ p^{\rm s},\ p^{\rm u},\ p^{\rm B}$	incumbent’s, adapted, served, raw update’s prediction; Bayes posterior
$\alpha,\ \tau,\ T$	the incumbent’s skip weight, step size and horizon
$h_{i}=D_{\infty}(p^{\rm r}_{i}\\|p^{\rm s}_{i})$ , $S^{\pm}$	one-sided damage of row $i$ ; worst-case loss increase and decrease of a call
$H^{+},\ H_{\rm row},\ \mathcal{B}_{\ell},\ \rho_{\ell,i}$	per-call and per-node budgets; remaining call budget; row allowance
$\mathcal{F}_{h}(p)$	floor set $e^{-h}p+(1-e^{-h})\Delta$
$\mathcal{O},\ \mathcal{G}$	label-free information; expected gain given it

Appendix

Table 20: Notation.

Explore similar work

Understanding and Mitigating Under-Confidence in GNNs from the Final Layer
May 16, 2025Jincheng Huang, Jie Xu, Xiaoshuang Shi +3Graph Neural Networks Confidence Estimation
School of Computer Science and Engineering, University of Electronic Science and Technology of China · Southeast University
Message Tuning Outshines Graph Prompt Tuning: A Prismatic Space Perspective
Jun 2, 2026Yancheng Chen, Dun Ma, Shuai Zhang +6Graph Foundation Model Soft Prompt Tuning
Academy of Mathematics and Systems Science, Chinese Academy of Sciences · School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences · Institute of Information Engineering, Chinese Academy of Sciences +4
When does distribution shift break graph neural networks calibration?
Jul 12, 2026Abderaouf BahiGraph Neural Networks Distribution Shifts
Computer Science and Applied Mathematics Laboratory (LIMA), Faculty of Science and Technology, Chadli Bendjedid University, El Tarf 36000, Algeria

May 16, 2025, cs.LGJ/K move · Enter open · S save

Understanding and Mitigating Under-Confidence in GNNs from the Final Layer

Jincheng Huang, Jie Xu, Xiaoshuang Shi, Ping Hu+2

School of Computer Science and Engineering, University of Electronic Science and Technology of China · Southeast University

Graph Neural Networks Confidence Estimation Confidence Calibration Overconfidence

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) have demonstrated remarkable effectiveness on graph-based tasks. However, their predictive confidence is often miscalibrated, typically exhibiting under-confidence, which harms the reliability of their decisions. Existing calibration methods for GNNs normally introduce additional calibration components, which fail to capture the intrinsic relationship between the model and the prediction confidence, resulting in limited theoretical guarantees and increased computational overhead. To address this issue, we propose a simple yet efficient graph calibration method. We establish a unified theoretical framework revealing that model confidence is jointly governed by class-centroid-level and node-level calibration at the final layer. Based on this insight, we theoretically show that reducing the weight decay of the final-layer parameters alleviates GNN under-confidence by acting on the class-centroid level, while node-level calibration acts as a finer-grained complement to class-centroid-level calibration, which encourages each test node to be closer to its predicted class prototype in the final-layer representations. Extensive experiments validate the superiority of our method. The code is released at https://github.com/huangJC0429/SCAR.

Abstract

Explore similar work

Understanding and Mitigating Under-Confidence in GNNs from the Final Layer

Message Tuning Outshines Graph Prompt Tuning: A Prismatic Space Perspective

When does distribution shift break graph neural networks calibration?