TL;DR
ReWY is an algebraic optimization that significantly speeds up the training of "delta-rule" linear attention models, such as Kimi Linear and Qwen3-Next. By reformulating the backward pass to eliminate redundant intermediate calculations, ReWY reduces the number of core matrix products from seven to three, delivering up to 1.8x speedups on NVIDIA GPUs and nearly 3x on Ascend NPUs without changing the model's output.
What Problem Does This Paper Address?
Linear attention has emerged as a powerful alternative to standard Softmax attention because its complexity grows linearly with sequence length, rather than quadratically. A popular variant is delta-rule attention, which uses a recurrent state update to capture long-range dependencies efficiently.
To make these models fast on modern hardware, researchers use "chunkwise" algorithms and a mathematical trick called the WY decomposition. However, the standard way to calculate gradients (the "backward pass") for these algorithms is surprisingly inefficient. It generates several "auxiliary adjoints"—intermediate gradient-like matrices—that are only used to calculate the final gradients and then discarded. This "redundant derivative graph" wastes millions of floating-point operations (FLOPs) per chunk, creating a bottleneck during training.
Methods
The authors introduce ReWY (Reformulated WY), which simplifies the backward pass through three key techniques:
-
Triangular Residual Differentiation: Instead of differentiating every step of the complex WY decomposition individually, ReWY treats the entire chunk correction as a single triangular residual system. This allows the algorithm to compute a "shared sensitivity" matrix ($P$) that directly feeds into all required gradients. This single change slashes the local matrix product count from seven down to three.
Figure 1. The local backward computation graph before and after ReWY. Arrows show dependencies between computed values; forward operands appear in the node formulas. The expanded graph forms ¯𝑊and ¯𝐴(orange) and propagates the inverse adjoint through two matrix products. ReWY shares 𝑃across the same three required gradients (green), using the forward correction 𝑅. The graphs contain seven and three matrix products, respectively; addition, masking, and the alias ¯𝑍= 𝑃 are not counted as products. -
Centered Matrix Contractions: For models with vector-based gates (like KDA), ReWY reorganizes pairwise token interactions into dense matrix operations. It uses a "centering" technique to keep exponential factors within a stable numerical range, preventing overflows without sacrificing speed.
- Gram Elimination: For scalar-gated models (like GDN), ReWY avoids the expensive step of forming a large "key Gram matrix" by cleverly reusing products already calculated for other parts of the gradient.
Datasets
The researchers evaluated ReWY using two main approaches:
- Synthetic Workloads: They tested six different "shapes" (combinations of batch size, sequence length, and head count) to stress-test the kernels across various computational intensities.
- Full-Model Integration: They integrated their optimized kernels into existing model architectures from the Flash Linear Attention (FLA) library, including 1.3B parameter language model shells, to measure real-world performance gains in a complete training loop.
Key Insights and Ideas
- Cutting out the Middleman: The core "aha!" moment is realizing that the intermediate matrices in the standard backward pass are mathematically unnecessary. By applying the classical reverse derivative of a linear solve to the entire chunk system at once, you can bypass the "auxiliary adjoints" entirely.
- Exact Arithmetic, Faster Execution: Unlike many optimizations (like pruning or quantization) that trade accuracy for speed, ReWY is mathematically exact. In infinite precision, it produces the same gradients as the original algorithm—it's just a more efficient way to get there.
- Hardware Agnostic Gains: Because the optimization is algebraic, it provides benefits across different hardware architectures, including NVIDIA's Ampere (A800), Hopper (H100/H200), and Huawei's Ascend NPUs.
Key Results
The performance gains are substantial across the board:
- NVIDIA GPUs: On RTX 5070Ti and A800 GPUs, ReWY achieved geometric-mean speedups of 1.15x to 1.81x for the complete backward operator. On high-end H100 and H200 GPUs, speedups ranged from 1.18x to 1.70x.
-
Ascend NPUs: The results were even more dramatic on the Ascend 950DT, with speedups reaching up to 2.89x for certain model configurations.
Complete-backward speedups across different hardware and model types. GDN2 shows particularly high gains on Ascend hardware. -
Memory Efficiency: By eliminating intermediate matrices, ReWY also reduces the peak memory footprint during training by up to 30% in some scenarios, allowing for larger batch sizes or longer sequences on the same hardware.
Limitations and Future Work
- Numerical Stability: While mathematically equivalent, the reordered operations result in different floating-point rounding patterns. While the authors validated these against high-precision references, bitwise identity is not guaranteed.
- Backward-Only Focus: ReWY specifically targets the backward pass. While this is a major component of training time, it does not improve inference (forward pass) speed.
- Long-term Convergence: The paper proves the gradients are correct and the kernels are stable over short runs. However, the authors note that full-model training convergence over billions of tokens is a separate challenge that remains for future large-scale empirical studies.
Summary updated