✗ Failed on benchmark 2026

Kac-rotated fast projection

Implementation & benchmark of arXiv:2608.17374 — On the Pseudo-Mixing of Kac's Walk

Usefulness7/10

Difficulty4/10

Novelty5/10

Architecture Speedup Memory Accuracy Mlp Embedding Inference speedup Initialization Lie groups Representation theory Probability Random matrix Linear algebra

Source paper: On the Pseudo-Mixing of Kac's Walk arXiv:2608.17374 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace a dense Haar or Gaussian random projection with a streamed product of random two-coordinate rotations followed by coordinate subsampling. The transform is exactly orthogonal before subsampling, requires only a list of rotation triples, and the paper's pseudo-mixing result predicts that degree-two statistics relevant to norm preservation and Johnson–Lindenstrauss embeddings become Haar-like after only O(n polylog(n)) rotations.

Formulas

$$X_{t+1}=R_{i_tj_t}(\theta_t)X_t$$

$$R_{ij}(\theta)=I_n+(\cos\theta-1)(E_{ii}+E_{jj})+\sin\theta\,E_{ij}-\sin\theta\,E_{ji}$$

$$Q_T=R_{i_Tj_T}(\theta_T)\cdots R_{i_1j_1}(\theta_1),\qquad y=\sqrt{\frac{n}{m}}\,P_mQ_Tx$$

$$\|P_mQ_Tx\|_2^2=\sum_{r=1}^{m}(e_r^TQ_Tx)^2$$

Mathematical statement

Kac's walk starts from X_0 in \mathcal{SO}(n) and updates by X_{t+1}=R_{i_tj_t}( heta_t)X_t, where \mathcal{SO}(n)=\{X\in\mathbb{R}^{n imes n}:X^TX=I_n,\det X=1\}, (i_t,j_t) is uniform over pairs 1\leq i<j\leq n, and heta_t\sim\mathrm{Unif}[0,2\pi). The two-coordinate rotation is R_{ij}( heta)=I_n+(\cos heta-1)(E_{ii}+E_{jj})+\sin heta E_{ij}-\sin heta E_{ji}, with E_{ab} the matrix having a one at (a,b) and zero elsewhere. Each R_{ij}( heta) is orthogonal and changes only coordinates i and j. The paper proves that the first k columns mix in time nk\,\mathrm{polylog}(n), and uses a representation-theoretic argument to show that degree-k polynomials cannot distinguish a Kac matrix from Haar measure after nk^2\,\mathrm{polylog}(n) steps. For a projection whose main observables are quadratic, use k=2: Q_T=R_{i_Tj_T}( heta_T)\cdots R_{i_1j_1}( heta_1), y=\sqrt{n/m}\,P_mQ_Tx, where P_m selects m coordinates. The relevant degree-two statistic is \|P_mQ_Tx\|_2^2, a quadratic polynomial in entries of Q_T; pseudo-mixing predicts Haar-like norm behavior at substantially fewer steps than full Haar mixing.

Implementation notes

Integrate this at a location currently using a dense fixed random projection, such as an embedding bottleneck, random feature map, sketching layer, or fast-JL preprocessing stage. Store a seed or an explicit list of T triples (i_t,j_t,theta_t), rather than an n-by-n matrix. For each input vector x, initialize z=x and execute: for t=1,...,T, read a=i_t, b=j_t, c=cos(theta_t), s=sin(theta_t), set u=z[a] and v=z[b], then set z[a]=c*u+s*v and z[b]=-s*u+c*v; finally return y=sqrt(n/m)*z[indices]. This computes multiplication by Q_T followed by P_m, up to the chosen left/right multiplication convention. For a batch, vectorize each pair update over the batch dimension. On GPU, benchmark both the literal sequence and blocks of disjoint pairs; the latter may improve memory coalescing but must be evaluated separately because reordering rotations changes Q_T. The transform itself is computed exactly from the Kac update. Estimate the useful pseudo-mixing threshold empirically by sweeping T over {0.25n, 0.5n, n, 2n, 4n} multiplied by a small logarithmic factor. First test CIFAR-10 or TinyImageNet with n=1024 and m=256, comparing dense Gaussian, dense Haar, SRHT, and Kac projections inside the same MLP. Measure projection wall-clock time, storage bytes, pairwise distance distortion on 10,000 held-out examples, and downstream accuracy after identical training. A useful result is at least 2x lower projection cost and much lower storage, with median and 95th-percentile distortion within 10% of Haar or SRHT and accuracy loss below 1 percentage point. Varying T should show quadratic statistics stabilizing near the predicted O(n polylog n) regime.

Verification

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Inconclusive

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 exact streamed Kac-rotation projection and numerically verified the core mechanism. Orthogonality stayed at 1.33e-15 defect, the measured quadratic mean matched the analytic relaxation within 0.0159 absolute error, and quadratic-statistic spread approached the Haar reference by 8n rotations. The mechanism is real, but the literal Python implementation was far slower than dense BLAS, so no speed win was demonstrated; storage was 4x smaller than a full dense orthogonal matrix.

Agent confidence: 8/10

Baseline: Dense Gaussian: pair-distance MAE 0.2749, 95th-percentile absolute error 0.6406, 4.39e-5 s/batch; Haar: MAE 0.2898, 95th-percentile absolute error 0.6618.
Idea: Kac at T=8n: pair-distance MAE 0.2678, 95th-percentile absolute error 0.5414, 0.0173 s/batch; quadratic-statistic standard-deviation ratio to Haar 1.002; explicit triples use 8192 bytes versus 32768 bytes for a dense full orthogonal matrix.

Limitations: Only a small n=64 NumPy toy experiment was run; no GPU/fused kernel, MLP training, CIFAR accuracy, large-n scaling, SRHT comparison, or end-to-end production benchmark was tested. Runtime is dominated by Python sequential-loop overhead and should not be interpreted as the performance of a fused Kac implementation.

How to run: python3 run_experiment.py

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

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

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 18.6347
Idea mean: 17.1931
Effect (Δ): 1.4415 (+7.7%; negative = idea better)
Wins: 2 / 8 paired seeds
p-value: 0.2698 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±18.8%
Mechanism: Not confirmed ✗
Practical effect: Inconclusive
Baseline tuning: swept over 0 configs

Limitations:

Only the structurally matched built-in tabular track was tested. The fixed projection was precomputed rather than benchmarked as a fused inference kernel, so runtime speedup was not established. The complete baseline sweep and complete idea sweep are in the saved bench_report.json artifact.

How to run: python3 stage2_bench.py

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

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 9/10

The full Stage-2 tabular benchmark used the registered built-in track, identical end-to-end MLP systems, an equal learning-rate sweep, three Kac rotation counts, and eight paired seeds. The selected Kac projection had mean test MSE 17.1931 versus 18.6347 for the selected dense Gaussian baseline, but the paired permutation test was not significant (p=0.26985), so the idea did not win the benchmark. The trained-model norm signature was confirmed within the declared tolerance, but this does not override the task-metric result.

Baseline: Dense Gaussian projected mlp_tiny, best configuration lr=0.01, M=6, full 8-seed mean test MSE=18.634669303894043.
Idea: Kac-rotated projected mlp_tiny, best configuration lr=0.01, T=80, full 8-seed mean test MSE=17.193141102790833.
Mechanism signature: map[confirmed:true n_observations:3200 observed_abs_error:0.06847155094146729 observed_mean:0.9315284490585327 prediction:1 statistic:scaled projected input norm ratio measured on trained benchmark systems tolerance:0.08]
Paired comparison: make_report comparison: delta_mean=1.4415282011032104, idea_wins=2/8, p_value=0.26985, verdict=no significant win.

Benchmark result