acceptodds
Under review as a conference paper at ICLR 2027

FlashRLS: Exact Differentiable Second Order Online Learning

Abstract

Second-order online methods adapt to streaming data through sequential matrix updates that are costly on GPUs. Existing chunked implementations handle squared loss, where update weights are known in advance. Logistic and robust losses intro- duce response-dependent weights, making both batching and exact differentiation more difficult. We present FlashRLS, a block formulation that runs local update rules on a small matrix of observation interactions and batches the dense work into matrix products. It covers recursive least squares (RLS), online Newton, recursive Laplace, and robust updates, and we prove that it reproduces sequential execution and its exact gradients. With the forward rule held fixed, exact differentiation improves associative recall by 9.4 points and reduces outlier-regression MSE from 0.085 to 0.057. FlashRLS matches sequential estimators with 38.8×, 42.3×, and 53.3× speedups on Criteo, echo cancellation, and chaotic-system readouts.

Primary area:
optimization
Keywords:
Recursive Least Squares, Preconditioned Delta Net, Adaptive Filtering, Kernel Ridge Regression, Backward pass, Kernel speedups, GPU implementation

Reviews

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

The paper introduces a block version of a 2nd order online learning algorithm for a linear model under a specific form of loss, which extends formulations commonly used in test-time training of language models. The paper establishes differentiability, justifying its use for end-to-end training, and performs controlled experiments to isolate the effects of the proposed method.

Critical strengths
  • Interesting theoretical result that informs the design of a new adaptive version of an RLS algorithm.
  • Informative experiments that support the theory and attribute the predicted and observed effects, e.g. forward vs backward rules
Critical weaknesses
  • Actual performance on the motivating use case of test-time training is weak. Perplexity is very similar to the baseline while throughput is significantly reduced
  • Throughput increases are shown against weak baselines, i.e. a sequential high-precision implementation
  • Minor:
    • Results in the abstract are unattributed or ambiguous. The MQAR benchmark could be named up front, and the baseline method for the 9.4 point increase could be described briefly. The numbers for MSE are also absolute figures that are difficult to interpret without further context of the synthetic regression task, so mentioning the setting and reporting a relative improvement may be a bit more informative.
    • The theory for the applicable piecewise smooth setting is in the appendices instead of the main paper.
Questions for authors
  • How tight is the bound in unnumbered inline inequality from Section 3.5 ∥A^−A∥2≤∥T−1∥2∥R∥2\|\hat A - A\|_2 \le \|T^{-1}\|_2 \|R\|_2 in practice?
3 comments
AuthorsOpenReview ↗

Response to reviewer GC6c

Thanks for the thoughtful review! We agree that FlashRLS is not yet throughput-competitive with optimized learned-memory layers, but we think the results show a more interesting accuracy–throughput tradeoff than perplexity alone suggests.

In our 50M-parameter Gated KalmaNet experiment trained on 1B SlimPajama tokens, exact reads recover 6.4 ± 1.2 MQAR points under weaker regularization, while maintaining comparable perplexity and reducing read error from 1.6×10⁻² to 5×10⁻⁵. More broadly, weaker regularization preserves low-variance feature directions that can carry useful associative information, but makes the system harder to solve accurately. Gated KalmaNet (Peng et al., CVPR 2026) identifies this tradeoff, and MesaNet (von Oswald et al., ICLR 2026) demonstrates the broader value of regression-based learned memories. Our near-duplicate-key experiment illustrates the benefit: at κ≈10⁶, direct reads achieve 98% recall versus 22% for CG-30. This suggests that accurate direct solves could enable learned memories to retain finer distinctions without relying on strong regularization, although throughput remains a limitation.

We also want to highlight Criteo, where the adaptive formulation is tested on 45.8M real-world examples. FlashRLS achieves better logloss than Adagrad and FTRL (0.4630 vs. 0.4698 and 0.4716), and higher AUC (0.7885 vs. 0.7810 and 0.7795), while matching sequential online Newton at 38.8× lower runtime. This demonstrates practical benefits beyond language-model test-time training.

Regarding the speedup baselines, Appendix K.4 identifies the tokenwise PyTorch/autograd implementation. We also compare custom GPU Householder, Givens, and pivoted QR implementations in Section 4.3 and Appendix N, reporting 3.9–61.2× speedups across the tested configurations.

For the Section 3.5 bound, we conducted a small additional numerical experiment using fp32 triangular solves against fp64 references, across chunk sizes C = 16–128 and incoming covariance condition numbers 1–10⁶. For response-adaptive logistic Laplace at C = 64, the median ratio of actual reconstruction error to its residual bound was 0.957–0.993 across five seeds per setting. Thus, the bound is quite tight in the tested regimes.

Finally, we agree that the abstract could identify MQAR and the stopped-curvature baseline more explicitly, and describe the Huber result as a roughly 33% MSE reduction under outlier contamination. We will also move the key piecewise-smooth result from Appendix G.6 into the main text when given the additional space.

Thanks to the authors for the responses. They are useful for better contextualizing the paper and its results.

For the section 3.5 bound, from your description, it sounds like the matrices in the additional numerical experiment are synthetic, instead of coming from actual use cases. Could the authors confirm this understanding? If my understanding is correct, then this experiment would not answer the question. If I misunderstood, then being explicit about how realistic the matrices are would be advised.

As Reviewer aaDw pointed out, the sequential implementation in PyTorch is not meaningful. What optimization and validation was performed on the custom GPU implementations, considering this paper isn't primarily GPU kernel optimization work? Comparing against existing implementations may have been preferable, so that this would not need additional justification.

Thanks for the follow up!

  1. On the Section 3.5 bound, our original controlled-conditioning experiments used synthetic matrices. As requested, we also evaluated the bound along FlashRLS trajectories using MNIST, digits, and breast-cancer features with logistic updates, fp32 recurrent state, an fp64 core, and chunk sizes 16, 64, and 128. The ratio of true direction-solve error to the residual bound has medians of 0.66–0.98 across settings, with a minimum of 0.21. The triangular systems are generally well-conditioned on these trajectories (median condition number 1–3, maximum 23). These show tightness on real-data trajectories and complement the controlled synthetic conditioning tests.

  2. We did look for already existing implementations, but to our knowledge, there isn't a maintained public GPU implementation of QRD-RLS that supports our setup: batched sequential updates, intermediate reads at every observation, and a backward pass. The closest work we found was Andrew and Dingle (2014), which implements GPU QR updating, but not this complete online-learning workload and their code isn't publicly available. Libraries like cuSOLVER and MAGMA provide optimized QR and Cholesky factorizations but applying these naively looks more like this:

Compared to FlashRLS speedup- torch.linalg.cholesky, refactor every row (GPU) 365× FlashRLS time torch.linalg.qr, refactor every row (GPU) 2,110× FlashRLS time So the GPU based implementations we have are significantly more optimized than this.

Repeatedly refactorizing the matrix introduces a lot of unnecessary overhead work. Structure-aware QR updates avoid that cost, but require sequential factor modifications and intermediate solves (this is the method we went for, it gave the best speed optimized baselines.) For response-dependent updates, the local weights are also determined in order, so we cannot precompute a weighted block and factorize it. In terms of hyper optimizing the updates: Even an optimized factor-based implementation must either perform these dependent factor updates and reads in order, or move the dependencies into a smaller interaction system and batch the expensive matrix ops afterward. The "hyperoptimized" baseline would be the construction we have developed in FlashRLS.

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

The authors propose FlashRLS, a block formulation of second-order online learners: RLS, online Newton, recursive Laplace, and robust (Huber) updates. In these learners, each observation’s correction and information weight can depend on the learner’s own response. Within a block of C observations, a small C×C interaction recurrence runs the local rules in order. It yields the exact predictions, uncertainties, and weights that sequential execution would produce. The update directions are then recovered by a lower-triangular solve. The authors prove it reproduces sequential exectuion, which leads to the design of an exact backward pass.

Critical strengths
  1. The formulation is very clean and covers response-dependent weights which existing chunked forms do not handle. Their method is exact (proven) for both forward and backward.

  2. Their gradient study is well-designed. The forward rule is held fixed and only the backward changes. There is a null control (quadratic loss gives an identical gradient), and a dose-response check.

  3. Their method is tested completely and numerically.

Critical weaknesses
  1. The sequential baselines may be weak, which would inflate the headline speedups. The paper doesn’t describe how the sequential baselines are implemented.

  2. No practical gain for learned memory layers, which is the motivation in the introduction.

  3. The main novelty, exact backward through adaptive curvature, is only shown on small synthetic tasks.

4.The main text depends heavily on the long appendix, which the ICLR 2027 guide says reviewers aren’t required to read.

Questions for authors
  1. Can you please explain (or better open source) your implementation of the sequential baselines?

  2. Can you test the exact backward through adaptive curvature using real-world data?

4 comments
AuthorsOpenReview ↗

Review for aaDw

Thanks for the thoughtful review! Glad you appreciate the formulation.

On the baselines, Appendix K.4 describes the tokenwise PyTorch/autograd implementation used for the exact-operator speedups. We also compare against custom GPU Householder, Givens, and pivoted QR implementations in Section 4.3 and Appendix N, with 3.9–61.2× speedups across the tested configurations. We agree these distinctions should be clearer in the main text.

In terms of learned memory practical gains: In our 50M-parameter Gated KalmaNet experiment trained on 1B SlimPajama tokens, exact reads recover 6.4 ± 1.2 MQAR points under weaker regularization, while maintaining comparable perplexity and substantially improving read accuracy. The tradeoff is throughput, which we highlight. We don't claim to outperform optimized first-order memory layers in raw speed, but the results show where accurate second-order updates can improve learned-memory performance.

Our Criteo results also demonstrate the practical value of the adaptive formulation on real-world data. Across 45.8M examples, FlashRLS achieves lower logloss than both FTRL and Adagrad (0.4630 vs. 0.4716 and 0.4698), with higher AUC (0.7885 vs. 0.7795 and 0.7810). It matches sequential online Newton's predictive quality while running 38.8× faster. Unlike the squared-loss experiments, Criteo directly exercises response-dependent curvature at scale.

For adaptive differentiation, the controlled experiments isolate the backward by keeping the forward computation identical. Across ten seeds, the exact backward improves recall by 9.4 points and reduces robust regression MSE from 0.085 to 0.057. We agree that extending this backward-specific comparison to larger real-world nonlinear tasks would strengthen the evidence, although the paper already evaluates the broader method on real-world classification, speech, and language-modeling workloads.

We also agree that some details are buried in the appendix and will bring the key implementation and experimental distinctions into the main text when given the extra page of space.

I thank the authors for their clarifications. The rebuttal mainly agrees with my points rather than resolving them, and as a results I'll keep my current assessment of the work.

My main concern is the sequential baseline. A tokenwise PyTorch/autograd loop is dominated by kernel-launch and framework overhead, so speedups against it mostly measure that overhead rather than the benefit of the block formulation. More clarifications regarding the baseline will help me change my assessment.

Thanks for your response!

We went back and checked our baseline and it is indeed kernel-launch dominated. Thank you for pushing us on this. We will update the numbers in the paper with the following:

On the sequential baselines: We rebuilt and optimized the sequential online Newton implementation using fused Triton kernels, sparse gathers, CUDA graphs, and lower-triangular state updates. We also implemented a stronger delayed-update baseline that reduces repeated writes to the information matrix.

At d = 4096, the optimized sequential implementation runs at 69.0 µs/row in fp64 and 31.8 µs/row in fp32, compared with 3.10 µs/row for FlashRLS. This gives 22.2× and 10.2x speedups, respectively, and 3.9× over the delayed-update baseline. The sequential fp64 kernel is now approximately 9× faster than our originally reported implementation.

We profiled implementations: The sequential kernel achieves around 75% of the H100's peak DRAM bandwidth, and disabling CUDA graphs changes its fp64 runtime by only 7%. The optimized comparison is now mostly limited by memory traffic, not framework or launch overhead.

On real-world adaptive learning: We evaluated FlashRLS on Intel Berkeley Lab temperature data, predicting five minutes ahead while retaining actual sensor battery-failure readings.

Instead of using a manually specified fault detector or state reset, we let the information weight depend on the residual and input features, including sensor voltage and disagreement with neighboring motes. This allows the model to learn when an observation is unreliable.

With these real faults retained, FlashRLS trained with the adaptive backward achieves 2.2 ± 0.2°C RMSE, compared with 2.6 ± 0.2 for robust Student-t Kalman filtering, 4.1 ± 0.6 for Gated DeltaNet, and 4.4 ± 0.6 for Mamba2. The oracle robust batch refit reaches 1.9 ± 0.1. Gated DeltaNet and Mamba2 also receive voltage and neighboring sensor information.

Our earlier 50M-parameter Gated KalmaNet experiment also showed a 6.4 ± 1.2-point improvement in MQAR under weaker regularization. The controlled ten-seed exact-versus-stopped backward experiments separately isolate the contribution of differentiating through adaptive curvature, improving recall by 9.4 points and reducing robust-regression MSE from 0.085 to 0.057. Together with the new real world experiment, we believe this showcases the use of the adaptive backward.

We will update the paper with both experimental results and replace the sequential baseline with the updated baseline.

Finally, we want to thank you for being an engaged reviewer and working with us on our paper, we appreciate the technical feedback and the careful reading of our method.

I thank the authors for their clarifications. All my concerns are addressed, and I'd like to maintain my positive assessment of the work.

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

RLS and other online second order methods update a dense matrix after every observation, which is a bad match for GPUs. Chunked implementations such as DeltaNet work only for the squared loss; the paper introduces FlashRLS which computes updates in blocks (differentiably), and makes it possible for also non-squared loss based learners to benefit from chunked based efficient updates. It tracks how observations in a block interact with each other, and captures this through a CxC table, where a recurrence is used to run the update rules in order and a triangular solve recover intermediate calculations and the output. The paper proves that their chunked computation recovers sequential execution and its gradients. Several experiments are presented, including many that show that it can match the sequential second order udpates much faster, although it is also the case that it remains slower than first-order learners (which is of course not surprising), and overall the empirics actually, do not speak favorably for the use of second order learners.

Critical strengths
  • The adaptive way of doing the recurrence preserves the sequential execution while batching the dense work; this makes the effort GPU friendlier
  • The experiments presented are quite substantial, and the paper reports unfavorable comparisons too.
  • The paper shows differentiability through updates is feasible
Critical weaknesses
  • The algorithmic novelty seems to be much more modest than what the paper claims, e.g., (3) looks like an LDLTLDL^T recursion, and later there's a trailing update in Algorithm 1. The paper does not mention LDL' in the maintext somehow.
  • The writing is unclear, and seems to hide the actual principles behind the construction, because it seems that the bulk of the work could be viewed in a sense through the light of a lazy-pivot version of LDL'
  • The actual technical capability of the paper is shown mostly on toy problems
  • The speed claims and experiments seem to have been done against weak, untuned (and not fully described) baselines.
Questions for authors
  • Isn't Algorithm 1 essentially just an unpivoted LDLTLDL^T factorization of a suitable matrix --- I'm having trouble putting together which precise matrix that is (it could be some kind of innovation matrix / term coming eventually from the Woodbury identity, but I'm not sure).
  • What are the sequential baselines and how are they implemented (fused GPU kernel? simple pytorch? any specific optimizations?)
  • fp64 is used in places -- comments on numerical sensitivity? because afaik rarely is such high floating point budget being used in large models
3 comments
AuthorsOpenReview ↗

Rebuttal to bxmZ

Thanks for reading our paper! Totally agree that LDLᵀ and Woodbury are classical, and we explicitly derive their relationship to FlashRLS in Appendix A. Extending this structure to response-dependent curvature, where each observation changes the geometry used by subsequent updates, while preserving the exact sequential trajectory and its gradients is the main novelty. Unlike fixed-weight LDLᵀ, the weights cannot be determined before factorization because each depends on the preceding predictions and curvature updates. Pivoting across observations would also change the sequential learner. An adaptive LDLᵀ implementation is possible, but would need to handle these same dependencies. FlashRLS does so within a small observation-space core, keeping the dense operations batched.

We also want to clarify the experiments: Beyond synthetic tests, we evaluate 45.8M Criteo examples, real speech echo cancellation, CIFAR-10, and 50M-parameter language models trained on 1B tokens. The 38.8× Criteo speedup matches sequential online Newton's predictive quality, while the exact backward improves MQAR recall by 9.4 points over ten seeds.

For baselines, Appendix K.4 identifies the tokenwise PyTorch/autograd comparison, while Section 4.3 and Appendix N compare GPU Householder, Givens, and pivoted QR implementations. We agree these distinctions should be clearer in the main text, but we did not have too much space given the constraints on page count and the density of our text.

Regarding precision, fp64 is confined to the small (C\times C) core but the full recurrent state remains fp32. This is a deliberate stability–performance tradeoff rather than a requirement for double-precision model states. Our 65,536-observation stability study shows roughly 6×10⁻⁶ relative inverse-state drift, compared with 2.6–5×10⁻⁵ for stabilized sequential inverse updates (Appendix K.2). We also report fp32-core ablations: in echo cancellation, fp32 and fp64 cores achieve comparable ERLE (20.2 vs. 20.3 dB), although fp64 reduces numerical failures. The fp64 core is therefore used for numerical robustness, not because the entire learner requires fp64 computation.

Reviewer_bxmZOpenReview ↗

novelty

The statement about novelty and the argumentation provided are a bit cursory, it is hard to upgrade the score based on that claim.

Thanks for your response! We can try to clarify the novelty a bit more here.

As the initial review correctly summarizes, FlashRLS extends GPU-efficient block execution beyond squared-loss RLS to learners with response-dependent updates. We will make the distinction from prior methods more clear in our rewrite of the work for camera ready.

The important distinction in Eq. 5 is that the information weights and corrections depend on predictions made earlier in the block. Classical block RLS assumes these coefficients are already available. Adaptive LDLᵀ methods can update them sequentially, but still require repeated high-dimensional operations (Bojanczyk et al., 1993; Davis and Hager, 2001; Brust and Gill, 2024).

FlashRLS moves these dependencies into a small observation-space recurrence and batches the expensive matrix operations. This avoids updating the full dense state after every observation while preserving every intermediate prediction and state, as proved in Theorem 3.4. The novelty is in this construction, not the LDLᵀ identity.

We also want to highlight Theorem 4.2, which proves that the backward recovers the exact gradients of the sequential learner at the same order of dense arithmetic as the forward pass. Eq. 12 shows why this matters: an earlier response changes both later predictions and their curvature. The second path disappears for quadratic loss, but not generally for nonlinear losses. Ordinary differentiation through a fixed factorization does not account for this dependency.

We also think the empirical results might've focused too heavily on the LLM methods and we intend to rewrite the paper in a way that makes the better results much more clearly explained. FlashRLS is a general online second-order learning method, not primarily a language-model architecture. The LM experiments are one possible application.

For example:

  • Criteo: On 45.8M examples, AUC improves by 0.0075–0.0090 over Adagrad and FTRL, with 1.45–1.82% lower logloss. These are meaningful differences in CTR prediction (Guo et al., 2017). We also match sequential online Newton at 38.8× lower runtime.
  • Acoustic echo cancellation: Around 20 dB ERLE on real speech, with a 42.3× speedup.
  • Huber regression: Keeping the forward rule fixed, exact backward reduces MSE from 0.085 to 0.057 (33%).

We have also run two additional experiments with separate ~50M-parameter hybrid models for continual adaptation, not language modeling. Only the sequence mixer changes, with parameters matched within 2% and frozen weights during evaluation. Both use five seeds.

  • Simulated robot dynamics: Under 2% Cauchy sensor corruption, adaptive FlashRLS achieves 0.17 MSE versus 0.27 for clipped DeltaNet and 0.61 for KDA, with no diverged runs. Squared RLS reaches 1.8 MSE and diverges in 3/5 seeds. This shows why response-dependent weighting matters.
  • Continual in-context regression: Across 16 overlapping data types, FlashRLS achieves 0.40 retention MSE versus 0.79 for KDA, while reaching 0.15 versus 0.21 on the newest type after 500 examples. It retains earlier information while continuing to adapt.

We know second-order learners are not universally faster than first-order methods, and that isn't our claim. Our contribution is making these sequential, response-dependent updates GPU-efficient without approximating their predictions or gradients. The experiments show why these methods can be worthwhile, particularly with correlated inputs, changing regimes, and outliers.

We hope this clarifies the novelty and practical value. If this response addresses your concerns, we would appreciate it if you could reconsider your score.

References: Bojanczyk et al. (1993); Davis and Hager (2001); Brust and Gill (2024); Guo et al. (2017).

Comments on the paper

1 comment

Dear Reviewers, Area Chairs, and Program Chairs,

We thank everyone for their feedback and discussion. We addressed the concerns about novelty, practical relevance, baseline optimization, numerical stability, and experimental clarity through explanations, new experiments, and much more optimized baselines. We summarize the main responses below:

1. Algorithmic novelty and exactness (responses to bxmZ and aaDw). As bxmZ's initial review recognizes, FlashRLS preserves exact sequential execution while batching the expensive dense operations. We clarified that the novelty is in the observation-space construction that handles response-dependent predictions and curvature without repeated high-dimensional updates, which does not exist in prior RLS literature. Theorems 3.4 and 4.2 establish exact sequential equivalence and exact gradients, respectively. We explained the difference between classical adaptive LDLᵀ methods, with references to prior literature. The remaining novelty concern has not identified any equivalent existing construction or a specific technical flaw in the math/construction.

2. Practical relevance (responses to bxmZ and aaDw). The original submission already evaluated 45.8M Criteo examples, real speech echo cancellation, CIFAR-10, and nonlinear learning tasks. We clarified these results and provided further experiments on robust robot dynamics, continual in-context regression, and real sensor faults to show results on real world data. The MQAR results are especially relevant to the review's concerns about language modeling: associative recall is a known weakness of linear and recurrent sequence model layers, and FlashRLS improves it without changing the underlying language-modeling objective.

3. Stronger baselines and performance (responses to bxmZ, aaDw, and GC6c). In response to concerns about implementation quality, we rebuilt the sequential baseline, improving it by 9×, introduced a tuned delayed-update baseline, and further optimized FlashRLS. At d = 4,096, FlashRLS remains 18.2× faster than sequential FP64, 8.4× faster than sequential FP32, and 3.3× faster than delayed updates. Nsight profiling shows that the optimized sequential implementation is close to its memory-bandwidth floor, establishing that the speedups are not simply due to Python or launch overhead. We have corrected the original headline speedups accordingly.

4. Numerical validation and reproducibility (responses to aaDw, GC6c, and bxmZ). We clarified the use of FP64 only in the small observation-space core, provided stability and precision comparisons, and validated the optimized implementations against FP64 references. We also clarified the differences between sequential, delayed, GPU QR-based, and autograd baselines, and documented which application experiments have not yet been rerun with the new implementations.

Taken together, we hope these results strengthen the evidence for our paper. Several concerns, particularly regarding practical relevance, were already addressed by experiments in the original submission and the additional evaluations, optimized baselines, and profiling now provide further confirmation. We ask the reviewers and ACs to consider these updated responses when evaluating the paper for final decisions. Lastly, we would like to again thank the reviewers for their thorough participation in this review process and we really appreciate the feedback from everyone!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.