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:
- Computational Bottleneck: It is highly sequential by nature, often consuming up to 40% of the total layer runtime.
- 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%.
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.
- 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.
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