Representer explanations rank the training landmarks that most influence a self-supervised representation.
At scale, this ranking rests on up to four stacked approximations of the empirical neural tangent kernel (eNTK). These are random output heads, a parameter sketch, landmark sampling and a coefficient fit.
Existing analyses bound each approximation separately, but none certifies the top-$K$ set against their combined error.
We introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking.
We derive the exact variance of the sketched multi-head eNTK, which matches measurement within $4\%$ where Johnson-Lindenstrauss bounds err by up to $2.5\times$. This yields a high-probability top-$K$ certificate for a fixed coefficient fit, alongside exact residual-trace certificates for discarded spectral mass.
An exact product-variance identity separates kernel error from fit variability and identifies when a larger kernel budget can still sharpen a ranking.
Stochastic Lanczos Quadrature (SLQ) estimates the effective dimension within $0.72\%$ and guides the landmark budget without dense eigendecomposition.
We show that residual mass does not control class coverage, and residual-greedy selection cuts the worst coverage excess of $k$-means++ from $8.5\times$ to $1.55\times$ ($4\times$ on the sketched eNTK).
Cross-view initializers outperform principal-component initialization in five (AUI) to all six (CSI) settings.
Against the KREPES Gauss-Newton solver, CAIRN converges $2.5$ to $11.3\times$ faster, trails by at most $0.31$ points and gains up to $3.14$ points on MNIST.
Together, these results make the reliability of representer explanations measurable and show where approximation budgets are best spent.