# Permutation-Mixed Orthogonal Quantization

- ID: 2532
- Canonical URL: https://synthcore.org/idea/2532/permutation-mixed-orthogonal-quantization
- API JSON: https://synthcore.org/api/idea/2532.json
- API Markdown: https://synthcore.org/api/idea/2532.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.18557](https://arxiv.org/abs/2608.18557)
- Category: architecture
- Solves: memory, accuracy, inference-speedup
- ML areas: quantization, embedding, kv-cache, inference-speedup, memory
- Math tags: linear-algebra, probability, random-matrix
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## 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.

## 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.

## Key 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).$$

## 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

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 8/10
- 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.

## Artifacts

- [experiment.py](https://synthcore.org/code/972/experiment.py)
- [report.md](https://synthcore.org/code/972/report.md)
- [results.json](https://synthcore.org/code/972/results.json)
- [Download all files as ZIP](https://synthcore.org/download/972)

## Disclaimer

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