# Tolerance-controlled adaptive low-rank layers

- ID: 493
- Canonical URL: https://synthcore.org/idea/493/tolerance-controlled-adaptive-low-rank-layers
- API JSON: https://synthcore.org/api/idea/493.json
- API Markdown: https://synthcore.org/api/idea/493.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.06758](https://arxiv.org/abs/2607.06758)
- Category: architecture
- Solves: memory, inference-speedup, accuracy
- ML areas: mlp, attention, memory, inference-speedup
- Math tags: linear-algebra, random-matrix, probability, numerical-analysis
- Ratings: usefulness 7/10; difficulty 5/10; novelty 6/10

## Idea description

Replace selected dense neural-network operators by low-rank factors whose rank is selected by a randomized residual test at a user-specified tolerance. Construct candidate bases in large blocks for efficient matrix operations, then prune the block to the smallest rank that passes the residual criterion instead of treating the block size as the final rank.

## Mathematical statement

The paper formulates fixed-tolerance approximation as finding an orthonormal matrix \(\mathbf Q\in\mathbb R^{m\times k}\) and coefficient matrix \(\mathbf B\in\mathbb R^{k\times n}\) satisfying \(\|\mathbf A-\mathbf Q\mathbf B\|\leq\tau\), where \(\mathbf A\) is the linear operator being compressed, \(k\) is an unknown rank, and \(\tau\) is either an absolute tolerance \(\varepsilon\) or a relative tolerance \(\varepsilon\|\mathbf A\|\). The paper targets both Frobenius and spectral norms and estimates the residual directly from randomized probes. For an implementable Frobenius estimator, let \(\mathbf R=\mathbf A-\mathbf Q\mathbf B\), let \(\mathbf z_i\in\{-1,+1\}^n\) have independent Rademacher entries, and define \(\widehat e_F^2=\frac1s\sum_{i=1}^s\|\mathbf R\mathbf z_i\|_2^2\); then \(\mathbb E[\widehat e_F^2]=\|\mathbf R\|_F^2\). For a spectral check, use normalized power iteration on \(\mathbf R\): \(\mathbf v_{t+1}=\mathbf R^T\mathbf R\mathbf v_t/\|\mathbf R^T\mathbf R\mathbf v_t\|_2\), with estimate \(\widehat e_2=\|\mathbf R\mathbf v_T\|_2\). The neural adaptation applies these tests to a weight matrix or matrix-free linear operator and stops when \(\widehat e\leq\tau/\gamma\), where \(\gamma>1\) is a safety factor controlling underestimation risk. Rank pruning uses an oversized candidate block of width \(b\), computes \(\mathbf B=\mathbf Q^T\mathbf A\), and retains only the smallest prefix of basis directions whose measured residual satisfies the tolerance.

## Key formulas

- $$\|\mathbf A-\mathbf Q\mathbf B\|\leq\tau,\qquad \mathbf Q\in\mathbb R^{m\times k},\quad \mathbf B\in\mathbb R^{k\times n},\quad \tau\in\{\varepsilon,\varepsilon\|\mathbf A\|\}.$$
- $$\widehat e_F^2=\frac{1}{s}\sum_{i=1}^{s}\|(\mathbf A-\mathbf Q\mathbf B)\mathbf z_i\|_2^2,\qquad \mathbf z_i\in\{-1,+1\}^{n},\qquad \mathbb E[\widehat e_F^2]=\|\mathbf A-\mathbf Q\mathbf B\|_F^2.$$
- $$\mathbf v_{t+1}=\frac{\mathbf R^T\mathbf R\mathbf v_t}{\|\mathbf R^T\mathbf R\mathbf v_t\|_2},\qquad \widehat e_2=\|\mathbf R\mathbf v_T\|_2,\qquad \mathbf R=\mathbf A-\mathbf Q\mathbf B.$$
- $$k^*=\min\left\{k:\widehat e(\mathbf A-\mathbf Q_k\mathbf B_k)\leq\frac{\tau}{\gamma}\right\},\qquad \gamma>1.$$

## Implementation notes

Integrate this at the inference-compression or checkpoint-compression stage for dense MLP matrices and attention projections, not inside every ordinary training step initially. For a weight matrix \(\mathbf W\in\mathbb R^{d_{out}\times d_{in}}\), use an oversized block size \(b\), for example 64 or 128, and incrementally build an orthonormal basis \(\mathbf Q\) from randomized range samples \(\mathbf Y=\mathbf W\mathbf\Omega\), where \(\mathbf\Omega\in\mathbb R^{d_{in}\times b}\) is Gaussian or Rademacher. Orthogonalize \(\mathbf Y\), set \(\mathbf B=\mathbf Q^T\mathbf W\), and evaluate the residual on fresh probes. Compact pseudocode is: `Q=[]; while True: Omega=random(din,b); Y=W@Omega; Y=Y-Q@(Q.T@Y); Q=orth(Y); B=Q.T@W; RZ=W@Z-Q@(B@Z); e=sqrt(mean(sum(RZ**2,axis=0))); if e <= tau/gamma: break`. Here `Z` contains \(s\) fresh Rademacher probes, \(e\) is the estimated Frobenius residual, and `tau=epsilon*||W||_F` for relative compression. After each block, test every prefix \(\mathbf Q_k\) or compute a small SVD of \(\mathbf B\) to prune the oversized block; retain the smallest prefix passing the same test. The paper supplies the tolerance principle and randomized residual construction; the implementation estimates \(\|W\|_F\) with the same probe estimator and chooses \(s\) empirically, starting at 16 or 32. For a matrix-free operator, replace `W@x` by its forward matvec; use the power-iteration formula only when adjoint products are available, and otherwise use the Frobenius test. First test on a 2-layer MLP or a single Transformer feed-forward projection on CIFAR-10 or WikiText-2, comparing dense inference, fixed-rank SVD, and this adaptive method at equal output-error tolerances. Measure retained rank, parameter count, latency, and validation loss. A successful result is substantially smaller rank than the block size, near-SVD validation loss, and lower inference time or memory at the same tolerance.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a randomized blocked QB compressor with fresh Rademacher residual tests, safety-factor stopping, coefficient-space prefix pruning, and reproducible sanity and MLP experiments. The mechanism manifested: estimator bias stayed below 0.36%, observed variance times s varied by only 15%, and adaptive ranks increased with tighter tolerance while staying within 0–3 ranks of optimal SVD rank and largely independent of block width. It did not produce a practical tiny-MLP win: factor parameters exceeded dense parameters and latency was about 10–12 times slower, so this is a mathematical mechanism success but not an inference-performance win at this scale.

### Mechanism check

- Verdict: Built a randomized blocked QB compressor with fresh Rademacher residual tests, safety-factor stopping, coefficient-space prefix pruning, and reproducible sanity and MLP experiments. The mechanism manifested: estimator bias stayed below 0.36%, observed variance times s varied by only 15%, and adaptive ranks increased with tighter tolerance while staying within 0–3 ranks of optimal SVD rank and largely independent of block width. It did not produce a practical tiny-MLP win: factor parameters exceeded dense parameters and latency was about 10–12 times slower, so this is a mathematical mechanism success but not an inference-performance win at this scale.
- Confidence: 9/10
- Limitations: Only explicit dense NumPy matrices and a synthetic two-layer MLP were tested. No CIFAR/WikiText model, GPU path, matrix-free operator, spectral estimator, training-quality evaluation, or large-scale latency and memory benchmark was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.32615
- Paired wins: 4/8
- Benchmark verdict: no significant win

## Artifacts

- [adaptive_lowrank.py](https://synthcore.org/code/238/adaptive_lowrank.py)
- [bench_lowrank.py](https://synthcore.org/code/238/bench_lowrank.py)
- [bench_report.json](https://synthcore.org/code/238/bench_report.json)
- [patch_lowrank.py](https://synthcore.org/code/238/patch_lowrank.py)
- [report.md](https://synthcore.org/code/238/report.md)
- [report_bench_2026-08-30T212732.md](https://synthcore.org/code/238/report_bench_2026-08-30T212732.md)
- [results.json](https://synthcore.org/code/238/results.json)
- [summarize.py](https://synthcore.org/code/238/summarize.py)
- [summary.json](https://synthcore.org/code/238/summary.json)
- [Download all files as ZIP](https://synthcore.org/download/238)

## Disclaimer

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