Load-Aware Polynomial Inversion for Large-Chunk Linear Attention

Linear attention models such as Gated DeltaNet (a recurrent alternative to softmax attention that updates a fixed-size memory token by token) avoid the quadratic cost of standard attention. In practice, though, they are trained and run in "chunks" of tokens, and each chunk needs the inverse of a small lower-triangular matrix. The usual way to compute that inverse, forward substitution, solves for one row at a time. When Good Enough Is Optimal measured this sequential step at over 30% of layer runtime on a phone NPU. It replaced the step with a short truncated Neumann series, a sum of the first few matrix powers, that uses only matrix multiplications. That works at chunk size 64. At chunk size 128 the matrix powers overflow 16-bit floating point, and the method falls back to block-wise decomposition.

Wireless engineers hit the same wall twenty years ago. A massive-MIMO base station, one with many antennas serving many users at once, must invert a Gram matrix (the matrix of inner products between users' channel vectors). Truncated Neumann detectors work only while users are few relative to antennas. In that regime the channel vectors are nearly orthogonal and the matrix is close to diagonal, a property called channel hardening. This note proposes that the intra-chunk matrix of linear attention is the same object. Chunk length plays the role of the number of users, key dimension plays the role of the number of antennas, and the ratio between them predicts when a cheap polynomial inverse will fail. The proposal borrows the wireless fix, polynomials with optimized rather than unit coefficients, as a training-free, calibration-only replacement that we hypothesize allows single-level chunks of 128 in 16-bit and 8-bit arithmetic.

Core Claim

In the chunked recurrence, the matrix being inverted has entries of the form $\beta_i\, k_i^\top k_j$ for $j<i$, scaled by gate decays. Here $k_i$ is the normalized key of token $i$ and $\beta_i$ is its write strength. If keys within a chunk point in roughly independent directions, each off-diagonal entry shrinks like $1/\sqrt{d_k}$, where $d_k$ is the key dimension; this follows from concentration of inner products between random unit vectors. A row's total off-diagonal mass then grows like $\beta\sqrt{C/d_k}$, where $C$ is the chunk length. This is the analogue of the users-to-antennas load factor $K/M$ that governs Neumann detectors in Wu et al.. That paper reports under 0.25 dB loss at order 3, but only for 8 users on 128 antennas. Under this analogy, chunk 64 with $d_k=128$ is a lightly loaded system and chunk 128 is a fully loaded one.

We make two claims. The first is that the per-head load factor, corrected by measured key correlation within the chunk, predicts both the truncation error and the peak magnitude of the matrix powers. That makes the choice of polynomial order a per-head decision rather than a global constant. The second is that, at a fixed low order, replacing the unit coefficients of the Neumann series with coefficients fitted to calibration data closes most of the remaining error and bounds intermediate magnitudes. This is the move from PEACH to weighted PEACH in Shariati et al..

The weighted estimator for head $h$ is

$$T_L(A) = \sum_{\ell=0}^{L} \alpha^{(h)}_\ell A^\ell, \qquad \alpha^{(h)} = \arg\min_{\alpha}\ \mathbb{E}_{A,B}\big\|T_L(A)\,B - (I-A)^{-1}B\big\|_F^2 .$$

In this objective, $A$ is the strictly lower-triangular chunk matrix and $B$ is the actual right-hand side the layer applies the inverse to (the $\beta$-scaled keys and values). The expectation runs over calibration chunks. The minimization is an $(L+1)$-dimensional least-squares problem, solved once offline per head.

Relation to Prior Work

When Good Enough Is Optimal supplies the setting, the hardware measurements and the components we keep: multiplication-only evaluation, diagonal masking and parallel residual correction. It uses unit coefficients and one order shared by all layers, and lists adaptive order as future work. We add a criterion for choosing the order and fitted coefficients, and we target exactly the chunk-128 regime where that paper fails.

The wireless papers supply the method. Shariati et al. and its extension to arbitrary statistics (Shariati et al., arbitrary statistics) show that MSE-optimal scalar weights reach MMSE performance at lower polynomial order than unweighted expansion. Zhang et al. show that when channels are correlated, seeding the series with a tridiagonal approximation rather than the diagonal alone recovers accuracy, staying within 0.3 dB of exact MMSE. We test the lower-bidiagonal analogue only for heads whose consecutive keys are strongly correlated. In those heads the bidiagonal inverse's entries are running products, computable by a parallel prefix scan.

LcgNet motivates the step from fixed to learned solver coefficients: its unrolled conjugate gradient reaches −30 dB NMSE in 7 layers versus 14 iterations. We deliberately stop at closed-form, calibration-fitted coefficients rather than end-to-end training, so the method applies post hoc to released checkpoints.

We do not pursue landmark-based attention. Nyströmformer and LaplacianFormer do invert a matrix iteratively, but it is only $m\times m$ for a few dozen landmarks, so exact inversion there is cheap. The measured bottleneck lives in chunked recurrences.

Research Program

The first stage is diagnostic. We will instrument Qwen3.5 models from 0.8B to 9B on calibration text and images, using the C4 and LLaVA-COCO calibration sets of When Good Enough Is Optimal. For every head and chunk, we record:

  1. the effective load factor $\beta\sqrt{C/d_k}$;
  2. a correlation statistic, the mean absolute cosine similarity between adjacent keys;
  3. the peak magnitude of $A^\ell$;
  4. the truncation error at orders 1 to 6.

The test is whether these two cheap statistics predict truncation error and overflow across heads, layers and chunk sizes 32, 64 and 128. If they do not, the wireless analogy is wrong and the program stops here.

The second stage builds the solver. For each head we fit $\alpha^{(h)}$ at order $L\in\{2,3,4\}$ and choose the smallest order that meets an error budget predicted from the load statistic. We then apply the polynomial to the right-hand side by nested (Horner) multiplication, $\alpha_0 B + A(\alpha_1 B + A(\alpha_2 B + \dots))$, so that no bare power $A^\ell$ is ever materialized. Intermediate tensors are $C\times d$ and their range is bounded by the fitted coefficients. Zhang et al.'s residual correction step is kept on top. For heads above a correlation threshold, the diagonal seed is replaced by the bidiagonal seed.

The third stage implements the solver as a single matrix-multiply kernel in FP16 and INT8. It runs on GPU via Flash Linear Attention, and on Snapdragon 8 Elite if access permits; otherwise we report GPU results and operation-count models.

Baselines

The naive reference is exact forward substitution as implemented in Flash Linear Attention. It sets quality and anchors the latency cost that When Good Enough Is Optimal measures at over 30% of layer runtime.

The strongest existing method is that paper's unit-coefficient truncated Neumann series with diagonal masking and residual correction. It reports a 5.2x kernel speedup at 32×32, 4.2x at 64×64, and an 18.1% to 24.6% reduction in layer cycles on Snapdragon 8 Elite, with "virtually zero" perplexity degradation. No reported absolute perplexity on WikiText-v2 was found on Lacuna for it, so we will rerun it ourselves on identical checkpoints, calibration data and kernels. We run it at chunk 64, its validated setting, and at chunk 128 with its hierarchical block fallback. That fallback is the specific competitor our chunk-128 single-level solver must beat.

The third baseline is exact recursive block inversion of the 128 matrix from 64 blocks in FP32. It is the upper bound on quality for any multiplication-only approach at chunk 128.

Two ablations isolate the key ingredient. One fits coefficients but keeps a single global order, separating the fitted weights from load-aware order selection. The other uses load-aware order with unit coefficients, separating order selection from the weights.

Beating the strongest method means two things at chunk 128. The first is matching its chunk-64 perplexity and downstream scores within run-to-run noise. The second is lower end-to-end layer latency than both its chunk-64 configuration and its chunk-128 hierarchical fallback, all in FP16, with INT8 inversion remaining stable without hand-tuned masking widths.

Why not just…?

Why not just stay at chunk size 64, where the existing method already works? This is the most serious threat. If moving to chunk 128 gives no end-to-end speedup, because inter-chunk state passing is already cheap at 64, then the chunk-128 motivation collapses. The contribution would shrink to per-head adaptive order at chunk 64, which may still save cycles in lightly loaded heads. For that reason the first latency experiment measures layer time versus chunk size using exact inversion, before any of our solver is built, and the proposal is rescoped if 128 does not help.

Why not just use exact recursive block inversion or doubling products? For a nilpotent matrix, the product $(I+A)(I+A^2)(I+A^4)\cdots$ gives the exact inverse in $\log_2 C$ multiplications. Block recursion is also exact and multiplication-only. But the doubling product forms high powers explicitly, which is precisely the source of FP16 overflow, and block recursion is the fallback Zhang et al. already resort to. Both are run as baselines. If either matches our latency at equal precision, we will report that the fitted polynomial is unnecessary.

Why not just learn the coefficients end-to-end, LcgNet-style? Learned step sizes clearly help in LcgNet. However, end-to-end learning requires fine-tuning billion-parameter models and makes the inverter depend on the training run. Our closed-form fit needs only calibration data. If the gap between fitted and fine-tuned coefficients on a 0.8B model is large, that is a finding in itself, and we will report it rather than hide it.

Why not just raise the Neumann order or compute the inversion in FP32? Higher order costs more multiplications, and FP32 halves throughput on NPUs. Both appear on the latency-versus-error curve. The method wins only where its curve dominates both.

Decisive Checks

We evaluate WikiText-v2 perplexity, MMLU, common-sense reasoning and RealWorldQA on Qwen3.5 0.8B to 9B, plus kernel microbenchmarks at chunks 32, 64 and 128. These are the protocols of When Good Enough Is Optimal.

Three outcomes decide the proposal. First, rank correlation between predicted and measured truncation error across heads should be high; if it is weak, the channel-hardening analogy fails. Second, at chunk 128 in FP16, the fitted order-3 solver must show no overflow and must match exact-inversion perplexity, where the unit-coefficient series overflows. Third, whole-layer latency at chunk 128 must fall below the best chunk-64 configuration. A secondary check repeats the second outcome with INT8 inversion and diagonal masking disabled, to test whether fitted coefficients make the masking heuristic unnecessary.