acceptodds
Under review as a conference paper at ICLR 2027

Seeing Sparsity: Pattern-Guided Agents for Hardware-Adaptive SpMV Optimization

Abstract

Sparse matrix-vector multiplication (SpMV) performance depends on both matrix sparsity and GPU architecture, making it difficult to choose an effective kernel from structure alone. We present Sparrow, which combines a sparsity-aware decision model with feedback-guided kernel search. The model encodes local nonzero occupancy patches with a Transformer and global matrix statistics with an MLP to rank expert-defined strategies for work mapping and reduction. An agent starts from these strategies, tunes template parameters, and generates or revises kernel code using compilation, correctness checks, target-GPU measurements, and available profiler feedback in a search tree. Within its search budget, it returns the lowest-latency kernel that passes its correctness checks. We evaluate Sparrow on NVIDIA A100 and Hygon DCU GPUs against vendor libraries, a supervised strategy selector, and general-purpose code agents. With GLM, Sparrow achieves a speedup over cuSparse on NVIDIA A100 and a speedup over hipSparse on Hygon DCU. In ablations, throughput falls from 207.38 GFLOPS to 190.33 without sparsity awareness and 134.59 without the agent search. The results show that structure-based strategy selection and target-device feedback both contribute to SpMV kernel performance across the evaluated GPUs.

Primary area:
foundation or frontier models, including LLMs
Keywords:
GPU kernel, Code Generation, High-Performance Computing

Reviews

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

The paper presents optimized SpMV optimizations implementations for different sparsity patterns and GPU architectures. The authors introduce SPARROW, ɑ 2-stɑge kernel generation framework inspired by human cognition: System 1 (based on intuition): sparsity-aware decision model: pairs ɑ multi scale Transformer encoder (different-sized occupancy patches) with ɑ global feature MLP (matrix dims, nnz, etc.) to rank an expert library of 22 SpMV strategy topologies. System 2 (feedback-guided tree search agent): takes the top-ranked strategy and iteratively refines parameters, thread mappings, code structure, correctness validation and execution profiling over ɑ search budget of 10 attempts. The evaluation is done on 291 SuiteSpɑrse matrices. SPARROW achieves 1.74x speedup over cuSPARSE on NVIDIA A-100 and 3.9x speedup over hipSpɑrse on Hygon DCU.

Critical strengths

SPARROW achieves higher speedup compared with existing expert-driven strategies and only hardware guided feedback search. By combining of offline-learned structural prior and hardware-in-the-loop search, it streamlines the search and reduces LLM context/search budget. It achieves good accuracy by encoding both local spatial occupancy patches across multiple grid granularities and global statistics. It achieves 87% compilation success rate vs. general coding agents like Codex (67%) by constraining the agent to expert-designed structured templates.

Critical weaknesses

While the results are promising, this study does not provide any insights on what kinds of sparsity patterns are conducive to what algorithmic strategies. For instance, how do unstructured vs. locally dense or power-law sparsity structures shift thread tile sizes, shared memory usage and load balancing?

The paper also does not provide any information on what are the strategies that were finally chosen for each type of hardware architecture. Are there any lessons learned that can be used to further optimize the search?

In many workloads, the sparsity changes is not known or changes during execution. The overhead of the proposed method is too high to be useful for such cases.

Questions for authors

Are the benefits listed here due to agentic search or due to sparsity-aware expert strategies? Can the agent recover from ɑ suboptimal initial strategy?

What is the chosen layout for SpMV processing? If there are different layouts, is the memory footprint and conversion overhead of specialized storage layouts considered?

How would SPARROW handle dynamic graphs or streamlining workloads where the sparsity pattern in not known apriori? System 2 search loop introduces significant compilation and profiling overhead. Will you then fallback to System 1?

The x axis of Figure 5 is the number of non-zeroes. What are the corresponding sparsity numbers? In other words, how would the figure change if the GFLOPS was plotted against density?

In Figure 5, how close are the SPARROW implementations to theoretical limits? Was a roofline analysis done here?

The compiled candidates are checked against reference SpMV using one deterministic input vector. Is one reference sufficient to check for correctness?

3 comments

W1. Understanding the relationship between sparsity patterns and optimization strategies.

In fact, there is no "golden rule" that can accurately predict the optimal optimization strategy for a given sparse pattern; this depends on both hardware characteristics and the properties of the sparse matrix. Sometimes, even similar sparse patterns may require different optimal strategies.

However, we did encounter some counterintuitive cases where the performance of expert-optimized operators degraded quite severely. As a representative example, consider the boyd1 matrix. Under the storage representation used in our experiments, it contains 93,279 rows and 652,246 nonzeros. Among these rows, 93,261 contain only one nonzero each, while the remaining 18 rows account for 85.70% of all nonzeros, with the longest row containing 93,261 nonzeros. This represents an extremely imbalanced mixture of short and long rows.

This example illustrates an important optimization principle: when a small number of exceptionally long rows dominate the computational workload, partitioning thread blocks by a fixed number of rows can lead to severe load imbalance. Allowing long rows to be distributed across multiple warps and blocks exposes additional parallelism across SMs and improves workload distribution.

The current challenge in optimizing spMV (sparse matrix-vector multiplication) is not a lack of mappings between sparse patterns and optimization strategies, but rather the instability of these mappings. A given matrix might require "Strategy A" when running on an A100 GPU, yet necessitate "Strategy B" on a BW100.

W2. Architecture-specific strategy selection and lessons for future search.

The optimal strategy depends on both the sparsity structure and hardware characteristics, such as warp/wavefront organization, memory hierarchy, and resource constraints. This is precisely why SPARROW combines a hardware-independent structural prior with hardware-in-the-loop optimization.

Our analysis reveals that the two GPUs exhibit common high-level strategy patterns, while the specific levels of work partitioning and parameter granularity need to be adapted to the target device. A common characteristic is that workloads are partitioned according to sparsity structures, with computation organized through a combination of data layouts, local accumulation, and segmented reduction. Two strategies frequently selected on both GPUs are thread-level column partitioning with local reduction and NNZ-based partitioning with bitmaps and warp-level segmented reduction. The differences are mainly manifested at two levels:

  • Different levels of work partitioning: BW100 more frequently selects explicit hierarchical row partitioning from CTAs to threads, whereas A100 tends to favor direct thread-level row processing.
  • More prevalent parameter tuning: Although 65% of the matrices select the same strategy on both GPUs, only 4% have identical complete configurations. The most frequently selected thread block size is 256 on both GPUs, but smaller thread blocks (≤192 threads) are more common on BW100 than on A100 (41% vs. 23%).

Consider the same matrix, ASIC_100k. With the same strategy template and a fixed thread block size of 256, varying only the number of nonzeros (NNZs) processed per thread block yields the following results:

  • A100: A configuration of 16 NNZs is 20.6% faster than one of 3 NNZs.
  • BW100: A configuration of 3 NNZs is 18.4% faster than one of 16 NNZs.

These results demonstrate that the same workload granularities can exhibit opposite performance rankings on different devices, highlighting the importance of hardware-specific parameter tuning even when the same high-level optimization strategy is employed.

The lesson we learnt is that we can envision extending SPARROW with a persistent experience database that records successful strategies, sparsity characteristics, hardware configurations, and profiling results. Such a database could serve as long-term memory for the agent.

W3. Optimization overhead and applicability to dynamic sparsity.

We agree that SPARROW has limited applicability to workloads with frequently changing sparsity patterns, where the optimization overhead may outweigh the performance benefits. However, in many important SpMV applications, such as iterative solvers, algebraic multigrid (AMG), and preconditioned iterative methods, the sparsity pattern is typically available before repeated SpMV executions and remains unchanged across multiple iterations. In such scenarios, the one-time optimization cost can be amortized over sufficiently many SpMV operations. This assumption is also common in existing sparsity-aware optimization approaches, such as SparseZeta. Therefore, SPARROW targets an important class of workloads with reusable sparsity patterns rather than arbitrary dynamic sparsity.

Q1. Are the performance gains attributable to agentic search or sparsity-aware expert strategies? Can the agent recover from a suboptimal initial strategy?

  • Q1.A benefits from agent search or sparsity-aware expert strategies?: As shown in Table.3 in our paper
Agent DesignGFLOPSSpeedup*fast1fast2
Without sparsity-aware190.331.59×86%31%
Without agent134.591.13×62%14%
Sparsity-aware with Agent (GLM)207.381.74×90%40%

Speedup is calculated against cuSPARSE.

The ablation study in this Table addresses this question, SPARROW outperforms both the expert-driven strategies and hardware-feedback-only search, demonstrating that the performance gains arise from the complementary contributions of sparsity-aware structural priors and hardware-guided agentic optimization, rather than from either component alone.

  • Q1.B Can the agent recover from ɑ suboptimal initial strategy? Yes, the agent can recover because the LLM is not restricted to refining the initial strategy. When profiling indicates that a strategy has reached a performance plateau, the agent can explore alternative strategies. For example, for the boneS01 matrix, the agent initially explored a strategy assigning ten nonzeros to each thread. After several iterations without further performance improvement, it switched to an alternative strategy that processes eight rows per warp. The final implementation achieved a 50% performance improvement over the initial strategy.

Q2. What is the chosen layout for SpMV processing? If there are different layouts, is the memory footprint and conversion overhead of specialized storage layouts considered?

  • Sparse matrix have many layout: CSR, COO, ELL, DIA. However SPARROW generates specific layouts and corresponding CUDA kernels for each matrix by employing a combination of techniques: sorting, partitioning into rows or non-zero elements, padding, interleaved storage, and the use of index metadata. which is not a known format but a specific NEW layout for this target matrix. This design philosophy is consistent with prior work such as AlphaSparse [1].
  • We have consider the layout conversion overhead. When a selected strategy requires converting the input matrix into a specialized layout, the conversion cost is accounted for as preprocessing overhead.

Q3. How does SPARROW handle dynamic graphs or streaming workloads where sparsity is not known a priori?

If the sparsity pattern cannot be determined prior to execution, a set of predefined expert heuristics—characterized by conservative upper bounds and aggressive lower bounds—can be employed to initiate the optimization process.

Q4. How would Figure 5 change if GFLOPS were plotted against matrix density?

We agree that plotting performance against matrix density would provide a complementary perspective to the current analysis based on the number of nonzeros.

We have replaced a Fig.5 in revised version with a plot of GFLOPS against matrix density, defined as nnz/(m × n), to further illustrate how performance varies across matrices with different sparsity levels.

Q5. How close are SPARROW implementations to the theoretical performance limits?

Since SpMV is predominantly memory-bandwidth-bound, we conducted a bandwidth-based roofline analysis to evaluate the achieved performance relative to the corresponding theoretical upper bounds.

The roofline figure has been add to the revised version, in Appendix. Fig.8.

The results are summarized below: We define PxP_x as the proportion of matrices that reach above x%x\% of their peak value.

MethodP40P_{40}P60P_{60}P70P_{70}
SPARROW70%32%9%
cuSPARSE19%0%0%

Q6. Is a single deterministic input vector sufficient for correctness validation?

We agree that comparison against a reference SpMV implementation using a single deterministic input vector provides only limited empirical validation and cannot rule out indexing or reduction errors that may be masked by that particular input.

To strengthen correctness validation, we will employ multiple reproducible randomized input vectors. For the final selected kernels, we will perform more comprehensive validation using independent inputs and check output initialization across repeated kernel invocations.

In our current follow-up experiments, the kernels generated are all correct.

REFERENCES

[1]AlphaSparse:Z. Du, J. Li, Y. Wang, X. Li, G. Tan, N. Sun. AlphaSparse: Generating High Performance SpMV Codes Directly from Sparse Matrices. SC 2022. DOI: 10.1109/SC41404.2022.00071。

Thank you for doing the additional experiments. This has helped me understand your method better. My score is till 3.

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

The paper presents SPARROW, a system that generates optimized GPU SpMV kernels for a given input matrix. It works in two stages. It starts by learning from 22 expert optimization strategies (templates). It encodes the sparsity pattern of those as multi-scale occupancy patches processed by a small transformer as well as global row and column statistics processed by an MLP. It is trained to predict the fastest strategy measured on an A100, using SuiteSparse matrices. The second stage features an LLM agent (GLM-5.3 or DeepSeek V4). It starts from the top-ranked strategies and performs a tree search with a couple of compile and measure trials. In each step it tunes parameters, switches templates or rewrites code. The search is guided by compiler output, correctness checks, measured throughput and profiler feedback. The evaluation uses 291 held-out SuiteSparse matrices on an NVIDIA A100 and a Hygon DCU. Baselines are the vendor libraries cuSPARSE and hipSPARSE, SparseZeta (a learned strategy selector) and two general-purpose code agents (Reflexion, Codex). On the A100 SPARROW achieves 207 GFLOPS compared to 119 GFLOPS for cuSPARSE and 196 GFLOPS for SparseZeta. On the Hygon DCU SPARROW achieves 83 GFLOPS compared to 20 GFLOPS for hipSPARSE and 67 GFLOPS for SparseZeta.

Using machine learning to select an SpMV format or kernel matrix structure and size is an established line of work in the community: Sedaghati et al. (2015) and Zhao et al. (2018, PPoPP) are cited; the latter is a CNN on density/histogram images and is used as a baseline. Multiple papers are not cited: Pichel & Pateiro-López (2018, 2019), who classify sparsity-pattern images with CNNs; Nisa et al. (2018); WISE (Yesil et al., 2023), which predicts SpMV performance with ML; Seer (Swann et al., 2024), which selects kernels at runtime and accounts for the cost of feature collection. Replacing a CNN with a multi-scale patch transformer is a small step. And it does not outperform simpler models in the paper's own ablation. Curiously, the strategy library is built from the operators of AlphaSparse (Du et al., 2022). The method section presents it as an "expert-designed strategy library", however the connection to AlphaSparse is only stated in the limitations. The strongest baseline, SparseZeta, is a learned strategy selector in the same AlphaSparse design space. It was published at PLDI 2026 (Du et al., 2026), but the paper uses it as its main learned baseline without citing it at all. LLM agents for kernel generation with hardware feedback are well covered by the related work the paper cites (e.g., STARK, KernelBand, QiMeng-Kernel). SparseRL (ICLR 2026), which generates sparse CUDA kernels from nonzero positions. The paper is cited but not compared against. From my point of view the novelty of the paper can only be seen in the combining of a learned template prior with an LLM refinement loop. This is an integration contribution rather than a new learning method.

Concurrent work: SparseDitto (Li et al., September 2026) uses a learned prior plus an LLM that writes and refines CUDA kernels with profiling feedback. It covers SpMV, SpMM and SpGEMM, compares against AlphaSparse and reports the search cost per matrix.

Cited

  • AlphaSparse: Z. Du, J. Li, Y. Wang, X. Li, G. Tan, N. Sun. AlphaSparse: Generating High Performance SpMV Codes Directly from Sparse Matrices. SC 2022. DOI 10.1109/SC41404.2022.00071
  • Zhao et al. Bridging the Gap between Deep Learning and Sparse Matrix Format Selection. PPoPP 2018. (PPoPP histogram CNN baseline)
  • SparseRL: ICLR 2026 (cited in the paper, not compared against).
  • DASP: Y. Lu, W. Liu. DASP: Specific Dense Matrix Multiply-Accumulate Units Accelerated General Sparse Matrix-Vector Multiplication. SC 2023.
  • D. Merrill, M. Garland. Merge-Based Parallel Sparse Matrix-Vector Multiplication. SC 2016. Not cited:
  • SparseZeta: Z. Du, Y. Liu, X. Chen, Y. Zhao, X. Feng, H. Cui, J. Li. SparseZETA: Intelligent Auto-tuner for Designing High-Performance SpMV Programs. PLDI 2026. DOI 10.1145/3808313. https://pldi26.sigplan.org/details/pldi-2026-papers/70/SparseZETA-Intelligent-Auto-tuner-for-Designing-High-Performance-SpMV-Programs
  • J. C. Pichel, B. Pateiro-López. A New Approach for Sparse Matrix Classification Based on Deep Learning Techniques. IEEE CLUSTER 2018.
  • J. C. Pichel, B. Pateiro-López. Sparse Matrix Classification on Imbalanced Datasets Using Convolutional Neural Networks. IEEE Access, 2019. https://doaj.org/article/49299f3e49b84364ac04669a6466b3ef
  • I. Nisa, C. Siegel, A. Sukumaran Rajam, A. Vishnu, P. Sadayappan. Effective Machine Learning Based Format Selection and Performance Modeling for SpMV on GPUs. IPDPS Workshops 2018. https://easychair.org/publications/preprint/ZlVr
  • S. Yesil, A. Heidarshenas, A. Morrison, J. Torrellas. WISE: Predicting the Performance of Sparse Matrix Vector Multiplication with Machine Learning. PPoPP 2023. DOI 10.1145/3572848.3577506
  • R. Swann, M. Osama, K. Sangaiah, J. Mahmud. Seer: Predictive Runtime Kernel Selection for Irregular Problems. CGO 2024. DOI 10.1145/3640537.3641569. https://arxiv.org/abs/2403.17017
  • W. Liu, B. Vinter. CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication. ICS 2015.
Critical strengths
  • The problem is in general important and practically relevant. The best SpMV kernel depends strongly on both the matrix and the hardware.
  • The split into a structure based prior and on device measurement makes a lot of sense.
  • The evaluation covers two GPU vendors, including a Hygon DCU for which there is little public knowledge and training data available. The A100 trained prior is reused there without retraining and the agent needs to adapt through measurements, which it seems to be doing well.
  • Compilation success is higher than for a generic agent and SPARROW clearly outperforms the Reflexion and Codex agents as shown in the paper.
Critical weaknesses
  • The gains seen be SPARROW are narrow. On the A100, SPARROW improves over SparseZeta from 196 to 207 GFLOPS, i.e., by about 5%. The headline speedups (1.74x, 3.9x) are measured against the vendor libraries not against state of the art. On the DCU, hipSPARSE is a weak baseline: a generic Codex agent with DeepSeek already reaches 3.6x, compared with 3.9–4.2x for SPARROW. There are no specialized hand-written SpMV kernels in the comparison (e.g., CSR5, merge-based SpMV, DASP).
  • There are now equal-budget baselines in the evaluation. No search is evaluated with the same budget of 10 measured trials over the same templates and parameters, e.g., random search or simply measuring the top-k strategies of the prior. AlphaSparse with an equal time budget and SparseZeta followed by 10 trials are also missing. The without sparsity-aware design already reaches 190 GFLOPS, close to SparseZeta's 196. This indiciates that much of the gain comes from measuring a few candidates from the AlphaSparse space. Without these baselines, the contribution of the agent cannot properly be established.
  • The "seeing sparsity" claim is not reflected in the paper. The paper's title and framing emphasize the learned pattern representation, but in Table 2 XGBoost on global statistics clearly beats the Transformer on Top-1 accuracy and is roughly on par for Top-3 and Top-5. There is no end-to-end experiment with XGBoost (or SparseZeta) as the prior. Without the agent, the decision model alone reaches only 134.6 GFLOPS, far below SparseZeta (196).
  • There is no cost analysis. Per-matrix wall-clock time, LLM token cost, compilation time and format conversion time are not reported. A gain of about 5% over a selector that runs in milliseconds has to be weighed against an agentic search that likely takes minutes per matrix.
  • Several experimental protocol details are not given or appear unfinished. For example: "The exact definitions of the two ablated variants and their search budgets are 10." It is unclear what what the Codex and Reflexion baselines receive (templates, prompts, budget); what exactly "without agent" and "without sparsity-aware" mean; whether SparseZeta was retrained for the DCU; how cuSPARSE/hipSPARSE were configured.
  • Statistics are lacking throughout the paper. There is no variance across LLM runs, which matters for a stochastic agent. It is not stated whether speedups are arithmetic or geometric means.
  • The paper does not fit ICLR. The machine-learning contribution (a small patch transformer classifier plus prompt and search design) is thin. Most of the value is systems engineering, which would typically be evaluated against stronger SpMV baselines at venues such as SC, PPoPP or CGO.
Questions for authors
  1. What is the per-matrix wall-clock time and LLM token cost of SPARROW, including search, compilation and format conversion? Essentially: after how many SpMV calls does it pay off relative to SparseZeta and cuSPARSE?
  2. With the same budget of 10 measured trials, how do other strategies fare? What results does one get with a search without an LLM over the same templates and parameters (random search, Bayesian optimization, top-k of your prior or of XGBoost)? How do SparseZeta followed by 10 measured trials and AlphaSparse with a matched budget perform?
  3. Given that XGBoost outperforms the Transformer on Top-1 accuracy and is on par for Top 3/5, what evidence supports the occupancy-patch transformer?
3 comments

Q1(W4). Per-matrix overhead and LLM cost

The average wall-clock time of SPARROW is 142.9 seconds per matrix. Each call to a large language model (LLM) consumes an average of approximately 3,000 tokens. The total token consumption per matrix can be calculated as (3,000 *times C), where C is the average number of LLM invocations per matrix. On an RTX 5090, calculate the geometric mean of GFLOPS for a collection of matrices:

  • SparseZeta takes 3.38 hours and achieves 254 GFLOPS. However, it also requires 5 days of training time.
  • cuSPARSE takes 23.17 minutes and achieves 124 GFLOPS.
  • SPPAROW takes 5.07 hours and achieves 350 GFLOPS.

Q2(W1,W2). Alternative strategies

(1)Comparison with alternative search strategies under matched budgets

To investigate whether SPARROW's improvements come from the search strategy rather than simply from measuring more configurations, we conducted additional experiments comparing different search strategies under the same budget of 10 measured trials.

SearchstrategyPerformance(GFLOPS)
RandomSearch110.75
HillClimbing150.21
LLM-guidedSearch190.33

Under the same measurement budget, LLM-guided search achieves 71.8% higher performance than Random Search and 26.7% higher performance than Hill Climbing. These results support the effectiveness of incorporating LLM-guided decision-making into the search process.

(2)Comparison with AlphaSparse across multiple GPU architectures.

Following the reviewer's suggestion, we further evaluate AlphaSparse and SPARROW on three GPU platforms: NVIDIA A100, Hygon BW100, and NVIDIA RTX 5090.

The following table reports the geometric mean SpMV throughput across the evaluated matrices.

MethodOptimizationtimeA100(GFLOPS)BW100(GFLOPS)RTX5090(GFLOPS)
AlphaSparse360s122.1956.00247.645
SPARROW145s207.3485.76345.279

For AlphaSparse, SPARROW uses approximately 145 seconds of optimization time, whereas AlphaSparse is allocated 360 seconds. Thus, SPARROW achieves higher reported throughput using approximately 40% of AlphaSparse's optimization time.

Approach(10trials)A100(GFLOPS)RTX5090(GFLOPS)
SparseZeta199286
SPARROW208350

Under the same search budget of 10 trials, SPARROW consistently outperforms SparseZeta on both GPU architectures. Specifically, SPARROW achieves 350 GFLOPS on RTX 5090, representing improvements of 22.4% over SparseZeta.The performance advantage is more pronounced on the newer RTX 5090 architecture, highlighting SPARROW's ability to adapt to different hardware architectures.

(3) Robustness to out-of-distribution matrices and limitations of purely model-based selection.

We agree that the average performance improvement over SparseZeta is relatively modest on A100. However, average throughput alone does not fully characterize the robustness of an optimization framework, particularly when the input matrices differ substantially from the training distribution.

In our experiments, training SparseZeta requires approximately five days. Despite this substantial offline training cost, we observe that its predictions can lead to severe performance degradation on certain out-of-distribution matrices.

The following table provides representative examples on A100.

MatrixSPARROW(GFLOPS)SparseZeta(GFLOPS)cuSPARSE(GFLOPS)
boyd1131.045.0196.40
matrix9474.4311.25276.38
aug3dcqp46.550.659.31
bcsstm3512.540.371.87
stat96v2517.16196.41310.26
FullChip233.80190.03192.74

These results show a limitation of relying predominantly on an offline-trained decision model: when the model encounters unfamiliar sparsity patterns, it can lead to substantial performance degradation, while SPARROW can also provide substantial benefits on challenging matrices where static model-based selection fails to generalize.

SparseZeta is constrained by its prior training set, leading to anomalous outputs when encountering unseen matrices—a limitation that raises concerns regarding prediction reliability and generalization. SPARROW, however, addresses this by leveraging hardware feedback to adjust its kernels, thereby avoiding such issues.

(4) Adaptation for new hardwares.

Another important limitation of purely model-based selection is that the relationship between matrix characteristics and optimal optimization strategies depends strongly on hardware architecture.

To further investigate this issue, we examine representative matrices for which SparseZeta achieves good performance on A100 but exhibits performance degradation on BW100.

MatrixSparseZeta(A100)SparseZeta(rtx5090)SparseZeta(BW100)SPARROW(A100)SPARROW(rtx5090)SPARROW(BW100)
ch7-8-b31.98×1.99×0.85×2.42×4.99×1.36×
cont-2012.60×2.03×1.13×2.69×5.00×1.72×
ch8-8-b31.81×1.98×0.92×2.36×4.99×2.81×
CurlCurl_11.34×2.07×0.85×1.91×3.50×1.42×
bfly2.42×2.05×1.06×2.47×5.00×1.56×

The table shows the speedup of rtx5090 and A100 compared to cuSPARSE, and the speedup of BW100 compared to hipSPARSE. SparseZeta underperforms the baseline on the unfamiliar BW100. In contrast, SPARROW achieves ~2x speedups on BW100.

SPARROW outperforms SparseZeta across different architectures, with an even larger performance advantage on the unfamiliar RTX5090 and BW100. This robustness stems from its LLM-guided method, which enables exploration beyond predefined expert strategies to handle challenging corner cases.

Q3(W3). Evidence supporting the Occupancy-Patch Transformer

We conducted additional analyses to evaluate the practical contribution of the learned prior.

End-to-end optimization performance on A100.

modelGFLOPS
XGBoost + agent(10 trials)189
Transformer + agent (10 trials)208

Given the same search budget, Transformer achieves superior end-to-end performance compared to XGBoost.

(W1). compare with human-craft spMV kernel To further evaluate SPARROW against conventional implementations, we extend our comparison to include manually implemented SpMV kernels.

RTX5090:

ApproachGeomean GFLOPSSpeedupfast1fast2
SPARROW350.732.83100%81%
SparseZeta254.562.0598%60%
cuSPARSE124.071.00--
CSR5[1]107.110.8628%2%
Merge-based spmv[2]119.970.9740%2%

BW100:

ApproachGeomean GFLOPSSpeedupfast1fast2
SPARROW83.344.244×100%56%
hipSPARSE19.641.000×--
SparseZETA65.153.317×92%43%
CSR classical[3,5]24.061.225×56%19%
CSR merge_path[4,5]15.250.776×28%21%
HYB[3,5]47.292.408×70%31%

For the BW100 experiments, we use the HIP implementations provided by the Ginkgo 1.9.0 library [5], including its classical CSR, merge-path CSR, and HYB implementations.

(W5). Additional notes

  • The "without agent" configuration employs a local search strategy for exploration.
  • The "without sparsity-aware" configuration omits the use of the aforementioned small model for generating predictive values to guide the agent.
  • SparseZeta: Retraining on a DCU (Deep Computing Unit) would be excessively time-consuming; due to hardware cost constraints, this was not performed.
  • For cuSPARSE, the CUSPARSE_SPMV_CSR_ALG1 algorithm is used with the CSR (Compressed Sparse Row) format.
  • For hipsparse, the implementation directly invokes rocSPARSE csr_adaptive.
  • ALL experimental results are reported using the geometric mean of GFLOPS.

REFERENCES

[1]Weifeng Liu and Brian Vinter. 2015. CSR5: An Efficient Storage Format for Cross-Platform Sparse Matrix-Vector Multiplication. In Proceedings of the 29th ACM International Conference on Supercomputing (ICS '15), 339–350.

[2]Duane Merrill and Michael Garland. 2016. Merge-based Parallel Sparse Matrix-Vector Multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '16), 678–689.

[3]Nathan Bell and Michael Garland. 2009. Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (SC '09), Article 18, 1–11.

[4]Steven Dalton, Sean Baxter, Duane Merrill, Luke Olson, and Michael Garland. 2015. Optimizing Sparse Matrix Operations on GPUs Using Merge Path. In Proceedings of the 2015 IEEE 29th International Parallel and Distributed Processing Symposium (IPDPS), 407–416.

[5]Hartwig Anzt, Terry Cojean, Goran Flegar, Fritz Göbel, Thomas Grützmacher, Pratik Nayak, Tobias Ribizel, Yuhsiang Mike Tsai, and Enrique S. Quintana-Ortí. 2022. Ginkgo: A Modern Linear Operator Algebra Framework for High Performance Computing. ACM Transactions on Mathematical Software, 48(1), 1–33.

Reviewer_bakWOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes using a learned decision model to aid in the understanding of first understanding the nature of the sparsity of a matrix then using that information to make an informed decision on the best strategy to lower that sparsity down to a compatible implementation for fast SpMV kernel processing. The new approach, Sparrow, decomposes the input matrix's nonzero structures into a non-overlapping subset of patches, studies those patches using an encoding process, and combines that knowledge with statistics regarding the matrix dimensions to query an existing strategy library for an initial implementation. The results demonstrate that SPARROW can outperform competing implementations, such as SparseZeta, and exceed the performance of vendor-supplied libraries when available.

Critical strengths
  • The overall quality of the writing is clear and easy to follow, with the motivation of the work clearly stated at the beginning and naturally explained in segments throughout the rest of the text. Good job.
  • The visualizations help to extend the reader's understanding of the processes and the experimental tests clearly illustrating how SPARROW compares not only with the vendor implementation but also with competing solutions.
Critical weaknesses
  • The hardware is a bit dated at this point, but that's no reason to redo the experiments; just a note. Hardware generation doesn't impact my scoring.
  • My biggest concern is a lack of transparency on the end-to-end cost of this process. Did I miss that part in the write-up? How long is all of this analysis taking vs the trade-offs? From the numerical community the code benefit analysis typically centers around the amortized costs of an optimization to verify that the effort was warrant for the amount of reuse that was extracted from the optimized implementation. I understand this domain doesn't have that same trade-off, but how long is training, how long is the generation, and what is the most time-consuming portion of this entire process? I have no idea, and I can't fairly judge the costs of that without some kind of data provided either in the main text or in the Appendix. I feel this should be addressed at some point before moving forward with this manuscript.
  • Quite a few of the design decisions feel a bit arbitrary, where there any alternative design choices were considered? Did the current design provide notable improvement. For example, I believe I've seen methods trying to use GNNs to extract similar structure given the nature proximity to graph data in sparsity. Was that attempted and didn't work? I can't refute the validity of the proposed method, I'm just curious about the origin.
  • I read this sentence "Compiled candidates are checked against reference SpMV using one deterministic input vector, xj = ((jPmod 17) − 8)/8, with float64 reference accumulation test cases and numerical tolerance 10−4 j |Aij xj | + 10−5." Ok, not sure what I'm supposed to do with that information. Maybe those types of details would be better served in the Appendix. Not very useful information for me at least.
Questions for authors

I posed most of the relevant questions in the weaknesses section. Please address my concerns there. Overall, it's an interesting idea and a well-written submission IMO.

1 comment

Q1. SPARROW on newer hardware architecture.

To further validate SPARROW's performance on newer GPU architectures, we conducted additional experiments on an NVIDIA RTX 5090 with CUDA 12.8:

ApproachGeomean GFLOPSSpeedupfast1fast2
SPARROW350.732.83100%81%
SparseZeta254.562.0598%60%
cuSPARSE124.071.000%0%
CSR5107.110.8628%2%
Merge-based spmv119.970.9740%2%

These results show that SPARROW achieves 350.73 GFLOPS on the RTX 5090, outperforming SparseZeta by approximately 37.8% and achieving a 2.83× speedup over cuSPARSE.

Q2. End-to-End Overhead and Amortization Analysis

We agree that the end-to-end cost of SPARROW is essential for evaluating its practical applicability, We have further profiled the entire pipeline and collected the following measurements. While SparseZeta requires five days to train the model.

  1. Offline model preparation

    • Dataset preprocessing(Feature Extraction for Sparse Matrices): about 25 minutes.
    • Model training: about 1.2 minutes.
  2. Per-matrix kernel generation overhead. For each input matrix, the average kernel generation pipeline takes approximately 142.9 seconds. The detailed breakdown is shown below.

StageTime (seconds)
LLM inference25.9
Candidate compilation, benchmarking, and correctness checking84.8
NCU profiling1.8
Startup, preprocessing, and other overhead30.3
Total142.9

The most time-consuming stage is candidate compilation, benchmarking, and correctness checking, accounting for 59.3% of the total generation time. In addition, the total token consumption is approximately 30,000 tokens per input matrix.

  1. Amortization and practical implications

The generation overhead can be amortized over the number of SpMV executions, once a suitable kernel has been generated, it can be reused on the same matrix without repeating the model inference and kernel generation process, which is a common pattern in solver. As also noted by Du et al. (SparseZETA [1]), iterative SpMV workloads in real-world applications, such as molecular dynamics and computational fluid dynamics, often run for minutes or even hours, providing opportunities to amortize the one-time optimization overhead of SPARROW.

Furthermore, developing high-performance kernels for new hardware architectures often requires substantial engineering effort and extensive manual tuning, which can take days or even weeks. In contrast, SPARROW can identify and generate competitive kernels within minutes.

Q3. Design Choices and Alternative Feature Extraction Methods

Our choice of Transformer was motivated by empirical exploration rather than an arbitrary design decision. We investigated both CNNs[2] and GNNs[3] for sparse matrix feature extraction, but neither yielded satisfactory prediction accuracy. The comparative results are shown below:

ModelTop-1 AccuracyTop-3 AccuracyTop-5 Accuracy
Transformer59.45%85.91%92.44%
histogramCNN[2]52.23%76.29%83.51%
GNN[3]49.14%74.23%80.76%

We hypothesize that the graph sampling required for large sparse matrices may discard important connectivity and node-degree information, limiting the effectiveness of GNN-based feature extraction. Similarly, histogram-based CNNs may lose important spatial information during feature aggregation.

Q4. Placement of Low-Level Numerical Validation Details

We agree and will move the details of the deterministic input vector and numerical tolerance to the Appendix, retaining only a brief description of the correctness validation procedure in the main text.

REFERENCES

[1] Zhen Du, Ying Liu, Xionghui Chen, Yanbo Zhao, Xiaobing Feng, Huimin Cui, and Jiajia Li. 2026. SparseZETA: Intelligent Auto-tuner for Designing High-Performance SpMV Programs. Proceedings of the ACM on Programming Languages, 10 (PLDI), 1660–1686.

[2] Yue Zhao, Jiajia Li, Chunhua Liao, and Xipeng Shen. 2018. Bridging the Gap between Deep Learning and Sparse Matrix Format Selection. In Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '18), Vienna, Austria, February 24–28, 2018, 94–108. ACM.

[3] Khaled Abdelaal. 2024. Bridging the Gap Between Sparse Matrix Computation and Graph Models. Ph.D. Dissertation. University of Oklahoma, Norman, OK, USA.

Comments on the paper

1 comment
Area_Chair_KsBsOpenReview ↗

Reminder: Author–reviewer discussion ends today

Dear Reviewers,

As the author–reviewer discussion period ends today (November 18, AoE), please read the authors’ responses, any relevant manuscript updates, and the other reviewers’ comments, and engage with the authors before the deadline.

In particular, please clarify which of your concerns have been addressed and which remain unresolved, and raise any remaining questions promptly so the authors have an opportunity to respond. Even if your assessment is unchanged, a brief follow-up explaining your reasoning would be helpful.

Thank you for your time and thoughtful reviewing!

Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.