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

Problem Statement

As Large Language Models (LLMs) scale to longer context lengths, standard attention mechanisms face quadratic memory and runtime costs. Linear attention methods, such as Gated DeltaNet, address this by maintaining a fixed-size recurrent state. However, recent implementations of Gated DeltaNet (e.g., in Qwen3.5 and KiMi) utilize a chunk-wise parallel strategy to expose parallelism within token sequences. While this removes outer token-by-token dependencies, it introduces a new bottleneck: triangular matrix inversion within each chunk.

Specifically, the chunk-wise update requires computing $T = (I - A)^{-1}$, where $A$ is a strictly lower-triangular matrix. Traditional approaches rely on forward substitution, a sequential algorithm with $k-1$ iterations for a $k \times k$ matrix. This method exhibits limited parallelism and poor hardware utilization on Neural Processing Units (NPUs), as it relies heavily on vector operations rather than dense matrix multiplications. In Qwen3.5-4B, this inversion step accounts for 22%–31% of total cycle costs, with the overhead increasing as chunk size grows.

Furthermore, existing attempts to parallelize this via block-wise decomposition or Neumann series expansion face challenges:

1. Block-wise inversion restricts matrix sizes, limiting available parallelism.
2. Direct Neumann series expansion ($(I-A)^{-1} = \sum A^n$) suffers from numerical instability under finite precision (FP16/INT). Higher-order terms grow rapidly, causing overflow and heavy-tailed distributions that degrade quantization performance.

Methodology

The authors propose a Multiplication-Only (MatMul) approximation algorithm tailored for strictly lower-triangular matrices in chunk-wise linear attention. The core philosophy is "Good Enough Is Optimal": exact inversion is unnecessary if the approximation preserves the model's accuracy while enabling hardware-efficient execution.

The method consists of three key components:

1. Low-Order Truncated Neumann Expansion

Instead of computing the full finite expansion (which requires $k$ terms), the method truncates the Neumann series after a small number of terms $N$ ($N \ll k$).

• Theoretical Basis: Lemma 3.1 establishes that for a strictly lower-triangular matrix $A$, the $n$-th power $A^n$ only contributes to the $n$-th sub-diagonal and below. Consequently, the inverse's energy is concentrated near the main diagonal.
• Implementation: The initial approximation is $T^{(0)} = \sum_{n=0}^{N} A^n$. Empirical analysis shows that a low order (e.g., $N \approx 3$) captures the majority of the inverse structure, avoiding the computational cost of full expansion.

2. Structural Diagonal Masking

To address the numerical instability caused by higher-order terms growing rapidly (potentially exceeding FP16/INT ranges), the authors apply a diagonal mask $M^{(N)}$.

• Mechanism: The mask sets entries to zero if their distance from the main diagonal exceeds the truncation order $N$ (i.e., $M_{ij} = 1$ if $i-j \le N$, else $0$).
• Effect: This removes "extraneous" large-magnitude values in the lower-left region of the matrix that contribute little to the inverse's accuracy but cause overflow and quantization noise. This makes the approximation robust for low-bit integer (INT) quantization.

3. Parallel Residual Correction

Truncation and masking introduce approximation errors. To recover accuracy without re-introducing sequential dependencies, the authors employ a parallel residual correction scheme.

• Formulation: Instead of iterative updates ($T^{(m+1)} = T^{(m)} + T^{(m)}R^{(m)}$), which are sequential, the method reformulates the correction as an accumulation of matrix powers of the residual error $E = I - (I-A)T^{(0)}$.
• Execution: The final approximation is computed as $T \approx T^{(0)} \sum_{s=0}^{S} E^s$. This allows the entire process to be executed using only Matrix Multiplication (MatMul) kernels, fully exposing parallelism to NPUs.

Adaptation to Quantization

The method is specifically tuned for low-bit inference (e.g., INT8/INT16). The authors observe that increasing the truncation order $N$ (e.g., from 3 to 4) drastically expands the dynamic range of values, leading to severe quantization errors. By limiting $N$ (e.g., $N=3$) and compensating with residual steps ($S=8$), the method balances numerical stability, accuracy, and efficiency.

Key Contributions

1. Approximate-but-Sufficient MatMul-Only Inversion: The paper replaces sequential triangular inversion with a low-order Neumann approximation combined with structured masking and parallel residual correction. This maps the dominant computation to MatMul kernels, preserving accuracy under both floating-point and integer quantization.
2. Hardware-Efficient NPU Execution: By eliminating triangular-solve dependencies, the formulation exposes dense matrix multiplications. This achieves up to 5× kernel-level speedup on NPUs and reduces decode-layer overhead by 20% without accuracy degradation.
3. Robustness under Low-Precision: The approach mitigates dynamic range expansion in repeated matrix power operations, enabling stable inference with INT16 and INT8 quantization where previous methods fail or degrade significantly.

Experimental Results

The method was evaluated on the Qwen3.5 family of models (0.8B to 9B parameters) and the Qwen3-Next model.

• Accuracy:
  • Single Kernel: The method maintains high Signal-to-Noise Ratio (SNR) in FP16 and INT16, comparable to FP32 baselines.
  • End-to-End: Perplexity (PPL) and downstream task accuracy (MMLU, CSR, RealWorldQA) match the Flash Linear Attention (FLA) baseline across all model scales.
  • Quantization: Under W4A16 quantization, the proposed method preserves performance significantly better than standard FLA, particularly on RealWorldQA, with negligible differences in PPL and MMLU scores.
• Performance:
  • Speedup: Achieved 5.2×, 4.2×, and 4.6× speedups for matrix inversion kernels at chunk sizes 32, 64, and 128, respectively.
  • Overhead Reduction: Reduced the matrix-inverse cost from ~22–31% of total cycles (in FLA) to ~5–9%, resulting in overall cycle reductions of 18.1% to 24.6%.
• Ablation Studies:
  • Low-order truncation alone ($N=3$) causes divergence in low precision; however, adding the diagonal mask and residual correction ($S=8$) restores stability and accuracy.
  • For a 64×64 matrix, the optimal configuration is $N=3$ and $S=8$.

Significance and Claims

The paper claims to offer an efficient and hardware-friendly solution for scalable linear attention, specifically targeting the bottlenecks of long-context modeling on NPUs.

• Scalability: By enabling larger chunk sizes (up to 128) without the sequential penalty of forward substitution, the method supports more efficient long-context processing.
• Deployment: The approach facilitates the deployment of long-context models on resource-constrained devices (mobile and edge platforms) by reducing compute and energy requirements through integer-friendly approximations.
• Trade-off Philosophy: The work emphasizes that "exact" inversion is not required for high-quality model performance. By accepting a "good enough" approximation that aligns with hardware capabilities (MatMul-heavy, parallel), the method achieves optimal practical performance.

The authors note that while the method improves efficiency, it relies on careful evaluation to ensure reliability, particularly under low-precision constraints, and does not claim to solve all numerical instability issues in all potential architectures, but specifically targets the Gated DeltaNet context.