Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

Escaping Parameter Space: Tight Generalization Bounds via Representation Quality

Niclas Göring1∗ Shuofeng Zhang1

arXiv:2610.23729v1 [cs.LG] 16 Oct 2026

1

Branton DeMoss2

Ard A. Louis1

Rudolf Peierls Centre for Theoretical Physics, University of Oxford, Oxford, UK 2 Mathematical Institute, University of Oxford, Oxford, UK

Abstract We derive a tight generalization bound for deterministic neural We derive a tight generalization bound for deterministic neural networks based on their last hidden layer representations. By evaluating representation quality with a parameter-free k-nearest-neighbor (k-NN) classifier, our certificate avoids traditional parameterspace complexity measures, KL divergences to a posterior, weight norms, and compression. The bound is tight: trained from scratch, it reaches an 8.0 percentage point gap to test error on CIFAR-10 (ResNet-18) and yields the first non-vacuous certificates we are aware of on CIFAR-100; with frozen DINOv2 representations, it certifies at 1.4% on CIFAR-10 and 23.1% on 1,000-class ImageNet. It decomposes additively into three empirical, independently measurable quantities: local class geometry (k-NN decoder error), decoder-network agreement, and training stability. This allows the bound to act as a diagnostic tool: we demonstrate that actively destroying local class geometry eliminates generalization while leaving dataset memorization intact, identifying class geometry as a causally relevant mechanism for generalization. Finally, we show that learned representations are significantly less sensitive to weight noise than linear readouts, suggesting why parameter-space certificates often struggle to remain tight.

1

Introduction

Almost every existing non-vacuous generalization bound for deep networks pays a price for their treatment of parameter space. PAC-Bayes certificates add noise to the weights and pay through KL divergence Dziugaite and Roy [2017], Pérez-Ortiz et al. [2021], Lotfi et al. [2022]. Compression bounds quantize or prune and pay through description length Zhou et al. [2019], Lotfi et al. [2022]. Recent work has produced non-vacuous certificates for deterministic networks by reasoning about partitions Than and Phan [2025] or distribution and loss complexity. Each line of work has produced progressively tighter results, but all share a common design: they reason about parameters, or parameter-derived quantities, to certify predictions. We take a different route. Instead of certifying the parameterized network through its weights, we certify it through its learned representation. Concretely, we produce two bounds: in the transfer setting, where the feature map is fixed independently of the target data, we certify a k-nearest-neighbor (k-NN) classifier built on the last-hidden-layer representations h(L) (x); in the cross-fit setting, where the network is trained on the target task, we certify the deployed deterministic network itself, using the k-NN decoder. The proof uses only cross-fitting and the KL concentration inequality for i.i.d. Bernoulli variables. The representation is of course produced by the parameters, but no parameterspace complexity measure, no KL to a posterior, weight norm, covering number, or description length enters the argument. The bound is a function of three empirical quantities on the learned feature map φ : X → Z (Figure 1a): ∗ Corresponding author: niclas.goring@physics.ox.ac.uk

40th Conference on Neural Information Processing Systems (NeurIPS 2026).

Q1 Can a simple classifier in Z predict labels? That is, does the representation have clean local class geometry? Q2 Does that classifier agree with the network? That is, does the representation capture what the network actually computes? Q3 Is training stable under fold removal? That is, do models trained on n versus n − nj points make essentially the same predictions?

Figure 1: Any learned feature map φ : X → Z raises three questions: Q1 Can a simple classifier in Z predict labels? Q2 Does it agree with the network? Q3 Is training stable under fold removal? a) A k-NN classifier on the last-hidden-layer representation h(L) (x) yields ŷkNN (Q1), compared against ŷNN (Q2); a fold-trained model tests stability (Q3). b) ResNet-18 on CIFAR-10: the bound converges to within 8.0 pp of test error at n=50,000, the tightest known certificate from a deterministic network without modified training. Stacked bars show Q1 dominates: representation quality is the binding constraint. When all three answers are yes, the deterministic deployed network is certified without ever reasoning about its parameters. The bound decomposes additively into one term per question, turning the certificate into a diagnostic of representation quality. Our contributions are: 1. A representation-level certificate for deterministic networks (Theorem 2.6). Three empirical terms, decoder error (Q1), decoder–network disagreement (Q2), and training stability (Q3) bound the test error of the deployed network, without any parameter-space KL term, weight norm, covering number, or compression in the proof. 2. Tight bounds across scales. Trained from scratch: gaps to test error as small as 8.0 pp obtain on CIFAR-10, and the first non-vacuous certificates we are aware of on CIFAR-100 for unmodified deterministic networks. Frozen pretrained representations achieve 1.4% on CIFAR-10 and 23.1% on 1,000-class ImageNet (DINOv2), the first non-vacuous k-NN decoder certificates we are aware of at ImageNet scale. See Tables 1 and 2. 3. Implications of the decomposition. The three terms can be measured independently, which localizes where generalization succeeds or fails. Double descent lives in the linear readout (Q2), not the representation (Q1); see Section 4.1. An intervention that destroys local class geometry eliminates generalization while training accuracy stays at 100%, interventional evidence that Q1 is causal, not a correlate of generalization (Section 4.2). 1.1

Related work

Most non-vacuous certificates for deep networks reason through parameter-space quantities, whether via PAC-Bayes perturbation of the weights [McAllester, 1998, Dziugaite and Roy, 2017, Neyshabur et al., 2017, Pérez-Ortiz et al., 2021] or compression and quantization [Hinton and Van Camp, 1993, Arora et al., 2018, Zhou et al., 2019, Lotfi et al., 2022]. Our bound takes a different route: no parameter-space complexity measure enters the certificate, and its tightness depends on representation quality rather than parameter count (Section 4.1). Function-space PAC-Bayes analyses also move beyond parameter space [Valle-Pérez and Louis, 2020, Zhang and Louis, 2025]; our approach is not the first to do so, but requires only held-out error, agreement, and stability. Two recent methods are related: [Than and Phan, 2025] certify deterministic networks via an a priori data partition; [Bazinet et al., 2026] certify via a separately trained surrogate and empirical disagreement. Our surrogate is 2

neither trained nor chosen: it is a parameter-free k-NN decoder induced by the representation itself, and the bridge to the deployed network reduces to training stability [Bousquet and Elisseeff, 2002, Hardt et al., 2016]. Our proof uses cross-fit held-out evaluation with KL concentration [Langford and Schapire, 2005, Blum et al., 1999]; our contribution is not the technique but the object being evaluated. k-NN probing of representations is standard in self-supervised learning [Wu et al., 2018, Caron et al., 2021, Oquab et al., 2023]; our contribution is that probe performance, combined with agreement and stability, becomes a formal certificate for the deployed network. We compare numerical values of our certificates in Tables 1 and 2 and discuss related work in more depth in Appendix B.

2

Theory: A Representation-Level Bound

Any learned feature map φ : X → Z turns a dataset into a point cloud in some metric space (Z, d). In practice, φ is the network’s last hidden layer representation h(L) (x), the vector fed into the final linear classifier, and d is ℓ2 distance; extraction requires a single forward pass with no modification to the network (details in Appendix F). The theorems apply verbatim to any deterministic feature map (e.g. another layer of the network) and metric d. We instantiate the three questions from the introduction by taking the “simple classifier” to be a k-NN rule in (Z, d). It requires no training, has no parameters of its own, and makes all three quantities directly measurable. We emphasize what this does and does not mean: the representation φ is of course produced by the trained parameters, but the bound uses no parameter-space complexity measure. The proofs use a single structural property: conditioned on the complement sample, the held-out points are i.i.d. and the decoder is deterministic, so standard concentration applies. 2.1

Technical setup

Let P be a distribution on X × [C], where [C] := {1, . . . , C}. Draw an i.i.d. sample Sn = {(xi , yi )}ni=1 ∼ P n . Let A be a (possibly randomized) training algorithm that maps any labeled dataset T to network parameters A(T ), producing a classifier fbA(T ) and a feature map φA(T ) : X → Z into a metric space (Z, d). All internal randomness of A (initialization, data ordering, augmentation) is fixed in advance; every statement below is conditional on this randomness. Write θ (full) = A(Sn ) for the full-data parameters, fb(full) for the deployed classifier, and φ(full) = φθ(full) for its feature map. This is the object we wish to certify. Definition 2.1 (Cross-fit k-NN decoder). Partition [n] into J disjoint folds F1 , . . . , FJ with |Fj | = nj P and j nj = n. For each fold j, train on the complement:
 θ (−j) = A S−j , S−j = (xi , yi ) : i ∈ / Fj . (−j) Write φ(−j) for the fold-j feature map, zi = φ(−j) (xi ) for the embedded points, and fbj = fbθ(−j) (k) for the fold-j classifier. The cross-fit k-NN decoder hj maps a query x to the majority label among (−j)

the k nearest neighbors of φ(−j) (x) in the reference set {zi tie-breaking rules are fixed in advance and deterministic.

: i ∈ / Fj }, with distance d. All

Three empirical quantities control the certificate: Definition b(k) R j

Measures

(k) i∈Fj 1[hj (xi ) ̸= yi ]

P 1 nj

b (k) D j

1 nj

P

∆stab j

1 nj

P

Q1: decoder error

(k) b i∈Fj 1[hj (xi ) ̸= fj (xi )]

Q2: decoder–network gap

b b(full) (xi )] i∈Fj 1[fj (xi ) ̸= f

Q3: fold–full gap

Note that ∆stab is independent of k: it compares the two networks’ hard predictions directly. j 1−q Notation. The binary relative entropy is kl(q∥p) = q log pq + (1−q) log 1−p for q, p ∈ [0, 1] −1 (extended by continuity at the boundary), and its upper inverse is kl+ (q, c) = sup{p ∈ [q, 1] : kl(q∥p) ≤ c}.

3

2.2

Certifying the decoder (Q1)

The first step certifies the k-NN decoder alone, treating it as a classifier in its own right. Because the fold points Fj are held out from training θ (−j) , the decoder is conditionally deterministic and the error indicators are conditionally i.i.d. Hence, a direct application of KL concentration suffices. Theorem 2.2 (Cross-fit decoder certificate). Fix a finite search set K ⊂ N (e.g. K = {1, 3, 5}). With probability at least 1 − δ over Sn , for every j ∈ [J] and k ∈ K simultaneously: !

log |K| J/δ + log(nj +1) (k) −1 b (k) . (1) Pr hj (X) ̸= Y | S−j ≤ kl+ Rj , nj (X,Y )∼P (k)

Since hj Sn .

depends on Sn only through S−j , conditioning on S−j is equivalent to conditioning on

Proof. See Section D.1 for the proof. 2.3

Transfer certificate

When the feature map φ is learned without access to the target data, e.g. pretrained on a different dataset, the cross-fit construction simplifies. There is no fold/full distinction, so Q3 vanishes, Q2 is irrelevant (the k-NN decoder is the deployed classifier), and a single reference/evaluation split replaces the J-fold construction. For example, this lets us certify a k-NN decoder built from an ImageNet-pretrained ResNet-50 representation on CIFAR-10; see Section 3.1. Theorem 2.3 (Transfer certificate). Let φ be fixed independently of the target sample Sn (e.g. pretrained on disjoint data). Split Sn ∼ P n into Sref (size m) and Seval (size ne = n−m). Let b(k) Ieval ⊂ [n] denote the indices of the evaluation points. Build h(k) from φ(Sref ). Define R as in Section 2.1 but computed on Seval . With probability ≥ 1 − δ over Sn , for every k ∈ K simultaneously:

b(k) , ce , Pr h(k) (X) ̸= Y | Sref ≤ kl−1 (2) + R (X,Y )∼P



 where ce = log(|K|/δ) + log(ne +1) /ne . Q2 = 0 and Q3 = 0 by construction: the k-NN decoder is the classifier and φ does not depend on the target data. Eq. (2) certifies the decoder via Q1 alone.

Proof. See Section D.2 for the proof. 2.4

Certifying the full network

When the network is trained on the target task, Q2 and Q3 are both non-trivial. We handle them in two steps. We bound the deployed network fb(full) without accessing its parameters: its error is at most (a) the error of a surrogate fold network plus (b) the disagreement between fold and full networks on unlabeled data. Step A: from decoder to fold network. Theorem 2.4 (Fold-network certificate). Fix K ⊂ N. With probability at least 1 − δ over Sn , for every j ∈ [J] and k ∈ K simultaneously:


b(k) b (k) Pr fbj (X) ̸= Y | S−j ≤ kl−1 + kl−1 (3) + Rj , cj + Dj , cj (X,Y )∼P {z } {z } | | Q1

Q2

  where cj = log(2 |K| J/δ) + log(nj +1) /nj . Since fbj depends on Sn only through S−j , conditioning on S−j is equivalent to conditioning on Sn . Proof. See Section D.3 for the proof. 4

Step B: from fold network to full-data network. For any (x, y) and j ∈ [J],       1 fb(full) (x) ̸= y ≤ 1 fbj (x) ̸= y + 1 fbj (x) ̸= fb(full) (x) ,

(4) since the full network can only err if the fold network also errs or the two disagree. Taking expectations conditional on Sn introduces the stability gap
∆stab = Pr fbj (X) ̸= fb(full) (X) | Sn . (5) j

X∼PX

This is a disagreement probability over X alone; labels play no role, so it can be certified from unlabeled data. Rather than derive an optimizer-specific analytic stability bound that would need to be rewritten for SGD, Adam, RAdam, Lion, Shampoo, or any new optimizer, we certify this term empirically. This keeps the certificate practically usable across training setups. m 2 Theorem 2.5 (Direct stability certification). Let U = {xr }m r=1 ∼ PX be independent of Sn . Define P m b b(full) (xr )]. With probability ≥ 1 − δ ′ over the joint draw (Sn , U), for bU = 1 ∆ j r=1 1[fj (xr ) ̸= f m every j ∈ [J] simultaneously:   log(J/δ ′ ) + log(m+1) −1 b U stab ∆j ≤ kl+ ∆j , =: Bjstab . (6) m Proof. See Section D.4 for the proof. Combining Theorem 2.4, (4), and Theorem 2.5: m ′ Theorem 2.6. Let U = {xr }m r=1 ∼ PX be independent of Sn . With probability ≥ 1 − δ − δ over (Sn , U), for every k ∈ K and j ∈ [J]:



bU b(k) b (k) Pr fb(full) (X) ̸= Y | Sn ≤ kl−1 + kl−1 + kl−1 + ∆j , c m + Rj , c j + Dj , cj (X,Y )∼P | {z } | {z } {z } | Q1: local class geometry

Q2: decoder– network agreement

Q3: training stability

(7)     where cj = log(2 |K| J/δ) + log(nj +1) /nj and cm = log(J/δ ′ ) + log(m+1) /m. The   −1 b (k) −1 b U b(k) tightest certificate is minj,k kl−1 + (Rj , cj ) + kl+ (Dj , cj ) + kl+ (∆j , cm ) . Interpretation b(k) small ⇐⇒ the representation has clean local class geometry. > Q1 R j b (k) small ⇐⇒ the network computes through this representation. > Q2 D j

small ⇐⇒ the training algorithm is stable under fold removal. > Q3 ∆stab j

Proof. See Section D.5 for the proof. b(k) , The representation φ and metric d enter the bound only through the three empirical quantities R j (k) U b b Dj , and ∆j ; no parameter-space complexity measure appears anywhere. What makes the bound tight is not the proof technique but the learned representation, which creates a local class geometry so clean that a trivial classifier nearly matches the network. The bound measures that quality; it does not create it.

3

Results

We evaluate the certificate in two settings: transfer with zero target training (Section 3.1) and cross-fit certification of networks trained from scratch (Section 3.2), then compare with prior bounds. All bounds use ℓ2 distance on the last-hidden-layer representation hθ : X → RD , the vector fed into the final linear classifier, computed by a single unmodified forward pass. For ResNets, hθ is the output of global average pooling (D=512 or 2048); for Vision Transformers, the class token after the final layer norm (D=768 or 1024); for DINOv2, the class-token embedding from the frozen backbone. Full extraction details are in Section F. 2 The standard test inputs of MNIST, CIFAR-10, and CIFAR-100 satisfy this: no test point participates in training any fold

or full model.

5

3.1

Transfer certification without training

When the feature map is fixed independently of the target data (e.g. pretrained on ImageNet), Q2 and Q3 vanish and Theorem 2.3 applies directly. The certified object is the k-NN decoder built on top of the frozen representation, not the pretrained network’s own classifier head. We evaluate eight pretrained models plus a randomly initialized ResNet-18 as a null control. For each, we extract the ℓ2 representation with a single forward pass, split the target data 80/20 (ne ≈ 10k), and report the tightest bound over k ∈ {1, 3, 5, 7, 11, 15, 21} at δ=0.05 (the reported certificates are best-of-grid; the union bound over k is already included). Four target datasets are used: CIFAR-10, CIFAR-100, ImageNet validation, and ImageNet-V2 (distribution shift). No model undergoes any target-task network training. Table 1 reports the results. CIFAR-10

CIFAR-100

ImageNet

ImageNet-V2

Model

Params

Err

Bnd

Gap

Err

Bnd

Gap

Err

Bnd

Gap

Err

Bnd

Gap

DINOv2-L/14 DINOv2-g/14 DINOv2-B/14 ViT-B/16 ViT-L/16 WRN-50-2 ResNet-50 ResNet-18

304M 1.1B 86M 86.6M 304M 68.9M 25.6M 11.7M

0.9 — 2.3 6.8 7.7 10.1 12.1 18.0

1.4 — 3.2 8.3 9.2 11.8 13.9 20.1

0.5 — 0.9 1.5 1.5 1.7 1.8 2.1

10.4 — 14.9 28.1 29.5 34.3 36.7 43.6

12.1 — 16.9 30.5 32.0 36.9 39.3 46.2

1.7 — 2.0 2.4 2.5 2.6 2.6 2.6

20.9 21.2 23.4 21.6 21.8 24.1 26.5 44.1

23.1 23.5 25.7 23.8 24.0 26.4 28.9 46.8

2.2 2.3 2.3 2.2 2.2 2.3 2.4 2.7

37.5 37.7 41.3 39.2 40.3 47.6 49.4 70.2

43.0 43.2 46.8 44.7 45.8 53.1 55.0 75.1

5.5 5.5 5.5 5.5 5.5 5.5 5.6 4.9

ResNet-18 (rand.)

11.7M

63.3

65.8

2.5

87.8

89.5

1.7

99.0

99.4

0.4

99.5

99.9

0.4

Table 1: Transfer decoder certification (ℓ2 , δ=0.05). The certified object is the k-NN decoder, not the pretrained classifier head (Q2, Q3 vanish by construction). Err: k-NN error (%). Bnd: certified bound (%). Gap: <5 5–15 15–30 30–50 >50 pp . Three findings stand out. (i) First, the bounds are tight: DINOv2-L/14 certifies at 1.4% on CIFAR-10 and 12.1% on CIFAR-100; all eight pretrained models produce non-vacuous certificates on 1,000-class ImageNet, the tightest being 23.1%. To our knowledge, these are the first non-vacuous ImageNetscale certificates for k-NN decoders built from unmodified deterministic pretrained representations. (ii) Second, the certificate extends to distribution shift: all eight models also certify on ImageNetV2 [Recht et al., 2019], with the wider gap (∼5.5 pp vs. ∼2.2 pp in-distribution) reflecting the harder setting rather than a limitation of the bound. (iii) Third, the bound tracks representation quality, not model size: DINOv2-g (1.1B params) and DINOv2-L (304M) produce nearly identical certificates on ImageNet (23.5% vs. 23.1%), while ResNet-18 pretrained vs. random, same 11.7M parameters, spans 20.1% to 65.8% on CIFAR-10. The certificate measures what the network learned, not how many parameters were used to express it. 3.2

Cross-fit certification of trained networks

We now certify networks trained from scratch using the full certificate (Theorem 2.6) with J=5 folds, δ=δ ′ =0.025, and U = standard test inputs. Table 2 reports the results alongside recent certificates from prior work. On MNIST all architectures certify tightly (best: ResNet-18 at 2.6%); on CIFAR-10, ResNet-50 certifies at 12.4%; and on CIFAR-100, ResNet-50 certifies at 44.6%. To our knowledge, these are the first non-vacuous CIFAR-100 certificates we are aware of, and among the tightest CIFAR-10 certificates, for networks trained from scratch without modifying the certified network. The three-term decomposition shows why. ResNet-50 on CIFAR-10 splits as Q1 = 5.7%, Q2 = 1.8%, Q3 = 1.2%: clean geometry, faithful decoder, stable training. ViT on CIFAR-100 is vacuous and every term is large (Q1 = 43.7%, Q2 = 20.2%, Q3 = 35.4%). A small ViT on 40,000 images does not learn a stable, class-coherent representation. The same architecture pretrained certifies at 30.5% (Table 1), with Q3=0 by construction: same theorem, only the representation changed. The bound diagnoses representation quality, not architecture: FFNNs certify tightly on MNIST (4.8%) and correctly vacuously on CIFAR (> 95%, where they genuinely fail at 44% test error). Comparison with prior bounds. On MNIST our cross-fit bound (2.6%) is comparable to the tightest known certificate [Pérez-Ortiz et al., 2021] while certifying a deterministic network rather than a stochastic perturbation. On CIFAR-10, our ResNet-18 bound (13.0%) improves on [Bazinet 6

Method

Architecture

n

Test

Bound

Gap

Certified object

MNIST Dziugaite and Roy [2017] Zhou et al. [2019] Lotfi et al. [2022] Pérez-Ortiz et al. [2021]

FCN-600 LeNet-5 LeNet-5 FCN

60k 60k 60k 60k

∼2.5% ∼1% ∼1% ∼1.4%

∼17% ∼46% 11.6% ∼2.3%

14.5 45 10.6 0.9

Stochastic net Compressed net Quant. subspace Stochastic net

Ours (FFNN) Ours (ViT) Ours (ResNet)

FFNN ViT-small ResNet-18

60k 60k 60k

1.5% 0.9% 0.6%

4.9% 3.5% 2.6%

3.4 2.6 2.0

Det. net via repr. Det. net via repr. Det. net via repr.

CIFAR-10 Lotfi et al. [2022] Bazinet et al. [2026]

ConvNet ResNet-18

50k 50k

– 5.8%

∼58.2% 17.36%

– 11.5

Quant. subspace Det. net via surr.

Ours (FFNN) Ours (ViT) Ours (ResNet-18) Ours (ResNet-50)

FFNN ViT-small ResNet-18 ResNet-50

50k 50k 50k 50k

44.6% 12.3% 4.7% 4.3%

95.5% 31.9% 13.0% 12.4%

50.9 19.6 8.3 8.0

Det. net via repr. Det. net via repr. Det. net via repr. Det. net via repr.

CIFAR-100 Lotfi et al. [2022]

ConvNet

50k

–

94.6%

–

Quant. subspace

Ours (FFNN) Ours (ViT) Ours (ResNet-18) Ours (ResNet-50)

FFNN ViT-small ResNet-18 ResNet-50

50k 50k 50k 50k

75.2% 37.1% 21.2% 19.4%

100.0% 99.3% 51.1% 44.6%

24.8 62.3 29.9 25.2

Det. net via repr. Det. net via repr. Det. net via repr. Det. net via repr.

Table 2: Cross-fit certification vs. prior bounds. Per-dataset blocks list prior work (above the rule) and our cross-fit bounds across architecture families (below, shaded). Best row per dataset in darker shade and bold. ReLU activation; SiLU results are in Table 3. ℓ2 metric, δ=δ ′ =0.025, best over k ∈ {1, 3, 5, 7, 11, 15, 21} and j ∈ [5]; union-bound cost included. Prior-work numbers from original publications.

et al., 2026] at the same architecture (17.36%); on CIFAR-100 we are not aware of prior non-vacuous certificates. The comparison is not entirely apples-to-apples: different methods certify different objects (stochastic nets, compressed nets, surrogates, deterministic nets, decoders), catalogued in Table 4. The distinctive property of our approach is that it certifies the deployed deterministic network without modified training and extends to pretrained representations.

4

What the bound reveals

4.1

Overparameterization dissolves at the representation level

Our bound does not index parameters, only the representation they produce. DINOv2-g (1.1B params) and DINOv2-L (304M) give nearly identical certificates on ImageNet (23.5% vs. 23.1%); ResNet-18 pretrained vs. random, same 11.7M parameters, spans 20.1% to 65.8% on CIFAR-10 (Table 1). The relevant variable is representation quality, not parameter count. The width-scaling experiment (Figure 2) makes this precise and yields a sharper claim: the bound decomposes double descent into a monotone representation term and a transient head–representation misalignment. We train ResNet-18 at width multipliers (w) 1×–32× on CIFAR-10 with 0%, 10%, and 20% label noise, and evaluate each term at every width. To isolate the shape of each term we report its excess over the widestnetwork baseline, ∆Q1 (w) = Q1 (w) − Q1 (wmax ) and analogously for ∆Q2 . ∆Q1 is monotone in width: wider networks produce strictly cleaner local class geometry, with label noise shifting the curve upward without changing its shape. ∆Q2 is the only non-monotone term, peaking sharply near the interpolation threshold and then collapsing. At the critical width the representation already supports accurate local classification, but the linear head fails to exploit this geometry. The classical doubledescent curve in test error is therefore the sum of a monotone improvement in representation quality (Q1 ) and a transient spike in head–representation misalignment (Q2 ), both of which the certificate measures directly; the test-error hump is localized to Q2 . The overparameterization question carries an implicit assumption that parameter count is the relevant variable; our decomposition reframes it as: why does training on natural data produce representations where simple local classifiers succeed? 7

Figure 2: ResNet-18 width sweep on CIFAR-10 (0%, 10%, 20% label noise, 3 seeds). a) Test error and total bound. b) ∆Q1 (w) and ∆Q2 (w), each measured as excess over the widest-network baseline. c) ∆Q1 (local class geometry) decreases monotonically in width. d) ∆Q2 (decoder–network agreement) is the only non-monotone term, peaking at the interpolation threshold and then collapsing. The test-error hump is localized to Q2 . The Q3 term is not analyzed in this sweep.

4.2

Local class geometry is causal, not correlational

The experiments above show that the bound tracks generalization. Does it measure a cause, or a symptom? A natural worry is that Q1 and generalization are both downstream of some third factor (good optimization or a well-conditioned loss landscape, for example), in which case Q1 would be a correlate rather than a mechanism. We test this with an intervention that alters Q1 while leaving the network’s predictions on the training set unconstrained, and ask whether generalization follows. Define a regularizer targeting exactly what Q1 measures, within-class representation similarity: Lrep =

2 1 X  h̄(xi )⊤ h̄(xj ) , |P|

 P = (i, j) : i ̸= j, yi = yj , i, j ∈ S ,

(8)

(i,j)∈P

where h̄(x) = h(x)/(∥h(x)∥2 + ε) is the ℓ2 -normalized representation at each hidden layer. Minimizing Lrep pushes same-class representations apart, destroying the local class geometry that Q1 quantifies. Crucially, it places no constraint on the network’s outputs: with enough capacity the network can reach Lrep ≈ 0 and LCE = 0 simultaneously, i.e. perfect training accuracy with destroyed class geometry, as shown ing Figure 3. We train six-layer FFNNs (width=1024) on SVHN with LCE + λ Lrep across four activation functions. Training accuracy saturates near 100% in every case: the network memorizes the data perfectly. Test accuracy strongly degrades. The trajectories differ across ReLU, SiLU, GELU, and tanh in both timing and the relative position of Q1 and test error. But, the qualitative pattern is invariant: training stays at 100%, while test accuracy collapses as the Q1 deteriorates. These results provide novel interventional evidence linking a certifiable quantity to generalization. By introducing a penalty that degrades the quality measure Q1 without constraining the network’s training predictions, we demonstrate that a generalizing network can be driven into a memorizing regime. Because this effect persists across the distinct optimization dynamics induced by four different activations, it strongly suggests that local class geometry acts as a fundamental mechanism separating generalization from mere memorization.

0.75 0.50

GELU

tanh Accuracy

SiLU train acc test acc Q1

Accuracy

ReLU Accuracy

Accuracy

1.00

0.25 100

Epoch

1000 5000

100

Epoch

1000 5000

100

Epoch

1000 5000

100

Epoch

1000 5000

Figure 3: Six-layer FFNNs (width=1024) trained on SVHN with LCE + λ Lrep across four activation functions. Training accuracy (blue) saturates near 100%; test accuracy (red) degrades toward chance (∼ 10%). Q1 (black) decays together with test error in every case. The qualitative Q1 -to-test-error coupling is invariant across activation functions, although trajectories differ quantitatively.

8

4.3

Why parameter-space certificates can be loose

PAC-Bayes bounds certify a stochastic classifier fˆθ+ε by adding noise to the weights. The bound is tight when the full network, including the linear readout, tolerates perturbation. Figure 4 suggests why this can be difficult: under Gaussian weight noise, k-NN accuracy in representation space degrades far more slowly than the network’s own predictions. At σ=0.01 on a ReLU ResNet-18, the k-NN decoder retains 84% accuracy while the network has fallen to 67%. The pattern holds across activations and label-corruption levels (Figure 4b), with the gap ranging from +2 pp to +46 pp. The linear readout is consistently the more fragile component. This does not show that PAC-Bayes bounds cannot be tight; tighter variants exist [Pérez-Ortiz et al., 2021, Lotfi et al., 2022]. It offers an intuition for why certifying through parameters can pay for the fragility of the head, while certifying through the representation avoids this cost.

Figure 4: a) ReLU ResNet-18 on CIFAR-10. Under Gaussian weight noise at level σ, k-NN accuracy in ℓ2 representation space (solid blue) degrades more slowly than the network’s own predictions (dashed red). At σ=0.01 the k-NN decoder retains 84% accuracy while the network has fallen to 67%. b) The representation advantage holds across activation functions and label-corruption levels at σ=0.01, with the gap ranging from +2 pp (40% corruption) to +46 pp (tanh).

5

Discussion

The question we study is not: Why do overparameterized networks generalize?, but rather: What determines good generalisation at the representation level?. This is a question about representation learning and data structure, not capacity control. We find that good classification follows from clean local class geometry via elementary concentration. Our bound provides a quantitative tool for measuring this: a network with 108 parameters and one with 105 that induce the same feature geometry will receive the same bound. Limitations. Q3 is certified empirically rather than analytically. This ensures the bound remains usable across any optimizer (e.g., Adam), schedule, or augmentation without requiring re-derivation. The certificate specifically bounds classification error using last-layer ℓ2 distance; exploring calibration, robustness, regression, or alternate metrics is left to future work. Finally, cross-fit certification requires training J fold models, a nontrivial one-off cost at ImageNet scale. Broader impacts. While our certificates enable transparent evaluation by localizing generalization bottlenecks, the primary risk is over-trust. Our guarantee strictly bounds classification error under stated assumptions; it does not certify fairness, privacy, robustness, or overall deployment safety. Therefore, these bounds should inform, rather than unilaterally approve, high-stakes systems. Future work. While our representation-level bound successfully decouples generalization from parameter-space capacity, it leaves open a crucial question: how does SGD reliably build this clean local class geometry in the first place? A natural next step is to investigate this mechanism through the emerging lens of “learning mechanics” [Simon et al., 2026], exploring whether the formation of certifiable class geometry can be derived as a predictable, macroscopic observable governed by the fundamental dynamics of the training process.

9

Acknowledgments and Disclosure of Funding This work was supported by the Laboratory for AI Security Research (LASR). The views expressed in this paper are those of the authors and do not necessarily reflect the position of LASR or His Majesty’s Government.

References Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International conference on machine learning, pages 254–263. PMLR, 2018. Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651–1686, 1998. Peter L Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525–536, 2002. Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of machine learning research, 3(Nov):463–482, 2002. Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017. Mathieu Bazinet, Valentina Zantedeschi, and Pascal Germain. Bound to disagree: Generalization bounds via certifiable surrogates, 2026. URL https://arxiv.org/abs/2602.23128. Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849–15854, 2019. Avrim Blum, Adam Kalai, and John Langford. Beating the hold-out: Bounds for k-fold and progressive cross-validation. In Proceedings of the twelfth annual conference on Computational learning theory, pages 203–208, 1999. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929–965, 1989. Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499–526, 2002. Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 9650–9660, 2021. Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597–1607. PmLR, 2020. Eugenio Clerico, Tyler Farghly, George Deligiannidis, Benjamin Guedj, and Arnaud Doucet. Generalisation under gradient descent via deterministic pac-bayes. arXiv preprint arXiv:2209.02525, 2022. Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21–27, 1967. Nan Ding, Xi Chen, Tomer Levinboim, Soravit Changpinyo, and Radu Soricut. Pactran: Pac-bayesian metrics for estimating the transferability of pretrained models to classification tasks. In European Conference on Computer Vision, pages 252–268. Springer, 2022. 10

Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, 2017. URL https://arxiv.org/abs/1703.11008. Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario Marchand, and Jean-Francis Roy. Risk bounds for the majority vote: From a pac-bayesian analysis to a learning algorithm. arXiv preprint arXiv:1503.08329, 2015. Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225–1234. PMLR, 2016. Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5–13, 1993. Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=SJgIPJBFvH. Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. In Proceedings of the tenth annual conference on Computational learning theory, pages 152–162, 1997. Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European conference on computer vision, pages 491–507. Springer, 2020. Simon Kornblith, Jonathon Shlens, and Quoc V Le. Do better imagenet models transfer better? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2661–2671, 2019. John Langford and Robert Schapire. Tutorial on practical prediction theory for classification. Journal of machine learning research, 6(3), 2005. Sanae Lotfi, Marc Finzi, Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and Andrew Gordon Wilson. Pac-bayes compression bounds so tight that they can explain generalization, 2022. URL https://arxiv.org/abs/2211.13609. David A McAllester. Some pac-bayesian theorems. In Proceedings of the eleventh annual conference on Computational learning theory, pages 230–234, 1998. Vaishnavh Nagarajan and J Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905.13344, 2019. Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021. Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on learning theory, pages 1376–1401. PMLR, 2015. Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrallynormalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 2017. Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, et al. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07193, 2023. Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652–24663, 2020. María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor, and Csaba Szepesvári. Tighter risk certificates for neural networks, 2021. URL https://arxiv.org/abs/2007.12911. 11

Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? CoRR, abs/1902.10811, 2019. URL http://arxiv.org/abs/1902. 10811. Matthias Seeger. Pac-bayesian generalisation error bounds for gaussian process classification. Journal of machine learning research, 3(Oct):233–269, 2002. Matthias Seeger, John Langford, and Nimrod Megiddo. An improved predictive accuracy bound for averaging classifiers. In Proceedings of the 18th International Conference on Machine Learning, pages 290–297, 2001. Jamie Simon, Daniel Kunin, Alexander Atanasov, Enric Boix-Adserà, Blake Bordelon, Jeremy Cohen, Nikhil Ghosh, Florentin Guth, Arthur Jacot, Mason Kamb, Dhruva Karkada, Eric J. Michaud, Berkan Ottlik, and Joseph Turnbull. There will be a scientific theory of deep learning, 2026. URL https://arxiv.org/abs/2604.21691. Khoat Than and Dat Phan. Non-vacuous generalization bounds for deep neural networks without any modification to the trained models, 2025. URL https://arxiv.org/abs/2503.07325. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. Guillermo Valle-Pérez and Ard A Louis. Generalization bounds for deep learning. arXiv preprint arXiv:2012.04115, 2020. Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pages 11–30. Springer, 2015. Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via nonparametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733–3742, 2018. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. Shuofeng Zhang and Ard Louis. Position: Many generalization measures for deep learning are fragile. arXiv preprint arXiv:2510.18934, 2025. Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: A pac-bayesian compression approach, 2019. URL https://arxiv.org/abs/1804.05862.

12

A

Appendix / supplemental material

B

Related work

While the history of generalization theory spans VC and uniform-convergence analyses, PAC learning, Rademacher complexity, margin and norm-based bounds, algorithmic stability, PAC-Bayes, compression, and modern non-vacuous deep-network certificates [Vapnik and Chervonenkis, 2015, Bartlett and Mendelson, 2002, Valiant, 1984, Blumer et al., 1989, Bartlett et al., 1998, Bartlett, 2002, McAllester, 1998, Hardt et al., 2016, Neyshabur et al., 2015, Bartlett et al., 2017, Arora et al., 2018, Dziugaite and Roy, 2017], we focus on a smaller universe: computable numerical certificates for a fixed trained predictor. In that narrower sense, our proof template is closer to the classical hold-out tradition than to global capacity measures. Practical prediction theory has long emphasized that fresh-sample error, combined with a sharp concentration inequality, already yields useful guarantees [Langford and Schapire, 2005]. The same perspective extends naturally to K-fold and progressive validation [Blum et al., 1999], leave-one-out and algorithmic-stability analyses [Kearns and Ron, 1997, Bousquet and Elisseeff, 2002], and modern SGD-based stability bounds [Hardt et al., 2016]. Our cross-fit analysis is squarely in this lineage: the mathematics is intentionally elementary, relying on held-out Bernoulli errors, cross-fitting, and KL concentration. The unusual step is the object being evaluated—a simple k-NN rule in the learned representation [Cover and Hart, 1967]. The strongest computable non-vacuous certificates for deep networks have mostly come from PACBayes and compression. Classical PAC-Bayes work established general-purpose risk bounds for randomized predictors [McAllester, 1998, Seeger et al., 2001, Seeger, 2002], and modern deeplearning instantiations include spectrally normalized or localized certificates with increasingly tight numerical performance [Neyshabur et al., 2017, Dziugaite and Roy, 2017, Pérez-Ortiz et al., 2021]. A parallel line certifies models through description length, pruning, or compression [Hinton and Van Camp, 1993, Arora et al., 2018, Zhou et al., 2019, Lotfi et al., 2022]. These methods are the natural numerical baselines for any new certificate, but they typically reason through parameter-space perturbation, posterior complexity, or compressibility. A positioning nuance important here is that PAC-Bayes is not only a parameter-space story: function-space and marginal-likelihood PAC-Bayes analyses also exist [Valle-Pérez and Louis, 2020, Zhang and Louis, 2025]. Our contribution is therefore not “the first non-parameter-space bound” in the broadest sense, but a particularly simple representation-space certificate based on held-out error, agreement, and stability. A smaller recent literature has moved closer to certifying the exact deployed deterministic predictor. [Nagarajan and Kolter, 2019] derive deterministic PAC-Bayes bounds via noise resilience, and [Clerico et al., 2022] study deterministic PAC-Bayes bounds along gradient-descent trajectories. [Than and Phan, 2025] obtain non-vacuous bounds for unmodified trained networks through an a priori data partition rather than post-hoc stochastic perturbation or compression. Our results belong to this deterministic family, but the route is different: instead of certifying the predictor through weight perturbations, trajectory quantities, or partition structure alone, we certify a simple representation-space decoder and then bridge from decoder to the deployed network. A particularly close modern comparator is disagreement-based certification. PAC-Bayesian majorityvote analyses already show that disagreement can be a certificate-relevant quantity [Germain et al., 2015], and [Bazinet et al., 2026] turn this into a general recipe: certify an auxiliary predictor, then use unlabeled disagreement to transfer the guarantee to the target model. Our method is spiritually close to that template, but with less auxiliary machinery. The surrogate is not separately trained; it is a parameter-free k-NN decoder induced by the representation itself. The unlabeled term is also more interpretable: it measures fold/full prediction stability, which reconnects the argument to the classical stability literature [Bousquet and Elisseeff, 2002, Hardt et al., 2016]. Outside the certification literature, the premise that a frozen representation should be judged by simple probes is standard in modern vision. Nearest-neighbor evaluation appears already in non-parametric instance discrimination [Wu et al., 2018] and remains common, alongside linear probing, in transfer and self-supervised learning [Kornblith et al., 2019, Kolesnikov et al., 2020, Chen et al., 2020, Caron et al., 2021, Oquab et al., 2023]. Relatedly, Ding et al. [2022] use PAC-Bayesian quantities to estimate the transferability of pretrained representations. Our contribution is therefore not the observation that k-NN is a useful probe. It is that, with cross-fitting, agreement, and stability, held-out probe performance becomes a formal certificate for the deployed network itself. 13

The empirical claims of this paper also touch two further literatures. First, modern work on double descent studies the interpolation peak in model size, training time, and sample size [Belkin et al., 2019, Nakkiran et al., 2021]. Second, neural-collapse work studies the simple class geometry that emerges in the last layer of trained classifiers, including nearest-class-center behavior [Papyan et al., 2020]. Our Q1 term is not a neural-collapse theorem, but it measures a nearby object: local class geometry sufficient for a simple local classifier to succeed. Likewise, our causal manipulation of Q1 should be read against memorization results showing that deep networks can fit labels without learning useful structure [Zhang et al., 2017]. Finally, unlike post-hoc complexity measures that are primarily judged by correlation with test error across model families [Jiang et al., 2020], our method returns a finite-sample upper bound.

C

Further results

C.1

SiLU comparison CIFAR-10 (n=50k)

CIFAR-100 (n=50k)

Test

MNIST (n=60k) Bound

Gap

Test

Bound

Gap

Test

Bound

Gap

Feedforward networks FFNN ReLU 1.5 FFNN SiLU 1.4

4.9±0.4 4.8±0.1

3.4 3.4

44.6 44.3

95.5±1.1 96.2±1.0

50.9 51.9

75.2 75.4

100.0 100.0

24.8 24.6

Convolutional networks ResNet-18 ReLU 0.6 ResNet-18 SiLU 0.7 ResNet-50 ReLU 0.7 ResNet-50 SiLU 0.9

2.6±0.0 2.7±0.1 2.9±0.2 3.4±0.1

2.0 2.0 2.2 2.5

4.7 5.5 4.3 5.3

13.0±0.3 15.4±0.1 12.4±0.4 14.3±0.2

8.3 9.9 8.0 8.9

21.2 23.0 19.4 21.8

51.1±0.1 58.6±0.2 44.6±0.3 55.9±0.5

29.9 35.6 25.2 34.0

Vision Transformers (from scratch) ViT ReLU 0.9 3.5±0.2 ViT SiLU 0.9 3.7±0.1

2.6 2.8

12.3 12.3

31.9±0.5 32.3±0.3

19.6 20.1

37.1 38.2

99.3±0.2 100.0

62.3 61.8

Model

Act.

Table 3: Cross-fit certification of trained networks (ℓ2 , J=5, δ=δ ′ =0.025). Best bound over k ∈ {1, 3, 5, 7, 11, 15, 21} and j ∈ [5]. Each entry: mean ± std over 3 seeds.

14

Table 4: Desiderata for generalization certificates. Our approach satisfies all desiderata; the stability term is certified empirically from unlabeled data rather than bounded analytically. Method

No stoch. Pretrained Arch.- Diagnoses Det. No mod. No No net training surrogate compress. weights / transfer agnostic repr.

Dziugaite and Roy [2017] Pérez-Ortiz et al. [2021] Zhou et al. [2019] Lotfi et al. [2022] Bazinet et al. [2026] Than and Phan [2025]

✗ ✗ ✗ ✗ ✓ ✓

✗ ✗ ✗ ✗ ✗ ✓

✓ ✓ ✓ ✓ ✗ ✓

✓ ✓ ✗ ✗ ∼ ✓

✗ ✗ ✗ ✗ ✓ ✓

✗ ✗ ✗ ✓ ✗ ✓

✓ ✓ ✓ ✓ ✓ ✗

✗ ✗ ✗ ∼ ✗ ✗

Ours

✓

✓

✓

✓

✓

✓

✓

✓

D

Proofs

D.1

Proof of Theorem 2.2

Proof. Fix j ∈ [J] and k ∈ K. Conditioned on the complement sample S−j , the fold-j parameters (k) θ (−j) = A(S−j ) are fixed, so the decoder hj is a deterministic function (the reference set and the k-NN rule are fully determined by S−j and the pre-specified tie-breaking). The fold points {(xi , yi )}i∈Fj are i.i.d. draws from P that are conditionally independent of S−j . Define the conditional risk (k)

Rj

=

Pr (X,Y )∼P

(k) hj (X) ̸= Y | S−j .

 (k)  (k)
The indicators Zi = 1 hj (xi ) ̸= yi , i ∈ Fj , are conditionally i.i.d. Bernoulli Rj , and their b(k) = 1 P Zi . empirical mean is R j

nj

i∈Fj

We apply the KL concentration inequality for i.i.d. Bernoulli random variables [see e.g. ?, Theorem 1]: for n i.i.d. Bernoulli(p) variables with empirical mean p̂,
Pr kl(p̂∥p) > c ≤ (n + 1) e−nc for all c > 0. Applied conditionally on S−j , with δ ′ > 0 to be chosen, this gives (k)

Pr Rj

(k)

b > kl−1 + Rj ,

log((nj +1)/δ ′ )
nj

S−j

≤ δ′

a.s.

Define the event Ej,k =

n o ′
(k) b(k) log((nj +1)/δ ) . Rj ≤ kl−1 + Rj , nj

c The conditional bound gives Pr(Ej,k | S−j ) ≤ δ ′ a.s., so by the tower property:   c c Pr(Ej,k ) = E Pr(Ej,k | S−j ) ≤ δ ′ .

A union bound over all |K| · J pairs (k, j) gives   c Pr ∃ j ∈ [J], k ∈ K : Ej,k ≤ |K| · J · δ ′ . Setting δ ′ = δ/(|K| · J) yields: with probability at least 1 − δ over Sn , for all j ∈ [J] and k ∈ K, !
log |K| J/δ + log(nj +1) (k) −1 b (k) Rj ≤ kl+ Rj , , nj which is Equation (1). 15

D.2

Proof of Theorem 2.3

Proof. Since φ is fixed by assumption, conditioning on Sref makes the decoder h(k) deterministic (the reference set fixes the k-NN rule). The evaluation points {(xi , yi )}i∈Ieval are therefore conditionally i.i.d. from P .   (k) The error indicators Zi = 1 h(k) (xi ) ̸= yi , i ∈ Ieval , are conditionally i.i.d. Bernoulli(R(k) ), where R(k) = Pr( h(k) (X) ̸= Y | Sref ). The KL concentration inequality applied conditionally on Sref gives, for each k ∈ K:
′
b(k) , log((ne +1)/δ ) Sref ≤ δ ′ a.s. Pr R(k) > kl−1 + R ne By the tower property, each conditional bound promotes to an unconditional one (as in the proof of Theorem 2.2). A union bound over all |K| values of k gives total failure probability at most |K| · δ ′ . Setting δ ′ = δ/|K| yields
log |K|/δ + log(ne +1) ce = , ne which is (2). D.3

Proof of Theorem 2.4

Proof. The indicator decomposition    (k)   (k)  1 fbj (x) ̸= y ≤ 1 hj (x) ̸= y + 1 hj (x) ̸= fbj (x) splits the fold network’s risk into the population decoder error and the population disagreement rate:

(k) (k) (k) (k) Rj = Pr hj (X) ̸= Y | S−j , Dj = Pr hj (X) ̸= fbj (X) | S−j . (k) Conditioned on S−j , both hj and fbj are deterministic, so the fold points {(xi , yi )}i∈Fj are conditionally i.i.d. from P . This produces two families of conditionally i.i.d. Bernoulli indicators:  (k)   (k)  (k) (k)
(k) (k)
Wi = 1 hj (xi ) ̸= fbj (xi ) ∼ Bernoulli Dj , Zi = 1 hj (xi ) ̸= yi ∼ Bernoulli Rj ,

b(k) and D b (k) respectively. with empirical means R j j There are 2 · |K| · J events to control (two families × |K| values of k × J folds). Assigning confidence budget δ ′ = δ/(2 |K| J) to each, the KL concentration inequality applied conditionally on S−j gives
′
(k) b(k) log((nj +1)/δ ) S−j ≤ δ ′ a.s., Pr Rj > kl−1 + Rj , nj (k) b (k) . By the tower property, each conditional bound promotes to an and identically for Dj with D j unconditional one. A union bound over all 2 |K| J events  gives total failure probability  at most δ. Substituting δ ′ = δ/(2 |K| J) into the log yields cj = log(2 |K| J/δ) + log(nj +1) /nj , and the (k) (k) risk decomposition Pr(fbj (X) ̸= Y | S−j ) ≤ Rj + Dj gives (3).

D.4

Proof of Theorem 2.5

Proof. Conditioned on Sn , both fbj and fb(full) are deterministic. The indicators Vr = 1[fbj (xr ) ̸= fb(full) (xr )], r = 1, . . . , m, are therefore conditionally i.i.d. Bernoulli(∆stab ), with empirical mean j U b ∆j . Assign confidence budget δ ′′ = δ ′ /J to each fold. The KL concentration inequality applied conditionally on Sn gives
′′
b U log((m+1)/δ ) Sn ≤ δ ′′ a.s. Pr ∆stab > kl−1 j + ∆j , m By the tower property, Pr(·) = E[Pr(· | Sn )] ≤ δ ′′ . A union bound over j ∈ [J] gives total failure at most J · δ′′ = δ ′ . Substituting δ ′′ = δ ′ /J into the log yields the confidence radius probability ′ log(J/δ ) + log(m+1) /m, which is (6). 16

D.5

Proof of Theorem 2.6

Proof. The proof combines two high-probability events via a union bound. Event 1 (probability ≥ 1 − δ over Sn ). Theorem 2.4 gives, for all j ∈ [J] and k ∈ K:


−1 b (k) b(k) Pr fbj (X) ̸= Y | S−j ≤ kl−1 + Rj , cj + kl+ Dj , cj . (X,Y )∼P

Event 2 (probability ≥ 1 − δ ′ over (Sn , U)). Theorem 2.5 gives, for all j ∈ [J]:

bU ∆stab = Pr fbj (X) ̸= fb(full) (X) | Sn ≤ kl−1 j + ∆j , cm . X∼PX

On the intersection of both events (probability ≥ 1 − δ − δ ′ ), the indicator decomposition (4) gives

Pr fb(full) (X) ̸= Y | Sn ≤ Pr fbj (X) ̸= Y | Sn + ∆stab . j (X,Y )∼P

(X,Y )∼P

Since fbj depends on Sn only through S−j , the first term equals Pr(fbj (X) ̸= Y | S−j ), which is bounded by Event 1. Substituting both bounds yields (7).

E

Experimental Details

This appendix collects all information needed to reproduce the experiments. Section E.1 describes shared ingredients; Sections E.3–E.10 give per-table details; Sections E.6–E.9 give per-figure details; Section E.11 records seeds and compute. E.1

Common setup

Datasets. The supervised experiments use the standard train/test splits of MNIST, CIFAR-10, CIFAR-100, and SVHN. The transfer experiments additionally use the ImageNet ILSVRC-2012 validation set and ImageNet-V2. Evaluation is always deterministic and uses the standard held-out test or validation inputs. Representation and decoder. The representation φ(x) is the final hidden feature vector immediately before the linear readout: the output of global average pooling for convolutional networks, and the class-token embedding after the final layer norm for transformers. The decoder is a majority-vote k-nearest-neighbor rule in ℓ2 representation space, searching over k ∈ {1, 3, 5, 7, 11, 15, 21}. When a single bound is reported it is always the minimum over this grid; the union bound over |K| = 7 values of k is included in the confidence term. Distances are computed in float64; neighbor ties are broken by lowest reference index, and majority-vote ties by lowest class label. Architectures. Table 5 summarizes the four architecture families used in the trained-model experiments. The transfer experiments use pretrained ResNet-18, ResNet-50, WRN-50-2, ViT-B/16, ViT-L/16, DINOv2-B/14, DINOv2-L/14, and DINOv2-g/14, plus a randomly initialized ResNet-18 as a null control (see Appendix F for extraction details). Table 5: Architecture details for trained-model experiments. Family

Repr. dim

Notes

FFNN

D=1024

ResNet-18

D=512

ResNet-50 ViT (from scratch)

D=2048 varies

6 hidden layers, width 1024, no dropout. Activation (ReLU or SiLU) applied before readout. No data augmentation. CIFAR-style stem (3×3 conv, no maxpool) for 32×32 inputs. Standard torchvision stem for 224×224. Same stem conventions as ResNet-18. MNIST: patch 4, embed 192, depth 4, 3 heads, MLP ratio 4, dropout 0. CIFAR-10/100: patch 4, embed 256, depth 6, 8 heads, MLP ratio 4, dropout 0.

17

Table 6: Optimization hyperparameters for the cross-fit experiments (Table 2). All schedules are cosine decay to zero unless stated otherwise. “LS” denotes label smoothing. Family

Dataset

Optimizer

LR −3

Momentum

WD

LS

Batch

Epochs

−5

FFNN

MNIST CIFAR-10 CIFAR-100

AdamW AdamW AdamW

10 5·10−4 3·10−4

– – –

10 2·10−5 2·10−5

0 0 0

512 512 512

150 300 400

ResNet-18

MNIST CIFAR-10 CIFAR-100

SGD SGD SGD

0.05 0.1 0.1

0.9 0.9 0.9

10−4 5·10−4 5·10−4

0 0 0.1

256 128 128

120 200 240

ResNet-50

MNIST CIFAR-10 CIFAR-100

SGD SGD SGD

0.05 0.1 0.1

0.9 0.9 0.9

10−4 5·10−4 5·10−4

0 0 0.1

128 128 128

120 240 300

ViT

MNIST CIFAR-10 CIFAR-100

AdamW AdamW AdamW

5·10−4 5·10−4 5·10−4

– – –

0.01 0.05 0.05

0 0.1 0.1

256 128 128

200 300 300

ViT uses a 10-epoch linear warmup before cosine decay. CIFAR-scale convnets and ViTs use standard random-crop-and-flip augmentation during training; FFNNs use no augmentation. All AdamW runs use default (β1 , β2 ) = (0.9, 0.999).

Optimization recipes. Table 6 lists every hyperparameter for the cross-fit experiments of Table 2. Within each architecture family the recipe is fixed across activations; differences across datasets are shown explicitly. E.2

Cross-fit construction

The cross-fit procedure is shared by Table 2, Figure 1b, and Figure 2. We describe it once here; later subsections refer back. Fold partition. The n training indices are permuted with a fixed fold seed (42) and divided into J=5 contiguous blocks. The partition is a single uniform random permutation; it is not class-stratified. For the balanced datasets used here, a five-way random split still yields large per-class counts in every fold (about 1 200 per class for MNIST, 1 000 for CIFAR-10, 100 for CIFAR-100), so we accept the realized folds without imposing balance. Fold-model training. Each fold model is trained on the 0.8n complement examples using the same architecture, hyperparameters, and number of epochs as the full-data model. The batch size is unchanged, so a fold model executes fewer gradient steps per epoch than the full model. We intentionally do not compensate for this by rescaling epochs or learning rates: the Q3 term is designed to measure the stability of the entire training recipe under fold removal, including any optimization-trajectory change induced by the smaller sample. Certification computation. For each fold j and each k, we compute three quantities on the held-out fold and the independent unlabeled test set: 1. Q1 (decoder error): fraction of held-out fold examples where the k-NN decoder disagrees with the true label. 2. Q2 (decoder–network disagreement): fraction of the same held-out examples where the decoder disagrees with the fold-trained network. 3. Q3 (fold–full stability): fraction of independent test inputs where the fold-trained and full-data networks disagree. Labels are not used. Each empirical rate is converted to a KL upper bound with confidence radii cj =

log(2|K| J/δ) + log(|Fj |+1) , |Fj | 18

cm =

log(J/δ ′ ) + log(m+1) , m

using δ=δ ′ =0.025. The three bounds are summed, and the reported certificate is minj,k of that sum. The optimization over (j, k) is therefore part of the stated certificate, not an unaccounted model-selection step. E.3

Table 1: Transfer certification

No network is trained on the target task. For each target dataset (CIFAR-10, CIFAR-100, ImageNetval, ImageNet-V2), the labeled sample is split 80/20 into reference and evaluation portions using a fixed split seed 42. The k-NN decoder is built on the reference portion and evaluated on the held-out portion. Because the representation is fixed independently of the target data, Q2 and Q3 vanish by construction and the certificate reduces to a single KL bound on the decoder error. The pretrained backbones are listed in Table 1 of the main text. For each backbone, the representation is extracted with a single deterministic forward pass using the preprocessing pipeline bundled with the official weights (see Appendix F). E.4

Table 2: Cross-fit certification of trained networks

This table evaluates the full three-term certificate described in Section E.2, using the hyperparameters in Table 6 and the architectures in Table 5. Each configuration is run over multiple training seeds; the archived runs use seeds {0, 1, 2} for MNIST and CIFAR-10 and seeds {0, 1} for CIFAR-100. The table reports mean ± std over available seeds. E.5

Table 3: Comparison with prior bounds

This table is a positioning summary, not a unified rerun. Baseline entries are copied from the corresponding publications; the “Certified object” column records what each method actually certifies (stochastic net, compressed net, surrogate, or deterministic net). Source of “Ours” rows.

All three “Ours” rows are cross-fit results, not transfer results:

• MNIST: ResNet-18 / ReLU, seeds {0, 1, 2}. • CIFAR-10: ResNet-50 / ReLU, seeds {0, 1, 2}. • CIFAR-100: ResNet-50 / ReLU, seeds {0, 1}. E.6

Figure 1b: Sample-size sweep

A ReLU ResNet-18 is trained from scratch on CIFAR-10 subsets of size n ∈ {1 000, 5 000, 10 000, 20 000, 30 000, 40 000, 50 000}. Each subset is sampled uniformly at random (not stratified). The training recipe is fixed across all subset sizes: SGD, lr 0.1, momentum 0.9, weight decay 5·10−4 , cosine decay, batch size 128, 200 epochs, standard crop-and-flip augmentation. The full cross-fit certificate (Section E.2) is evaluated at each n. Seeds: {0, 1, 2} (training), 42 (fold partition). E.7

Figure 2: Width sweep and double descent

Width-scaled ResNet-18 models are trained on CIFAR-10 at multipliers {1, 2, 2.5, 3, 3.5, 4, 4.5, 5, 6, 8, 10, 12, 16, 20, 24, 32}. (Exploratory runs at 48× and 64× were also trained but are omitted from the figure.) The training recipe is held fixed: SGD, lr 0.1, momentum 0.9, cosine decay, batch size 128, 400 epochs. Label noise is injected at levels 0%, 10%, and 20% by replacing each selected label with a uniformly random class. Seeds: {42, 43, 44}. For each width, the plotted Q1 is the test-set decoder error at the k minimizing Q1 over the grid; Q2 is the decoder–network disagreement at that same k. The figure therefore decomposes test-error into a monotone representation term (Q1) and a readout-agreement term (Q2) that peaks near the interpolation threshold. 19

E.8

Figure 3: Causal geometry intervention

Architecture and training. Six-layer FFNN, hidden width 1024, trained on SVHN with AdamW (lr 10−4 , weight decay 10−5 ), cosine decay, batch size 1024, 5 000 epochs, seed 0. Four activation functions are shown: ReLU, SiLU, GELU, tanh. Regularizer schedule. The representation-repulsion regularizer Lrep (Eq. 8 of the main text) uses a fixed strength λ=2500, identical across all four activations with no per-activation tuning. The coefficient is held at zero through epoch 5, then increased linearly to its full value over the next 500 epochs (i.e. fully active after epoch 505). The ramp allows the network to begin fitting the classification task before the repulsion term dominates. E.9

Figure 4: Weight-noise diagnostic

Base model. This diagnostic uses a separate CIFAR-10 ResNet-18 checkpoint, distinct from the cosine-decay checkpoints used in the certification tables. It is trained with seed 42, SGD, lr 0.1, momentum 0.9, weight decay 5·10−4 , batch size 128, and a multistep schedule with drops by factor 0.2 at epochs 60, 120, and 160. A different schedule was chosen for this diagnostic because the experiment predates the unified cosine-decay recipe adopted for the rest of the paper; the qualitative conclusion (representation degrades more slowly than the readout) is not schedule-dependent. Noise protocol. Isotropic Gaussian noise N (0, σ 2 ) is added independently to every trainable parameter. The noise levels are σ ∈ {10−4 , 3·10−4 , 10−3 , 0.002, 0.003, 0.005, 0.008, 0.01, 0.015, 0.02, 0.03, 0.05, 0.1, 0.2, 0.3, 0.5, 1.0}. For each σ the noisy model is sampled 10 times; both network accuracy and k-NN decoder accuracy (k=5, fixed 40 000/10 000 reference/query split of the CIFAR-10 training set) are averaged over these 10 draws. The second panel fixes σ=0.01 and varies activation function and label-corruption level. This figure is purely diagnostic and does not contribute to any formal certificate. E.10

Table 4: Desiderata comparison

Table 4 is qualitative. It records structural properties of each certification approach (deterministic vs. stochastic, modified training, compression, surrogates, transfer applicability, architecture-agnostic proof, diagnostic interpretability). No experimental detail is needed beyond what is stated in the table itself. E.11

Seeds and compute

Table 7 collects all random seeds. Table 7: Random seeds used in each experiment. Experiment

Training seeds

Fold / split seed

Table 1 (transfer) Table 2 (MNIST, CIFAR-10) Table 2 (CIFAR-100) Table 3 (“Ours”) Figure 1b (sample-size sweep) Figure 2 (width sweep) Figure 3 (causal intervention) Figure 4 (weight noise)

– {0, 1, 2} {0, 1} same as Table 2 {0, 1, 2} {42, 43, 44} {0} {42}

42 42 42 42 42 42 – –

Compute. All runs are single-GPU, single-model jobs. Archived wall-clock metadata covers the following: Figure 1b: ≈ 10.8 GPU-hours (21 runs); Table 2: ≈ 102.7 GPU-hours (64 runs); Figure 2: ≈ 72.9 GPU-hours (162 runs); total logged: ≈ 186 GPU-hours. GPU model names were not recorded in the saved artifacts. Comparable timing metadata were not logged for the transfer, regularizer, and weight-noise experiments. 20

F

Representation extraction details

All representations are extracted by a single deterministic forward pass with no modification to the network. No gradient is computed. Evaluation inputs use deterministic preprocessing only (resize, center crop, channel normalization); no stochastic augmentation is applied at extraction time. Feedforward networks (FFNN). Our FFNNs consist of L fully connected hidden layers followed by a linear classification head. The representation hθ (x) is the post-activation output of the final hidden layer, i.e. the D-dimensional vector that is fed into the softmax classifier. For the experiments in Section 3.2 we use D = 1024 with L = 6 hidden layers. The activation function (ReLU or SiLU) is applied before readout; this is the same activation used throughout the network. ResNets (ResNet-18, ResNet-50, WRN-50-2). The representation is the output of the global average pooling layer, flattened to a vector of dimension D. For ResNet-18, D = 512; for ResNet-50 and WRN-50-2, D = 2048. Concretely, we register a forward hook on model.avgpool and flatten the resulting tensor to shape (B, D). The final fc layer is not part of the representation. Vision Transformers (ViT-B/16, ViT-L/16). For torchvision ViTs, the representation is the class token ([CLS]) extracted after the final encoder layer norm (model.encoder.ln). This yields D = 768 for ViT-B/16 and D = 1024 for ViT-L/16. We register a forward hook on the layer norm and slice the first token: output[:, 0, :]. DINOv2 (DINOv2-B/14, DINOv2-L/14, DINOv2-g/14). DINOv2 models are loaded via torch.hub from the facebookresearch/dinov2 repository. The forward pass returns the classtoken embedding directly, so no hook is needed. Dimensions are D = 768 (B/14), D = 1024 (L/14), and D = 1536 (g/14). All DINOv2 backbones are used frozen with no fine-tuning. Preprocessing. All models use ImageNet-normalized inputs (µ = (0.485, 0.456, 0.406), σ = (0.229, 0.224, 0.225)). For pretrained torchvision models, we use the preprocessing pipeline bundled with the official weights (weights.transforms()), which applies a deterministic resize and center crop to 224 × 224. For DINOv2 and randomly initialized models, we apply Resize(256), CenterCrop(224), ToTensor(), and the same normalization. For CIFAR experiments, models trained from scratch use 32 × 32 inputs with per-dataset normalization; stochastic augmentation (random crop, horizontal flip) is applied during training only and never during feature extraction or bound evaluation. Numerical precision. All ℓ2 distances for k-NN are computed in float64. Tie-breaking is deterministic: for the transfer experiments, a lexicographic perturbation of 10−12 × (reference index) is added to squared distances, so that among equidistant neighbors the one with the smallest index wins. For the cross-fit experiments, ties are broken by stable sort order over reference indices, which produces the same lowest-index-wins rule. Majority-vote ties are broken in favor of the lowest class label (argmax over a vote-count tensor). Computational cost. Feature extraction requires a single forward pass per input per model. The dominant cost is k-NN search, which is O(nref · nquery · D) per value of k. For the largest transfer experiment (ImageNet, nref = 40,000, neval = 10,000, D = 1536), this takes approximately 30 seconds on a single A100 GPU. All k values share the same distance matrix, so the total cost scales linearly in |K| only through the top-k selection step.

21

Related documents

• Training-Free Uncertainty Estimation for Embedding Models#1118355
• Falsification and future performance#697812
• Anchored or Drifting: What Recursive Self-Generation Reveals About Training Data#1202131
• Unambiguous Representations in Neural Networks: An Information-Theoretic Approach to Intentionality#695081
• Loss-Invariant Projections as Passive Probes of Learned Representations#1202614