acceptodds
Under review as a conference paper at ICLR 2027

Lazy Kernel QR: Adaptive Randomized QR Factorization via Sketched Telemetry

Abstract

QR decomposition underlies randomized range finders, Krylov solvers, low-rank adapters and KV-cache compression. Its dominant cost is the work needed to maintain an explicitly orthonormal . We introduce Lazy Kernel QR (LKQR), which adapts the number of orthogonalization corrections per column to the local geometry of the basis, using a low-dimensional sketched kernel as a telemetry signal. Because the telemetry lives in () and is maintained by a rank-one bordered update, the decision overhead is independent of . We prove exact reconstruction and condition-number and orthogonality bounds that depend on the cumulative laziness ; for a decaying schedule with , is independent of and . Across six machine-learning pipelines—ogbn-arxiv node classification (three GNN backbones, four eigenvector counts), GaLore gradient projection on six pretrained model families, randomized PCA on three datasets, QR-LoRA fine-tuning of three vision backbones, GPM continual learning and Qwen-2.5 KV-cache compression—LKQR removes – of MGS's orthogonalization FLOPs at no measurable downstream loss, where the FLOPs are measured by instrumenting every primitive rather than evaluated from a closed-form formula. On a continual-learning task sequence it also stays within points of the exact orthogonalizer, where fixed truncation loses a third of the accuracy. Finally we fix the operating regime precisely: for consumers that use the emitted basis itself as a metric, the exact orthogonalizer remains the right choice by a wide margin, and LKQR's advantage there is a – reduction in orthogonalization FLOPs rather than a better basis. LKQR is stable where normal-equation methods (CholeskyQR) break down.

Primary area:
optimization
Keywords:
randomized QR, sketched telemetry, adaptive orthogonalization, GaLore, QR-LoRA, KV-cache compression

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_FLRMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Lazy Kernel QR (LKQR), an adaptive randomized QR method for tall-and-skinny matrices. The main idea is to use low-dimensional sketched correlations to decide whether further orthogonalization is needed for each column, rather than using a fixed correction budget. The paper provides reconstruction and conditioning guarantees and evaluates the method on several machine-learning pipelines, including GNNs, GaLore, randomized PCA, QR-LoRA, continual learning, and KV-cache compression.

Critical strengths

1.LKQR provides a simple adaptive alternative to fixed-budget selective orthogonalization. It can reduce unnecessary ambient-space corrections while keeping the monitoring cost low.

2.The experimental evaluation is fairly broad, and the paper also discusses cases where exact orthogonalization is still preferable, which makes the scope of the method clearer.

Critical weaknesses

1.The main concern is novelty relative to SSQR. SSQR already performs sketch-based selective correction, while LKQR mainly replaces the fixed budget with an adaptive threshold and updates residual correlations during the process. The improvement is useful, but the conceptual difference seems somewhat limited.

2.The practical experiments mainly use a constant threshold, while the stronger theoretical guarantee applies to the decaying schedule. The theoretically safer schedule appears to approach full orthogonalization, which weakens the practical speed advantage.

Questions for authors

1.Could the authors provide a direct wall-clock comparison between LKQR and SSQR using a reasonably optimized implementation? Since SSQR is sometimes cheaper in FLOPs, it would be useful to understand whether LKQR provides a practical runtime advantage.

2.How sensitive is LKQR to the choice of threshold tt across different matrix spectra and basis dimensions? In particular, it would be helpful to know whether a single default threshold remains reliable across substantially different problem settings, or whether additional tuning is still required in practice.

Reviewer_EgEAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces a method (LKQR) to accelerate QR decomposition by choosing, at each iteration, whether to orthogonalize the basis vector against preceding vectors. The authors develop a method that decides, during basis construction, whether the newly added basis vector is already sufficiently orthogonal so that othogonalization work can be skipped. They construct a sketch SS of the constructed basis matrix QQ and maintain it at every iteration. The inner products in this sketched space are then used to decide whether a new basis vector should be orthogonoalized against preceding basis vectors or not. The core idea is that maintaining the sketch and evaluating orthogonality in the sketched space is cheap, but still informative of whether a vector might already be sufficiently orthogonal. LKQR preserves exact factorization but allows to trade off exact orthogonality of QQ against faster runtime. Similar methods exist, the novelty in this work seems to be that the computational budget is not fixed in advance but instead adapts to the geometry of the input matrix.

Critical strengths

The problem setup and method are well explained, relevant and seem sensible.

The authors provide intuition and theoretical justification for their design choices. This is important because it shows that their design choices are well founded and give theoretical guarantees. I did not check the proofs in detail.

Moreover, the authors evaluate their LKQR on a wide range of real-world applications and show no degradation in downstream utility of the QR decomposition despite loss of exact orthogonality. This is important because it shows that the method can be used in relevant, practical applications.

The paper is well written and easy to follow, despite the technical nature of its contributions.

Critical weaknesses

Most importantly, the runtime acceleration of LKQR in experiments is reported only with respect to full Gram-Schmidt. I could not find any runtime comparison between LKQR and the other baseline methods such as SSQR. The directly comparable baselines for the runtime-utility trade-off proposed in this paper should include other sketching-based methods. Ideally, runtime comparisons should be reported for all methods already evaluated in the paper.

Moreover, I find Figure 1 very difficult to follow. I appreciate the attempt to illustrate the method, and I think a clear Figure 1 is very helpful here, but I think the current Figure 1 should be simplified.

Questions for authors

Can you please report runtime comparisons between LKQR and all other baseline methods included in the paper? This would substantially strengthen the runtime improvement claim. I vote weak reject only because of this gap in the paper which I think is critical. I am open to increasing my score if the authors can show that their method improves in runtime, not only against full Gram-Schmidt, but also against other sketching baselines.

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

The paper presents an intuitive idea to reduce the FLOPs count of QR, by using a small sketch of a matrix to decide which earlier columns to correct against. It is not a very complex idea, but the writing and presentation need improvements. Figure 1 is really not human-readable. It would be much clearer if a few more lines of math are provided with a simplified and concise flowchart. The paper emphasizes the FLOPs count reduction, but in the empirical evaluation it did not show how the proposed method compares with the baselines in terms of actual runtime on GPUs. Since a lot of heavy computational jobs are run on GPUs, and FLOPs reduction does not necessarily translate into wall-clock time reduction, due to complications with overhead, it is important to illustrate how the proposed method performs in real time on GPUs.

Critical strengths
  • The sketch allows LKQR (the proposed method) to decide which earlier columns need correction without checking every correlation in the full matrix.

  • The paper also shows that skipping corrections preserves exact reconstruction and the column space in exact arithmetic.

  • Overall, the main idea of the paper is sound.

Critical weaknesses
  • The central efficiency claim is not demonstrated at the level that matters in practice. The paper reports no GPU wall-clock comparison for its downstream experiments. Without an actual wall-clock saving comparison, it is hard to judge the practical value of the proposed method.
Questions for authors
  • I'd like to see how GPU wall-clock time compares in the experiments shown in the paper.

  • Also, rework Figure 1 and Figure 2, they are not very readable (Figure 2 is slightly better, but Figure 1 is a real mess). Maybe the authors should ask an LLM to help with writing the paper more clearly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.