When Good Enough Is Optimal: Multiplication-Only Matrix Inversion Approximation for Quantized Gated DeltaNet

• URL: http://arxiv.org/abs/2606.06034v1
• Date: Thu, 04 Jun 2026 11:29:05 GMT
• Title: When Good Enough Is Optimal: Multiplication-Only Matrix Inversion Approximation for Quantized Gated DeltaNet
• Abstract summary: Matrix inversion in chunk-wise parallel linear attention is a major bottleneck for long-context modeling.<n>We propose a fast, Matrix multiplication (MatMul)-based algorithm tailored for strictly lower-triangular matrices.<n> Experiments on Qwen3.5-family models demonstrate up to 5$times$ kernel-level speedup and a 20% reduction in decode-layer overhead.
• Score: 10.055354775930487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix inversion in chunk-wise parallel linear attention is a major bottleneck for long-context modeling, particularly on NPUs, where forward-substitution-based methods exhibit limited parallelism and poor hardware utilization. We propose a fast, Matrix Multiplication (MatMul)-based algorithm tailored for strictly lower-triangular matrices arising in chunk-wise linear attention. Motivated by the rapid growth of Neumann-series terms and the diagonal concentration of the inverse matrix, we employ a truncated Neumann expansion with structural masking and parallel residual correction to eliminate sequential dependencies. We further extend our method to low-bits INT by mitigating the dynamic range expansion arising from repeated matrix power operations, and adapt the approximation order and residual step to the chunk size to minimize computational cost while preserving the model's accuracy. Experiments on Qwen3.5-family models demonstrate up to 5$\times$ kernel-level speedup and a 20% reduction in decode-layer overhead, while preserving accuracy under both floating-point and low-precision inference. Our method offers an efficient and hardware-friendly solution for scalable linear attention.

Related papers

• Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers [35.36704326614983]
  Models that incorporate linear attention layers with the so-called Delta-Rule involve the inversion of triangular matrices as a core sub-routine.<n>This work provides a systematic analysis of both direct and iterative triangular inversion algorithms, targeting methods that are rich in matrix products.<n>Performance benchmarks on NPUs reveal up to $4.3times$ speed-up against the state-of-the-art implementations of SGLang for triangular matrix inversion.
  arXiv  Detail & Related papers  (2026-05-20T15:51:32Z)
• Bridging the Gap between Sparse Matrix Reordering and Factorization: A Deep Learning Framework for Fill-in Reduction [8.282571271774573]
  Sparse matrix reordering can significantly reduce the fill-in during matrix factorization.<n>Finding a minimal fill-in ordering is known to be an NP-hard problem.<n>We propose a deep learning framework to minimize a fill-in surrogate function based on spectral embedding.
  arXiv  Detail & Related papers  (2026-05-17T09:15:42Z)
• GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal $k$-sparse GLMs [7.079949618914198]
  Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations.<n>Existing methods for solving these relaxations are computationally intensive, limiting their scalability.<n>We develop a unified proximal framework that is both linearly convergent and computationally efficient.
  arXiv  Detail & Related papers  (2026-03-01T22:26:09Z)
• Orthogonal Finetuning Made Scalable [92.34573849209238]
  Orthogonal finetuning (OFT) offers highly parameter-efficient adaptation while preventing catastrophic forgetting, but its high runtime and memory demands limit practical deployment.<n>We identify the core computational bottleneck in OFT as its weight-centric implementation, which relies on costly matrix-matrix multiplications with cubic complexity.<n>We propose OFTv2, an input-centric reformulation that instead uses matrix-vector multiplications (i.e., matrix-free computation), reducing the computational cost to quadratic.<n>These modifications allow OFTv2 to achieve up to 10x faster training and 3x lower GPU memory usage without
  arXiv  Detail & Related papers  (2025-06-24T17:59:49Z)
• An Alternative Graphical Lasso Algorithm for Precision Matrices [0.0]
  We present a new/improved (dual-primal) DP-GLasso algorithm for estimating sparse precision matrices. We show that the regularized normal log-likelihood naturally decouples into a sum of two easy to minimize convex functions one of which is a Lasso regression problem. Our algorithm has the precision matrix as its optimization target right at the outset, and retains all the favorable properties of the DP-GLasso algorithm.
  arXiv  Detail & Related papers  (2024-03-19T02:01:01Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Fast Coherent Point Drift [4.369046007546103]
  Coherent point drift (CPD) is a classical method for nonrigid point set registration. By introducing a simple corresponding constraint, we develop a fast implementation of CPD. Experimental results in 3D point cloud data show that our method can significantly reduce burden of the registration process.
  arXiv  Detail & Related papers  (2020-06-11T09:35:23Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.