acceptodds
Under review as a conference paper at ICLR 2027

FlashDiffusion: Fused Tiled Kernel Spectral Decomposition

Abstract

Diffusion maps, and kernel methods more generally, provide an interpretable nonlinear spectral representation basis for geometric learning. In the geometric limit, small bandwidth, these matrices tend to be high rank and thus require materializing dense Gaussian kernels requires memory. We introduce FlashDiffusion, a matrix-free method that evaluates dense Gaussian kernel blocks in fused GPU tiles and couples the eigensolver to an empirical -flow that selects the finite-sample resolution scale. A continuation over sample size and bandwidth warm-starts increasingly expensive spectral solves from coarser resolutions.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
diffusion maps, manifold learning, kernel methods, spectral methods, GPU acceleration, matrix-free methods, Lanczos eigensolver, bandwidth selection, molecular dynamics

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_e2PGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

In this paper, the authors observe that kernel matrix is too large to be stored or computed. Therefore, they propose to adopt a matrix-free method to avoid storing the whole matrix. However, since the authors do not provide clear experimental evaluation and methodology discussion, I cannot understand how this method can advance the state of the art.

Critical strengths

S1: Storing kernel matrix is definitely the bottleneck in many tasks of kernel methods. This has also been studied extensively in the literature.

S2: It sounds interesting to avoid storing the kernel matrix in the machine learning tasks because this approach can potentially avoid the O(n2)O(n^2) time and space.

Critical weaknesses

W1: The authors do not provide the clear problem definition for what they want to solve. Do they want to optimize the time or space (or both)? Which task do they intend to handle? Without clear definition, I cannot understand this paper.

W2: To my understanding, I can only see that the authors only demonstrate the performance of their methods. No competitor has been provided for comparison.

W3: There is a lack of experimental comparison in this work. Many kernel matrix compression techniques and feature approximation techniques have been proposed in the literature. Howeer, the authors do not have any comparison in the experimental evaluation. Therefore, I cannot judge whether it can really advance the state of the art.

W4: I do not know how this method can be applied to some machine learning task. I think the authors should provide some case studies for illustration.

Questions for authors

Q1: What is the optimization objective of this work? (Reducing the time/space or both.)

Q2: Is there any formal problem definition?

Q3: Can kernel matrix compression/feature approximation methods be used as competitors?

Q4: Can the authors provide the case study to illustrate whether the proposed method can be adopted in some machine learning tasks?

2 comments

We thank the reviewer for their time and for the clear, direct questions. We agree with the central criticism: the original submission did not state its problem, its competitors or its applications clearly enough.

W1: The authors do not provide the clear problem definition for what they want to solve.\color{red}{\text{W1: The authors do not provide the clear problem definition for what they want to solve.}}

We agree that the original submission did not state the problem clearly. The revised introduction (§1) now does so explicitly. We quote the relevant passages here.:

In kernel and manifold-learning methods built on them, e.g. Laplacian-eigenmaps \citep{scholkopf1998_kpca, BelkinNiyogi2003_LaplacianEigenmaps}, nonlinear affinities $\mathsf{K}=\exp_\odot(-\beta\mathcal{H})$ are obtained by elementwise-exponentiation of a pairwise matrix $\mathcal{H}\in\mathbb{R}^{N\times N}$, e.g. squared-distances. Compared with linear methods, e.g. principal component analysis (PCA), they face two difficulties, and our aim is to address both of them. First, kernel-methods introduce a hyperparameter, the bandwidth $\beta>0$, whose choice appears arbitrary. Second, the elementwise-exponential does not factorize and requires ${O}(N^2)$ operations, which appears prohibitive for real-world data compared with ${O}(N)$ for PCA.

In summary. in kernel methods we need to solve the bandwidth β>0\beta>0 (solved by beta-flow) and large NN datasets (this is O(N^2) in space (which we solve matrix-free tech.) and O(N^2) in time (solved by using GPUs). caution is its easy to cheat small \beta\to0 implies easy to solve (not our objective).

W2: To my understanding, I can only see that the authors only demonstrate the performance of their methods. No competitor has been provided for comparison.\color{red}{\text{W2: To my understanding, I can only see that the authors only demonstrate the performance of their methods. No competitor has been provided for comparison.}}

We (in appendix) compared our matrix-free primitive XGEMM to KeOPs, both methods were on par. Now we also have, a brute-force full-N scan in §2.1 as a reference to the ladder is evaluated against in Table 1.

$\color{red}{\text{W3: There is a lack of experimental comparison in this work. Many kernel matrix compression techniques and feature approximation techniques have been proposed in the literature. Howeer, the authors do not have any comparison in the experimental evaluation. Therefore, I cannot judge whether it can really advance the state of the art.}}$

We agree that the paper should make this comparison explicit. These methods target a different regime from ours, and the revision explains why (§1, App.A).

Low-rank methods (Nyström, RFF) are accurate at small β\beta, but resolving many harmonics requires large β\beta, where the kernel is high-rank and compression discards the higher modes (§1). Our ladder uses Nyström only to warm-start each rung; the final solve is exact.

kNN/ANN methods do not provide a true comparison for reasons listed in (App.A).

Existing scalable kernel solvers (KeOps, EigenPro) leave β\beta to the user; GP frameworks (GPyTorch, gp2Scale) do learn it, but by marginal likelihood, which requires labels. We know of no scalable method that selects β\beta without supervision, so our comparisons are against the same exact operator: KeOps for evaluation (App.B; comparable timings, agreement to ∼10−6\sim10^{-6} in fp32), and a brute-force scan of 240 bandwidths at full NN for the ladder (\S2.1, Table~1). We will add a quantitative comparison against Nyström and random features in the final version.

W4: I do not know how this method can be applied to some machine learning task. I think the authors should provide some case studies for illustration.\color{red}{\text{W4: I do not know how this method can be applied to some machine learning task. I think the authors should provide some case studies for illustration.}}

Our primary experiment in the past and current work was Alanine-Dipeptide for use in Molecular Dynamics (MD) simulations. Dynamical systems more generally, finding exact harmonics on empirical data.

Q1: What is the optimization objective of this work? (Reducing the time/space or both.)\color{red}{\text{Q1: What is the optimization objective of this work? (Reducing the time/space or both.)}}

Eq. 1 and 2 of the revised work.

Q2: Is there any formal problem definition?\color{red}{\text{Q2: Is there any formal problem definition?}}

Our objective is to find the "best" harmonics of a kernel matrix. We define "best" as given: X⊂RDX\subset\mathbb{R}^D and α\alpha, find β⋆\beta^\star, the largest-β\beta local maximum of E(β)\mathcal{E}(\beta) before the graph fissions. The leading kk eigenpairs of Pα,β⋆P_{\alpha,\beta^\star} satisfying ∥Pψj−λjψj∥2≤ε\|P\psi_j-\lambda_j\psi_j\|_2\le\varepsilon, using O(ND+Nk)O(ND+Nk) memory and no approximation of the kernel.

Q3: Can kernel matrix compression/feature approximation methods be used as competitors?\color{red}{\text{Q3: Can kernel matrix compression/feature approximation methods be used as competitors?}}

Yes. Low-rank methods are accurate at small β\beta, and our ladder in fact uses the Nystr"om extension to warm-start each rung; but at the β⋆\beta^\star needed to resolve many harmonics the kernel is high-rank, so we keep the exact operator for the final solve (\S1, App.~A).

Q4: Can the authors provide the case study to illustrate whether the proposed method can be adopted in some machine learning tasks?\color{red}{\text{Q4: Can the authors provide the case study to illustrate whether the proposed method can be adopted in some machine learning tasks?}}

See W4.

Reviewer_e2PGOpenReview ↗

Reply to the comment

I have read the rebuttal. However, I still think the authors do not address (or partially address) my comments. As an example, they still do not provide any new experimental results related to W3. As another example, the reply is too brief related to my comment regarding the case studies (W4). Therefore, I do not change the scores.

Reviewer_GcDsOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This manuscript proposes computing relevant eigenpairs for diffusion maps via a "matrix free" (in the sense that the full matrix is never materialized) method for computing the requisite matrix vector products. This is coupled with an efficient method for identification of a reasonable bandwidth parameter.

Critical strengths

None

Critical weaknesses

There are two fundamental issues with this manuscript.

First, it is not clear that there is a substantive contribution here. As alluded to by appendix B there are existing codes/methods (e.g., KeOps) that achieve the same goal and there is no convincing argument that the presented method is, in any way, preferable. While the parameter sweep is structured sensibly for the computational problem and warm-starts can make sense, it is not clear there is anything particularly interesting added over prior work.

The second issue is that the manuscript is essentially one large non-sequitur. There is no flow, a concrete statement of the problem being solved is never really provided, details are introduced haphazardly and for seemingly no reason or out of order (e.g., at the top of page four "first term" of what). This is perhaps best exemplified by the random, out of place comment at the bottom of page three about how something "is retained for API compatibility."

Relevant to the above is that the manuscript is ripe with "Cladueisms" (replace with whatever model was actually used) to the point of being distracting. I have no issue with the use of LLM tools if the resulting manuscript is well written and structured, but this one is not. Notably, the required AI disclosure is not present.

Questions for authors

None

2 comments

We thank the reviewer for the frank assessment.

AI disclosure. The reviewer is right that the original submission omitted the required disclosure; this was our error. The revision includes it (§4): we used Claude Opus for [describe accurately, e.g. "drafting and editing prose, debugging code, and suggesting related literature"]. The authors checked every derivation, line of code and reference, and take full responsibility for the content.

Presentation. We agree the original lacked a clear structure. The revision is rewritten around a stated problem (§1): given data and a normalization, select the bandwidth β⋆\beta^\star and compute the leading eigenpairs of the exact diffusion operator in O(ND+Nk)O(ND+Nk) memory.

Contribution. We agree that matrix-free evaluation is not new, and the revision says so: KeOps, GPyTorch and EigenPro are cited in §1, and Appendix B shows our primitive matches KeOps. Our contribution is unsupervised bandwidth selection by the Dirichlet energy, with an analytic gradient, and its coupling to a warm-started (N,β)(N,\beta) continuation. On a Swiss roll with analytic eigenfunctions, the selected bandwidth recovers the harmonics with R2=1.000R^2=1.000, against 0.1660.166 at another stationary point.

I have perused the revision and the authors’ responses. While minor improvements have been made they do no appreciably address my concerns with the manuscript.

Reviewer_j4xkOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

Diffusion maps require the dense Gaussian kernel, whose O(N2)O(N^2) memory is prohibitive at large NN, and a bandwidth β\beta that sets how many eigenmodes are resolved. The paper computes kernel blocks on the fly in GPU tiles that feed a block Lanczos solver, as in FlashAttention and KeOps. Its proposed "β\beta-flow" doubles β\beta from a variance-based estimate, solves for the requested eigenpairs at each step, and stops at the minimum of a potential that sums a spectral bias term, a finite-sample term, and a barrier against the leading spectral gap reaching floating-point precision. Subsample solves can warm-start larger ones. Experiments cover four million points on a flat six-torus with known eigenfunctions and 256 modes on 750k alanine-dipeptide configurations, from which a linear decoder recovers the backbone dihedrals with errors below 5∘5^\circ.

Critical strengths
  • Exact dense spectra at the scale of millions of points. The method reaches N=222N = 2^{22} in 3.53.5 h on four GPUs, avoiding a ~70 TB kernel, and computes 256256 modes on 750750k configurations in 22 h on eight GPUs (L309–L314, L366–L368).
  • Evidence for a high-rank representation. On the alanine dataset, held-out dihedral error keeps falling beyond m=D=80m = D = 80, from 5.26∘5.26^\circ to 4.86∘4.86^\circ for ϕ\phi and from 4.42∘4.42^\circ to 3.95∘3.95^\circ for ψ\psi between m=128m = 128 and m=256m = 256, and λ256=0.21\lambda_{256} = 0.21 (L420–L428), consistent with a useful representation beyond a low-rank approximation of the 80-dimensional input (L429–L431). On the T6T^6 dataset, the selected bandwidth recovers the analytic eigenspace to 1−overlap≈10−41 - \text{overlap} \approx 10^{-4} at N=222N = 2^{22} without access to the ground truth (L255–L257, L354–L355).
  • A spectrum-based bandwidth criterion. The median rule, self-tuning bandwidths [1], the kernel-sum criterion [2], and dimension-based selection [3] set β\beta from distances, kernel sums, or intrinsic-dimension estimates. The β\beta-flow instead scores each bandwidth by the requested eigenvalues, an effective neighbor count, and the Perron gap relative to dtype precision, so the selected β\beta adapts to the number of modes, the sample size, and the arithmetic precision.

[1] NeurIPS 2004, Zelnik-Manor, Self-Tuning Spectral Clustering.

[2] IEEE TIP 2008, Coifman, Graph Laplacian Tomography from Unknown Random Projections.

[3] DMKD 2020, Lindenbaum, Gaussian Bandwidth Selection for Manifold Learning and Classification.

Critical weaknesses

The β\beta-flow could be more fully validated. Tiled dense evaluation already exists in KeOps [4], as the conclusion acknowledges (L435–L437) but the introduction omits, so the contribution rests on the β\beta-flow. However, all results are reported only at the selected bandwidth. The existing metrics, subspace error on T6T^6 and held-out dihedral error on alanine, could score the other probed bandwidths and those given by the median rule, [1], and [2].

Comparison with approximate methods would strengthen the case for the dense kernel. kNN graphs, Nyström [5], and random Fourier features [6] are not compared in eigenspace error at matched time or memory. Appendix A reports only retained row mass (L796–L798), and Appendix B compares with KeOps only in a timing plot, concluding that both "achieve similar results" (L946).

Ablations would isolate the role of the ladder and the potential. The (n,β)(n, \beta) ladder, which the paper names as its difference from prior work (L437–L439), is neither ablated nor used on alanine (L369–L370). The form of VstatV_\text{stat}, the equal weights, and p=6p = 6, κP=10\kappa_P = 10 (L188) are not justified.

Some reported values need clarification. The value 0.1570.157 is given both as the runtime exponent (L309) and as the slope of β×(N)\beta^\times(N) (L345). Eight dyadic probes from β0≤0.1\beta_0 \le 0.1 reach at most β=12.8\beta = 12.8, not β=276.4\beta = 276.4 (L371). No code is provided.

[4] JMLR 2021, Charlier, Kernel Operations on the GPU, with Autodiff, without Memory Overflows.

[5] NeurIPS 2000, Williams, Using the Nyström Method to Speed Up Kernel Machines.

[6] NeurIPS 2007, Rahimi, Random Features for Large-Scale Kernel Machines.

Questions for authors
  • The β\beta-flow targets the largest bandwidth at which the requested spectrum remains resolvable (L251–L253), but the benefit of this choice is not measured. On alanine, β=276.4\beta = 276.4 is selected after eight probes and β=552.8\beta = 552.8 remains admissible (L371–L372), while decoder errors are reported only at β=276.4\beta = 276.4. What are the held-out dihedral errors at the earlier probes and at β=552.8\beta = 552.8? On T6T^6, how does the subspace error vary with β\beta at fixed NN, and where do the median rule, [1], and [2] fall on that curve?
  • The selection rule requires VbiasV_\text{bias} to fall while VstatV_\text{stat} or VmachV_\text{mach} rises (L202–L205), but no term values are reported. Could the authors plot the three terms and their sum against β\beta for both experiments and state which term determines β×\beta^\times?
  • Each probe is a full eigensolve, and the alanine sweep runs at least ten probes, including β=552.8\beta = 552.8 and β=1105.7\beta = 1105.7 (L371–L372). Does the reported 73157315 s (L367) cover the whole sweep or only the final solve? How many Lanczos iterations does each probe take, and how much do warm starts between probes and the (n,β)(n, \beta) ladder on T6T^6 save compared with cold starts at full NN?
1 comment

We sincerely thank the reviewer for the most detailed and constructive review we received; it shaped the revision directly.

We substantially reworked the paper and formalized the β\beta-flow: the three-term potential is replaced by a single loss, L=−E(β)\mathcal{L}=-\mathcal{E}(\beta), the Dirichlet energy, with an analytic gradient and no tunable weights (Q1, Q2). For alanine dipeptide, Table 1 now separates the bandwidth search from the eigensolve for every staging schedule (Q3).

We also thank the reviewer for pointing us to Lindenbaum et al. (DMKD 2020), whose implied dimension is our energy computed on the unnormalized kernel; we will cite and discuss it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.