✗ Mechanism failed 2026

Permutation-Mixed Orthogonal Quantization

Implementation & benchmark of arXiv:2608.18557 — Randomly Permuted Orthogonal Products and Fast Dimension Reduction

Usefulness7/10

Difficulty5/10

Novelty5/10

Architecture Memory Accuracy Inference speedup Quantization Embedding Kv cache Inference speedup Memory Linear algebra Probability Random matrix

Source paper: Randomly Permuted Orthogonal Products and Fast Dimension Reduction arXiv:2608.18557 ⓘ · analyzed Sep 1, 2026

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

Idea description

Precondition activation or cache blocks with a fixed product U = A Sigma B of orthogonal transforms and a random signed permutation before quantization or coordinate sampling. The random permutation makes the product incoherent, so energy is less concentrated in a few coordinates and lossy compression should introduce less worst-case distortion.

Formulas

$$U=A\Sigma B,\qquad A^{\mathsf T}A=B^{\mathsf T}B=I_d,\qquad \max_{i,j}|U_{ij}|=O\left(\sqrt{\frac{\log d}{d}}\right)\ \text{with high probability}.$$

$$\Phi=\sqrt{\frac{d}{m}}\,P_IUD_{\xi'},\qquad m\asymp\varepsilon^{-2}\log N.$$

$$\widetilde{x}=U^{\mathsf T}Q(Ux),\qquad \|Ux\|_2=\|x\|_2,$$

$$Q(z)_k=\Delta\,\operatorname{clip}\left(\operatorname{round}(z_k/\Delta),-q,q\right).$$

Mathematical statement

The paper studies U = A Sigma B, where A and B are d by d orthogonal matrices satisfying A^T A = B^T B = I_d, and Sigma is a uniformly random signed permutation matrix. Under mild entry-spreading assumptions on A and B, the key result is max over i,j of absolute U_ij = O(sqrt(log(d)/d)) with high probability. This is an incoherence guarantee: no output coordinate has an excessively large dependence on a single input coordinate. The paper also defines the embedding Phi = sqrt(d/m) P_I U D_xi', where P_I selects m coordinates and D_xi' is an independent random Rademacher diagonal matrix, and obtains the optimal finite-set embedding dimension m proportional to epsilon^(-2) log(N). For neural compression, use U as a norm-preserving preconditioner because ||Ux||_2 = ||x||_2, then quantize or sample coordinates and optionally invert with U^T.

Implementation notes

1. Integration point: apply the transform independently to blocks of activation vectors, embedding rows, or KV-cache channels immediately before quantization or coordinate dropping. Use block sizes d = 64, 128, or 256. Initially choose A and B as fixed Hadamard-like orthogonal transforms, and sample one signed permutation Sigma per block. Freeze all transforms during training and inference. For reconstruction, apply U^T after dequantization; for a compressed linear layer, absorb U or U^T into the adjacent weight matrix when possible.

2. Pseudocode: compute z = B times x; permute and sign-flip z using Sigma; compute z = A times z; estimate a block scale Delta; quantize each coordinate with Q; transmit or store the quantized block; dequantize and reconstruct x_hat = B^T times Sigma^T times A^T times z_quantized. For coordinate sampling, retain a random subset I and rescale by sqrt(d/m), following Phi.

3. The mathematical quantities are the exact orthogonality relation, the random signed permutation, and the predicted coherence scale sqrt(log(d)/d). Measure empirical coherence mu(U) = sqrt(d) times the largest absolute matrix entry, activation kurtosis, maximum coordinate magnitude, quantization MSE, and reconstruction error. Estimate Delta using either maximum absolute value or a fixed percentile from calibration data.

4. First experiment: use a 125M-parameter Transformer on WikiText-103 with 8-bit and 4-bit activation quantization. Compare ordinary per-channel quantization, a random sign/permutation baseline, and the full A Sigma B preconditioner. Measure perplexity, activation MSE, maximum coordinate magnitude, memory traffic, and latency. A successful result is lower perplexity at the same bitwidth, or equal perplexity with fewer retained coordinates. The mechanism is falsified if incoherence and outlier statistics do not improve or if the extra transform cost dominates the compression savings.

Verification

Mechanism failed

Stage 1 · Toy mechanism gate: Failed ✗

Stage 2 · Mechanism transferred to benchmark: Not tested

Stage 2 · Practical benchmark result: Not run

Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a NumPy MVP for signed-permutation Hadamard preconditioning, exact reconstruction, quantization, coherence, and coordinate-sampling tests. Orthogonality was exact, transformed sparse vectors had maximum coordinates scaling downward from 0.335 at d=64 to 0.191 at d=256, and extreme sampling at d=128,m=4 matched the predicted NMSE (30.95 observed versus 31 predicted). However, max-scaled 4-bit quantization was consistently worse after mixing, so the promised general compression win was not observed.

Agent confidence: 8/10

Baseline: Per-vector max-scaled 4-bit quantization NMSE averages: 6.92e-5 at d=64, 4.67e-5 at d=128, and 2.97e-5 at d=256; identity coordinate sampling at d=128,m=4 gave 35.24 NMSE.
Idea: Mixed AΣB 4-bit quantization NMSE averages: 2.01e-4 at d=64, 1.14e-4 at d=128, and 6.13e-5 at d=256; mixed sampling at d=128,m=4 gave 30.95 NMSE, with maximum transformed coordinate energy 0.0625 versus 1.0 for identity.

Limitations: Only toy synthetic vectors and NumPy Hadamard transforms were tested; no Transformer, WikiText, KV cache, latency, memory traffic, percentile or fixed-scale calibration, or GPU experiment was evaluated. The coherence sweep used finite dimensions and structured Hadamard factors rather than independently sampled dense orthogonal matrices.

How to run: python3 experiment.py

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

Artifacts

Implementation overview ⬇ Download all as ZIP 3 files · code, reports and structured results

🐍 experiment.py 6.1 KB View Raw
📄 report.md 1.6 KB View
📊 results.json 7.7 KB View Raw