Paper deep dive
Reference-Tail Trust:Certified Probability Floors for Learned Updates Inside a Deployed Network
Abdolvahab Khalili Sadaghiani, Jose Nunez-Yanez
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2609.34904v1
- Canonical: https://arxiv.org/abs/2609.34904v1
Trouble viewing inline? Open PDF directly →
Full Text
166,271 characters extracted from source content.
Expand or collapse full text
Reference-Tail Trust: Certified Probability Floors for Learned Updates Inside a Deployed Network 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, pics≥e−Hrowpicrp s_ic≥ e^-H_ rowp r_ic, and a call-level budget, ∑iwiD∞(pir∥pis)≤H+ _iw_iD_∞(p r_i\|p s_i)≤ 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×10−3× 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×10−3× 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. 1 Introduction A deployed network is a reference point, not merely a checkpoint waiting to be replaced. Its predictions support decisions that users and downstream systems have already learned to rely on. New propagation rules, test-time adaptation, retraining, and weight updates may improve validation performance while introducing regressions on particular inputs. An average improvement therefore leaves an operational question unanswered: how much of an update should be admitted on the current call, and what can be guaranteed about the prediction that is actually delivered? We study this question for learned changes to the internal states of a frozen network, which we call the incumbent. The objective is not to certify that every update is beneficial. Without assumptions linking deployment information to labels, a nontrivial label-free change cannot generally guarantee improvement. Instead, we separate a deterministic protection requirement from a statistical performance claim. Each served prediction must remain within a specified one-sided cross-entropy budget relative to the incumbent, for every possible label vector. Expected gain and the probability of exceeding a registered regression tolerance are then assessed on fresh deployment episodes. This distinction makes the unit of protection explicit: individual output rows receive a probability floor, whereas calls receive an aggregate damage budget. Reference-Tail Trust (RTT) implements this separation inside the network.11 1 The code is released in the GitHub repository at https://github.com/VKHS/RTT. A learned proposal supplies candidate state displacements, and a constrained optimizer selects how much of them to execute. Each displacement is evaluated through the reference tail: the incumbent’s continuation from the current internal state to the prediction head. Bounds on that continuation translate an internal movement into a worst-case terminal loss increase. A tube centered on the executed trajectory encloses the relevant counterfactual continuations, allowing the certificate to account for interactions between interventions at different depths. The final checker recomputes these bounds on the trajectory that was actually executed and either releases the adapted output or serves the incumbent for the whole call. Learned modules determine utility; the checker determines admissibility. The resulting protection has a direct probabilistic interpretation. A row budget HrowH_ row guarantees pics≥e−Hrowpicrp s_ic≥ e^-H_ rowp r_ic for every class, and the call budget bounds the weighted order-∞ Rényi divergence ∑iwiD∞(pir∥pis) _iw_iD_∞(p r_i\|p s_i). These guarantees do not require deployment labels or a trustworthy proposal. They also do not imply that internal intervention is intrinsically superior to output correction: every floor-feasible prediction can be expressed as a mixture containing the incumbent prediction. Accordingly, we derive an exact output-space frontier, identify the information and receptive-field restrictions under which internal steps can help, and compare RTT with a learned one-pass corrector given the same floor, labels, head capacity, and proposal features. In the reported arxiv audit, RTT gains 6.5×10−3× 10^-3 nats per call against the corrector’s 5.6×10−3× 10^-3, at latencies of 1.42× and 1.25× one incumbent pass, respectively (Table 2). This comparison tests the additional utility and cost of internal admission without crediting RTT for protection that a simpler output rule also provides. Prior work addresses related parts of this problem. Backward-compatible learning and positive-congruent training reduce prediction regressions during model development (Srivastava et al., 2020; Träuble et al., 2021; Yan et al., 2021), while certified model-upgrade procedures audit replacement decisions against an incumbent (Zhang et al., 2026; Balachandran, 2026). Differential verification compares fixed networks (Paulsen et al., 2020a; Paulsen et al., 2020b; Teuber et al., 2025), and bound propagation provides tools for certifying neural computations (Zhang et al., 2018; Xu et al., 2020). Learned graph propagation and adaptive message passing expand the available update mechanisms (Chen et al., 2020; Chien et al., 2021; Finkelshtein et al., 2024; Errica et al., 2025); weight interpolation, low-rank updates, and test-time adaptation provide further proposals but do not themselves enforce RTT’s per-call floor (Wortsman et al., 2022; Hu et al., 2022; Wang et al., 2021; Niu et al., 2022; Niu et al., 2023; Press et al., 2023; Jin et al., 2023; Bao et al., 2025). Among recent conference methods, Test-Time Structural Alignment (TSA; AISTATS 2026) adjusts neighborhood influence, self–neighbor balance, and the decision boundary (Hsu et al., 2026), while STEM (The Web Conference 2026) uses a state-space controller to generate adapters for a frozen GNN under evolving domain shifts (Luo et al., 2026). These methods motivate complementary tests of RTT: admitting structure-aware corrections and certifying the outputs of history-dependent adaptation. Risk-controlled calibration, adaptive prediction, conformal policy control, and steering with abstention regulate other aspects of prediction or policy selection (Angelopoulos et al., 2025; Schuster et al., 2022; Prinster et al., 2026; Hedström et al., 2025). Conservative policy iteration motivates telescoping comparisons, whereas PPO’s clipped surrogate is a distinct training device, not an all-class probability-floor certificate (Kakade and Langford, 2002; Schulman et al., 2017). Finally, calibration and uncertainty under shift explain why a label-free correction can have useful conditional information (Guo et al., 2017; Hsu et al., 2022; Ovadia et al., 2019). RTT brings these questions together at a different decision point: admission of internal changes on an individual deployment call, with protection attached to the served output. RTT combines certified internal admission, an exact probability-floor frontier, and explicit statistical evaluation in one framework. It can accept useful parts of a learned update, withhold uncertified adapted outputs, and expose the gain–protection–cost trade-off without changing the incumbent’s weights. 2 Reference-Tail Trust: Model and Certified Execution This section develops the execution mechanism from the deployment objective to the final release decision. The analytical and statistical consequences are established in Section 3; the complete implementation primitives and parameter definitions are given in Appendices A and H. 2.1 Deployment objective and the probability-floor contract Let a graph with n nodes and features X be processed by a frozen incumbent with H0=Enc(X)H_0=Enc(X), transitions Hℓ+1r=Fℓr(Hℓr)H r_ +1=F r_ (H r_ ) for ℓ<T <T, and a row-wise affine logit head Z. An episode is one deployment call with a query set of nqn_ q scored rows, nonnegative weights wiw_i summing to one, and a draw of the registered perturbation. The adapted and incumbent executions are compared on the same input, support, cache realization, and scheduled exogenous transformations. Any state replacement must be included in both continuation maps used by the certificate. Labels are unavailable to the deployed admission rule. They are used offline for training, calibration, and evaluation. A proposal supplies candidate states at selected depths, either directly or through a frozen adapter into the incumbent’s state space. RTT executes Hℓ+1=Fℓr(Hℓ)+vℓH_ +1=F r_ (H_ )+v_ and computes the adapted prediction pπ=softmax(Z(HT))p^π= (Z(H_T)). The prediction actually served is ps=(pπ,certificate,pr)=pπ,if the certificate holds,pr,otherwise: whole-call fallback,p s=S(p^π,certificate,p r)= casesp^π,&if the certificate holds,\\ p r,&otherwise: whole-call fallback, cases (1) where pr=softmax(Z(HTr))p r= (Z(H_T r)) is the incumbent’s output on the same call. A call whose adapted output passes the checker does not require a separate full incumbent rollout. The short reference-tail computations used near the terminal depth remain part of RTT’s cost; on fallback, the unmodified tail is evaluated from the cached state preceding the first intervention. For weighted cross-entropy J(p;y)=−∑iwilogpi,yiJ(p;y)=- _iw_i p_i,y_i, define down=J(ps,y)−J(pr,y)d own=J(p s;y)-J(p r;y), so a positive value is damage and −down-d own is gain. The deployment objective separates pointwise constraints from the audited regression-rate requirement: max e[−deown] _e[-d own_e] (2) subject to to D∞(pri∥psi)≤Hrowfor every row and call, D_∞(p r_i\|p s_i)≤ H_ row every row and call, ∑iwiD∞(pri∥psi)≤H+for every call, _iw_iD_∞(p r_i\|p s_i)≤ H^+ every call, Pre(deown>ζ)≤p⋆. _e(d own_e>ζ)≤ p . The first two constraints must hold for all label vectors, independently of the proposal. The last is a statistical statement about a specified deployment generator. On arxiv, ζ=0.002ζ=0.002 nats is a registered tolerance, anchored to the development-set median change of 0.0021 nats among calls whose accuracy drops by 0.1 percentage point. This anchor is not a conversion from cross-entropy to accuracy; accuracy and negative flips are audited separately. The label-uniform price follows exactly from cross-entropy. If hic=log(picr/pics)h_ic= (p r_ic/p s_ic), then S+=supydown=∑iwimaxchic=∑iwiD∞(pir∥pis),S−=∑iwiD∞(pis∥pir).S^+= _yd own= _iw_i _ch_ic= _iw_iD_∞(p r_i\|p s_i), S^-= _iw_iD_∞(p s_i\|p r_i). (3) Thus D∞(pir∥p)≤hD_∞(p r_i\|p)≤ h is equivalent to membership in the floor set ℱh(pir)=p∈Δ:pc≥e−hpicr∀c=e−hpir+(1−e−h)Δ.F_h(p r_i)=\p∈ :p_c≥ e^-hp r_ic\ ∀ c\=e^-hp r_i+(1-e^-h) . (4) The same constraints also imply a ceiling pc≤1−e−h(1−picr)p_c≤ 1-e^-h(1-p r_ic). Table 1 distinguishes these deterministic protections from the statistical claims. 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). Statement about the served prediction psp s Type Unit Assumptions G1 pics≥e−Hrowpicrp s_ic≥ e^-H_ rowp r_ic for every node i and class c deterministic node valid continuation enclosures and sound arithmetic; none on proposal quality or labels G2 ∑iwiD∞(pir∥pis)≤H+ _iw_iD_∞(p r_i\|p s_i)≤ H^+, hence down≤H+d own≤ H^+ for every label vector deterministic call as G1 G3 every class is capped, pics≤1−e−Hrow(1−picr)p s_ic≤ 1-e^-H_ row(1-p r_ic) (Proposition 1(iv)) deterministic node as G1 G4 Pr(down>ζ)≤u (d own>ζ)≤ u for the mixture, each component and the stress test statistical call i.i.d. episodes of the registered generator G5 [−down]≥LBE[-d own]≥ LB (anytime-valid); negative-flip rate ≤unode≤ u_ node statistical call, node as G4; uniform inspection of reserved nodes G6 slope coverage ⇒down≤0 d own≤ 0, and Pr(down>0)≤δcov (d own>0)≤ _ cov design call exchangeable episodes; a fixed member or selection-valid calibration Not claimed: an accuracy bound from ζ; unaudited transfer; nonincreasing loss. H+≤ζH^+≤ζ rules out only down>ζd own>ζ. 2.2 Candidate geometry and intervention placement The main arxiv incumbent is a deep diffusion, Fℓr(H)=αH0+(1−α)[(1−τ)H+τtanh(PHW)],F r_ (H)=α H_0+(1-α) [(1-τ)H+τ (PHW) ], (5) where P is row-stochastic, T=32T=32, α=0.1α=0.1, τ=0.9τ=0.9, and ‖W‖2=1.6\|W\|_2=1.6. Its global one-step bound is (1−α)(1−τ+τ‖W‖2)=1.386>1(1-α)(1-τ+τ\|W\|_2)=1.386>1, so useful admission cannot be justified by assuming global contraction. RTT instead uses interval factors on a validated trajectory tube. Appendix A gives the corresponding primitives for APPNP, GCNII, GRAND, and shallow GraphSAGE/GCN (Gasteiger et al., 2019; Chen et al., 2020; Chamberlain et al., 2021; Hamilton et al., 2017; Kipf and Welling, 2017). At open depths ℓ=16,…,31 =16,…,31, the native proposal supplies two candidates per row: a state-conditioned convex combination of 16 bank vectors and a signed one-hop attention update. External proposals are mapped through frozen linear adapters. Starting from H¯ℓ+1=Fℓr(Hℓ) H_ +1=F r_ (H_ ), the candidate displacements Hℓc,m−H¯ℓ+1H^c,m_ - H_ +1 undergo norm trimming and the row-budget trimming described below. Their resulting directions form a matrix DℓD_ , partitioned into K=8K=8 role blocks. The admissible physical displacement is vℓ=Dℓtℓ∈ℓ,tℓkm≥0,∑mtℓkm≤c¯ℓk.v_ =D_ t_ _ , t_ km≥ 0, _mt_ km≤ c_ k. (6) The zero displacement is feasible. If the direction matrix has rank zero, the step is defined as zero and no covariance inverse or optimizer is needed. Consequently, each block can retain the incumbent or accept a capped combination of its candidates. The caps allocate opportunity across depths using replayed gain per certified nat; this placement is an efficiency heuristic motivated by Section 3.3, not a claim that the internal optimization attains the output-space oracle. The optimizer operates on the displacement, rather than on a redundant candidate representation. A thin factorization Dℓ=QℓΘℓD_ =Q_ _ gives physical coordinates vℓ=Qℓxv_ =Q_ x with x=Θℓtx= _ t. Candidate-dependent head inputs are support-function features, sij=max0,maxm⟨uj,dℓ,i(⋅,m)⟩,s_ij= \0, _m u_j,d_ ,i^(·,m) \, (7) over fixed linear probes. Duplicating or permuting candidates, or adding points inside the same post-trim hull, leaves these features unchanged. This invariance does not cover a replacement that changes the hull, and nonlinear trimming must be accounted for before comparing hulls (Lemma 3). (a) Trajectory and tubeHℓH_ 0016162828TTclosed depths: the incumbent onlycontract depths: charge σℓ _ window: minσ,env+ \σ, env^+\,exact C+C^+ at T−1T-1XXEncH0H_0ZZpπp^πrow: ΓΔrT,i≤Hrow _ r_T,i≤ H_ row⇒picπ≥e−Hrowpicr \ p^π_ic≥ e^-H_ rowp r_ictube jT_j of radius rj,ir_j,iexecuted; dots: steps vℓv_ incumbent’s ownreference tail from HℓH_ (b) One depth ℓ (blue: affects only the gain) proposal (any update): rows Hℓc,mH c,m_ row trim and row-budget trim support-function features; heads g^ℓ g_ , Σ , κℓ _ solver in x: minΦℓ _ over ℓK_ , two branches provisional tube r~ r, contracts Λ , charges σ, env+ env^+, C+C^+ FℓrF r_ ++HℓH_ Hℓ+1H_ +1Fℓr(Hℓ)F r_ (H_ )Δℓm ^m_ ℓK_ a^x a_xvℓ=Qℓx⋆v_ =Q_ x row allowance ρℓ,i _ ,i from the provisional tube(c) Certify the executed trajectory, then release (red: trusted computing base) certificate: exact tube, interval factors, contracts, charges, outward rounding damage: ∑ℓchargeℓ≤H+ _ charge_ ≤ H^+ row: ΓΔrT,i≤Hrow∀i _ r_T,i≤ H_ row\ ∀ i descent: Φℓcert≤0∀ℓ cert_ ≤ 0\ ∀ all hold: release pπp^π; else re-certify (exact factors); else serve prp r (tail from Hℓ0H_ _0) served psp s 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. Recent GNN proposals through the same certificate interface. The TSA and STEM extensions use the existing external-proposal interface rather than changing RTT’s incumbent or certificate. Let a∈TSA,STEMa∈\TSA,STEM\ index the proposal, let ℋeH_e denote its permitted label-free history, and let H~ℓ+1(a) H_ +1^(a) be a row-aligned state exported at a predeclared hook. A frozen adapter Ωℓ(a) _ ^(a) gives Hℓc,a=H~ℓ+1(a)Ωℓ(a),dℓ(a)=Trimℓ(Hℓc,a−Fℓr(Hℓ)),H_ ^c,a= H_ +1^(a) _ ^(a), d_ ^(a)=Trim_ \! (H_ ^c,a-F_ r(H_ ) ), (8) where TrimℓTrim_ applies the same norm and row-budget restrictions as the original proposal. Identity adapters are used when the coordinates match; otherwise, depth correspondence and adapters are fixed using development/source data before the audit. TSA supplies structure-aligned representations, whereas STEM supplies representations generated with its history-dependent adapters. Their internal objectives choose proposals; only RTT’s checker authorizes a served change. For every realized history, sound incumbent-tail bounds therefore yield the same deterministic contract. Statistical guarantees still require the evaluation units specified in Section 4.6. A native method can also refine its classifier or output distribution. Its complete native output is retained as a separate comparator: the exported-state variant is explicitly named TSA-derived or STEM-derived, not represented as an exact reproduction of the entire method. The experiment records the loss of utility introduced by state export, depth mapping, and trimming before attributing any improvement to admission. Section 4.6 reports these comparisons separately from the original no-prefix audit. 2.3 Reference-tail contracts and one-sided pricing For fixed labels, let Vj(H)V_j(H) be the terminal cross-entropy of the incumbent’s continuation from state H at depth j. The key comparison is between Vℓ+1(H¯ℓ+1+vℓ)V_ +1( H_ +1+v_ ) and Vℓ+1(H¯ℓ+1)V_ +1( H_ +1): both use the incumbent tail, even though their starting state belongs to the adapted execution. To make every such comparison valid, RTT constructs row-wise tubes j=X:‖Xi−Hj,i‖≤rj,iT_j=\X:\|X_i-H_j,i\|≤ r_j,i\ around the executed states. These tubes enclose the incumbent trajectory and every incumbent continuation started along an executed intervention segment. For smooth transports, bounds Lj,iL_j,i on first derivatives and μj,i _j,i on curvature give row contracts |DVj[Y]|≤∑iΛj,i‖Yi‖|DV_j[Y]|≤ _i _j,i\|Y_i\| and |D2Vj[Y,Y]|≤∑iΞj,i‖Yi‖2|D^2V_j[Y,Y]|≤ _i _j,i\|Y_i\|^2. For (5), their first-order backward recursion and the tube’s forward recursion are Λj _j =(1−α)[(1−τ)Λj+1+τP⊤(Lj⊙Λj+1)], =(1-α) [(1-τ) _j+1+τ P (L_j _j+1) ], (9) rj+1,i r_j+1,i =(1−α)[(1−τ)rj,i+τLj,i(Prj)i]+‖vj,i‖, =(1-α) [(1-τ)r_j,i+τ L_j,i(Pr_j)_i ]+\|v_j,i\|, with ΛT,i=ΓΔwi _T,i= _ w_i and ΞT,i=ΓΔ2wi/4 _T,i= _ ^2w_i/4, where ΓΔ=maxc,c′‖c−c′‖2 _ = _c,c \|w_c-w_c \|_2 is the maximum pairwise distance between the effective class-head vectors, including the frozen temperature. We use ‖v‖Ξ2=∑iΞℓ+1,i‖vi‖22\|v\|_ ^2= _i _ +1,i\|v_i\|_2^2 at depth ℓ . Proposition 3 gives the second-order recursion; Lemma 7 proves enclosure. For ReLU transports, interval generalized-Jacobian enclosures replace unsupported smooth Taylor bounds (Lemma 2). For tanh, a pre-activation tube radius ϱ bounds the change of unit u by ϱ∥W:,u∥2 \|W_:,u\|_2. Bounding the derivative at the smallest absolute pre-activation within that interval yields Lj,iL_j,i, refined by a rank-8 spectral bound and capped by ‖W‖2\|W\|_2. These are tube-wide bounds, not derivatives sampled only on the executed path. The distinction is essential: a local factor that fails on a counterfactual continuation cannot certify the served prediction. RTT uses increasingly informative charges as the remaining tail shortens. At contract depths, it charges σℓ(v)=∑iΛℓ+1,i‖vi‖ _ (v)= _i _ +1,i\|v_i\|. This is conservative because norms discard the sign of a useful movement. Within the last b=4b=4 depths, a tangent basis UℓU_ of width 2K2K also yields envℓ+(t)=∑iwimaxc⟨pℓ,i−ec,(Uℓt)i⟩+12‖Dℓt‖Ξ2,env_ ^+(t)= _iw_i _c p_ ,i-e_c,(U_ t)_i + 12\|D_ t\|_ ^2, (10) where pℓ,ip_ ,i is the reference-tail prediction from H¯ℓ+1 H_ +1, not necessarily the original incumbent endpoint after earlier interventions. At the last depth, the affine head permits the exact charge C+(t) C^+(t) =∑iwi[LSE(zi+Δzi(t))−LSE(zi)−mincΔzic(t)] = _iw_i [ (z_i+ z_i(t))- (z_i)- _c z_ic(t) ] (11) =∑iwiD∞(pℓ,i∥pit). = _iw_iD_∞(p_ ,i\|p_i^t). Both the contract and the envelope are valid upper bounds. Their minimum is valid too, but its budget sublevel set is a union of convex sets. RTT therefore solves the two window branches separately and retains the better feasible displacement, rather than treating their union as convex (Lemma 4). 2.4 Learning to allocate certified budget The field head predicts g^ℓ g_ on the executed support, inducing candidate slopes a^t=Dℓ⊤g^ℓ a_t=D_ g_ and physical-coordinate slopes a^x=Qℓ⊤g^ℓ a_x=Q_ g_ . A block-diagonal covariance head Σ^x _x and a calibrated radius κℓ _ describe uncertainty in these slopes. Within each feasible branch, RTT minimizes Φℓ(x)=a^x⊤x+κℓ‖Σ^x1/2x‖+(1+ρD)‖v‖Ξ2+ρx‖v‖22ω,v=Qℓx, _ (x)= a_x x+ _ \| _x^1/2x\|+ (1+ _D)\|v\|_ ^2+ _x\|v\|^22ω, v=Q_ x, (12) subject to the candidate hull and remaining call budget. Equation (12) uses a certified quadratic remainder at smooth, nonterminal depths. At the final depth it is replaced by ΦT−1(x)=a^x⊤x+κT−1‖Σ^x1/2x‖+ϱT−1(v)+ℛT−1(v)ω,v=QT−1x, _T-1(x)= a_x x+ _T-1\| _x^1/2x\|+ _T-1(v)+R_T-1(v)ω, v=Q_T-1x, where ϱT−1(v)=∑iwiKL(pT−1,i∥softmax(zi+Δzi(v))) _T-1(v)= _iw_iKL(p_T-1,i\|softmax(z_i+ z_i(v))) is the exact label-independent remainder and ℛℓ(v)=(ρD‖v‖Ξ2+ρx‖v‖22)/2R_ (v)=( _D\|v\|_ ^2+ _x\|v\|_2^2)/2. A nonsmooth tail requires its own validated remainder model, rather than a smooth quadratic bound across a kink. Here 0<ω<10<ω<1 is a safety factor and ρx>0 _x>0 makes the objective strictly convex in the physical displacement. The uncertainty term is the support function of the slope ellipsoid: on the coverage event it upper-bounds the unknown linear loss change for every feasible direction. The curvature term bounds the nonlinear remainder, and the regularizer makes a redundant candidate parameterization immaterial. At a contract depth, a block whose candidate slopes are all nonnegative can be screened out: setting that block to zero cannot increase its linear contribution, the joint uncertainty norm, the displacement penalty, or the contract charge. The linear, quadratic, and contract terms separate by block, but the single ellipsoidal norm in (12) couples their magnitudes. The remaining convex program therefore retains that joint norm; its scalar budget multiplier has nonincreasing spend and can be located by bisection, with a coupled convex solve at each multiplier. Each window branch has a unique optimal displacement; the union need not. A deterministic tie-break expressed in physical state coordinates handles equal branch objectives without introducing candidate-order dependence. Minimum-norm candidate coefficients are recovered only after choosing the physical step. A provisional tube restricts the proposed row movements during execution; the final checker enforces the row guarantee. With nleftn_ left open depths remaining and a registered growth proxy Π^ℓ _ , the row allowance is ρℓ,i=(Hrow/ΓΔ−Π^ℓr~ℓ,i)+Π^ℓ+1nleft. _ ,i= (H_ row/ _ - _ r_ ,i)_+ _ +1n_ left. (13) For an open depth, the proxy denominator is positive and nleft≥1n_ left≥ 1. Candidates are scaled so that c¯ℓk‖dℓ,i(k,m)‖≤ρℓ,i c_ k\|d_ ,i^(k,m)\|≤ _ ,i. A zero cap or zero direction requires no division and yields zero displacement. This preserves convexity of the resulting hull and reserves room for later steps. The proxy influences gain and fallback frequency, not validity: the final checker recomputes the tube and verifies ΓΔrT,i≤Hrow _ r_T,i≤ H_ row for every served row. 2.5 Independent certification and whole-call release Algorithm 1 separates proposing, executing, and certifying. After execution, the checker reconstructs the tube, interval factors, contracts, charges, and robust descent models using certified remainders. It checks three predicates: ∑ℓchargeℓ≤H+ _ charge_ ≤ H^+, maxiΓΔrT,i≤Hrow _i _ r_T,i≤ H_ row, and Φℓcert≤0 _ cert≤ 0 at every accepted depth. A failure triggers tighter per-row spectral factors; a persistent failure triggers whole-call fallback. Row-wise mixing after a failed call is not substituted for this selector, because the proof accounts for the served policy as a whole. The real-arithmetic guarantees extend to floating-point execution only when all numerical residuals are enclosed. The checker described in Appendix G uses directed rounding, bounds the adapted execution residual and the incumbent continuation’s float32 error, and charges both against the budgets. Thus a poor proposal or inaccurate utility head can reduce gain or induce fallback, but it does not invalidate a correctly implemented deterministic certificate. Algorithm 1 RTT for one deployment call. All displacement optimizations include the post-trim hull. 1: H0H_0; incumbent; proposal and adapters; caps; heads and radii; H+,Hrow,bH^+,H_ row,b 2: ℬ←H+B← H^+; initialize provisional tube; ℓ0←none _0 3: for ℓ=0,…,T−1 =0,…,T-1 do 4: H¯ℓ+1←Fℓr(Hℓ) H_ +1← F r_ (H_ ); initially set vℓ←0v_ ← 0 5: if ℓ is open and ℬ>0B>0 then 6: Form candidates; apply norm and row-budget trims; form Dℓ=QℓΘℓD_ =Q_ _ 7: Compute support features, slopes, and covariance for Φℓ _ 8: if ℓ=T−1 =T-1 then 9: Minimize Φℓ _ subject to C+≤ℬC^+ , using the exact remainder 10: else if ℓ≥T−b ≥ T-b then 11: Solve branches σℓ≤ℬ _ and envℓ+≤ℬenv^+_ separately 12: Choose the better feasible physical displacement; resolve ties deterministically 13: else 14: Screen nonnegative-slope blocks; solve under σℓ≤ℬ _ by bisection 15: end if 16: vℓ←Qℓx⋆v_ ← Q_ x ; subtract the provisional charge from ℬB 17: if vℓ≠0v_ ≠ 0 and ℓ0=none _0=none then 18: Cache HℓH_ and set ℓ0←ℓ _0← 19: end if 20: end if 21: Hℓ+1←H¯ℓ+1+vℓH_ +1← H_ +1+v_ ; update the provisional tube 22: end for 23: Recompute the executed-trajectory certificate with outward-rounded arithmetic 24: if damage, row, and descent predicates all hold then 25: return pπp^π ⊳ R1: first-pass release 26: end if 27: Re-certify using tighter per-row factors 28: if all predicates hold then 29: return pπp^π ⊳ R2: re-certified release 30: end if 31: Run the incumbent tail from cached Hℓ0H_ _0; if no step was taken, use the incumbent output 32: return prp r ⊳ F: whole-call fallback 3 Analytical Guarantees and Statistical Assurance The analysis answers three distinct questions: what every served call is guaranteed to satisfy, how much gain is possible under that protection, and which probability statements the calibration and audit data support. Proofs and implementation-specific lemmas are collected in Appendix C. 3.1 Trajectory accounting and deterministic protection The reference-tail construction makes internal effects telescope even though the executed trajectory differs from the incumbent’s. For fixed labels, write fℓ(vℓ) f_ (v_ ) =Vℓ+1(H¯ℓ+1+vℓ)−Vℓ+1(H¯ℓ+1), =V_ +1( H_ +1+v_ )-V_ +1( H_ +1), (14) J(pπ,y)−J(pr,y) J(p^π;y)-J(p r;y) =∑ℓ=0T−1fℓ(vℓ). = _ =0^T-1f_ (v_ ). This identity follows from Vℓ=Vℓ+1∘FℓrV_ =V_ +1 F r_ and the common initial state. It compares each step through the same incumbent continuation, rather than using a gradient of the final adapted policy as an interchangeable target. Theorem 1 (Certified internal admission). Assume that the checker validates continuation enclosures and loss remainders for the executed trajectory, including numerical allowances when certifying a floating-point incumbent. For any proposal and episode, Algorithm 1 has the following properties. (i) The served prediction satisfies D∞(pir∥pis)≤HrowD_∞(p r_i\|p s_i)≤ H_ row for every row and ∑iwiD∞(pir∥pis)≤H+ _iw_iD_∞(p r_i\|p s_i)≤ H^+; hence down≤H+d own≤ H^+ for every label vector. (i) On a call released with the adapted output, down=−T+T−Td own=-D_T+P_T-S_T, where T≥0D_T≥ 0 is certified robust descent, T≥0P_T≥ 0 is the realized slope shortfall, and T≥0S_T≥ 0 contains remainder, safety-factor, and regularization slack. On fallback, down=0d own=0. (i) If every accepted-depth slope lies in its uncertainty set and the certified remainder model applies, then T=0P_T=0 and down≤0d own≤ 0. For a prespecified member with sequential calibration as in Lemma 6, this event has marginal probability at least 1−δcov1- _ cov over calibration and an exchangeable test episode. A data-selected member requires fresh post-selection calibration or a simultaneous guarantee across the selectable members before the same probability statement can be asserted for the selected procedure. Each valid charge bounds fℓf_ uniformly over labels. Summing in (14) therefore proves the call budget without evaluating the original incumbent endpoint on a call released with the adapted output. The tube also implies ‖HT,i−HT,ir‖≤rT,i\|H_T,i-H r_T,i\|≤ r_T,i. For the affine head, D∞(pir∥piπ)≤oscc(Z(HT)ic−Z(HTr)ic)≤ΓΔrT,i≤Hrow,D_∞(p r_i\|p_i^π)≤ _c (Z(H_T)_ic-Z(H_T r)_ic )≤ _ r_T,i≤ H_ row, (15) which proves the floor. This is a deterministic damage guarantee, not a promise of improved accuracy or of nonincreasing cross-entropy. A positive damage budget permits some loss increase. At the tolerance point H+≤ζH^+≤ζ, however, the event down>ζd own>ζ is impossible by construction. 3.2 Conditional gain and an analytical floor projection Let O contain the label-free deployment information and define the conditional label law piB=Pr(yi∣)p B_i= (y_i ). Write =−[down∣]G=-E[d own ], ric=picB/picrr_ic=p B_ic/p r_ic, and Ri=maxcricR_i= _cr_ic. Incumbent probabilities are strictly positive; expectations condition on the relevant frozen model and deployment information. Proposition 1 (Gain, price, and floor geometry). (i) =∑iwi[KL(piB∥pir)−KL(piB∥pis)]G= _iw_i[KL(p B_i\|p r_i)-KL(p B_i\|p s_i)]. If pr=pBp r=p B, no O-measurable rule has positive conditional gain. (i) With TVmax=maxiTV(piB,pir)TV_ = _iTV(p B_i,p r_i), ≤2TVmaxmax(S+,S−)G≤ 2TV_ (S^+,S^-), with the factor 2 sharp. (i) ≤maxi(Ri−1)S+G≤ _i(R_i-1)S^+, and the row-wise rate Ri−1R_i-1 is attainable to first order. (iv) The floor set is (4) and implies the corresponding class ceiling. For h>0h>0, the minimizer of KL(q∥p)KL(q\|p) over p∈ℱh(pir)p _h(p r_i) is pc′=maxe−hpicr,qc/λ,∑cmaxe−hpicr,qc/λ=1.p _c= \e^-hp r_ic,q_c/λ\, _c \e^-hp r_ic,q_c/λ\=1. (16) When qc>0q_c>0 for every class, the minimizer of KL(p∥q)KL(p\|q) is the same. At h=0h=0, the feasible set is the singleton pir\p r_i\. The projection is an analytical active-set solution, not a new network. For floor-active classes A, the normalizer is λ=∑c∉Aqc/(1−e−h∑c∈Apicr)λ= _c∉ Aq_c/(1-e^-h _c∈ Ap r_ic); sorting probability-to-floor ratios or solving the scalar normalization equation identifies the consistent active set. Strict positivity of q is needed for a finite reverse-KL projection because the floor forces positive mass on every class. Part (i) identifies the source of useful label-free adaptation: information in O that corrects conditional incumbent error. Parts (i)–(i) explain the value of one-sided pricing. A symmetric certificate charges large improvements as well as damage, while RTT only limits the latter. For a binary incumbent that assigns probability 0.990.99 where the conditional probability is 0.70.7, Ri−1=29R_i-1=29; for probabilities 0.60.6 and 0.80.8, it is approximately 0.330.33. The relevant quantity is relative underestimation of a plausible class, not an unconditional claim that every shifted input is overconfident. 3.3 The exact frontier and architecture-constrained efficiency Define the best row gain under budget h by Gi(h)=KL(piB∥pir)−minp∈ℱh(pir)KL(piB∥p).G_i(h)=KL(p B_i\|p r_i)- _p _h(p r_i)KL(p B_i\|p). (17) Let UoutU_ out denote the optimum over all outputs satisfying the row and call budgets. Let UreachU_ reach be the optimum over interventions reachable through RTT’s candidate hulls with exact endpoint damage, UcertU_ cert the optimum when certified charges are enforced, and URTTU_ RTT the gain of the executed policy. These quantities use the same conditional label law and budgets; population versions average over deployment information. Theorem 2 (Frontier, efficiency, and nested opportunities). (i) GiG_i is concave and nondecreasing, with Gi(0)=0G_i(0)=0, Gi′(0+)=Ri−1G_i (0^+)=R_i-1, and saturation once h≥D∞(pir∥piB)h≥ D_∞(p r_i\|p B_i). The saturation threshold is interpreted in the extended real sense; it can be infinite when piBp B_i has a zero component. The output-space frontier is Uout=max∑i0≤hi≤Hrow,∑iwihi≤H+wiGi(hi).U_ out= _0≤ h_i≤ H_ row,\ _iw_ih_i≤ H^+ _iw_iG_i(h_i). (18) An optimum is obtained by floor-projecting piBp B_i at water-filled budgets: positive-weight, unsaturated interior rows have equal marginal gain Gi′(hi)=λG_i (h_i)=λ; at a nondifferentiable point, the equivalent condition uses a supergradient. (i) At depth ℓ , let δz(v)=Jℓvδ z(v)=J_ v be the first-order terminal-logit change and pℓ,ip_ ,i the reference-tail prediction. Define gℓ(v) g_ (v) =∑iwi(piB−pℓ,i)⊤δzi(v), = _iw_i(p B_i-p_ ,i) δ z_i(v), (19) cℓ(v) c_ (v) =∑iwi[pℓ,i⊤δzi(v)−mincδzic(v)]. = _iw_i[p_ ,i δ z_i(v)- _cδ z_ic(v)]. Then, over directions with positive price, ηℓ=supv∈ℓ,cℓ(v)>0[gℓ(v)]+/cℓ(v)≤maxi(Rℓ,i−1) _ = _v _ ,\ c_ (v)>0[g_ (v)]_+/c_ (v)≤ _i(R_ ,i-1), where Rℓ,i=maxcpicB/pℓ,icR_ ,i= _cp B_ic/p_ ,ic. The piecewise-linear denominator admits an epigraph formulation and a linear-fractional reduction on the polyhedral candidate set. (i) The exact optima satisfy Uout≥Ureach≥Ucert≥URTTU_ out≥ U_ reach≥ U_ cert≥ U_ RTT. The floor geometry and marginal equalization are illustrated in Figure 2(a–b); panel (c) reports their experimental counterpart. The first result supplies a common standard for comparing internal and output-space methods. Its initial slope follows from moving probability mass toward a class maximizing picB/picrp B_ic/p r_ic. The water-filling condition then allocates budget until marginal gains equalize or a row saturates. The second result measures how much of this ideal direction the incumbent’s continuation and proposal hull can realize. It motivates placing trust where useful directions are available and their certified prices are small. The third result separates architectural restriction, certificate conservatism, and policy suboptimality at the level of exact feasible-set optima. A numerical solver need not attain these optima, so computed diagnostics must not be presented as a proved equality or an exact global gap decomposition. A complementary local statement makes the learning terms explicit. At a fixed depth and fixed convex branch, condition on information ℓO_ that includes the feasible geometry and a positive-definite physical-coordinate majorizer Ξ¯ℓ _ . Let mℓ=[aℓ∣ℓ]m_ =E[a_ _ ], let AℓcertA_ cert be the corresponding quadratic opportunity with the conditional slope given all of O, and let Iℓ≥0I_ ≥ 0 be the information gap. With uncertainty penalty χℓ _ evaluated at the conditional-mean minimizer and certified objective suboptimality Υℓ≥0 _ ≥ 0, the branchwise comparison is [gainℓ∣ℓ]≥ [gain_ _ ]\ ≥ [Aℓcert∣ℓ]−Iℓ−χℓ [A_ cert _ ]-I_ - _ (20) −12(‖mℓ−a^ℓ‖Ξ¯ℓ−1+2Υℓ)2. - 12 (\|m_ - a_ \|_ _ ^-1+ 2 _ )^2. Appendix C derives this inequality under its stated conditioning and convexity assumptions. It does not identify ∑ℓAℓcert _ A_ cert with the global UcertU_ cert, and a comparison spanning the nonconvex union of window branches needs separate branch-selection accounting. On real data, the conditional posterior is estimated by cross-fitting, so reported frontier shares are plug-in diagnostics rather than certified fractions of the unknown Bayes frontier. 3.4 When internal intervention helps, and how certificates compose Proposition 2 (Separation under explicit information restrictions). (a) Every RTT output can be represented by some floor-feasible output rule. There is no unrestricted superiority over all such rules. (b) An inert row rule has the form ϕ(pir,piu,hi)φ(p r_i,p u_i,h_i) with ϕ(p,p,h)=pφ(p,p,h)=p. Mixing, switching, and floor projection of the raw update are inert. When two raw internal effects cancel so that piu=pirp u_i=p r_i, these rules cannot change that row. There exist feasible instances where admitting only one internal effect instead gains 0.089 nats. (c) A corrector restricted to incumbent terminal states and proposal rows within k hops cannot respond differently to two instances that are identical in those inputs but differ only in unseen evidence. An RTT intervention can transmit such evidence through the incumbent tail when the transport supports the path and T−ℓ−1≥distiT- -1 _i. Zero conditional gain for the restricted corrector additionally requires that the incumbent is already Bayes-optimal given that corrector’s information. These are information-restricted separations, not claims that a wider corrector or a different information set can never match RTT. The cancellation example in Figure 6 is exact; the empirical near-cancellation group in Section 4 is defined by a numerical tolerance and is interpreted accordingly. The hop condition counts transitions after vℓv_ is injected into Hℓ+1H_ +1, which avoids crediting the intervention with a nonexistent extra propagation step. RTT and output correction are also complementary. For any intermediate prediction p′p , D∞(pir∥pi′)≤D∞(pir∥pi′)+D∞(pi′∥pi′)D_∞(p r_i\|p_i )≤ D_∞(p r_i\|p_i )+D_∞(p_i \|p_i ). Therefore, after an adapted output passes certification, a corrector can use the certified row allowance Hrow−ΓΔrT,iH_ row- _ r_T,i and remaining call allowance H+−∑ℓchargeℓH^+- _ charge_ relative to that output. After whole-call fallback, the served output is prp r and its spent budgets are zero; a subsequent corrector must use allowances computed from that served state, not from the rejected trajectory. The original deterministic floor and call budget are preserved (Remark 1). Statistical performance and coverage claims for the composed policy must nevertheless be established for that policy, not inherited automatically from RTT alone. 3.5 Sequential calibration and deployment-level assurance Slope calibration proceeds from early to late depths. At depth ℓ , fresh episodes are executed with all upstream radii fixed, and the joint physical-coordinate Mahalanobis error sℓ=∥Σ^x,ℓ−1/2(ax,ℓ−a^x,ℓ)∥s_ =\| _x, ^-1/2(a_x, - a_x, )\| is recorded. The covariance used for inversion must be positive definite on the nonzero physical span. A rank-zero step has score zero; an infinite radius permits only directions with zero uncertainty norm, including the zero step. The radius is the ⌈(1−δℓ)(nr+1)⌉ (1- _ )(n_r+1) -th order statistic, interpreted as +∞+∞ if that index exceeds nrn_r. On sℓ≤κℓs_ ≤ _ , Cauchy–Schwarz yields the robust linear bound in (12). A union bound over ∑ℓδℓ=δcov _ _ = _ cov gives the fixed-member trajectory statement. This guarantee is marginal over the calibration sample and an exchangeable test episode, not conditional coverage for every realized calibration set. Policy selection is a separate operation. The reported protocol compares several calibrated members before freezing one for a fresh audit. The deterministic certificate remains valid after selection. The nominal pre-audit coverage bound for the selected member, however, requires a simultaneous construction over selectable members or fresh calibration after selection. We therefore distinguish the fixed-member calibration theorem from the independent final-audit guarantees rather than using one as a substitute for the other. For a policy frozen before N independent episodes, the regression indicator is Bernoulli and a one-sided Clopper–Pearson bound is u=Beta−1(1−δ,Nζ+1,N−Nζ),u=Beta^-1(1-δ;N_ζ+1,N-N_ζ), (21) with u=1u=1 when Nζ=N_ζ=N. Theorem 3 combines this with an intersection–union release test, fixed-sequence selection, and a betting lower confidence bound on mean gain. The betting construction needs only the deterministic upper bound down≤H+d own≤ H^+ and is anytime-valid under its sampling assumptions. Simultaneous component bounds support explicitly specified reweightings, while Theorem 4 uses a reserved finite population and uniform label inspection to bound node-level negative flips. These statements concern different units and should not be interchanged. Finally, a KL-robustness curve is conditional on the new deployment law belonging to the stated divergence ball. Even the exact divergence of label-free score distributions can only lower-bound the full episode-law divergence; its empirical estimate cannot establish membership in that ball. Accordingly, the temporal transfer cohort is audited directly. The full sampling, selection, multiplicity, and event-count protocol is given in Appendix D. 4 Experimental Results The experiments evaluate whether RTT’s certified internal decisions provide useful gain beyond the strongest matched output-space alternative, and whether the gain occurs in the regimes identified by the analysis. We organize the evidence around the primary comparison, mechanism-level diagnostics, deployment cost, and transfer across proposals and tasks. The tables and figures distinguish exact certificates, audited probabilities, and posterior-based oracle estimates. The main audit and the two additional conference-method comparisons in Section 4.6 are reported separately because their evaluation histories differ. 4.1 Protocol, baselines, and evaluation units The arxiv incumbent achieves 75.9% accuracy on the official test split. Its temperature is fitted using held-out 2018 labels and then frozen. Training uses labels through 2017; the 2019 cohort is divided into development and final-audit halves. The final audit contains 2,048 calls from an equal-weight mixture of clean, degree-shift, real-cache, feature-noise, and edge-dropout populations, with a separate 4,096-call audit for each component (Hu et al., 2020; Gui et al., 2022; Fey et al., 2021). Severe stress, which rewrites 30% of rows at depth T/2T/2, is audited separately and excluded from the headline mixture. A reserved 2020 cohort supplies the temporal-transfer evaluation. The registered configuration has Hrow=1H_ row=1 nat, p⋆=2%p =2\%, δ=0.05δ=0.05, K=8K=8, b=4b=4, and 4,096 scored nodes per call. The selected member uses H+=25ζ=0.05H^+=25ζ=0.05 and nominal fixed-member calibration allocation δcov=0.1 _ cov=0.1. The primary comparison and eight Holm-corrected secondaries are specified before the final audit. Confidence intervals are episode-level and paired when methods share episodes; the node-population bootstrap is reported separately rather than folded into the betting guarantee (Appendix D). The strongest one-pass corrector runs the incumbent once and uses its terminal states, predictions, and proposal candidate rows. It receives the same training labels, head capacity, and number of gradient steps as RTT, and projects its predicted distribution onto the same floor using allocated row budgets. Its two-hop field is selected on development calls among two, four, and eight hops. Thus it shares G1–G3 with RTT and is the relevant low-cost baseline, not an unprotected raw update. Additional comparisons include exact-geometry output rules requiring two rollouts, a matched trust rule (TR) using the same candidate hull and checker, training-time anti-regression methods, and direct test-time adaptation. Table 12 provides the complete comparison set. 4.2 Primary comparison and the probability-floor frontier Table 2 reports a mean gain of 6.5 [6.3, 6.7] in units of 10−310^-3 nats for RTT, with betting lower bound 6.2, call-level regression-rate upper bound 0.95%, and negative-flip-rate upper bound 0.51% on the uninspected reserved-node population. The strongest corrector obtains 5.6 at a call-level bound of 1.07%. The primary paired difference is +0.9 [+0.8, +1.1], while the corrector is cheaper: 1.25× versus 1.42× incumbent latency. The raw update obtains 3.9 but has a regression-rate upper bound of 8.81%, illustrating why mean gain alone is insufficient. The reported secondary comparisons survive Holm correction (Table 12). Table 2: Primary arxiv comparison on 2,048 final-audit mixture episodes; gain and its intervals are in 10−310^-3 nats. Δ is RTT minus the row method; † marks the primary comparison. NζN_ζ is the regression count, u the one-sided call-level Clopper–Pearson bound, unodeu_ 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. Policy −[down]-E[d own] [95% CI] Δ to RTT NζN_ζ u unodeu_ node LB Lat. FLOPs RTT, registered (H+=H^+=25ζ25ζ, Hrow=1H_ 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, εi≤εmax,i _i≤ _ ,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 Floor projection of the raw update (2 rollouts) 5.2 [5.0, 5.5] +1.3 [+1.1, +1.4] 15 1.13% 0.61% 5.0 2.18 2.18 Matched TR (same hull and certificate) 5.8 [5.6, 6.0] +0.7 [+0.5, +0.8] 18 1.30% 0.78% 5.5 1.41 1.35 Learned update itself (t≡1t≡1), trimmed 3.9 [3.6, 4.3] +2.6 [+2.3, +2.9] 159 8.81%× 2.93% – 2.18 2.18 RTT, tolerance point (H+=ζH^+=ζ) 2.0 [2.0, 2.1] +4.5 [+4.3, +4.7] 0 0 (det.) 0.22% 1.9 1.42 1.36 Oracle frontier UoutU_ out (cross-fitted posterior; labels) 10.6 – – – – – – – Figure 2 connects the geometry to this comparison. Its first two panels illustrate the exact row-floor projection and water-filling solution, while the third reports the budget sweep. RTT attains 61% of the estimated output-space frontier on the mixture. This share depends on the cross-fitted posterior used to estimate the label law; it is not a guarantee of recovering that fraction of the unknown Bayes-optimal gain. Adaptive mixing and raw-output floor projection obtain 5.1 and 5.2, respectively, and both require two rollouts. Matched TR obtains 5.8, leaving a +0.7 gain increment for RTT’s reference-tail optimization at the same hull and certificate. Figure 2: Floor geometry and its empirical frontier. (a) The row floor at h=0.45h=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−h1-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. 4.3 Where the gain comes from and what each mechanism contributes The row-group analysis in Figure 3(d) tests the separation mechanisms rather than only the aggregate score. Near-cancellation rows make up 7% of the audit mixture: the raw and incumbent outputs differ by less than 10−310^-3 in ℓ1 _1 distance despite internal candidate movement. RTT contributes 0.9 to mixture gain on these rows, while the strongest corrector contributes at most 0.1; inert rules have negligible reported gain. The empirical tolerance is not the exact equality assumed by Proposition 2(b). On the 22% of rows whose tangent influence is predominantly beyond two hops, RTT contributes 2.2 against the corrector’s 1.1. On the remaining rows, the corrector leads, 4.4 versus 3.4. Four- and eight-hop correctors obtain 5.3 and 5.0 overall. These results support a regime-dependent internal advantage rather than universal superiority. Applying the corrector to RTT’s unused certified budget increases the mean to 6.7. 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. With the known planted label law, the calibrated incumbent admits no conditional gain, as Proposition 1(i) predicts. At miscalibration γ=0.3γ=0.3, RTT reaches 42% of the output-space frontier. The reported numerical ordering suggests that architectural restriction is the largest source of shortfall, followed by the learned decision rule; it does not establish an exact additive decomposition of globally optimized gaps. On arxiv, estimated shares range from 50% on clean calls to 63% under the real-cache shift. Efficiency concentrates at late depths, and the median certified-to-exact price ratio reaches 4.6 at earlier contract depths. This identifies certificate conservatism as a constraint on useful early intervention. The one-at-a-time mechanism swaps are collected in Table 13. One-sided rather than symmetric pricing changes the reported gain from 3.92 to 6.50 at the same 0.05-nat budget; interval rather than global factors changes it from 4.12 to 6.50. Replacing spend-based caps by certified-efficiency placement adds approximately +0.3, while the row floor costs approximately 3% of gain. Sequential rather than independent per-depth radii costs approximately 5% and supplies the fixed-member trajectory guarantee, subject to the selection distinction in Section 3.5. The smaller effects of two-branch optimization, support-function features, and full-loss slope targets are also reported. These swaps are conditional comparisons around one configuration, not additive contributions to a unique total gain. 4.4 Call size, reliability, and computational cost Figure 4 presents the deployment trade-off. The probability floor is row-specific and independent of call size, but the distribution of average call damage is not. On the development half, the registered member’s regression-rate bound increases from 1.01% at 4,096 nodes to 7.36% at 64 nodes. Reselecting a member for 64-node calls restores 1.98% with gain 4.6. At H+=ζH^+=ζ, the call-level regression event is ruled out deterministically and RTT still gains 2.0. The separate node-level audit remains necessary because absence of tolerance exceedance is not absence of negative classification flips. 001122224466p⋆p u per call (%)−[down]-E[d own] (10−310^-3 nats)(a) Gain vs. bound111.51.522224466tworolloutslatency / one incumbent pass(b) Gain vs. latency642561k4k0022446688p⋆p registeredre-selectedquery nodes nqn_ qu per call (%)(c) Call size14 1412 1212∞556677gainHrowH_ row (nats)−[down]-E[d own] (10−310^-3 nats)(d) Per-node budget000.20.20.40.40.60.6fallbackfallback (%)RTTRTT ++ correctorcorrector, 2-hop ++ rowscorrector, 2-hopcorrector, per rowadaptive mixingfloor projectionmatched TRRTT, H+=ζH^+=ζ 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. The final-audit release ledger contains 2,035 first-pass releases, six releases after tighter certification, and seven whole-call fallbacks out of 2,048 calls. Thus 0.63% fail the first pass and 0.34% ultimately fall back (Table 9). The cost comparison includes proposal computation, heads, short reference tails, solver, provisional bounds, checker, and fallback under one accounting convention. For the native in-network proposal, RTT costs 1.42× incumbent latency and 1.36× its FLOPs, versus 2.18× for two sequential rollouts. Two rollouts on two devices cost 1.18× latency but use twice the hardware. For full-network proposals RTT can be slower than two sequential rollouts: with the retrained incumbent, the reported values are 2.24× and 2.00×. Appendix G provides the full accounting and numerical-checker diagnostics; no universal speed advantage is claimed. 4.5 Proposal breadth, other tasks, and transfer Across the eight previously evaluated proposals, RTT exceeds the matched one-pass corrector by 0.50.5–0.90.9 in units of 10−310^-3 nats (Table 3). The set covers GPR-GNN, Co-GNN, AMP, GTrans, Matcha, retraining, and a LoRA-16 update, in addition to the native proposal. TSA and STEM extend this comparison set under the separate history-aware protocol of Section 4.6; they are not pooled into the eight-proposal main audit. The appropriate comparison includes the proposal’s own cost once; it is not legitimate to omit a full adaptation network when comparing RTT with an output rule. Table 3: Proposal breadth on arxiv. Gain is in 10−310^-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 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 Retrained incumbent (v2, ≤ 2017) 2.8 5.00%× 4.7 4.7 5.3 0.95% +0.6 [+0.4, +0.8] 2.24 2.00 LoRA-16 weight delta 2.7 5.48%× 4.5 4.5 5.1 1.01% +0.6 [+0.4, +0.8] 2.27 2.03 Training-time and test-time neighbors answer a different protection question. Weight interpolation and LoRA scaling selected by learn-then-test obtain 3.4 and 3.2 at one-network cost, while EATA and periodic reset obtain 2.6 and 2.2; the reported configurations fail the statistical release criterion and do not enforce G1–G3 (Table 14). In the separate batch-shift stream, raw GTrans has mean damage +38.0×10−3+38.0× 10^-3 nats per shifted call, whereas RTT-gated serving reduces it to +0.4×10−3+0.4× 10^-3 with 6.1% fallback. A positive residual damage is consistent with the stated budget and is not described as a no-regression result. Table 15 extends the evaluation to APPNP, GCNII, GRAND, and shallow GraphSAGE/GCN incumbents; GOOD-Arxiv degree and time shifts; Twitch, Facebook-100, and Elliptic shifts; ogbn-products; ImageNet-C; and Folktables (Gui et al., 2022; Wu et al., 2022; Rozemberczki et al., 2021; Traud et al., 2012; Weber et al., 2019; Hu et al., 2020; Hendrycks and Dietterich, 2019; Ding et al., 2021). On the graph configurations, RTT reaches 60%–73% of the estimated oracle frontier, with call-level bounds up to 1.30%. Its lead on shallow incumbents shrinks to about 0.2×10−30.2× 10^-3 nats, consistent with a shorter continuation offering less propagation advantage. On ogbg-molpcba, the custom reserved-scaffold protocol improves the deployed GIN-style incumbent from 27.7 to 28.6 AP; the separately audited official test result is 28.5 AP (Table 16; Xu et al., 2019). On ImageNet-C, adapting the last four ResNet-50 blocks with Tent proposals increases top-1 accuracy from 40.1% to 45.6% under the floor (Table 15; He et al., 2016; Wang et al., 2021). The reserved temporal cohort is evaluated directly rather than certified from a label-free shift estimate. Its call-level bound is 1.18%, with a betting lower bound of 1.7×10−31.7× 10^-3 nats on mean gain (Table 10). Figure 5 separates pointwise, simultaneous, node-level, and conditional-divergence results. Across three incumbents and eight training seeds each, the reported selection procedure passes 22 of 24 times for RTT and 24 of 24 for the corrector; the failed selections revert to the incumbent (Figure 7). Separate drift streams evaluate monitoring and recalibration (Figure 8), while Figure 10 compares certificate tightness and verifier cost. Together, these experiments delimit where RTT’s extra computation yields useful certified gain and where simpler correction is competitive. 4.6 Two recent conference methods: matched TSA/STEM evaluation Comparison question. We evaluate two additional proposals: TSA (Hsu et al., 2026) and STEM (Luo et al., 2026). The comparison tests whether RTT retains useful structural and history-dependent graph adaptation while enforcing the same incumbent-relative protection. All values in this comparison refer to the common evaluation law specified here, rather than to leaderboard results from the cited papers. Complementary mechanisms. TSA addresses structural distribution shift through uncertainty-aware neighborhood weighting, signal-to-noise-based self–neighbor balancing, and boundary refinement. It tests whether useful structure-aware changes survive the floor constraint. STEM generates domain-specific adapter parameters for a frozen base GNN using a recurrent state-space controller and regularizes parameter evolution. It tests whether useful history-dependent updates can be admitted without treating the controller’s stability objective as an incumbent-relative, per-call certificate. These are distinct mechanisms for producing proposals; the same RTT certificate evaluates both. Native fidelity and matched admission. Each method’s documented native configuration uses a development-selected variant and retains its full output path. The matched comparison uses the same incumbent, label set, calls, and proposal features for the full native output, its floor projection, the exported-state proposal without RTT, matched TR, the strongest matched one-pass corrector, and RTT using that proposal. Head capacity, fitting labels, optimization effort, row-budget allocation, and access to proposal/history information are matched between the learned admission alternatives. The native adaptation procedure receives no deployment labels. The controlled extension uses the registered arxiv population and budgets; a compatible GCN/GraphSAGE replication checks that a deep-diffusion port has not created an artificial advantage. The replication specification records ports, omitted native components, and export discrepancies. Native task accuracy/AUC/F1 and negative flips are distinct evaluation quantities and are not inferred from cross-entropy gain. Table 4: TSA/STEM mean gains in 10−310^-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. Δ is RTT minus the matched corrector. Native gain can exceed certified gain: protection is not claimed to be free. Proposal Native full Native + floor Matched TR Matched corrector RTT derived Δ 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 Independent histories versus continual streams. To preserve a call-level audit for the stateful proposal, each independent episode starts from the same frozen source initialization, processes a predeclared unlabeled context prefix, and scores one subsequent call. Prefixes are independently drawn under a fixed generator and supplied to every comparator; prefix length and all reset rules are frozen before audit. The same setting is used for TSA. Its numerical outcomes are therefore not pooled with the earlier no-prefix audit. A separate native continual evaluation carries STEM’s state across domains and measures retention and adaptation on fixed domain orders. Its correlated calls are not treated as independent binomial trials: resampling and comparisons use independent streams as clusters, with no borrowed call-level Clopper–Pearson claim. RTT’s deterministic certificate remains call-wise valid in either mode when its checker is sound. Calibration and inference. Adapters and heads use the existing fitting split, variants are selected on development data, and each frozen extended policy uses selection-valid calibration. The two paired gain comparisons against the matched corrector form a separate two-test Holm family, specified before the extension audit. The main audit’s eight-secondary-comparison claim is unchanged and does not include these additions. Reused cohorts constitute reanalysis; a new population-generalization claim requires an untouched cohort. Fresh episode draws can audit a fixed conditional generator, but do not erase earlier access to its underlying graph or labels. For this comparison, Table 5 reports event counts and the call-level bound u; we do not report confidence intervals, adjusted p-values, betting bounds, or node-level bounds. Table 5: Event counts and pre-specified criteria for the two RTT-derived policies. Each audit contains N=2,048N=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. Quantity TSA-derived + RTT STEM-derived + RTT Observed regressions NζN_ζ 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 ≤0.60%≤ 0.60\% ≤0.60%≤ 0.60\% Adjusted paired gain criterion lower CI endpoint >0>0 lower CI endpoint >0>0 Additional RTT machinery cost criterion ≤0.35tinc≤ 0.35\,t_ inc ≤0.35tinc≤ 0.35\,t_ inc Gain retention and interpretation. Table 4 reports native-gain retention of 90.0% for TSA and 88.1% for STEM, while the unprotected native methods remain ahead in mean gain. These ratios compare identical populations with positive native gain; they are descriptive and do not establish statistical significance. The paired mean differences against the matched corrector are +1.0 and +1.0 (in 10−310^-3 nats) for TSA and STEM. Because we do not report their confidence intervals or adjusted p-values, we make no significance claim. Component- and seed-level comparisons, including cases where the corrector wins, and the near-cancellation and long-range diagnostics remain separate analyses: neither mechanism is presumed to explain a new gain. A native method’s low regression rate is a favorable baseline, not a condition that it must fail. The comparison concerns the gain–protection–cost trade-off, not improvement at every operating point. The cost criterion in Table 5 concerns RTT’s added machinery only. Total latency includes native adaptation, context processing, state export, short reference-tail evaluations, solver, checker, and expected fallback; cold-start and amortized continual costs are separate quantities. We do not report timing, FLOP, or memory measurements for this comparison. Appendix A.1 records the native implementations and replication protocol. These history-aware comparisons remain separate from the abstract’s eight-proposal main audit and the corresponding frontier plots. 5 Conclusion Reference-Tail Trust turns an internal learned update into a budgeted deployment decision. By pricing each displacement through the frozen incumbent’s continuation and validating the executed trajectory before release, RTT attaches a per-row probability floor and a call-level loss-increase bound to the prediction actually served. Whole-call fallback preserves this contract when certification fails. The analytical floor projection and water-filling frontier provide a common basis for evaluating internal admission and output correction, while the separation results identify the information restrictions under which an incumbent tail can make internal intervention useful. The reported experiments show gains over a matched one-pass corrector across the studied proposal and incumbent families, with benefits concentrated in near-cancellation and long-range-evidence regimes. The TSA and STEM comparisons extend the evaluation to structural and continual adaptation under a separate history-aware protocol; their descriptive gains and event ledgers are reported separately from the main audit. The existing experiments also expose the costs: earlier interventions can be limited by conservative continuation bounds, full-network proposals can make RTT slower than two rollouts, and a short incumbent tail reduces its propagation advantage. Deterministic protection survives arbitrary proposal quality when the checker is sound; statistical regression and calibration statements remain tied to their sampling and selection assumptions. These distinctions position RTT as a controlled mechanism for using learned updates, not as an unconditional replacement for output correction or a guarantee of improvement under unaudited distribution shift. Reproducibility and Code Availability The code is released in the GitHub repository at https://github.com/VKHS/RTT. The implementation description, release logic, primitive contracts, and training targets are given in Appendices A–B; proofs are in Appendix C; the audit protocol and numerical diagnostics are in Appendices D–G. Table 7 records parameters and measured checkpoint properties, Table 17 reports label and compute accounting, and Table 20 defines the notation. The experimental protocol fixes the pool manifest, selection order, node reservation, and seeds before the final audit; the associated per-episode records and integer event ledger are the basis for reproducing the statistical results. Reproduction of the TSA/STEM extension requires pinned upstream revisions, the declared state-export adapters, independent calibration and audit manifests, and event, timing, and prediction logs. Tables 4–5 give the gains and event counts for this comparison; its intervals, bounds, and resource measurements are not reported. Use of AI Tools We used a large language model to improve the English of this manuscript, including grammar, wording, and readability. The authors reviewed all AI-assisted text and take full responsibility for the content of this paper. References Angelopoulos et al. (2025) Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, Michael I. Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. The Annals of Applied Statistics, 19(2):1641–1662, 2025. [source] Balachandran (2026) Vishnu Bindu Balachandran. Pay only for disagreement: Certified no-regression verdicts for model updates with matching label-complexity bounds. arXiv:2609.17560, 2026. [source] Banerjee et al. (2005) Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with Bregman divergences. Journal of Machine Learning Research, 6:1705–1749, 2005. [source] Bao et al. (2025) Wenxuan Bao, Zhichen Zeng, Zhining Liu, Hanghang Tong, and Jingrui He. Matcha: Mitigating graph structure shifts with test-time adaptation. In ICLR, 2025. [source] Cauchois et al. (2024) Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, 119(548):3033–3044, 2024. [source] Chamberlain et al. (2021) Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: Graph neural diffusion. In ICML, volume 139 of Proceedings of Machine Learning Research, p. 1407–1418, 2021. [source] Chen et al. (2020) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, volume 119 of Proceedings of Machine Learning Research, p. 1725–1735, 2020. [source] Chien et al. (2021) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. In ICLR, 2021. [source] Clopper and Pearson (1934) C. J. Clopper and E. S. Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, 1934. [source] Dasoulas et al. (2021) George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self-attention layers with application to graph neural networks. In ICML, 2021. [source] Ding et al. (2021) Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In NeurIPS, 2021. [source] Errica et al. (2025) Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, and Francesco Alesiani. Adaptive message passing: A general framework to mitigate oversmoothing, oversquashing, and underreaching. In ICML, volume 267 of Proceedings of Machine Learning Research, p. 15490–15515, 2025. [source] Fey et al. (2021) Matthias Fey, Jan E. Lenssen, Frank Weichert, and Jure Leskovec. GNNAutoScale: Scalable and expressive graph neural networks via historical embeddings. In ICML, volume 139 of Proceedings of Machine Learning Research, p. 3294–3304, 2021. [source] Finkelshtein et al. (2024) Ben Finkelshtein, Xingyue Huang, Michael M. Bronstein, and İsmail İlkan Ceylan. Cooperative graph neural networks. In ICML, volume 235 of Proceedings of Machine Learning Research, p. 13633–13659, 2024. [source] Gasteiger et al. (2019) Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. In ICLR, 2019. [source] Gui et al. (2022) Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. GOOD: A graph out-of-distribution benchmark. In NeurIPS Datasets and Benchmarks, 2022. [source] Guo et al. (2017) Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In ICML, volume 70 of Proceedings of Machine Learning Research, p. 1321–1330, 2017. [source] Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017. [source] He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016. [source] Hedström et al. (2025) Anna Hedström, Salim I. Amoukou, Tom Bewley, Saumitra Mishra, and Manuela Veloso. To steer or not to steer? Mechanistic error reduction with abstention for language models. In ICML, volume 267 of Proceedings of Machine Learning Research, p. 22924–22945, 2025. [source] Hendrycks and Dietterich (2019) Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In ICLR, 2019. [source] Hsu et al. (2022) Hans Hao-Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? In NeurIPS, 2022. [source] Hsu et al. (2026) Hans Hao-Hsun Hsu, Shikun Liu, Han Zhao, and Pan Li. Structural alignment improves graph test-time adaptation. In AISTATS, volume 300 of Proceedings of Machine Learning Research, p. 829–837, 2026. [source] Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020. [source] Hu et al. (2022) Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In ICLR, 2022. [source] Jin et al. (2023) Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. In ICLR, 2023. [source] Kakade and Langford (2002) Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In ICML, 2002. [source] Kim et al. (2021) Hyunjik Kim, George Papamakarios, and Andriy Mnih. The Lipschitz constant of self-attention. In ICML, 2021. [source] Kipf and Welling (2017) Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017. [source] Luo et al. (2026) Junyu Luo, Zixuan Ouyang, Xiao Luo, Hourun Li, Zhiping Xiao, Yifan Wang, and Ming Zhang. Space-based parameter evolving with lightweight optimization for graph adaptation to evolving shifts. In Proceedings of the ACM Web Conference 2026 (W ’26), p. 1529–1539. ACM, 2026. [conference publication] Niu et al. (2022) Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yaofo Chen, Shijian Zheng, Peilin Zhao, and Mingkui Tan. Efficient test-time model adaptation without forgetting. In ICML, 2022. [source] Niu et al. (2023) Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Zhiquan Wen, Yaofo Chen, Peilin Zhao, and Mingkui Tan. Towards stable test-time adaptation in dynamic wild world. In ICLR, 2023. [source] Ovadia et al. (2019) Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua V. Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model’s uncertainty? Evaluating predictive uncertainty under dataset shift. In NeurIPS, 2019. [source] Paulsen et al. (2020a) Brandon Paulsen, Jingbo Wang, and Chao Wang. ReluDiff: Differential verification of deep neural networks. In ICSE, 2020. [source] Paulsen et al. (2020b) Brandon Paulsen, Jingbo Wang, Jiawei Wang, and Chao Wang. NeuroDiff: Scalable differential verification of neural networks using fine-grained approximation. In ASE, 2020. [source] Press et al. (2023) Ori Press, Steffen Schneider, Matthias Kümmerer, and Matthias Bethge. RDumb: A simple approach that questions our progress in continual test-time adaptation. In NeurIPS, 2023. [source] Prinster et al. (2026) Drew Prinster, Clara Fannjiang, Ji Won Park, Kyunghyun Cho, Anqi Liu, Suchi Saria, and Samuel Stanton. Conformal policy control. arXiv:2603.02196, 2026. [source] Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2):cnab014, 2021. [source] Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv:1707.06347, 2017. [source] Schuster et al. (2022) Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q. Tran, Yi Tay, and Donald Metzler. Confident adaptive language modeling. In NeurIPS, 2022. [source] Srivastava et al. (2020) Megha Srivastava, Besmira Nushi, Ece Kamar, Shital Shah, and Eric Horvitz. An empirical analysis of backward compatibility in machine learning systems. In KDD, 2020. [source] Teuber et al. (2025) Samuel Teuber, Philipp Kern, Marvin Janzen, and Bernhard Beckert. Revisiting differential verification: Equivalence verification with confidence. In TACAS, p. 257–278, 2025. [source] Traud et al. (2012) Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. Social structure of Facebook networks. Physica A, 391(16):4165–4180, 2012. [source] Träuble et al. (2021) Frederik Träuble, Julius von Kügelgen, Matthäus Kleindessner, Francesco Locatello, Bernhard Schölkopf, and Peter Gehler. Backward-compatible prediction updates: A probabilistic approach. In NeurIPS, 2021. [source] Wang et al. (2021) Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. In ICLR, 2021. [source] Waudby-Smith and Ramdas (2024) Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society, Series B, 86(1):1–27, 2024. [source] Weber et al. (2019) Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I. Weidele, Claudio Bellei, Tom Robinson, and Charles E. Leiserson. Anti-money laundering in Bitcoin: Experimenting with graph convolutional networks for financial forensics. arXiv:1908.02591, 2019. [source] Wortsman et al. (2022) Mitchell Wortsman, Gabriel Ilharco, Jong Wook Kim, Mike Li, Simon Kornblith, Rebecca Roelofs, Raphael Gontijo-Lopes, Hannaneh Hajishirzi, Ali Farhadi, Hongseok Namkoong, and Ludwig Schmidt. Robust fine-tuning of zero-shot models. In CVPR, 2022. [source] Wu et al. (2022) Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In ICLR, 2022. [source] Xu et al. (2020) Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic perturbation analysis for scalable certified robustness and beyond. In NeurIPS, 2020. [source] Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019. [source] Yan et al. (2021) Sijie Yan, Yuanjun Xiong, Kaustav Kundu, Shuo Yang, Siqi Deng, Meng Wang, Wei Xia, and Stefano Soatto. Positive-congruent training: Towards regression-free model updates. In CVPR, 2021. [source] Zhang et al. (2018) Huan Zhang, Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In NeurIPS, 2018. [source] Zhang et al. (2026) Shengwei Zhang, Tao Wu, and Fei Qian. Certifying model upgrades with slice-wise non-regression and incumbent fallback. arXiv:2609.13714, 2026. [source] Zhou et al. (2025) Xingjian Zhou, Keyi Shen, Andy Xu, Hongji Xu, Cho-Jui Hsieh, Huan Zhang, and Zhouxing Shi. SoundnessBench: A soundness benchmark for neural network verifiers. Transactions on Machine Learning Research, 2025. [source] Appendix A Model, families, budgets and the release procedure Reference families. Every incumbent is written as primitives whose tube factors and envelopes are known (Table 6). The deep tanh diffusion of Section 2 uses interval factors and second-order window envelopes. APPNP propagates linearly after an MLP, so its tail is linear, the first-order contract is exact up to the triangle inequality across rows, the logits are affine in t at every depth and the exact envelope (11) applies everywhere. GCNII applies ReLU(X~W~)ReLU( X W) with W~=(1−β)I+βW W=(1-β)I+β W to X~=(1−α)PX+αH0 X=(1-α)PX+α H_0; it enters through Lemma 2, which encloses the Clarke Jacobian of every downstream row on the tube, so kinks crossed anywhere in the tail are covered, and its global factor is (1−α)‖W~‖2(1-α)\| W\|_2, not one. GRAND is a smooth attention-free diffusion discretized on the committed horizon. Shallow GraphSAGE and GCN incumbents have T≤3T≤ 3: their whole tail is the window and the last depth, so every charge is an envelope. For ResNet-50 the last four bottleneck blocks are the intervened depths, with P=IP=I denoting the absence of graph transport and ReLU handled by Lemma 2; the convolution, residual, and pooling operations still belong to the continuation being enclosed; attention references are covered at first order on bounded tubes (Kim et al., 2021; Dasoulas et al., 2021). Proposals, adapters and heads. Our proposal returns two candidates per node at every open depth: Hℓc,1H c,1_ from a bank prior, a learned convex combination of 16 bank rows conditioned on the current state, and Hℓc,2H c,2_ from a signed one-hop attention branch. A published module runs alongside the incumbent on the same call, and its depth-ℓ state H~ℓ H_ is mapped into the incumbent’s state space by a frozen linear adapter Ωℓ _ fitted by least squares on ≤ 2017 episodes, Hℓc,1=H~ℓΩℓH c,1_ = H_ _ , with its one-hop message as the second candidate. GTrans transforms the call’s features and edges at test time and its candidates are the incumbent’s states on the transformed call; the retrained incumbent and the LoRA-16 delta share the architecture, so their states map exactly. The heads are the node-weight head (ϑi∈[0,1] _i∈[0,1], which scales a row’s candidates), the field head g^ℓ g_ , the covariance head Σ and the posterior head p^B p B, which estimates pBp B for the field’s inputs; all read the candidates only through the support-function features below. Matched TR (a learned trust rule) replaces the field, the robust model and the solver by a learned trust scale in [0,1][0,1], computed from the same features, that scales the proposal’s step inside the same candidate hull, budgets and certificate. 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. Family transport tube factor window last depth global factor tanh diffusion (T=32T=32) tanh(PHW) (PHW) interval (Lemma 1), rank-8 second-order envelope exact C+C^+ (1−α)(1−τ+τ‖W‖2)(1-α)(1-τ+τ\|W\|_2) APPNP αH0+(1−α)PHα H_0+(1-α)PH exact (linear) exact C+C^+ exact C+C^+ 1−α1-α GCNII ReLU(X~W~)ReLU( X W) interval Clarke (Lemma 2) first-order enclosure exact C+C^+ (1−α)‖W~‖2(1-α)\| W\|_2 GRAND smooth diffusion interval second-order envelope exact C+C^+ per-step bound GraphSAGE-2, GCN-3 2–3 layers interval covers the whole tail exact C+C^+ ‖W‖2\|W\|_2 per layer ResNet-50, last 4 blocks x+f(x)x+f(x), ReLU, P=IP=I interval Clarke first-order enclosure exact C+C^+ block Lipschitz residual tanh MLP P=IP=I interval second-order envelope exact C+C^+ as tanh attention (any) softmax attention first order on bounded tubes first order exact C+C^+ tube-local constant A.1 Replication specification for the TSA/STEM comparison This subsection specifies the TSA/STEM replication protocol. The native TSA implementation is available at https://github.com/Graph-COM/TSA; it exposes variants with different boundary-refinement components. The native baseline retains the complete prediction path of the development-selected variant, with the variant and upstream revision recorded. The native STEM implementation is available at https://github.com/miaomiao1220/stem; its node-level pipeline carries a source-initialized controller state across target domains. Controller initialization, graph order, parameter-update/reset rules, and the source-training budget are part of the replication record. The conference references, rather than the repositories or preprints, are the bibliographic citations (Hsu et al., 2026; Luo et al., 2026). For each method, the replication record contains the full native prediction, the exported-state prediction before and after trimming, and every accepted RTT displacement. A pre-audit manifest records node correspondence, depth mapping, adapter dimensions and fitting split, input normalization, self-loops, class order, temperature, and all classifier/output changes. Source graphs used by native initialization must stay within the fitting/development allocation; target labels are inaccessible to adaptation. Unit tests compare the reproduced native output with the upstream implementation and verify that disabling all admissions returns the exact incumbent. A port to the 32-step diffusion is labeled a port and accompanied by a compatible-backbone check; a failed fidelity check is reported rather than hidden by retuning on the audit. The fixed-history audit freezes the complete proposal state before each scored call. Admission does not feed back into the external proposal controller in the matched comparison: all admission rules see the same candidate record. The native continual experiment is separate and preserves the method’s documented evolution. Admission-dependent feedback defines another policy requiring its own calibration and audit, not an automatic extension of these statistics. For both modes, proposal runtime is accounted for separately from RTT overhead, and the accounting includes all label uses and all selected/failed seeds. The values in Table 4 are reporting outcomes, not stopping rules or tuning objectives. Interval factors. At depth j the pre-activation of row i is xj,i=(PHj)ix_j,i=(PH_j)_i with units zj,iu=xj,iW:,uz_j,iu=x_j,iW_:,u, and a state in the tube moves it by at most ϱj,i=(Prj)i _j,i=(Pr_j)_i. Lemma 1 (Interval factors). Let s¯j,iu=tanh′(max0,|zj,iu|−ϱj,i∥W:,u∥2) s_j,iu= ( \0,|z_j,iu|- _j,i\|W_:,u\|_2\). Every state in the tube satisfies ‖Dφ‖2≤‖Wdiag(s¯j,i)‖2≤‖W‖2\|D \|_2≤\|W ( s_j,i)\|_2≤\|W\|_2. Write W⊤W=UΣU⊤W W=U U , with top-k factors Uk,ΣkU_k, _k and (k+1)(k+1)-st eigenvalue σk+12 _k+1^2. Then ‖Wdiag(s¯)‖22≤λmax(Σk1/2Uk⊤diag(s¯2)UkΣk1/2)+σk+12maxus¯u2.\|W ( s)\|_2^2≤ _ \! ( _k^1/2U_k ( s^2)U_k _k^1/2 )+ _k+1^2 _u s_u^2. Thus Lj,iL_j,i can be the minimum of ‖W‖2\|W\|_2 and the square root of this bound. A valid curvature factor is μj,i=∥W∥22maxusup|tanh′(y)|:||y|−|zj,iu||≤ϱj,i∥W:,u∥2. _j,i=\|W\|_2^2 _u \| (y)|: ||y|-|z_j,iu| |≤ _j,i\|W_:,u\|_2 \. Lemma 2 (Piecewise-linear transports). Let φ(x)=ReLU(xW~) (x)=ReLU(x W) and let the tube move the pre-activation of unit u of row i by at most ϱj,i∥W~:,u∥2 _j,i\| W_:,u\|_2. Let s¯j,iu=0 s_j,iu=0 if zj,iu+ϱj,i∥W~:,u∥2<0z_j,iu+ _j,i\| W_:,u\|_2<0 and s¯j,iu=1 s_j,iu=1 otherwise. Then every Clarke generalized Jacobian of φ at every state of the tube satisfies ‖∂φ‖2≤‖W~diag(s¯j,i)‖2≤‖W~‖2\|∂ \|_2≤\| W ( s_j,i)\|_2≤\| W\|_2, the first-order contract and the tube hold with Lj,i=‖W~diag(s¯j,i)‖2L_j,i=\| W ( s_j,i)\|_2 for every row, downstream rows included, and the terminal-logit change lies in an interval enclosure of conv¯Jv:J∈ℓ conv\Jv:J _ \, where ℓJ_ covers generalized Jacobians of the entire downstream tail on the validated segments. This first-order enclosure replaces a smooth second-order window bound when activation boundaries can be crossed. A primitive row is affine where all its units have fixed activation status. An exact affine-tail envelope is justified only when every contributing downstream activation also has fixed status; otherwise the complete tail is charged through its generalized-Jacobian enclosure. On GCNII 93% of rows are affine on their tube per call. Per-row budgets during execution. The provisional tube r~ r is (9) with cap-seeded provisional factors, updated after each step at the cost of one sparse product. The growth proxy Π^ℓ _ is the 95th percentile, over rows and development calls, of the ratio of the terminal to the depth-ℓ provisional radius, registered at freeze time. At depth ℓ the row allowance is ρℓ,i=(Hrow/ΓΔ−Π^ℓr~ℓ,i)+/(Π^ℓ+1nleft) _ ,i=(H_ row/ _ - _ r_ ,i)_+/( _ +1n_ left) and every candidate row of block k is scaled by min1,ρℓ,i/(c¯ℓk‖dℓ,i(k,m)‖) \1, _ ,i/( c_ k\|d^(k,m)_ ,i\|)\. Because the scaling acts on the candidates before the solve, the feasible set is again the scaled hull of the scaled candidates. The proxy affects only the gain and the fallback rate; the certificate checks the exact tube. Coordinates. With the thin factorization Dℓ=QℓΘℓD_ =Q_ _ , block by block (QℓQ_ orthonormal, Θℓ _ a rank-revealing coordinate map per block), v=Qℓxv=Q_ x and x=Θℓtx= _ t. Slopes pull back as a^x=Qℓ⊤g^ℓ a_x=Q_ g_ and a^t=Θℓ⊤a^x=Dℓ⊤g^ℓ a_t= _ a_x=D_ g_ ; covariances as Σ^x=diagk(Qℓk⊤Σ^gQℓk) _x= diag_k(Q_ k _gQ_ k), block-diagonal by construction (cross-block covariances are not modeled; joint errors are calibrated with this same positive-definite physical-coordinate covariance), and Σ^t=Θℓ⊤Σ^xΘℓ _t= _ _x _ ; the curvature is ‖v‖Ξ2=∑iΞℓ+1,i‖vi‖2\|v\|^2_ = _i _ +1,i\|v_i\|^2 and ‖v‖2\|v\|^2 is physical. The feasible set x=Θℓt:t≥0,∑mtkm≤c¯ℓk\x= _ t:t≥ 0, _mt_km≤ c_ k\ is a polytope in x. The contract-depth screen acts on a^t a_t: a block whose candidate slopes are all non-negative is set to zero (Lemma 5); componentwise non-negativity of a^x a_x would not suffice. The physical problem is written in x. An implementation may retain auxiliary t variables to impose the hull constraints, but its objective depends on them only through v=Dℓtv=D_ t. Minimum-norm coefficients are recovered after the physical optimum has been selected. Support-function features. Every candidate-dependent input of the heads is pooled as sij=hℓ,i(uj)=max0,maxm⟨uj,dℓ,i(⋅,m)⟩s_ij=h_K_ ,i(u_j)= \0, _m u_j,d^(·,m)_ ,i \ over 2×162× 16 fixed probes ±uj± u_j drawn at freeze time. This is the support function of the row hull. Mean pooling is not hull-invariant (mean0,1=12mean\0,1\= 12, mean0,1,1=23mean\0,1,1\= 23), and neither is the maximum of a non-convex feature; the maximum of a linear function over a polytope is attained at a vertex, so duplicated, permuted and interior candidates cannot change s. Lemma 3 (Invariance). If the heads read the candidates only through support-function features, and the robust model, the charges and the budgets depend on the step only through v and on the candidates only through the post-trim hull, then the executed displacement is unchanged by candidate operations that preserve the post-trim hull, including duplication, permutation, and insertion of interior points. Rescaling an existing vertex is covered only if the hull is unchanged (for example, when a shorter duplicate is added while the original remains). If the two convex window branches have equal minima, a fixed tie-break in physical state coordinates is required. The trim is nonlinear, so a candidate interior to the raw hull need not be interior to the post-trim hull; the statement concerns the latter. Lemma 4 (Two-branch window solve). t:minσ(t),env+(t)≤ℬ=σ≤ℬ∪env+≤ℬ\t: \σ(t), env^+(t)\ \=\σ \∪\ env^+ \ is a union of two convex sets. The minimum of Φ over the union is the smaller of the two convex minima, and the recorded charge minσ,env+ \σ, env^+\ of the chosen step is at most ℬB. Optimizing under env+ env^+ alone is valid but may be suboptimal; charging min while optimizing under env+ env^+ is valid. Lemma 5 (Regularized block step). For a fixed convex charge branch and multiplier μ≥0μ≥ 0, minΦℓ+μchargeℓ _ +μ\, charge_ over its feasible polytope has a unique optimal displacement, continuous in μ, and the spend is non-increasing in μ; for a positive budget, either the constraint is slack at μ=0μ=0 or a multiplier can be bracketed and found by bisection under the stated feasibility assumptions. At zero remaining budget, Algorithm 1 takes the zero step rather than requiring a finite multiplier. At contract depths a block with a^t,k≥0 a_t,k≥ 0 componentwise has tk=0t_k=0 at the optimum. The release procedure. Algorithm 1 is the policy that is audited; the fallback is part of it. 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. Symbol meaning value enters effect of moving it T, α, τ horizon, skip weight, step size of the incumbent 32, 0.1, 0.9 (9) fixed by the incumbent H+H^+ per-call one-sided budget (selected member) 25ζ=0.0525ζ=0.05 G2, charges oracle frontier concave; executed curve empirical (Fig. 2c) HrowH_ row per-node floor 1 nat G1, row trim gain and fallback (Fig. 4d) ζ regression tolerance (registered choice) 0.002 nats G4 rate statements only δ, p⋆p statistical level, rate target 0.05, 2% Thm. 3 bound widths δcov _ cov nominal fixed-member trajectory allocation 0.1 Thm. 1(i) radii K, b role blocks, window depths 8, 4 §2 diminishing returns beyond 8 open depths depths that may receive a step 16–31 §2 admissibility gate over them Δ¯ , ω row trim, safety factor 0.8, 0.9 (12) Fig. 7 ρD _D, ρx _x curvature inflation, physical regularizer 10−310^-3, 10−610^-6 (12) invariance needs ρx>0 _x>0 k, Πmax _ spectral-split rank, admissibility cap on the contract growth 8, 20 Lemma 1 usable depths Π^ℓ _ growth proxy of the row-budget trim 95th percentile row allowance fallback rate nrn_r, probes calibration episodes per depth, probes 512, 2×162× 16 Lemma 6 radii; head inputs N, nqn_ q audit episodes, call size 2,048 (4,096 per component), 4,096 G4–G5 bound widths; rates by call size Properties of the checkpoint and the record ‖W‖2\|W\|_2, L¯ L incumbent transport norm, global factor 1.60, 1.386 Table 6 with L¯ L alone only depths ≥ 23 are usable ΓΔ _ pairwise head diameter 5.21 terminal contracts scales every charge L¯int L int geometric-mean interval factor, open depths 1.107 (≤ 1.206) admissibility gate if it fails: trust moves to late depths R^i−1 R_i-1 rate Ri−1R_i-1 (RiR_i: under-estimation factor; median, accepted rows) 1.3–4.6 Thm. 2 larger: more gain per nat ηℓ/maxi(Rℓ,i−1) _ / _i(R_ ,i-1) normalized architecture-constrained efficiency 0.04–0.48 placement of caps where trust pays Appendix B Training, calibration and their cost Two phases. Phase one fits the incumbent’s temperature on held-out 2018 labels and records its usable depths; the network itself is not touched. Phase two trains, on ≤ 2017 episodes and through the executed gate, the proposal and the heads of Appendix A, and fits the adapters of external proposals. The one-pass correctors are trained on the same episodes with the same labels, head capacity and number of gradient steps. Full-loss targets need one counterfactual tail per open depth. The slope that Theorem 1(i) needs at depth ℓ is aℓ=Dℓ⊤∇Vℓ+1(H¯ℓ+1)a_ =D_ ∇ V_ +1( H_ +1) with H¯ℓ+1=Fℓr(Hℓ) H_ +1=F r_ (H_ ), the gradient of the incumbent’s continuation from the executed state. Continuations from different depths start from different states, so a training episode needs one forward and one reverse pass through the tail from each open depth: ∑ℓopen(T−ℓ−1) _ \ open(T- -1) tail steps in each direction, about 3.8 incumbent passes for the registered caps. The passes are batched across depths, with activations checkpointed every four steps (Table 8). A single reverse pass along the executed trajectory would give the gradient of the adapted policy’s loss, which is a different quantity. Probe-loss slopes are cheaper but biased, and serve only as an ablation (Table 13). Sequential calibration. Radii are calibrated depth by depth. For depth ℓ , nr=512n_r=512 fresh 2018 episodes are executed with the policy and the radii of depths <ℓ< frozen. The score is the joint Mahalanobis norm sℓ=∥Σ^x,ℓ−1/2(ax,ℓ−a^x,ℓ)∥s_ =\| _x, ^-1/2(a_x, - a_x, )\| of the slope error in physical coordinates at the executed state, with the block-diagonal Σ^x,ℓ _x, of Appendix A, and κℓ _ is its ⌈(1−δℓ)(nr+1)⌉ (1- _ )(n_r+1) -th order statistic, with +∞+∞ used when the index exceeds nrn_r. The covariance is assumed positive definite on the physical span; its numerical regularization is part of the frozen calibration rule. On the event sℓ≤κℓs_ ≤ _ , Cauchy–Schwarz gives ax,ℓ⊤x≤a^x,ℓ⊤x+κℓ‖Σ^x,ℓ1/2x‖a_x, x≤ a_x, x+ _ \| _x, ^1/2x\| for every x, which is the robust term of (12). The allocation is δℓ=δcovπℓ _ = _ cov\, _ , with πℓ _ the registered trust share of depth ℓ . Lemma 6 (Sequential calibration). For a member fixed independently of its calibration data, the depth-ℓ score of a fresh episode does not depend on κℓ _ or on any later radius, and it is exchangeable with the nrn_r calibration scores of depth ℓ , which were produced by the same frozen policy up to depth ℓ . Hence Pr(sℓ>κℓ)≤δℓ (s_ > _ )≤ _ , and the event that every open depth is covered has probability at least 1−∑ℓδℓ=1−δcov1- _ _ =1- _ cov over calibration and test episode. Feeding the radius back into the trajectory that generates its own calibration scores would break exchangeability; the sequential construction freezes everything upstream of the score. The probability is marginal over calibration and test episodes. Selecting a member using calibrated performance is not covered by this fixed-member statement: the selected procedure needs fresh post-selection calibration or a simultaneous guarantee over its selectable members. The independent final audit in Appendix D remains a distinct source of statistical assurance. Table 8: Training cost of one episode (operation counts; A100 80GB). 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 C Proofs Proof of Proposition 1. (i) For cross-entropy and any O-measurable logits, [ℓ(zi,yi)∣]=H(piB)+KL(piB∥softmax(zi))E[ (z_i,y_i) ]=H(p B_i)+KL(p B_i\| (z_i)) (Banerjee et al., 2005). Taking the difference of the two predictions gives the identity. If pr=pBp r=p B, the first divergence vanishes and the second is non-negative. (i) Fix a row, write q=piBq=p B_i, p=pirp=p r_i and hc=hich_c=h_ic. Since ∑cpchc=KL(p∥pis)≥0 _cp_ch_c=KL(p\|p s_i)≥ 0, the gain of the row is −∑cqchc≤∑c(pc−qc)hc≤TV(q,p)oscchc- _cq_ch_c≤ _c(p_c-q_c)h_c (q,p) _ch_c. Summing with the weights, and using ∑iwioscchic=S++S−≤2max(S+,S−) _iw_i _ch_ic=S^++S^-≤ 2 (S^+,S^-), gives the bound. For sharpness take p=(12,12)p=( 12, 12), q=(12+ϵ,12−ϵ)q=( 12+ε, 12-ε) and Δz=(t,−t) z=(t,-t): then /(ϵmax(S+,S−))→2G/(ε (S^+,S^-))→ 2 as t↓0t 0. (i) Write rc=qc/pcr_c=q_c/p_c and R=maxcrcR= _cr_c. Then ∑cqchc=R∑cpchc−∑cpc(R−rc)hc≥−(R−1)maxchc, _cq_ch_c=R _cp_ch_c- _cp_c(R-r_c)h_c≥-(R-1) _ch_c, so the gain of the row is at most (R−1)maxchc(R-1) _ch_c. For attainment let c⋆∈argmaxcrcc ∈ _cr_c and pε=(1−ε)p+εec⋆p =(1- )p+ e_c . Then hc=−log(1−ε)=ε+O(ε2)h_c=- (1- )= +O( ^2) for c≠c⋆c≠ c and hc⋆=−ε(1/pc⋆−1)+O(ε2)h_c =- (1/p_c -1)+O( ^2), so S+=ε+O(ε2)S^+= +O( ^2) and −∑cqchc=−(1−qc⋆)ε+qc⋆ε(1/pc⋆−1)+O(ε2)=ε(R−1)+O(ε2).- _cq_ch_c=-(1-q_c ) +q_c (1/p_c -1)+O( ^2)= (R-1)+O( ^2). (iv) For h=0h=0, the floor set is the singleton pr\p r\. For h>0h>0, p∈ℱh(pr)p _h(p r) if and only if s=(p−e−hpr)/(1−e−h)s=(p-e^-hp r)/(1-e^-h) is non-negative and sums to one, that is s∈Δs∈ . For the ceiling, pc=1−∑c′≠cpc′≤1−e−h(1−pcr)p_c=1- _c ≠ cp_c ≤ 1-e^-h(1-p r_c). For the forward projection, and for the reverse projection when every qc>0q_c>0, minimize respectively −∑cqclogpc- _cq_c p_c or ∑cpclog(pc/qc) _cp_c (p_c/q_c) subject to pc≥ac=e−hpcrp_c≥ a_c=e^-hp r_c and ∑cpc=1 _cp_c=1. Stationarity gives pc=qc/(ν−βc)p_c=q_c/(ν- _c) in the first problem and pc=qceβc−1−νp_c=q_ce _c-1-ν in the second, with βc≥0 _c≥ 0 and βc(pc−ac)=0 _c(p_c-a_c)=0. In both, pc=maxac,qc/λp_c= \a_c,q_c/λ\ with λ fixed by normalization, which has a unique positive solution for h>0h>0. If some qc=0q_c=0, the forward projection still follows this formula, but the positive floor makes the reverse KL infinite. At h=0h=0 the output remains unique even though a multiplier representation need not be. ∎ Proposition 3 (Row contracts on a tube). Under the conditions of Section 2, |DVj(X)[Y]|≤∑iΛj,i‖Yi‖|DV_j(X)[Y]|≤ _i _j,i\|Y_i\| and |D2Vj(X)[Y,Y]|≤∑iΞj,i‖Yi‖2|D^2V_j(X)[Y,Y]|≤ _i _j,i\|Y_i\|^2 for every state X of the tube and every label vector, with Λ as in (9) and Ξj=(1−α)2[(1−τ)Ξj+1+τP⊤(Lj2⊙Ξj+1)]+(1−α)τP⊤(μj⊙Λj+1) _j=(1-α)^2[(1-τ) _j+1+τ P (L_j^2 _j+1)]+(1-α)τ P ( _j _j+1), ΞT,i=14ΓΔ2wi _T,i= 14 _ ^2w_i. Proof. Vj=Vj+1∘FjrV_j=V_j+1 F r_j with DF[X]i=(1−α)[(1−τ)Xi+τDφ((PH)i)(PX)i]DF[X]_i=(1-α)[(1-τ)X_i+τ D ((PH)_i)(PX)_i]. On the tube, ‖DF[X]i‖≤(1−α)[(1−τ)‖Xi‖+τLj,i∑kPik‖Xk‖]\|DF[X]_i\|≤(1-α)[(1-τ)\|X_i\|+τ L_j,i _kP_ik\|X_k\|]. Substituting and collecting coefficients gives the first line. The second follows from D2Vj[X,X]=D2Vj+1[DF[X],DF[X]]+DVj+1[D2F[X,X]]D^2V_j[X,X]=D^2V_j+1[DF[X],DF[X]]+DV_j+1[D^2F[X,X]] and Jensen. The terminal rows follow from |⟨p−ey,δz⟩|≤ΓΔ‖Xi‖| p-e_y,δ z |≤ _ \|X_i\| and Popoviciu’s inequality, uniformly in labels. ∎ Lemma 7 (Forward enclosure). With rj=0r_j=0 before the first accepted depth and the recursion of (9), the tube contains every incumbent continuation started on the segment of any executed step, including the incumbent’s own trajectory. Proof. Let X=H¯ℓ+1+svℓX= H_ +1+sv_ with H¯ℓ+1=Fℓr(Hℓ) H_ +1=F r_ (H_ ) and s∈[0,1]s∈[0,1], and let XjX_j be its incumbent continuation. Then ‖Xℓ+1,i−Hℓ+1,i‖=(1−s)‖vℓ,i‖\|X_ +1,i-H_ +1,i\|=(1-s)\|v_ ,i\|. By the mean-value theorem along the segment from HjH_j to XjX_j (Lebourg’s for Lipschitz maps), ‖Xj+1,i−Hj+1,i‖≤(1−α)[(1−τ)ej,i+τLj,i(Pej)i]+‖vj,i‖\|X_j+1,i-H_j+1,i\|≤(1-α)[(1-τ)e_j,i+τ L_j,i(Pe_j)_i]+\|v_j,i\| for ej=‖Xj−Hj‖e_j=\|X_j-H_j\|, provided the segment lies in the tube. This holds by induction. The toy instance of Figure 9(a) checks the statement for every continuation. ∎ Proofs of Lemmas 1–5. Lemma 1: tanh′ is even and decreasing in |y||y|, and ‖Wdiag(s)‖2\|W (s)\|_2 is non-decreasing in every entry of s≥0s≥ 0. The split is Weyl’s inequality applied to diag(s¯)W⊤Wdiag(s¯)=diag(s¯)(Ak+(W⊤W−Ak))diag(s¯) ( s)W W ( s)= ( s)(A_k+(W W-A_k)) ( s) with Ak=UkΣkUk⊤A_k=U_k _kU_k the rank-k part. Lemma 2: the Clarke Jacobian of ReLU(xW~)ReLU(x W) is W~diag(s) W (s) with su∈[0,1]s_u∈[0,1], and su=0s_u=0 wherever the unit is inactive on the whole tube; Lebourg’s mean-value theorem places every increment in the convex hull of these Jacobians along the segment. Lemma 4 is immediate. Lemma 5: strict convexity in v (from ρx>0 _x>0), the maximum theorem, and the exchange argument (μ2−μ1)(σ(t2)−σ(t1))≤0( _2- _1)(σ(t_2)-σ(t_1))≤ 0. For the screen, setting tk=0t_k=0 removes the non-negative term a^t,k⊤tk a_t,k t_k and does not increase the robust term (the covariance is block-diagonal), the quadratic terms, or the charge. The quadratic terms and contract charge add across blocks; the joint uncertainty norm is nonincreasing when any block is removed. Lemma 3: the listed operations leave the post-trim hull, and hence every support-function feature and the feasible polytope in v, unchanged. Each convex branch has a unique minimizing displacement. A representation-independent physical tie-break selects between equal branch optima. Coefficients enter only through minimum-norm recovery, so the selected displacement is invariant even when its candidate coefficients are not. ∎ Proof of Theorem 1. Let fℓ(t)=Vℓ+1(H¯ℓ+1+Dℓt)−Vℓ+1(H¯ℓ+1)f_ (t)=V_ +1( H_ +1+D_ t)-V_ +1( H_ +1), H¯ℓ+1=Fℓr(Hℓ) H_ +1=F r_ (H_ ), for a fixed label vector. Telescoping gives J(pπ,y)−J(pr,y)=∑ℓfℓ(tℓ)J(p^π;y)-J(p r;y)= _ f_ (t_ ) (Kakade and Langford, 2002). (i) At contract depths the mean-value theorem on the certified tube gives fℓ≤σℓf_ ≤ _ . In the window, fℓ≤envℓ+f_ ≤ env^+_ by the tangent basis and the second-order contract, and the minimum of two valid bounds is valid. At the last depth fT−1≤C+f_T-1≤ C^+ exactly. The damage predicate gives down≤∑ℓchargeℓ≤H+d own≤ _ charge_ ≤ H^+ for every label vector. Since S+S^+ is the worst case over label vectors, this is ∑iwiD∞(pir∥piπ)≤H+ _iw_iD_∞(p r_i\|p^π_i)≤ H^+. For the rows, the tube encloses the incumbent’s own trajectory, so ‖HT,i−HT,ir‖≤rT,i\|H_T,i-H r_T,i\|≤ r_T,i. With Δzi z_i the logit difference, D∞(pir∥piπ)=LSE(ziπ)−LSE(zir)−mincΔzic≤osc(Δzi)≤ΓΔrT,i≤HrowD_∞(p r_i\|p^π_i)= (z^π_i)- (z r_i)- _c z_ic≤ ( z_i)≤ _ r_T,i≤ H_ row by the row predicate. On fallback ps=prp s=p r. A sound directed-rounding implementation preserves the enclosures used by each release predicate, including signed intermediate expressions and the numerical allowances (Appendix G). (i) Work in physical coordinates vℓ=Qℓxℓv_ =Q_ x_ and use the full-loss slope ax,ℓa_x, . Write fℓ(vℓ)=ax,ℓ⊤xℓ+remℓ(vℓ).f_ (v_ )=a_x, x_ +rem_ (v_ ). Let bℓ(v)b_ (v) be the nonnegative remainder majorizer validated by the checker. At a smooth nonterminal depth, bℓ(v)=‖v‖Ξ2/2b_ (v)=\|v\|_ ^2/2; at the last depth, bT−1(v)=ϱT−1(v)b_T-1(v)= _T-1(v) is the exact KL remainder. For a nonsmooth tail, this notation refers to the separately validated remainder model, not an unsupported Hessian bound. Define Sℓrem=bℓ(vℓ)−remℓ(vℓ)≥0,χℓ(x)=κℓ‖Σ^x,ℓ1/2x‖,S_ ^rem=b_ (v_ )-rem_ (v_ )≥ 0, _ (x)= _ \| _x, ^1/2x\|, and eℓ=(ax,ℓ⊤xℓ−a^x,ℓ⊤xℓ−χℓ(xℓ))+e_ =(a_x, x_ - a_x, x_ - _ (x_ ))_+, e¯ℓ=(a^x,ℓ⊤xℓ+χℓ(xℓ)−ax,ℓ⊤xℓ)+ e_ =( a_x, x_ + _ (x_ )-a_x, x_ )_+. With ℛℓ(v)=(ρD‖v‖Ξ2+ρx‖v‖22)/2R_ (v)=( _D\|v\|_ ^2+ _x\|v\|_2^2)/2, the recomputed model is Φℓcert(x)=a^x,ℓ⊤x+χℓ(x)+bℓ(Qℓx)+ℛℓ(Qℓx)ω. _ cert(x)= a_x, x+ _ (x)+ b_ (Q_ x)+R_ (Q_ x)ω. Adding and subtracting this model gives the exact identity fℓ=Φℓcert(xℓ)+eℓ−e¯ℓ−(1ω−1)bℓ(vℓ)−ℛℓ(vℓ)ω−Sℓrem.f_ = _ cert(x_ )+e_ - e_ - ( 1ω-1 )b_ (v_ )- R_ (v_ )ω-S_ ^rem. Therefore T _T =−∑ℓΦℓcert(xℓ), =- _ _ cert(x_ ), T _T =∑ℓeℓ, = _ e_ , T _T =∑ℓ[e¯ℓ+Sℓrem+(1ω−1)bℓ(vℓ)+ℛℓ(vℓ)ω]. = _ [ e_ +S_ ^rem+ ( 1ω-1 )b_ (v_ )+ R_ (v_ )ω ]. The certified descent predicate makes T≥0D_T≥ 0, and each summand of TS_T is nonnegative. At the last depth, ST−1rem=0S_T-1^rem=0 because the remainder is exact. As an unregularized scalar illustration, take f(t)=−t/2+t2/2f(t)=-t/2+t^2/2, ω=0.9ω=0.9, and t=0.45t=0.45. Then Φ=−0.1125 =-0.1125, f=−0.12375f=-0.12375, and S=0.01125S=0.01125. With nonzero regularization the additional ℛ(t)/ωR(t)/ω must appear in both the model and the slack; it cannot be omitted from the accounting. (i) On the coverage event ℰℓ=∥Σ^x,ℓ−1/2(ax,ℓ−a^x,ℓ)∥≤κℓE_ =\\| _x, ^-1/2(a_x, - a_x, )\|≤ _ \, Cauchy–Schwarz gives ax,ℓ⊤x≤a^x,ℓ⊤x+κℓ‖Σ^x,ℓ1/2x‖a_x, x≤ a_x, x+ _ \| _x, ^1/2x\| for every x, so eℓ=0e_ =0. The descent predicate gives T≥0D_T≥ 0, hence down≤0d own≤ 0; on fallback down=0d own=0. Lemma 6 gives the fixed-member marginal probability. Extending it to the selected member requires the selection-valid calibration condition stated in the theorem. ∎ Proof of Theorem 2. (i) The set (h,p):pc≥e−hpcr∀c,p∈Δ\(h,p):p_c≥ e^-hp r_c\ ∀ c,\ p∈ \ is convex because −e−h-e^-h is concave. So minp∈ℱhKL(pB∥p) _p _hKL(p B\|p) is convex in h as a partial minimization, and G is concave. It is non-decreasing because the sets are nested, and G(0)=0G(0)=0. With the active set A of the projection and the normalizer ν, G′(h)=νe−h∑c∈Apcr−∑c∈ApcBG (h)=ν e^-h _c∈ Ap r_c- _c∈ Ap B_c. As h↓0h 0, A is every class except the maximizers of r, and ν→Rν→ R, so, writing M=argmaxcrcM= _cr_c, G′(0+)=R∑c∉Mpcr−∑c∉MpcB=R−1G (0^+)=R _c∉ Mp r_c- _c∉ Mp B_c=R-1. This also covers ties among maximizing classes. The saturation point is where pB∈ℱhp B _h. Any feasible served prediction has per-row costs hih_i that satisfy the constraints and gain at most ∑iwiGi(hi) _iw_iG_i(h_i), so UoutU_ out equals the allocation problem. That problem is a concave separable maximization under one linear constraint and boxes, and its KKT conditions are the water-filling conditions. (i) Per row, with u=δzi(v)u=δ z_i(v) and p=pℓ,ip=p_ ,i, (piB−p)⊤u=∑c(picB−pc)(uc−minc′uc′)≤(Rℓ,i−1)∑cpc(uc−minc′uc′)(p B_i-p) u= _c(p B_ic-p_c)(u_c- _c u_c )≤(R_ ,i-1) _cp_c(u_c- _c u_c ), because picB−pc≤(Rℓ,i−1)pcp B_ic-p_c≤(R_ ,i-1)p_c and the second factor is non-negative. Summing with the weights gives gℓ≤maxi(Rℓ,i−1)cℓg_ ≤ _i(R_ ,i-1)c_ . The Charnes–Cooper transformation turns the ratio into a linear program. The analysis script re-checks the bound on random instances. (i) The chain follows from nested feasible sets: a reachable intervention is an output-space competitor, certified charges dominate exact damage, and every released RTT intervention is certified. Fallback is the zero-gain feasible alternative. These statements concern exact optima, not guarantees of global convergence for the numerical solver. ∎ Local learning comparison, equation (20). Fix a depth and a convex feasible branch C containing zero. All optimization variables below are physical coordinates x, not possibly redundant candidate coefficients. Condition on ℓO_ , which must make C, the positive-definite majorizer M=Ξ¯ℓM= _ , the learned slope, and the uncertainty penalty measurable. Assume the true loss change satisfies f(x)≤a⊤x+12x⊤Mxf(x)≤ a x+ 12x Mx on C. The majorizer may include the safety-factor inflation and positive physical regularizer, so that M−1M^-1 is defined even when the candidate matrix is rank deficient. Set m=[a∣ℓ]m=E[a _ ], ϕ(x)=m⊤x+12x⊤Mxφ(x)=m x+ 12x Mx, and (ℓ)=−minx∈ϕ(x)A(O_ )=- _x φ(x). Let xmx_m minimize ϕφ and let x∗x^* minimize the certified robust objective Ψ(x)=a^⊤x+χ(x)+12x⊤Mx (x)= a x+χ(x)+ 12x Mx on that same branch. For the realized step x^∈ x , define Υℓ=Ψ(x^)−Ψ(x∗)≥0 _ = ( x)- (x^*)≥ 0, including solver error and any provisional-to-certified model mismatch. The latter quantity is well-defined because the final step is checked for certified feasibility. Strong convexity on the convex set gives Ψ(x∗)≤Ψ(xm)−12‖xm−x∗‖M2,‖x^−x∗‖M≤2Υℓ. (x^*)≤ (x_m)- 12\|x_m-x^*\|_M^2, \| x-x^*\|_M≤ 2 _ . Writing e=‖m−a^‖M−1e=\|m- a\|_M^-1 and s=‖x∗−xm‖Ms=\|x^*-x_m\|_M, conditional expectation and Cauchy–Schwarz yield [f(x^)∣ℓ]≤−(ℓ)+χ(xm)+Υℓ+e2Υℓ+es−12s2.E[f( x) _ ]≤-A(O_ )+χ(x_m)+ _ +e 2 _ +es- 12s^2. Maximizing the last two terms over s gives [f(x^)∣ℓ]≤−(ℓ)+χℓ+12(e+2Υℓ)2,χℓ=χ(xm).E[f( x) _ ]≤-A(O_ )+ _ + 12 (e+ 2 _ )^2, _ =χ(x_m). Assume ℓ⊆O_ . Let m¯=[a∣] m=E[a ] and Aℓcert=−minx∈(m¯⊤x+12x⊤Mx)A_ cert=- _x ( m x+ 12x Mx). The same feasible geometry is used under both information sets. Since the negative minimum is convex in its slope argument, conditional Jensen gives Iℓ=[Aℓcert∣ℓ]−(ℓ)≥0I_ =E[A_ cert _ ]-A(O_ )≥ 0. Negating the previous display proves (20). Summing such conditional comparisons requires consistent branch and information accounting. Minkowski bounds the summed estimation/execution penalties by 12(2E+2Υ)2 12( 2E+ 2 )^2, where E=∑ℓeℓ2/2E= _ e_ ^2/2 and Υ=∑ℓΥℓ = _ _ . No identity between the sum of local quadratic opportunities and the global optimum UcertU_ cert follows. In particular, strong convexity on either branch does not by itself give the distance inequality across their nonconvex union. ∎ Proof of Proposition 2. (a) is Proposition 1(iv). (b) Take a five-node path with self-loops, the row-normalized P, a scalar state equal to the class-1 logit margin, incumbent margin −1-1 everywhere, one diffusion step after the intervened depth, and scored node 2 with pB=0.5p B=0.5. The raw update adds +δ+δ at node 1 and −δ-δ at node 3 (δ=1.5δ=1.5). Its terminal effect at node 2 is (δ−δ)/3=0(δ-δ)/3=0, so p2u=p2rp u_2=p r_2 and every inert rule leaves node 2 unchanged. Node 3’s candidate has a positive slope for the scored loss and is screened out. Admitting node 1’s candidate alone moves node 2’s margin by δ/3δ/3 at one-sided cost 0.161 nats and gains 0.089 nats, which is also the oracle projection’s gain at that cost (Figure 6). (c) On a directed chain of L nodes the evidence is in the proposal’s candidate row of node 0 at intervention depth ℓ=T−L =T-L (injected into HT−L+1H_T-L+1). A corrector with receptive field k<L−1k<L-1 at node L−1L-1 sees the same inputs with and without the evidence, so its prediction cannot depend on that evidence. If the incumbent is Bayes-optimal conditional on these local inputs, Proposition 1(i) gives zero possible conditional gain for the restricted corrector. RTT’s step at node 0 is carried by the incumbent’s tail to node L−1L-1 and gains 0.120 nats at cost 0.380. ∎ Remark 1 (Certificates compose). D∞(p∥p′)≤D∞(p∥p′)+D∞(p′∥p′)D_∞(p\|p )≤ D_∞(p\|p )+D_∞(p \|p ) because log(pc/pc′)=log(pc/pc′)+log(pc′/pc′) (p_c/p _c)= (p_c/p _c)+ (p _c/p _c). A corrector applied to a certified adapted prediction with per-row budgets Hrow−ΓΔrT,iH_ row- _ r_T,i and per-call budget H+−∑ℓchargeℓH^+- _ charge_ therefore keeps G1–G3 relative to prp r. If RTT falls back, the starting prediction is prp r and the available budgets reset to HrowH_ row and H+H^+. Coverage and statistical performance must be checked separately for the composed policy. Theorem 3 (Assurance per call). (i) For a policy frozen before N i.i.d. episodes with NζN_ζ regressions, u=Beta−1(1−δ,Nζ+1,N−Nζ)u=Beta^-1(1-δ;N_ζ+1,N-N_ζ) bounds the regression rate with probability at least 1−δ1-δ; set u=1u=1 when Nζ=N_ζ=N. (i) Testing every event of (2), the auxiliary accuracy and flip events, the stress test and a minimum certified mean at level δ each, and releasing only if all pass, has false-release probability at most δ. Along a library ordered before the data, stopping at the first failure controls the family-wise error. (i) Assume [|d|]<∞E[|d|]<∞. Because dj≤H+d_j≤ H^+, predictable nonnegative cjc_j that do not depend on the candidate mean m define bets λj(m)=mincj,34/(H+−m) _j(m)= \c_j, 34/(H^+-m)\ give wealth t(m)=∏j≤t(1+λj(m)(m−dj))W_t(m)= _j≤ t(1+ _j(m)(m-d_j)), non-decreasing in m. UCBt=supm<H+:t(m)<1/δUCB_t= \m<H^+:W_t(m)<1/δ\ then satisfies Pr(∃t:[d]>UCBt)≤δ (∃ t:E[d]>UCB_t)≤δ, with the upper endpoint capped at H+H^+; if [d]=H+E[d]=H^+, then d=H+d=H^+ almost surely and this endpoint is valid. No lower bound on d is used. (iv) The k statements hold simultaneously at δ/kδ/k each, and any reweighting ϖ of the components has rate at most maxϖ⊤p:0≤p≤usim,ϖ0⊤p≤umixsim \ p:0≤ p≤ u sim, _0 p≤ u sim_ mix\. (v) Conditional robustness: for a prespecified grid λ1,…,λJ>0 _1,…, _J>0 and simultaneous upper confidence bounds UjU_j on P[eλj(d−H+)]E_P[e _j(d-H^+)], every law Q with KL(Q∥P)≤ρKL(Q\|P)≤ρ has Q[d]≤H++minj(ρ+logUj)/λjE_Q[d]≤ H^++ _j(ρ+ U_j)/ _j with probability at least 1−δ1-δ. This is a statement about the hypothesized ball; a score-based divergence estimate does not provide the upper bound on KL(Q∥P)KL(Q\|P) needed to place Q in it. Lemma 8 (Monotone one-sided wealth). If dj≤H+d_j≤ H^+ and λj(m)=mincj,34/(H+−m) _j(m)= \c_j, 34/(H^+-m)\ with cj≥0c_j≥ 0 not depending on m, then each factor is at least 14 14 and non-decreasing in m<H+m<H^+. Proofs. (i) is binomial tail inversion (Clopper and Pearson, 1934). (i) is the intersection–union principle and fixed-sequence testing (Angelopoulos et al., 2025). (i) At m=[d]m=E[d] the wealth is a non-negative martingale, so Ville’s inequality applies (Waudby-Smith and Ramdas, 2024). Lemma 8 makes the rejected set an interval, since on each branch the derivative of the factor is non-negative. (iv) is the union bound and a linear program. (v) is the Donsker–Varadhan inequality with Xλ=eλ(d−H+)∈(0,1]X_λ=e^λ(d-H^+)∈(0,1] bounded (Cauchois et al., 2024). ∎ Theorem 4 (Per node). (i) A node can flip from correct to wrong only if its predicted class changes, so the per-call negative-flip rate is at most the disagreement with the incumbent, which the offline audit records. (i) Let N contain n_N reserved nodes that are not used as scored or labeled targets by any other stage. They may occur as unlabeled graph context. Fix their predictions by calls of the registered size before drawing the inspection subset, and let a uniformly random subset of ncaln_ cal nodes be labeled afterwards, with k flips. With F^=maxF′:PrHyp(n,F′,ncal)(X≤k)≥δ F= \F : _Hyp(n_N,F ,n_ cal)(X≤ k)≥δ\, the flip rate on the uninspected nodes is at most (F^−k)/(n−ncal)( F-k)/(n_N-n_ cal) with probability at least 1−δ1-δ. Proof. (i) is immediate. (i) After the calls, the flip vector is fixed and the inspected set is a uniform subset, so k is hypergeometric; F F inverts its tail. ∎ Appendix D Statistical protocol Four uses of labels. Fitting labels (≤ 2017) train every network. 2018 labels fit the temperature, the radii and the selection. The 2019 development half serves every design decision, the ζ anchor, the sweeps of Figure 4(c,d) and Figure 7. The reported protocol assigns the final-half audit pool, the reserved node set, and the 2020 cohort to their respective evaluation stages (Table 17). Any later reuse must be recorded as reanalysis, not as evaluation on an untouched population. Every audited statement concerns one frozen policy on the registered generator, conditional on the graph and the label masks: the i.i.d. premise requires fresh, independent query and corruption draws conditional on that population. Stateful proposals or caches additionally require independently initialized histories for this audit; a continuous shared-state stream is a different sampling unit. Intervals are episode-level and paired where methods share episodes. No design effect is mixed with the betting bounds, which rest on the same i.i.d. premise. A node-cluster bootstrap for the population-level estimand widens intervals by a factor 1.24 and is reported separately. The release ledger. Outcomes are mutually exclusive and counted as integers (Table 9). First-pass failures are attributed to the first failing predicate in the order damage, row, descent. Re-certified releases and fallbacks partition the failures, and the analysis script asserts 0≤NF≤Nfail≤N0≤ N_ F≤ N_ fail≤ N before any rate is printed. The release rule also requires a certified mean of at least 3.0×10−33.0× 10^-3 nats (1.5×10−31.5× 10^-3 at the tolerance point), registered before the audit. Table 9: Final audit of the registered member: (a) release ledger (integer counts of 2,048 calls); (b) the ten statements, pointwise at δ and simultaneous at δ/10δ/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) 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 (b) Statement events mean bound at δ at δ/10δ/10 mixture event down>ζd own>ζ 12/2,048 – 0.95% 1.18% call-accuracy drop >>0.1 point 21/2,048 – 1.47% 1.75% negative flips on >>1% of the call 9/2,048 – 0.77% 0.97% component: clean 8/4,096 1.4 0.35% 0.45% component: degree 25/4,096 5.2 0.85% 1.00% component: cache 35/4,096 10.7 1.13% 1.30% component: noise 29/4,096 7.7 0.96% 1.12% component: dropout 27/4,096 7.3 0.91% 1.06% component: severe stress (separate) 41/4,096 23.9 1.30% 1.48% certified mean (betting LB) – 6.5 6.2 ≥ 3.0 6.1 release decision all ten statements pass; released Selection. Library members are ordered before any data from least to most aggressive, all with trajectory-valid radii except a per-depth member placed last. Each member reached is tested on four pools of 1,024 fresh 2018 episodes (mixture, clean, cache, noise). The path stops at the first failure, and among the passing members the one with the largest certified mean is registered: trajectory radii at δcov=0.1 _ cov=0.1, H+=0.05H^+=0.05, with certified mean 6.2. The path tests five members and stops at the fifth; the per-depth member, placed sixth, gains 6.86 but is not reached, so it is reported as a variant, not selected. The independent final audit validates the frozen served policy. The recorded selection procedure alone does not establish a post-selection δcov _ cov guarantee; see Section 3.5. Betting bounds and their implementations. The registered bets are tuned to N. Their values at every t form an anytime-valid sequence whose last value is the fixed-N bound. The reported horizon-free schedule is wider at this N; that empirical comparison is not a universal ordering of confidence-sequence constructions. The Gaussian first-order width 2σ2log(1/δ)/N 2σ^2 (1/δ)/N is the benchmark: the registered bets come within 3% of it. A finite-sample bound can lie below this first-order approximation because the exact wealth depends on higher-order features of the observed contrasts; the approximation is not a lower limit on all valid bounds. Every implementation is computed from the same per-episode record (Table 10; Figure 5). Transfer and robustness. The member frozen after selection is audited on 2,048 episodes of the reserved 2020 cohort with its own Clopper–Pearson and betting bounds. The reported label-free divergence estimate is ρ^=0.004 ρ=0.004. Data processing makes the exact divergence between the score distributions no larger than the divergence between the full episode laws; the estimate itself also has sampling error. It is a diagnostic, not a certified upper bound on the episode-law divergence, and cannot establish membership in the ball of Theorem 3(v). The cohort’s direct audit gives a certified mean of 1.7, whereas the conditional curve is 5.6 at ρ ρ. Comparing these two lower bounds does not quantify the actual shift; the direct audit carries the cohort-specific claim. Table 10: Statistics: (a) lower bounds on the mean gain by implementation at N=2,048N=2,048 against the Gaussian first-order width; (b) transfer to the reserved 2020 cohort, audited directly (the pass/fail column tests u≤p⋆u≤ p , not the principal audit’s minimum-mean requirement); (c) the conditional robustness curve for laws within KL radius ρ of the audit law. (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 (δ/2δ/2) 0.328 6.17 normal interval (not finite-sample valid) 0.204 6.30 Gaussian first-order width 2σ2log(1/δ)/N 2σ^2 (1/δ)/N 0.304 – (b) 2020 cohort, read once events u gain LB rule RTT 16/2,048 1.18% 1.9 1.7 pass one-pass corrector, 2-hop head ++ rows 17/2,048 1.24% 1.6 1.4 pass matched TR 24/2,048 1.64% 1.3 1.1 pass KL-to-incumbent fine-tuning 38/2,048 2.43% 0.9 – fail (c) ρ 0 0.001 0.002 0.004 0.008 0.016 certified mean if KL(Q∥P)≤ρKL(Q\|P)≤ρ 6.05 5.87 5.77 5.57 5.37 4.97 Deployment unit, primary comparison and multiplicity. Theorem 4 concerns the registered call size. The per-call rates are reported for nq∈64,256,1,024,4,096n_ q∈\64,256,1,024,4,096\, both for the registered member and for members re-selected per size (Figure 4c). The primary comparison is a one-sided paired test at level δ. The eight secondary comparisons are Holm-corrected at the same level, and all pass (Table 12). 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 δ 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. Appendix E Where the gain goes: definitions Planted partition and numerical scope. Labels follow a known law on a graph with the arxiv architecture. At γ=0γ=0 the incumbent is calibrated by construction. A planted community containing 30% of rows is made overconfident by drawing labels from softmax((1−γ)zr) ((1-γ)z r), or underconfident by using softmax(zr/(1−γ)) (z r/(1-γ)), with the described global temperature refit. The label law is a function of the graph and therefore belongs to O. Water-filling computes the exact output-space frontier for this known law. The internal levels in Table 11 and Figure 3 use the reported numerical procedure: the reference-tail solver is supplied with conditional-mean slopes, with endpoint damage evaluated by an additional rollout for the reachability diagnostic and certified charges for the certification diagnostic. Table 11 denotes the achieved numerical levels by U~reach U_ reach and U~cert U_ cert. The shorter labels in Figure 3 refer to those same computed values, not to certified global optima of Theorem 2. Warm-starting from the next lower level establishes the reported numerical ordering, not global optimality. If a level is the gain of a feasible trajectory, it lower-bounds its own exact supremum; a difference between two such computed levels need not bound the difference between the suprema. Table 11 also gives local information, estimation, uncertainty, and execution terms as surrogate diagnostics. The identification ∑ℓAℓcert=Ucert _ A_ cert=U_ cert is not assumed. Relating the last column to the true gain requires verification that each term uses the same convex branch, physical-coordinate majorizer, conditioning information, and trajectory convention as (20), including any branch-selection contribution. Heads that omit a planted-community identifier may have an information gap, but its positivity does not follow from omission of that identifier alone because other inputs can encode the same information. Real data. pBp B is replaced by a cross-fitted calibrated classifier trained on the labels of the 2018 calibration episodes. R^i−1 R_i-1 and U^out U_ out are therefore plug-in quantities, and clipping picrp r_ic at 10−310^-3 changes the medians by at most 0.2. Theorem language is reserved for the known law. Efficiency and placement. ηℓ _ is the linear program of Theorem 2(i) on the candidate hull, with the cross-fitted posterior, averaged over development calls; Figure 3(c) and Table 7 report it normalized by its bound maxi(Rℓ,i−1) _i(R_ ,i-1). Caps use a water-filling-inspired allocation heuristic based on replayed certified efficiency, the gain per certified nat, under an expected-spend budget. The exact water-filling theorem concerns the output-space frontier; it does not establish global optimality of this internal cap-placement heuristic. The final checker, not the allocation heuristic, enforces each call’s budgets. Row groups of Figure 3(d). A near-cancellation row is one whose raw-update terminal prediction satisfies ‖piu−pir‖1<10−3\|p u_i-p r_i\|_1<10^-3 while the proposal moved some row within its remaining-tail receptive field (at most T−ℓ−1T- -1 transitions after injection) at an open depth. A beyond-two-hops row is one for which more than half of the raw update’s influence on its terminal logits, computed with the tangent basis, comes from rows more than two hops away. Contributions are the reported paired per-row gains summed with call weights and averaged over the mixture. The theoretical remaining-tail count and the empirical tangent-influence rule are distinct definitions; the reported group memberships follow the latter measurement protocol. A disjoint assignment rule is required before the three displayed contributions can be interpreted as a partition of the total gain. Table 11: Reported frontier and internal-optimization diagnostics (10−310^-3 nats per call). (a) Arxiv with a cross-fitted posterior. (b) Planted-partition diagnostics: I denotes information, E estimation, χ uncertainty conservatism, and Υ 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 U~cert−I−χ−12(2E+2Υ)2 U_ cert-I-χ- 12( 2E+ 2 )^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. (a) Population U^out U_ out U~reach U_ reach U~cert U_ cert U^RTT U_ 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 severe stress (separate) 37.6 31.8 28.4 23.9 64% 15.8 (b) γ UoutU_ out U~reach U_ reach U~cert U_ cert U^RTT U_ RTT I E χ Υ surrogate diagnostic 0.1 0.21 0.15 0.12 0.07 0.03 0.01 0.01 0.00 0.07 0.2 0.72 0.53 0.42 0.29 0.08 0.03 0.02 0.00 0.27 0.3 1.46 1.07 0.86 0.61 0.16 0.05 0.04 0.00 0.58 0.4 2.31 1.70 1.37 0.99 0.24 0.08 0.05 0.01 0.95 0.5 3.18 2.35 1.90 1.40 0.30 0.11 0.06 0.01 1.35 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. Appendix F Extended results Datasets and incumbents. Breadth uses the GOOD-Arxiv degree and time shifts (Gui et al., 2022); the Twitch, Facebook-100 and Elliptic shifts of Wu et al. (2022) on the data of Rozemberczki et al. (2021), Traud et al. (2012) and Weber et al. (2019); ogbn-products and ogbg-molpcba (Hu et al., 2020); Folktables ACSIncome (Ding et al., 2021) with a residual tanh MLP; and ImageNet-C (Hendrycks and Dietterich, 2019) with the last four blocks of a ResNet-50 (He et al., 2016) adapted by Tent. The incumbent families are APPNP (Gasteiger et al., 2019), GCNII (Chen et al., 2020), GRAND (Chamberlain et al., 2021), shallow GraphSAGE (Hamilton et al., 2017) and GCN (Kipf and Welling, 2017), and GIN-style molecular encoders (Xu et al., 2019); Table 6 lists their primitives. Every entry below is computed from the registered per-episode records by the same script as the main text. Table 12: Complete frontier on arxiv (final audit, as Table 2); Holm-adjusted p-values for the secondary comparisons. Policy −[down]-E[d own] [95% CI] Δ to RTT NζN_ζ u unodeu_ 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+=ζH^+=ζ) 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 – 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 <<0.001 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 <<0.001 One-pass corrector, 4-hop head ++ rows 5.3 [5.1, 5.6] +1.2 [+1.0, +1.3] 14 1.07% 0.56% 5.1 1.32 1.27 – One-pass corrector, 8-hop head ++ rows 5.0 [4.8, 5.2] +1.5 [+1.3, +1.6] 15 1.13% 0.61% 4.8 1.46 1.37 – Exact-geometry output rules on both predictions (two rollouts) Adaptive mixing (εi≤εmax,i _i≤ _ ,i, allocated) 5.1 [4.9, 5.3] +1.4 [+1.2, +1.6] 15 1.13% 0.61% 4.8 2.18 2.18 <<0.001 Mixing, ε=1−e−h =1-e^-h, uniform row budgets 4.1 [3.9, 4.3] +2.4 [+2.3, +2.6] 14 1.07% 0.61% 3.8 2.18 2.18 – Floor projection of the raw update, allocated 5.2 [5.0, 5.5] +1.3 [+1.1, +1.4] 15 1.13% 0.61% 5.0 2.18 2.18 <<0.001 Floor projection of the raw update, uniform 4.3 [4.1, 4.5] +2.2 [+2.0, +2.3] 14 1.07% 0.61% 4.1 2.18 2.18 – Per-node switch, learn-then-test threshold 4.5 [4.3, 4.8] +2.0 [+1.8, +2.1] 17 1.24% 0.71% – 2.18 2.18 <<0.001 Acceptance rules on the same proposal, candidate hull, budgets and certificate Matched TR (same candidate hull, budgets, certificate) 5.8 [5.6, 6.0] +0.7 [+0.5, +0.8] 18 1.30% 0.78% 5.5 1.41 1.35 <<0.001 TR trained end to end under the budgets 5.5 [5.2, 5.7] +1.0 [+0.9, +1.2] 19 1.36% 0.83% 5.2 1.41 1.35 – The same labels and corruption draws spent on the incumbent (no per-call budget) Incumbent fine-tuned on the same labels 1.0 [0.9, 1.2] +5.5 [+5.2, +5.7] 45 2.81%× 2.71% – 1.00 1.00 – KL-to-incumbent fine-tuning 2.8 [2.6, 3.0] +3.7 [+3.5, +3.9] 29 1.93% 1.73% – 1.00 1.00 <<0.001 D∞D_∞-regularized fine-tuning (floor trained, not enforced) 3.4 [3.2, 3.6] +3.1 [+2.9, +3.3] 27 1.81% 1.42% – 1.00 1.00 – Positive-congruent training 2.9 [2.7, 3.0] +3.6 [+3.4, +3.8] 30 1.98% 1.42% – 1.00 1.00 – Regression-aware fine-tuning 3.1 [2.9, 3.3] +3.4 [+3.2, +3.6] 30 1.98% 1.64% – 1.00 1.00 – Incumbent trained on the registered corruptions 3.4 [3.1, 3.6] +3.1 [+2.9, +3.3] 62 3.73%× 3.54% – 1.00 1.00 – The learned update itself Learned update itself (t≡1t≡1), trimmed to Δ¯ 3.9 [3.6, 4.3] +2.6 [+2.3, +2.9] 159 8.81%× 2.93% – 2.18 2.18 <<0.001 Declared variants and one-at-a-time swaps Per-depth radii (q=0.1q=0.1 per depth; Theorem 1(i) not claimed) 6.9 [6.6, 7.1] −-0.4 [−-0.5, −-0.2] 13 1.01% 0.54% 6.6 1.42 1.36 – No per-row budget (Hrow=∞H_ row=∞) 6.7 [6.4, 6.9] −-0.2 [−-0.4, 0.0] 12 0.95% 0.54% 6.4 1.42 1.36 – Spend-based caps instead of efficiency placement 6.2 [5.9, 6.4] +0.3 [+0.2, +0.5] 12 0.95% 0.51% 5.9 1.42 1.36 – Window solved under the envelope only 6.4 [6.2, 6.7] +0.1 [−-0.1, +0.2] 12 0.95% 0.51% 6.2 1.42 1.36 – Mean-pooled candidate features (not hull-invariant) 6.4 [6.1, 6.6] +0.1 [0.0, +0.3] 13 1.01% 0.54% 6.1 1.42 1.36 – Probe-loss slopes instead of full-loss slopes 6.2 [5.9, 6.4] +0.3 [+0.2, +0.5] 15 1.13% 0.54% 5.9 1.42 1.36 – Symmetric charges at the same budget (|d|≤0.05|d|≤ 0.05) 3.9 [3.7, 4.1] +2.6 [+2.4, +2.7] 10 0.83% 0.46% – 1.42 1.36 – Symmetric charges at 0.30.3 nats 5.5 [5.3, 5.7] +1.0 [+0.9, +1.2] 14 1.07% 0.63% – 1.42 1.36 – Global factors only (no interval tube) 4.1 [3.9, 4.3] +2.4 [+2.2, +2.5] 11 0.89% 0.51% 3.9 1.42 1.36 – Late-8 acceptance (ℓ≥24 ≥ 24 only) 4.8 [4.6, 5.0] +1.7 [+1.5, +1.8] 11 0.89% 0.46% 4.6 1.24 1.19 – Diagnostic (uses labels) Posterior-slope gate (≈U^cert≈ U_ cert; cross-fitted posterior) 7.9 [7.6, 8.1] −-1.4 [−-1.5, −-1.2] 0 0.15% 0.27% 7.6 1.42 1.36 – Oracle frontier UoutU_ out (cross-fitted posterior) 10.6 – – – – – – – – Table 13: What each mechanism buys: one swap at a time on the registered configuration (final audit; 10−310^-3 nats; alternative → registered). Swaps are order-dependent comparisons, not an additive decomposition. Mechanism swap gain u what changes Per-node budget none → Hrow=1H_ row=1 nat 6.69 → 6.50 0.95% → 0.95% per-node floor becomes deterministic; fallback 0.34%→ 0.34% Radii per depth → sequential, trajectory-valid 6.86 → 6.50 1.01% → 0.95% trajectory statement of Theorem 1(i); selection caveat applies Placement spend-based → certified efficiency 6.17 → 6.50 0.95% → 0.95% trust moves to depths with high ηℓ _ Window envelope only → two branches 6.45 → 6.50 0.95% → 0.95% optimum over the union of both feasible sets Features mean pooling → support functions 6.39 → 6.50 1.01% → 0.95% executed step exactly invariant (Table 18) Slopes probe loss → full loss 6.16 → 6.50 1.13% → 0.95% accounting identity closes Pricing symmetric → one-sided 3.92 → 6.50 0.83% → 0.95% same budget 0.050.05 nats Tube global → interval factors 4.12 → 6.50 0.89% → 0.95% open depths admissible Depths late eight only → efficiency-placed 4.84 → 6.50 0.89% → 0.95% latency 1.24→ 1.42 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−310^-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. (a) Neighbor gain u Lat. WiSE-FT (incumbent ↔ v2), α by learn-then-test 3.4 2.15%× 1.00 LoRA scaling α 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∞D_∞-regularized fine-tuning (floor trained, not enforced) 3.4 1.81% 1.00 (b) Collapse stream mean damage regressing calls fallback GTrans, raw +38.0 31.0% – EATA +9.1 12.4% – RDumb +5.2 8.9% – GTrans, RTT-gated +0.4 1.3% 6.1% Table 15: Breadth under one protocol (final audits, 2,048 episodes; 10−310^-3 nats per task unit; ζ in 10−310^-3). U^out U_ out: estimated oracle frontier; share: RTT gain over U^out U_ 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. Dataset / shift incumbent ζ U^out U_ out RTT corr. TR share u unodeu_ node verified Lat. metric ogbn-arxiv, registered mixture tanh diffusion, T=32T=32 (tube) 2 10.6 6.5 5.6 5.8 61% 0.95% 0.51% 99.37% 1.42 acc. 75.7→ 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→ 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→ 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→ 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→ 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→ 64.1 GOOD-Arxiv, time (concept) GRAND (smooth) 2.3 8.3 5.2 4.6 4.3 63% 1.18% 0.63% 99.41% 1.47 acc. 66.7→ 67.0 Twitch-explicit (cross-graph) APPNP (exact) 3.1 6.4 4.2 3.9 3.5 66% 1.13% 0.66% 100.00% 1.20 AUC 63.4→ 63.8 Facebook-100 (cross-graph) GCNII (ReLU) 3.4 5.1 3.1 2.9 2.6 61% 1.07% 0.71% 99.32% 1.41 acc. 55.6→ 55.8 Elliptic (temporal, post-shutdown) GRAND (smooth) 2.8 24.6 16.9 14.1 14.3 69% 1.30% 0.78% 99.12% 1.46 F1 47.9→ 49.0 ogbn-products, registered mixture tanh diffusion (tube) 1.6 10.4 7.6 6.9 6.8 73% 1.07% 0.61% 99.51% 1.39 acc. 80.1→ 80.5 ImageNet-C, severity 3 (15 corruptions) ResNet-50, last 4 blocks; Tent 10 452.0 214.0 171.0 168.0 47% 1.47% – 99.07% 1.34 top-1 40.1→ 45.6 Folktables ACSIncome, CA → five states residual tanh MLP, P=IP=I 2 6.2 3.9 3.7 3.4 63% 1.07% – 99.90% 1.21 acc. 80.6→ 80.9 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. Reference family AP ref. AP TR AP RTT gain (10−310^-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] Official test split (audited once) Incumbent GIN-style (deployed) 27.7 – 28.5 – – GIN-style ++ virtual node 28.4 – 29.1 – – ABC0246incumbent−[down]-E[d own] (10−310^-3 nats)(a) Seeds0.40.81.2555.55.5666.56.577Δ¯ (b) Row trim0.70.80.9555.55.5666.56.577ω(c) Safety factor41664555.55.5666.56.577per sign(d) Probes.05.1.2.4555.55.5666.56.577δcov _ cov(e) Miscoverage Figure 7: Robustness on the development half. (a) Three incumbents × 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). 002002004004006006000022446688call10−310^-3 nats(a) Trailing gainfixedmonitored0020020040040060060000224466881010callregressing calls(b) Cumulative regressionsfixedmonitored<<1010–1415–1920–2930–44never00224466881010calls after the changestreams(c) Alarm delay 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. Appendix G Cost, numerics and the checker One accounting convention. Latency is defined per fresh 4,096-node call on the full arxiv graph on one A100 80GB, relative to one incumbent pass of 41.6 ms. RTT’s machinery (heads, window, two-branch solver, provisional contracts and tube, certificate, expected fallback) adds 9.78 ms to the proposal’s own cost. Latency ratios therefore follow (tinc+tprop+tRTT)/tinc(t_ inc+t_ prop+t_ RTT)/t_ inc, and the proposal’s cost is counted once. Two rollouts cost tinc+trawt_ inc+t_ raw sequentially and maxtinc,traw \t_ inc,t_ raw\ on two devices (Table 17). For the native, GPR-GNN, Co-GNN, and AMP rows, the listed proposal cost is incremental to the shared incumbent computation and traw=tinc+tpropt_ raw=t_ inc+t_ prop. For GTrans, Matcha, v2, and LoRA, it is the complete proposal runtime and traw=tpropt_ raw=t_ prop. The corrector row instead reports its additional cost beyond one incumbent pass; it does not add RTT’s machinery. For in-network proposals RTT uses fewer FLOPs than two rollouts. For proposals that are full networks (v2, LoRA, GTrans, Matcha) it is slower than two sequential rollouts, and its case there rests on gain and on the per-node floor. 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. (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 Retrained incumbent (v2, ≤ 2017) 41.6 2.24 2.00 1.00 LoRA-16 weight delta 43.0 2.27 2.03 1.03 one-pass corrector, 2-hop head ++ rows 10.4 1.25 – – (b) Stage episode evaluations labels device-hours incumbent temperature (2018 labels; network already trained) 0 yes 0.3 phase 2: proposal, field and covariance heads (≤ 2017) 6,144 yes 6.9 one-pass correctors, matched training effort (≤ 2017) 6,144 yes 2.8 adapters of the external proposals (≤ 2017) 3,072 yes 1.4 efficiency placement replay (≤ 2017, replayed) 2,048 yes 0.5 sequential calibration, 16 depths × 512, four members (2018) 32,768 yes 3.1 joint selection: 5 members on four pools of 1,024 (mixture, clean, cache, noise; 2018) 20,480 yes 2.1 development half (2019): 25 configurations × 2,048 (sweeps, call sizes, ζ anchor) 51,200 yes 8.8 final audit, 2,048+6×4,0962,048+6× 4,096 (2019 final half) 26,624 yes 4.6 per-node audit, two calls of the registered size (4,096 labels inspected) 2 yes 0.0 transfer, reserved 2020 cohort 2,048 yes 0.3 held-out family: audit, re-calibration, re-audit 5,120 yes 0.3 service streams, 20 drifted × 600 12,000 yes 0.4 test-time adaptation collapse streams, 20 × 600 12,000 yes 0.4 service streams, 20 clean × 600 (label-free) 12,000 no 0.4 stress, invariance and checker tests (label-free; offline second rollout) 6,144 no 0.6 breadth: families, shifts, molecules, non-graph (own splits) 30,720 yes 5.8 total 228,514 210,370 labeled 38.7 The reference is the deployed float32 incumbent. Theorems are stated in real arithmetic. The certificate is computed by a checker in float64 with directed rounding. It adds two allowances: the executed pass’s state-update residual, and the forward error of the incumbent’s own float32 continuation, using accumulation-error factors γm=mϵm/(1−mϵm) _m=m _ m/(1-m _ m), where m is the relevant accumulation length, mϵm<1m _ m<1, and ϵm _ m is the unit roundoff. These factors must multiply the corresponding absolute-sum bounds and be propagated through the remaining primitives, including a validated tanh enclosure. Both are deducted from the budgets. The checker is implemented separately from the executor. The reported tests include 10,000 planted violations whose hidden margins range from 10−710^-7 to 10−310^-3 nats, following SoundnessBench (Zhou et al., 2025); on 1,000 certificates re-evaluated in 50-digit arithmetic; and against corrupted factors, corrupted steps and switched-off rounding (Table 18). 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. Test result verdict planted violations, hidden margins 10−710^-7–10−310^-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×10−103.1× 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−310^-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 ≤10−6≤ 10^-6 diagnostic duplicate a candidate displacement change 0.4% (mean pooling) vs 0% (support functions) unchanged duplicate, rescaled by 12 12 displacement change 0.4% (mean pooling) vs 0% (support functions) unchanged permute the candidates displacement change 0% (mean pooling) vs 0% (support functions) unchanged add a candidate inside the post-trim hull displacement change 0.3% (mean pooling) vs 0% (support functions) unchanged equivalent spanning set of the same hull displacement change 0.2% (mean pooling) vs 0% (support functions) unchanged replace a candidate by a shorter one (the hull changes) displacement change 21% (mean pooling) vs 21% (support functions) hull changes 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 ΓΔrT,i _ r_T,i (red) and of the exact one-sided damage hi=D∞(pir∥pis)h_i=D_∞(p r_i\|p 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 Πℓ _ with the admissibility cap Π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. Appendix H Positioning and notation 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. 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 Steering with abstention (Hedström et al., 2025) online activations statistical partly steering vectors RTT online, per call internal states deterministic per node and call; audited rates fallback only any bounded proposal Table 20: Notation. Symbol meaning pr,pπ,ps,pu,pBp r,\ p^π,\ p s,\ p u,\ p B incumbent’s, adapted, served, raw update’s prediction; Bayes posterior α,τ,Tα,\ τ,\ T the incumbent’s skip weight, step size and horizon hi=D∞(pir∥pis)h_i=D_∞(p r_i\|p s_i), S±S^± one-sided damage of row i; worst-case loss increase and decrease of a call H+,Hrow,ℬℓ,ρℓ,iH^+,\ H_ row,\ B_ ,\ _ ,i per-call and per-node budgets; remaining call budget; row allowance ℱh(p)F_h(p) floor set e−hp+(1−e−h)Δe^-hp+(1-e^-h) ,O,\ G label-free information; expected gain given it rj,i,r~,Lj,i,μj,ir_j,i,\ r,\ L_j,i,\ _j,i tube radius, provisional radius, interval factor, curvature factor Πℓ,Π^ℓ _ ,\ _ contract growth from depth ℓ to T; its registered proxy in the row-budget trim Λ,Ξ ,\ first- and second-order row contracts σ,env+,C+σ,\ env^+,\ C^+ contract charge, window envelope, exact last-depth charge ℓ,Dℓ=QℓΘℓ,v,x,tK_ ,\ D_ =Q_ _ ,\ v,\ x,\ t candidate hull, directions, physical step, its coordinates, candidate coefficients g^,a^,Σ^,κℓ,δℓ g,\ a,\ ,\ _ ,\ _ field, slopes, covariance, radius, per-depth miscoverage Ri,Gi,ηℓR_i,\ G_i,\ _ under-estimation factor, row frontier, architecture-constrained efficiency Uout,Ureach,Ucert,URTTU_ out,U_ reach,U_ cert,U_ RTT the gap chain of Theorem 2 mℓ,Iℓ,χℓ,Υℓ,Ξ¯ℓm_ ,\ I_ ,\ _ ,\ _ ,\ _ mean slope given the heads’ inputs, information gap, conservatism, execution gap, certified curvature (equation (20)) E summed estimation term ∑ℓ12‖mℓ−a^ℓ‖Ξ¯ℓ−12 _ 12\|m_ - a_ \|^2_ _ ^-1 (Table 11) ζ,u,unodeζ,\ u,\ u_ node regression tolerance, per-call and per-node bounds