Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers

Aleksandros Sobczyk, Gioele Gottardo, Christos K. Matzoros, Mirko De Vita, Filip Skogh, Anastasios Zouzias, Jiawei ZhuangarXiv 2026 · arXiv

TL;DR

Inverting triangular matrices is a critical but computationally slow and numerically risky step in modern Delta-Rule Linear Transformers like Qwen3.5. This paper systematically analyzes hardware-friendly inversion algorithms and introduces a Mixed Recursion (MXR) method that delivers up to a 4.3× kernel speedup on NPUs while fully preserving end-to-end model accuracy.

What Problem Does This Paper Address?

Linear attention mechanisms (such as DeltaNets and Gated Delta Networks) are rapidly becoming the architecture of choice for handling massive context lengths efficiently without the quadratic memory cost of traditional softmax attention. To maximize hardware utilization on modern AI accelerators, these models process sequences in parallel "chunks."

However, this chunking strategy introduces a tricky mathematical requirement: computing the inverse of a unit-diagonal lower triangular matrix for every single chunk. This operation presents two major challenges:

  1. Computational Bottleneck: It is highly sequential by nature, often consuming up to 40% of the total layer runtime.
  2. Numerical Instability: Triangular inversion is notoriously sensitive to floating-point errors. When implemented naively in low-precision hardware (like float16 or bfloat16), errors compound rapidly, completely destroying the model's reasoning capabilities. For instance, an unstable inversion method can cause Qwen3.6's MMLU accuracy to plummet from a strong 75.6% down to a useless 0.2%.
Figure 1: Left: Runtime breakdown of single GDN layer. Right: Accuracy drop in end-to-end benchmark evaluation due to inversion errors accumulation.

Methods

The authors evaluate several direct and iterative triangular inversion methods designed to maximize matrix multiplications, which run efficiently on modern hardware matrix cores:

  • Matrix Column Sweep (MCS): Highly stable but slow, requiring $O(n)$ sequential matrix multiplications.
  • Cayley-Hamilton Method (MCH): Fast ($\approx 2\log(n)$ matmuls) but catastrophically unstable for larger matrices due to exponential error growth.
  • Bunch-Hopcroft (MBH): A divide-and-conquer recursive algorithm that achieves logarithmic stability.
  • Mixed Recursion (MXR): The paper's primary contribution. MXR strategically combines the best of both worlds: it uses the ultra-fast but unstable MCH method only for tiny, constant-sized diagonal blocks (up to 16×16) where errors remain safely bounded, and then switches to the stable MBH recursion to assemble the final matrix inverse.
  • Newton-Schulz (NS) Iteration: An iterative method driven entirely by matrix products, requiring a carefully tuned number of iterations to reach stability.

Datasets

The algorithms were evaluated using a 10-subject subset of the MMLU (Massive Multitask Language Understanding) benchmark to accelerate end-to-end testing. The evaluation spanned three state-of-the-art large language models:

  • Qwen3-80B-A3B
  • Qwen3-35B-A3B
  • Qwen3.5-0.8B

Key Insights and Ideas

  • Delta-Rule Matrices are Naturally Well-Conditioned: While random triangular matrices usually suffer from exponentially terrible condition numbers, the authors prove that matrices arising from Delta-Rule layers have a condition number bounded by $n^2$. This mathematical guarantee explains why low-precision quantization can succeed in these architectures.
  • Harnessing Instability: The Cayley-Hamilton (MCH) method is traditionally avoided in numerical analysis due to horrific stability properties. However, the authors realized it can be safely isolated as a low-level subroutine for very small blocks, unlocking massive hardware parallelism without triggering catastrophic error accumulation.
  • Float16 Outperforms Bfloat16 for Inversion: Counterintuitively for some deep learning workflows, float16 is preferred over bfloat16 here. Because bfloat16 sacrifices mantissa bits to achieve a larger exponent range, it introduces higher precision errors during matrix inversion.

Key Results

  • Kernel-Level Speedups: The proposed MXR algorithm achieved up to a 4.3× speedup at the kernel level compared to the state-of-the-art Triton implementations in SGLang, and a 3× speedup over TileLang.
  • Layer-Level Impact: When fused into a single "mega-kernel" encompassing the entire Gated Delta Network (GDN) layer, MXR yielded a 2.5× end-to-end layer speedup.
GDN layer execution time comparison
  • Accuracy Preservation: Unlike unstable baselines, the MXR method fully maintains baseline accuracy across all tested Qwen models.
  • Iterative Thresholds: For the iterative Newton-Schulz method, the authors demonstrated that at least 12 iterations are required to stabilize end-to-end model accuracy; fewer iterations lead to severe performance degradation.
Figure 3: Number of Newton-Schulz iterations (x-axis) versus matrix inversion error using fp32 (left y-axis) and MMLU aver- age accuracy (right y-axis). Chunk size C = 64.

Limitations and Future Work

While the paper provides strong empirical evidence and builds on existing proofs for related problems, a formal, rigorous proof of end-to-end numerical stability for the Newton-Schulz iteration specifically applied to unit-diagonal triangular matrices remains an open theoretical question.

Summary updated

Abstract

Linear attention has emerged as a cornerstone for efficient long-context architectures, as evidenced by its integration into state-of-the-art open-source models including Qwen3.5/3.6, Kimi Linear, and RWKV-7. Models that incorporate linear attention layers with the so-called Delta-Rule involve the inversion of triangular matrices as a core sub-routine. This operation often forms a performance bottleneck, and, due to its high-sensitivity to numerical errors, it can significantly deteriorate end-to-end model accuracy if it is not carefully implemented. This work provides a systematic analysis of both direct and iterative triangular inversion algorithms, targeting methods that are rich in matrix products, and, therefore, have the potential to efficiently utilize modern hardware. To that end, our analysis covers a broad spectrum of mathematical and practical aspects, with a heavy focus on numerical stability, computational complexity, and, ultimately, hardware efficiency and practical considerations. We provide a rigorous experimental evaluation to verify these properties in practical scenarios, and in low-precision floating-point representations, highlighting the strengths and limitations of each method. Performance benchmarks on NPUs reveal up to $4.3\times$ speed-up against the state-of-the-art implementations of SGLang for triangular matrix inversion, leading to significant performance improvements on the entire layer level, while maintaining full end-to-end model accuracy.
BibTeX
@misc{sobczyk2026fast,
  author = {Aleksandros Sobczyk and Gioele Gottardo and Christos K. Matzoros and Mirko De Vita and Filip Skogh and Anastasios Zouzias and Jiawei Zhuang},
  title = {{Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers}},
  year = {2026},
  eprint = {2605.21325},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.21325},
}
Figure