cs.DCSep 30, 2026

Reinforcement Learning-Guided Graph Transformations for SpTRSV Optimization

Authors: Buse Yılmaz

Organizations: Department of Computer Engineering, MEF University, Huzur, Maslak Ayazağ̆a Cd., İstanbul, Turkey.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Sparse triangular solve (SpTRSV) is a fundamental kernel in numerous scientific and engineering applications. However, the data dependencies inherent in sparse triangular matrices significantly limit the available parallelism and make efficient workload distribution challenging. Recent graph transformation techniques address these limitations by modifying the dependency graph of the input matrix to improve parallel execution. Existing graph transformation strategies, however, rely on manually designed heuristics, making their development and adaptation to different optimization objectives challenging. This work proposes a reinforcement learning-guided graph transformation framework for SpTRSV, in which graph transformation is formulated as a sequential decision-making problem and an RL agent learns matrix-dependent transformation policies. Experimental results on real-world sparse matrices demonstrate level reductions of up to 94% and reductions of up to 80% in the coefficient of variation of level costs, while modifying only 1.50% of the rows in the highest case. On average, the RL- guided graph transformation achieves a 23% reduction in the number of levels and a 29% reduction in the coefficient of variation of level costs while rewriting only 0.82% of the matrix rows. Although the heuristic strategies generally achieve more aggressive level reduction(between 31% and 46%), the RL-based approach achieves the largest average reduction in the coefficient of variation of level costs, demonstrating its ability to balance competing graph transformation objectives. The results further show that the learned policies can be transferred to previously unseen matrices through curriculum learning and fine-tuning, while zero-shot experiments provide insights into the limitations of generalizing graph transformation policies across different sparsity patterns.

Figures & tables

Figure 1: Graph Transformation Framework Chainbreaker and the relationship between its modules. DG: dependency graph.
Level-specific featuresGlobal features
Computational cost of each levelCurrent and reference CV of level costs
Number of nodes in each levelCurrent and reference CV of level node counts
Source level affinity valuesLevel count
Target level affinity valuesRewrite ratio
Completion ratio of each levelThin levels completion ratio
Thin levelsCritical path ratio
Table 1: Global information about the current graph state and local information describing individual levels.
Matrix NameKind# of rows# of NNZ (L)# of levels
bcsstk17Structural Prob.10,974219,8121,332
bcsstk37Structural Prob.25,50358,3245,030
cfd2Comp. Fluid Dynamics Prob.123,4402,605,6694,357
gearboxStructural Prob.153,7464,617,0754,586
lung2Comp. Fluid Dynamics Prob.109,460273,647479
PR02RComp. Fluid Dynamics Prob.161,0704,174,2362,838
Table 2: Matrices from SuiteSparse Matrix Collection Davis and Hu (2011) that are used in experiments. The number of nonzeros (# of NNZ) are for the lower triangular part of the matrix (L).
 Individual Model
 explained var.explained var.approx_klentropy_lossentropy_loss
 (avg.)(max.)(avg.)(min.)(avg.)
lung20.1270.4320.007-3.890-3.467
bcsstk170.1670.4700.015-6.610-5.574
torso2-8.169E-051.980E-040.002-5.820-5.090
 Curriculum Model
Table 3: PPO learning behavior for individually trained models, curriculum model trained using lung2, bcsstk17 and torso2, and fine-tuned models that use the curriculum model.
initiallung2bcsstk17torso2
num. of levels4791,332513
ALC9143212014
ARL228.5188.23874226.057
AIR1.4999719.03033.95588
CV of level cost6.720.830.82
RL transformationlung2bcsstk17torso2
Table 4: Graph transformation results for training results for individual training, transfer learning and individual inference results.
initialcfd2gearboxvenkat01PR02Rbcsstk37
num. of levels4,3574,5864,1762,8385,030
ALC7081,9794112,884226
ARL28.3333.5314.9556.755.07
AIR12.0129.0313.2624.9221.87
CV of level costs0.570.880.460.370.76
RL transformationcfd2gearboxvenkat01PR02Rbcsstk37
Table 5: Graph transformation results for training results using transfer learning and inference results for transfer learning and zero-shot experiments.
Individual Model Inference
 lung2bcsstk17torso2  
avg. reward1.1150.043-1.076  
cv level cost1.36840.28330.4647  
levels301015420  
thin level ratio0.30.0180.319  
move count250226196144  
Table 6: Inference behavior for individually trained models, the curriculum model and zero-shot learning
 Reduction in num. of levels
matrixnum. of levelsthree Criteria3CRI_ THICKENED3CRI_ AGGRESSIVE2CRIRLTrans
bcsstk17133216%27%33%48%24%
bcsstk37503014%30%46%53%24%
cfd2435710%17%19%33%3%
gearbox458621%37%38%45%16%
lung247946%90%90%90%94%
Table 7: Comparison of RL-based graph transformation strategy (named RLTrans) with heuristic-based graph transformation strategies from Yılmaz (2026) , namely threeCriteria, 3CRI_THICKENED, 3CRI_AGGRESSIVE and 2CRI.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Level costs before and after RL graph transformation.
Figure 3: Level costs before and after RL graph transformation.

Explore similar work

CardsList
May 17, 2026cs.LG

Learning Fill-in Reduction Ordering via Graph Policy Optimization for Sparse Matrices

Matrix reordering in large sparse solvers seeks a permutation that minimizes factorization fill-in to reduce memory and computation. Because the minimum fill-in ordering problem is NP-complete and fill-in is implicit in the sparsity pattern, graph-theoretic heuristics are used. Existing reinforcement learning methods either ignore sparsity patterns--missing the global fill-in--or lack local exact fill-in feedback. We propose a graph policy optimization method, modeling fill-ins from global and local views: both the policy and value networks use a multi-hop graph neural backbone to embed global fill-in; the policy further interacts with symbolic factorization over graphs to extract local, step-level fill-ins, and the resulting feedback is aligned with the value network via an adaptive saturation function to improve convergence. On the SuiteSparse Matrix Collection, our method achieves mean reductions of 29.3 in fill-ins and 31.3 in peak memory usage over state-of-the-art baselines.

Ziwei Li, Shuzi Niu, Huiyuan Li +2

Institute of Software, Chinese Academy of Sciences, Beijing, China

Tensor CompletionSolver IterationsConvex RelaxationOffline Reinforcement LearningFeedback
AskPDF
May 17, 2026cs.LG

Self-Supervised Learning for Sparse Matrix Reordering

Rearranging the rows or columns of a sparse matrix using an appropriate ordering can significantly reduce fill-ins, i.e., new nonzeros introduced during matrix factorization, decreasing memory usage and runtime. However, finding an ordering that minimizes fill-ins is NP-complete. Existing approaches, including graph-theoretic and deep learning methods, rely on surrogate objectives without theoretical guarantees. The Fill-Path Theorem reveals a direct and intrinsic relationship between fill-in generation and the sparse structure of the matrix as path triplet inequalities. Here we first employ a multigrid graph network to capture structural information for each vertex. We then derive a triplet sampling strategy based on inequalities. Finally, we introduce an end-max chain loss function to reduce the number of triplets whose predicted scores satisfy these inequalities. Experimental evaluations on the publicly available SuiteSparse matrix collection demonstrate the superiority of the proposed method in terms of both fill-in reduction and speedup in LU factorization time.

Ziwei Li, Tao Yuan, Fangfang Liu +3

Institute of Software, Chinese Academy of Sciences, Beijing, China

SparsityGraph Edge SparsificationLoss FunctionSelf-Supervised Learning
AskPDF
Jul 28, 2026cs.AR

At-the-Roofline Sparse Tensor Contractions on Vector Processors for Transformer Inference

Fine-grained weight pruning and activation sparsification have emerged as effective approaches for reducing the compute and memory cost of inference for Transformer models. In the moderate-sparsity regime, Gustavson's dataflow provides a natural execution model for exploiting both activation and weight sparsity on vector processors through metadata-driven indexed accumulation. However, existing RVV architectures lack native support for this pattern, forcing kernels to rely on software index decoding and L1-backed indexed memory operations that keep sparse tensor contractions far below their roofline performance bound. We present Ventaglio, a runtime-configurable sparse execution unit coupled with RVV ISA extensions that drives sparse tensor contractions toward their roofline through indexed gather-accumulate-scatter support. Integrated into an open-source vector processing cluster and implemented in 12nm FinFET, Ventaglio accelerates sparse tensor contraction kernels by 6.9–7.4×6.9\text{--}7.4\times over optimized RVV baselines, with only 3.1%3.1\% area overhead for a cluster of tightly-L1 coupled vector processing elements. We build a performance-accurate instruction-level model of the Ventaglio extension, calibrate it against RTL implementation, and leverage it for scale-out performance analysis on a large 4×44\times4 multi-cluster system. Using a DuoGPT-pruned LLaMA-3-8B model with practical 40–60%40\text{--}60\% dual sparsity, Ventaglio achieves 2.40–5.25×2.40\text{--}5.25\times and 2.06–3.16×2.06\text{--}3.16\times speedup over dense baselines during prefill and autoregressive decoding, respectively.

Bowen Wang, Chi Zhang, Diyou Shen +3

*IIS, ETH Zürich, Switzerland · ‡Computing Systems Lab, Huawei, Switzerland · †DEI, Universit`a di Bologna, Italy

Dynamic Sparse AttentionVectorizationTransformer Architectures
AskPDF