△ Mechanism confirmed, baseline not beaten 2026

Adaptive Householder Gradient Subspaces

Implementation & benchmark of arXiv:2608.28941 — A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition

Usefulness7/10

Difficulty5/10

Novelty5/10

Memory Memory Stability Speedup Optimizer Training Memory Linear algebra Numerical analysis Random matrix

Source paper: A GPU-Accelerated Blocked Adaptive Randomized Range Finder Based on an Implicit Householder QR Decomposition arXiv:2608.28941 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace fixed-rank randomized SVD or unstable block Gram–Schmidt in a GaLore-like optimizer with an adaptive blocked randomized range finder using implicit Householder QR. The basis grows in Gaussian blocks until the residual Frobenius energy is below a layer-specific tolerance, allowing compressible layers to use fewer projected dimensions while preserving orthogonality over repeated refreshes.

Formulas

$$A\approx QQ^{T}A,\qquad Q^{T}Q=I_k.$$

$$Q=\prod_{i=0}^{k}\left(I-V_{0:j,i}T_iV_{0:j,i}^{T}\right).$$

$$E_0=\lVert A\rVert_F^2,\qquad \text{add Gaussian blocks while }E>\sigma^2.$$

$$R_{i+1}=(I-Q_iQ_i^T)R_i,\qquad E_{i+1}=\lVert R_{i+1}\rVert_F^2,\qquad \widehat G=QQ^TG.$$

Mathematical statement

The paper seeks an orthonormal basis Q for A in R^{m x n} satisfying A approximately Q Q^T A and Q^T Q = I_k, where A is the matrix being approximated, Q has k columns, and I_k is the k x k identity. Its adaptive algorithm initializes E = ||A||_F^2 and repeatedly samples Omega in R^{n x b} with independent standard Gaussian entries, forms a residual sketch, and adds a block of basis vectors until E <= sigma^2, where b is the block size and sigma is the prescribed absolute residual tolerance. Instead of explicitly materializing Q, the orthogonal basis is represented as a product of block Householder reflectors Q = product_{i=0}^k (I - V_{0:j,i} T_i V_{0:j,i}^T), where V_{0:j,i} contains the Householder vectors for block i and T_i is the compact triangular factor defining that block reflector. Each reflector is orthogonal up to floating-point error, avoiding the loss of orthogonality associated with unreorthogonalized Gram–Schmidt. For a neural-network gradient G, use R_0 = G and, after adding block Q_i, update R_{i+1} = (I - Q_i Q_i^T)R_i. The projected gradient is Q Q^T G, while optimizer moments can be stored in the reduced coordinates Q^T G.

Implementation notes

Integrate this at the gradient-compression and optimizer-state update point for large linear layers, attention projections, or embeddings. Every S optimizer steps, reshape the layer gradient G into a matrix in R^{m x n}. Set R = G, E = ||G||_F^2, and maintain an empty list of Householder blocks. Pseudocode: while E > sigma^2 and num_columns < k_max: Omega = randn(n,b); Y = R @ Omega; apply all previous reflectors to remove components in the existing span; compute an in-place blocked Householder QR of Y; store V_i and compact T_i; define Q_i(x) = x - V_i @ (T_i @ (V_i.T @ x)); append (V_i,T_i); R = R - Q_i(Q_i.T @ R); E = ||R||_F^2; end. Apply the stored reflectors to G to obtain reduced coordinates Z = Q^T G. Run AdamW or SGD on Z, storing first and second moments with shape k x n rather than m x n, then reconstruct the parameter update as Q times the reduced update. Store reflector factors in FP32 even when matrix products use BF16 or FP16. Initially compute the residual norm exactly after each block; later test Hutchinson estimates if memory bandwidth dominates. The first experiment should use a small Transformer on WikiText-2, comparing fixed-rank GaLore, randomized QR with one-pass Gram–Schmidt, and adaptive Householder QR at equal optimizer-state memory. Measure validation perplexity, peak memory, wall-clock refresh cost, average retained rank, and ||Q^TQ-I||_F. Success means lower orthogonality error, no loss in perplexity, and lower average rank or refresh time at the same memory budget.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built an adaptive Gaussian residual range finder with implicit Householder QR factors and a one-pass Gram–Schmidt baseline. The mechanism manifested: Householder orthogonality stayed around 0.9–1.4e-15 across condition numbers up to 1e14, while Gram–Schmidt error grew from 1.1e-13 to 1.41; tightening tolerance monotonically increased rank and measured residuals stayed below the requested tolerance. The synthetic layer test used ranks 8/20/32 for decay rates 0.40/0.16/0.03 versus fixed rank 32, showing the intended rank savings on compressible layers, but this is not evidence of a training win.

Agent confidence: 8/10

Baseline: One-pass Gram–Schmidt: orthogonality error 1.14e-13, 5.65e-9, 1.32, 1.41 for condition numbers 1e2, 1e6, 1e10, 1e14; fixed randomized rank-32 relative errors 2.4e-5, 0.01884, and 0.47745 on the three synthetic layers.
Idea: Implicit Householder: orthogonality error 1.05e-15 to 1.38e-15 across the same condition sweep; adaptive ranks 8, 20, and 32 at relative tolerance 0.10, with errors 0.0943, 0.0905, and 0.4584. Relative residuals for tolerances 0.4, 0.2, and 0.1 were 0.2685, 0.1563, and 0.0922.

Limitations: No Transformer, WikiText-2, AdamW/GaLore integration, GPU benchmark, peak-memory measurement, refresh wall-clock comparison, BF16/FP16 test, or large-scale training experiment was performed. The adaptive method uses explicit Q blocks internally for this MVP, while production use would retain reflector factors and apply them implicitly.

How to run: python3 adaptive_householder.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.28941) Sep 2, 2026

No significant difference vs. the tuned baseline (+1.0%, p=0.7055, wins 2 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 15.3652
Idea mean: 15.5147
Effect (Δ): 0.1495 (+1.0%; negative = idea better)
Wins: 2 / 8 paired seeds
p-value: 0.7055 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the optimizer-matched tabular track was tested. The MVP materializes Q using torch.linalg.qr instead of retaining implicit reflector factors, and did not measure peak memory, refresh wall-clock cost, BF16/FP16 behavior, or large-scale GaLore/Transformer training.

How to run: python3 adaptive_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 2, 2026 latest Failed ✗

Agent confidence: 9/10

Built and ran Adaptive Householder Gradient Subspaces on the structurally matched tabular Friedman regression track with the shared mlp_tiny architecture. Trained-model measurements confirmed adaptive rank reduction and good orthogonality, but the best idea MSE was 15.514657 versus 15.365185 for tuned Adam; paired delta was +0.149472 with permutation p=0.7055. The benchmark verdict is no measurable effect, not a significant improvement.

Baseline: Tuned Adam, lr=0.006: test MSE mean 15.3651849031, std 2.4159352500, 8 seeds.
Idea: Adaptive projected-gradient Adam, lr=0.006, rel_tol=0.30, block=4, kmax=16: test MSE mean 15.5146573782, std 1.7595013101, paired delta +0.1494724751, permutation p=0.7055, 2/8 wins; observed mean rank 3.0 and orthogonality error 2.247122e-7.

Benchmark result