WY / UT: from Householder reflectors to linear attention
Why does a modern linear-attention paper suddenly talk about Householder matrices, triangular solves, and blocked kernels? Because the same systems problem keeps returning: many small dependent matrix updates are mathematically convenient, but hardware prefers fewer large matrix operations. WY and UT are ways to bridge that gap.
From Householder reflections to linear attention
Start smaller than Householder: a rank-one update
Take a column vector u and a row vector vᵀ. Their outer product uvᵀ is a matrix, but a very constrained one: it reads one direction and writes one direction. Its rank is one.
I is the identity matrix, so it means “leave the input alone.” The term uvᵀ adds one structured correction. The interesting part starts when you multiply many such factors.
= I − u₁v₁ᵀ − u₂v₂ᵀ + u₁(v₁ᵀu₂)v₂ᵀ
The last term is the interaction between the two updates. With a long sequence there are many ordered interactions. WY and UT are ways to collect them in a compact object instead of replaying every small update against a large matrix.
A Householder reflector is an actual mirror
Pick a vector v. The matrix H flips the component parallel to v and leaves every perpendicular component unchanged. Geometrically, it is a reflection across the hyperplane perpendicular to v.
It is also an orthogonal matrix: HᵀH = I. That means it preserves lengths instead of stretching some directions while shrinking others.
QR factorization
QR factorization rewrites a matrix A as
Q is orthogonal. R is upper triangular, meaning everything below its main diagonal is zero. Triangular systems are easy to solve by substitution, so the factorization turns a general matrix problem into a simpler triangular one.
Householder reflections give a practical way to build this factorization. Choose the first reflector so the first column of A is mapped onto the first coordinate axis. That zeros every entry below the first diagonal element. Then do the same to the second column, then the third, and so on. After the sweep, the transformed matrix is R; the accumulated reflections make Q.
Householder reflectors became numerical infrastructure
Householder worked at Oak Ridge during the transition from hand and electromechanical computation to electronic machines. Matrix problems were real machine workloads. His 1958 work gave a stable orthogonal route to triangularizing a nonsymmetric matrix.
By 1965, Businger and Golub had published Householder-based least-squares software. Least squares appears whenever measurements outnumber unknown parameters: fit the model parameters that best explain noisy data. The application asks for the fitted orbit, calibration, survey, or regression coefficients. It does not care that a chain of reflections produced them.
The same squared-error objective also produced a separate online-learning branch: Widrow and Hoff's delta rule updates weights one observation at a time instead of factoring the full data matrix. The least-squares lineage follows both branches from Householder QR and ADALINE through their reunion in DeltaNet.
EISPACK, LINPACK, BLAS, and LAPACK solve different parts of the stack
| Thing | What it was | Main job | Why it matters here |
|---|---|---|---|
| EISPACK 1972 | Portable Fortran routines built from the Wilkinson–Reinsch eigensystem tradition. | Eigenvalues and eigenvectors. | Shows the pre-blocking style of carefully engineered numerical software. |
| LINPACK Users' Guide 1979 | A Fortran package by Dongarra, Bunch, Moler, and Stewart. | Linear systems, least squares, dense factorizations. | Built around relatively fine-grained vector operations appropriate to its machines. |
| BLAS Level 1 → 2 → 3 | Standard interfaces for common linear-algebra kernels, with reference and tuned implementations. | Vector, matrix-vector, then matrix-matrix work. | Lets numerical algorithms hand hot kernels to machine-specific implementations. |
| LAPACK project began 1987 | The successor that reorganized and extended LINPACK/EISPACK functionality. | Dense solves, least squares, eigenproblems, SVD. | Designed around block algorithms so expensive work becomes Level-3 BLAS. |
BLAS is the contract between algorithms and hardware
Matrix-matrix multiplication can reuse loaded tiles many times. That is why the move from Level 2 to Level 3 matters: it changes how much arithmetic the machine can do per byte moved.
LINPACK package versus LINPACK benchmark. The package provides numerical routines. The benchmark grew from timing a standard solve in the LINPACK Users' Guide and later became a machine-comparison tradition.
Accumulate reflectors before updating the trailing matrix
Suppose a narrow group of columns has produced b Householder reflectors, and all of them must update a much larger matrix C.
C ← H₂C
⋮
C ← H_bC
Touch the large target over and over for rank-one work.
QC = C + W(YᵀC)
Represent the product once, then do matrix-matrix work.
Bischof and Van Loan's 1987 WY representation was motivated by exactly this change in granularity. W and Y are just matrix names, not acronyms.
WY, compact WY, and UT
| Form | Name | Stored objects | Point |
|---|---|---|---|
| Q = I + WYᵀ | WY Bischof & Van Loan, 1987 | Two skinny matrices. | Turn a product of reflectors into block matrix operations. |
| Q = I + YTYᵀ | compact WY Schreiber & Van Loan, 1989 | The reflector vectors plus a small triangular matrix T. | Same idea with less extra storage. |
| Q = I − VTVᵀ | LAPACK-style compact form | V plus triangular T. | The form many programmers encounter inside block-reflector routines. |
| Q = I − UT⁻¹Uᵀ | UT Walker, 1988; revisited 2006 | U plus triangular T. | Apply through matrix products and a small triangular solve; do not form the inverse explicitly. |
The signs and exact definitions vary between papers and libraries. The common shape is the part worth remembering: skinny factors plus a small triangular object summarize a long ordered product.
Why triangular? Because dependence has an order. An earlier transform can affect what a later transform sees; a later one cannot go backward and change how the earlier one was formed.
WY accelerates the expensive application; it does not erase every dependency
A blocked QR implementation works in three stages:
- Factor a narrow panel. Generate its Householder reflectors. This part is still partly sequential because each new reflector sees the panel after the previous ones.
- Accumulate the panel's reflectors. Build the compact block representation, including the small triangular factor.
- Apply the block to the trailing matrix. This is the large update, now expressed as Level-3 BLAS instead of a pile of rank-one passes.
A panel is the narrow block of columns currently being factored. The trailing matrix is the larger block to its right that still needs updating.
In LAPACK, routines such as xLARFT form the triangular factor and xLARFB apply the block reflector. This is why WY became invisible: it turned into library plumbing.
DeltaNet has the same identity-minus-rank-one shape
DeltaNet keeps a fixed-size matrix state S. For token t, let kₜ be the key direction, vₜ the value to write, and βₜ the learned write strength. One orientation of the update is:
The factor I − βₜkₜkₜᵀ is Householder-shaped, but it is generally not an orthogonal reflection because βₜ is learned rather than fixed to the reflector coefficient.
The 2024 DeltaNet parallelization work groups consecutive tokens into chunks and compacts their ordered state transitions. The expensive operations become matrix multiplies instead of a strictly token-by-token state update.
| Classical blocked QR | Chunked DeltaNet | Same systems idea |
|---|---|---|
| Householder vector | token key + write strength | parameterize a structured rank-one transition |
| panel | token chunk | small group whose internal interactions are summarized |
| block reflector | chunk transition | avoid replaying every fine-grained update against the large state |
| Level-3 BLAS | GPU GEMMs / tiled kernels | turn small dependent work into high-throughput matrix work |
Modern code often says “WY/UT” because both descriptions are useful around this chunked kernel family: WY describes the compact product; UT emphasizes the triangular reorganization used to construct or apply the dependent factors.
Exact chunking depends on the state update staying affine
An update is affine in the state when it has the form
where A and B are determined without depending on the current value of S. Affine maps compose into affine maps, so a whole chunk can still be represented by fixed factors.
If the coefficients themselves depend nonlinearly on the current state, that closure disappears. The specific WY/UT factorization above no longer gives the exact recurrence. A model can still choose an approximation, for example by linearizing around the state at the start of a chunk, but that is a different computation.
This is the exact connection to the Trellis training discussion: its chunk-parallel forward freezes the nonlinear state at the chunk boundary to recover a locally linear problem.
From Householder to DeltaNet
Orthogonal triangularization using reflections.
Householder least-squares software makes the method a practical fitting engine.
Portable eigensystem routines.
Dense solve/factorization software built around standardized vector kernels.
WY: accumulate Householder products so the expensive application becomes matrix-matrix work.
Rebuild dense numerical software around block algorithms and higher-level BLAS.
A Householder accumulation form later discussed as UT appears in GMRES work.
Compact WY reduces storage by reusing the reflector vectors.
Revisit the accumulation history and put the UT description back in view.
The same algebraic shape reappears in fixed-state sequence models and chunked GPU kernels.
References
- A. S. Householder, Unitary Triangularization of a Nonsymmetric Matrix, 1958.
- P. Businger and G. H. Golub, Linear Least Squares Solutions by Householder Transformations, 1965.
- C. Bischof and C. Van Loan, The WY Representation for Products of Householder Matrices, 1987.
- R. Schreiber and C. Van Loan, A Storage-Efficient WY Representation for Products of Householder Transformations, 1989.
- T. Joffrain et al., Accumulating Householder Transformations, Revisited, 2006.
- LAPACK FAQ and Netlib BLAS.
- S. Yang et al., Parallelizing Linear Transformers with the Delta Rule over Sequence Length, 2024.