On the Robustness of Sparse Randomized Sketching to FP16 Rounding on GPUs
Abstract
Randomized sketching replaces large matrices with smaller surrogates that preserve geometry for downstream numerical linear algebra. Sparse sketches promise faster formation than dense projections, but irregular GPU atomic updates become costly when each input row contributes to several output rows, as in SparseStack. FP16 accumulation halves sketch storage and update traffic, relieving cache pressure. How much does this rounding affect sketch geometry and downstream accuracy? For SparseStack with four nonzeros per column, cuSPARSE's FP16 path is slower than its FP32 baseline. Our custom kernel instead pairs FP32 inputs and signed products with packed FP16 vector atomic accumulation, turning lower precision into substantial gains. On NVIDIA H200, it forms complete sketches up to 1.91× faster than our FP32 baseline and up to 1.58× faster than cuSPARSE FP32. Under stated independence and range assumptions, random sketch signs cancel round-to-nearest conversion-error cross terms, giving expected squared Frobenius error no greater than ideal stochastic rounding. We assess accumulation empirically. At a sketch dimension of twice the number of input columns, the least-squares pipeline is $1.44−1.47\times$ faster than FP32, with median paired residual increases below 0.4%. Rescaling exposes range limitations and cases where stochastic conversion degrades accuracy.
Related
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
- Computing Robustness to Sparse Diagonal Uncertainty
- L-PASSO: Adaptive Log-penalized Variable Selector, with Sparse Selection and Robustness to the Pilot Estimator
- Generative modeling via hierarchical tensor sketching
- Fast matrix-vector products in tensor-train format via structured sketching
BibTeX
@misc{jeendgar2026robustness,
title = {{On the Robustness of Sparse Randomized Sketching to FP16 Rounding on GPUs}},
author = {Aryaman Jeendgar and Clément Flint and Hartwig Anzt},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.20195},
eprint = {2606.20195},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.20195},
}
RIS
TY - UNPB
TI - On the Robustness of Sparse Randomized Sketching to FP16 Rounding on GPUs
AU - Aryaman Jeendgar
AU - Clément Flint
AU - Hartwig Anzt
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2606.20195
UR - https://arxiv.org/abs/2606.20195
AB - Randomized sketching replaces large matrices with smaller surrogates that preserve geometry for downstream numerical linear algebra. Sparse sketches promise faster formation than dense projections, but irregular GPU atomic updates become costly when each input row contributes to several output rows, as in SparseStack. FP16 accumulation halves sketch storage and update traffic, relieving cache pressure. How much does this rounding affect sketch geometry and downstream accuracy? For SparseStack with four nonzeros per column, cuSPARSE's FP16 path is slower than its FP32 baseline. Our custom kernel instead pairs FP32 inputs and signed products with packed FP16 vector atomic accumulation, turning lower precision into substantial gains. On NVIDIA H200, it forms complete sketches up to 1.91× faster than our FP32 baseline and up to 1.58× faster than cuSPARSE FP32. Under stated independence and range assumptions, random sketch signs cancel round-to-nearest conversion-error cross terms, giving expected squared Frobenius error no greater than ideal stochastic rounding. We assess accumulation empirically. At a sketch dimension of twice the number of input columns, the least-squares pipeline is $1.44−1.47\times$ faster than FP32, with median paired residual increases below 0.4%. Rescaling exposes range limitations and cases where stochastic conversion degrades accuracy.
ER -