Lazy Kernel QR: Adaptive Randomized QR Factorization via Sketched Telemetry

QR decomposition underlies randomized range finders, Krylov solvers, low-rank adapters and KV-cache compression. Its dominant cost is the $\mathcal{O}(n{l}^2)$ work needed to maintain an explicitly orthonormal $Q$. 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 ${\mathbb{R}}^k$ ($k\ll n$) and is maintained by a rank-one bordered update, the decision overhead is independent of $n$. We prove exact reconstruction and condition-number and orthogonality bounds that depend on the cumulative laziness $T$; for a decaying schedule $t(i)=\alpha /i^{1+\beta }$ with $\alpha /\beta <1$, $T\le \alpha /\beta$ is independent of $n$ and $l$. 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 $4.2\times$–$44.1\times$ 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 $3.2$ 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 $1.8\times$–$7.9\times$ reduction in orthogonalization FLOPs rather than a better basis. LKQR is stable where normal-equation methods (CholeskyQR) break down.