- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
Representer explanations rank the training landmarks that most influence a self-supervised representation. This ranking generally rests on several stacked approximations. Existing analyses bound each approximation separately, but none certifies the top-K set against their combined error. The authors introduce CAIRN (Certified Approximation for Interpretable Representer laNdmarks), a framework that carries this error through to the ranking. These results make the reliability of representer explanations measurable and show where approximation budgets are best spent.
The paper is so hard to follow that I am not able to assess the novelties. I think that this paper is suitable for experts only. Hence, I think that the audience for this paper is very limited in its current state.
Critical strengths
Certifying the top-K set against their combined error is a great idea. It is well known that controlling each error separately does not warrant an accurate global bound.
The authors propose a lot of theoretical results to analyse each part of the proposed pipeline. Calculating theoretical bounds is still very appreciable.
Critical weaknesses
This paper is very hard to follow. I think it is suitable for experts only. The authors do not motivate clearly their work. They do not describe carefully KREPES in the main part of the document. The already published methods KREPES seems to be the main source of motivation.
In Theorem 3.1 for example, the authors propose to compute a variance. I do not figure out what is the role of this variance and why its calculation is relevant. The same comment holds for almost of the results.
The paper gives the feeling to be a collection of results without any clear guide. In other words, the problem addressed in the paper is not well stated. It is very complicated to assess the quality of the paper and its potential impact.
Questions for authors
Clarification request.
-
The authors should present KREPES in the main part of the paper to clearly motivate their work.
-
They should also present more clearly the elements composing their pipeline. Figure 1 is a useful addition, but its interpretation remains challenging.
-
They should explain why their calculations are useful instead of adding more and more technical details that do not help to understand the main contributions of the paper.
5 comments
Response to Authors
Thank you for your detailed response.
CW: The motivation for your work has been significantly improved by your revisions. However, the concept of certification remains rather obscure. There is no clear mathematical definition of what you mean by a certification. Your paper is still clearly aimed at experts in the field. As someone who is not an expert in certification, I find many of your results difficult to understand, despite having a substantial background in statistics and probability.
Q1: KREPES is now better explained. I have reread the paper that introduced KREPES:
Maedeh Zarvandi, Michael Timothy, Theresa Wasserer, and Debarghya Ghoshdastidar. Interpretable self-supervised learning via representer landmarks and Nyström approximation. In Forty-third International Conference on Machine Learning, volume 306 of PMLR, 2026.
In my opinion, this paper is still more accessible than yours in its current form. For example, the experiments in the KREPES paper help readers visualize the landmarks. Your paper would benefit from similar efforts to make the underlying concepts and results more accessible.
Q2: The pipeline is now clearer. Thank you.
Q3: To be honest, I appreciate your efforts to provide interpretations of your results, but I am not sure that they help me very much. For example, you write that "Proposition 3.2 separates output-head and sketch randomness, showing how the number of heads and sketch width affect that uncertainty." However, after carefully searching your paper for the term "head", I could not find a definition of this concept. Consequently, the notion of a "Gaussian head" remains a mystery to me.
Without a clear definition, I cannot relate this concept to other existing results in the literature, nor can I properly assess the novelty and relevance of the proposition. The same comment applies to several other results in the paper.
In conclusion, I genuinely appreciate your efforts to improve the paper and address my questions. However, I am still unable to clearly identify the novelty and assess the relevance of your contributions.
Response to Reviewer WxoT
We thank Reviewer WxoT for rereading the paper and for the constructive feedback. Changes are marked in blue in the revised PDF.
CW: What is a certificate? Section 3.2 now defines the term formally. Fix an instance (data, backbone, landmarks, initialization, fitted coefficients, and query), with reference set . A rule based on randomized scores either returns a -landmark set or abstains. It is a -certificate if
with probability over the heads and sketch used in evaluation. Thus, the chance of issuing a wrong set is at most . Here is an error budget chosen by the user before any evaluation draw; all real-data results use , i.e., at most a chance of issuing a wrong set, or confidence per query. The reference is fixed by . The guarantee does not cover landmark-selection variability or compare with the full-training-set ranking.
Theorem 3.3 uses simultaneous Chebyshev intervals: CAIRN issues a set only if every selected landmark's lower bound exceeds every excluded landmark's upper bound. This builds on rank confidence sets (Mogstad et al., 2024), with widths from our exact variance analysis. App. K gives Definition K.2, a five-step procedure, and the three outcomes (certified, uncertified, fit-limited).
Q3: What is an output head? Section 3.1 now opens with an output-heads paragraph that defines it (Definition K.1 in App. K). For inputs , the eNTK is the matrix , where . An output head forms the scalar output , with gradient and scalar kernel
One head needs one backward pass rather than all output Jacobians. A Gaussian head draws ; averaging independent heads estimates without bias. "Head" means a random direction in output space, not a trained layer, a projection head (as in SimCLR or BYOL), or an attention head. This construction follows Lee et al. (2020) and KREPES; it differs from the deterministic sum-output pseudo-NTK of Mohamadi et al. (2023). KREPES uses .
This clarifies Proposition 3.2:
-
Known: Without sketching (), the output-axis variance is the classical Gaussian Hutchinson variance (Hutchinson, 1990; Avron & Toledo, 2011).
-
New: With one SRHT sketch shared across heads, the parameter-axis variance contains , where . This term does not decrease with , so adding heads alone cannot remove all sketch error.
Prior work and what CAIRN adds. Section 3 adds citations, and Table 25 (App. K) lists, for each result, its foundations and what CAIRN adds.
Q1: Making the results easier to see. Figure 2(d) shows two MNIST queries and their top-5 landmark images: one has both top-1 and top-5 certified; the other has top-1 certified, but top-5 abstains because ranks 5 and 6 are too close (gap/radius ). Figure 12 (App. K) shows four more cases, including a wrong sketch-ranked-first landmark for which the certificate abstains. App. C walks through all four stages on 18 points, three classes, and six landmarks.
Scope of real-data results. None of the certificates (Table 5; App. H.3) was incorrect. All use the fixed head of Section 3.1 and are checked against its exact kernel . They control sketch error, not head error (Section 4; Remark H.1); Theorem 3.3 also covers fresh-head randomness.
Novelty and relevance. Prior work bounds individual approximation errors or reports empirical ranking preservation (Hu et al., 2026; Tong et al., 2026). CAIRN propagates approximation uncertainty, including coefficient-fit variability, to the final landmark ranking, and returns a top- set with a stated error probability or abstains. As mentioned in the Introduction, CAIRN’s novelty is not a new sketching primitive but propagating approximation uncertainty, including a coefficient-fit component, to the final landmark ranking. The Introduction summarizes our contributions, both novelties and performance gains: an exact error model, certificates and the fit floor, the residual-versus-coverage distinction, cross-view initializers, and speed-ups of 28-32× on Adult and 3.8-4.3× on MNIST over KREPES.
We would be grateful if the reviewer would reconsider their evaluation in light of these changes.
Response to Reviewer WxoT
We thank Reviewer WxoT for the feedback. We have uploaded a revised paper (new text in blue) that addresses each point. Responses to each critical weakness (CW) and question (Q) follow.
CW (Motivation and overall presentation).
Motivation. The Introduction now starts from a practical question: when can a top-K explanation be trusted, motivated by the need to identify which training examples shaped a self-supervised representation (e.g., to audit or remove problematic data). Representer methods provide ranked explanations, but at scale these rankings depend on randomized approximations, and a small kernel error alone does not guarantee a reliable top-K ranking.
Problem and Roadmap. Section 3 now states the problem formally and introduces a Pipeline paragraph and Roadmap connecting the theoretical results to the final certificate. Section 3.1 defines output heads and Section 3.2 defines the δ-certificate (Definitions K.1–K.2, App. K).
Experiments. Section 4 opens with four questions: whether CAIRN matches KREPES at lower cost (Table 2), whether the error model is accurate (Figure 2), how often top-K sets certify (Table 5, Figure 2(d)), and how initialization and landmark selection affect the explanations (Tables 3–4, Figures 3–4). Table 1 and Table 13 provide the experimental protocol for main-text and appendix results.
Worked example. An illustrative example in App. C (Figure 5, Tables 11–12) walks through all four stages with 18 training points, three classes, and six landmarks.
Q1 (KREPES in the main text). A dedicated Background paragraph at the start of Section 3 now introduces KREPES. It explains its eNTK expansion over landmarks, PCI initialization using the leading eigenvectors of the landmark Gram matrix, one Gauss–Newton step on the SSL loss, and coefficient-displacement ranking.
CAIRN retains the KREPES model and score while adding an error analysis for the resulting rankings.
The full KREPES algorithm is in App. E (Algorithm 1), and its results are reproduced in App. I (Table 23).
Q2 (Pipeline and Figure 1). The Figure 1 caption has been revised, and the new Pipeline paragraph has been added in Section 3 to explain the four stages:
1. Landmark selection: Approximate the eNTK using random output heads and an optional SRHT sketch, then select landmarks using an effective-dimension budget.
2. Coefficient fitting: Fit landmark coefficients to the SSL objective using one of four initializers.
3. Influence ranking: Rank landmarks for each query using kernel similarity and coefficient displacement.
4. Certification and audit: Certify the top-K set when the score intervals separate; otherwise, identify whether coefficient-fit variability limits certification. A deletion audit provides an independent empirical check.
The two arrows beneath the pipeline distinguish the sources of uncertainty: kernel approximation variance determines the score-error radii, while coefficient-fit variance can impose a floor on certification.
Q3 (Practical value of the theoretical analysis). The revised Section 3 introduces each result through the practical question it addresses, with proofs in App. D. Table 25 (App. K) states each result in plain language, with the prior work it builds on and what CAIRN adds.
Theorem 3.1 gives the exact variance of a sketched kernel inner product, quantifying the uncertainty in an approximated kernel entry.
Proposition 3.2 separates output-head and sketch randomness, showing how the number of heads and sketch width affect that uncertainty.
Theorem 3.3 turns the variance estimates into score-error radii and certifies the top-K set when the selected and excluded score intervals separate. The guarantee is conditional on the query, landmark set, and coefficient fit.
Theorem 3.4 shows how variability across repeated coefficient fits can impose a floor on the certificate radius. In that case, a wider sketch alone may not help. This limits the certificate but does not imply that the ranking is wrong.
Sections 3.3 and 3.4 examine two further practical choices: landmark selection, where a small Nyström residual does not necessarily ensure class coverage, and coefficient initialization, including lower-memory Lanczos and cross-view alternatives to dense PCI.
Together, these results connect randomized kernel approximation to a high-probability statement about the final ranking. The practical results support this purpose: paired MoM certifies 83–88% of top-1 explanations on Adult and 32–57% on MNIST, compared with at most 21% for the basic Chebyshev certificate. None of the 274,728 issued certificates disagreed with their corresponding exact-kernel ranking (Table 5, App. H.3).
These changes aim to make the paper accessible beyond kernel-method specialists. We would be grateful if the reviewer would reconsider their evaluation in that light.