# Ranking-Aware Projection Dimension Rule

- ID: 3044
- Canonical URL: https://synthcore.org/idea/3044/ranking-aware-projection-dimension-rule
- API JSON: https://synthcore.org/api/idea/3044.json
- API Markdown: https://synthcore.org/api/idea/3044.md
- Verification status: mechanism_failed
- Source: [arXiv:2609.02155](https://arxiv.org/abs/2609.02155)
- Category: memory
- Solves: memory, accuracy, scalability
- ML areas: embedding, inference-speedup, kv-cache, attention
- Math tags: probability, statistics, random-matrix, linear-algebra
- Ratings: usefulness 7/10; difficulty 3/10; novelty 7/10

## Idea description

Replace the usual JL dimension choice with a task-specific dimension budget based on the paper's asymptotic ranking law. For retrieval, nearest-neighbor search, or compressed attention keys, choose m from a target Kendall correlation and automatically expand the projection when measured ranking quality falls below the target.

## Mathematical statement

Let d be the original feature dimension and m the rank of a random linear sketch. For isotropic Gaussian data, the paper states that when m,d    o\infty with m/d    o0, expected Kendall correlation between original and projected pairwise distance orderings is \rho_K=(2/\pi)\sqrt{m/d}(1+o(1)). Therefore a target ranking correlation \rho_* requires the approximate budget m\geq d(\pi\rho_*/2)^2, subject to finite-sample safety factors. For fixed nearest-neighbor list size q, nearest-neighbor agreement tends to 1/q when m/d    o0, so a JL event alone cannot justify an aggressive projection bottleneck. The paper also states that a rank-m sketch can preserve at most m/d of the variance of any feature of one squared distance. The engineering rule is consequently to select m from ranking or neighbor-agreement validation, not from the standard m=O(\varepsilon^{-2}\log n) bound. Here d is the full feature dimension, m is the projected dimension, \rho_* is the desired Kendall correlation, q is the candidate-neighbor list size, and n is the number of indexed points.

## Key formulas

- $$\rho_K=\frac{2}{\pi}\sqrt{\frac{m}{d}}\,(1+o(1)).$$
- $$m_{\mathrm{rank}}\approx d\left(\frac{\pi\rho_*}{2}\right)^2.$$
- $$\operatorname{Var}\!\left(\mathbb{E}[f(D)\mid S]\right)\leq\frac{m}{d}\operatorname{Var}(f(D)).$$
- $$\text{nearest-neighbor agreement}\longrightarrow \frac{1}{q}\quad\text{when }m/d\to0.$$

## Implementation notes

Use this as an adaptive compression layer for a retrieval index, transformer keys, or a low-dimensional attention score path. Given full vectors h in R^d, maintain a projection W in R^{m    imes d}; for retrieval, store z=Wh and compute approximate distances or dot-product scores in m dimensions. Before deployment, choose a target correlation rho_star and compute the initial dimension m=max(m_min, ceil(d*(pi*rho_star/2)^2)), rounding to a hardware-friendly multiple such as 32 or 64. On a held-out calibration set, sample queries, compute full-space top-q neighbors and projected top-q neighbors, and estimate Kendall tau over sampled candidate pairs together with top-1 and top-q agreement. If measured tau is below rho_star minus a safety margin, increase m; if it exceeds the target substantially, decrease m and retest. Pseudocode is: m=ceil(d*(pi*rho_star/2)^2); W=orthogonal_random_matrix(m,d); z=W@h; tau=kendall(full_pair_order,projected_pair_order); while tau<rho_star: m=ceil(1.25*m); reproject. The asymptotic formula and q-neighbor failure limit come from the paper; the 1.25 growth factor, minimum dimension, and confidence intervals are empirical. First test on a 100k-item FAISS-style image or sentence retrieval benchmark with d=768, comparing standard JL sizing against the ranking rule. Measure index memory, query latency, Kendall tau, Recall@1, and Recall@10. Success is at least 2x lower index memory or latency at fixed Recall@10, or materially higher recall at the same m.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a reproducible ranking-aware projection module with exact Beta–arcsine evaluation, Monte Carlo verification, adaptive dimension expansion, and a retrieval benchmark. The core mathematical phenomenon was clearly observed: empirical Kendall correlation matched the exact law and scaled approximately as (2/pi)sqrt(m/d). However, on the toy retrieval task the ranking-rule projection used 80/128 dimensions, reducing memory by 37.5%, but reduced Recall@10 from 1.00 to 0.631 and Recall@1 to 0.303, so the proposed compression did not deliver the promised fixed-quality win.

### Mechanism check

- Verdict: Built a reproducible ranking-aware projection module with exact Beta–arcsine evaluation, Monte Carlo verification, adaptive dimension expansion, and a retrieval benchmark. The core mathematical phenomenon was clearly observed: empirical Kendall correlation matched the exact law and scaled approximately as (2/pi)sqrt(m/d). However, on the toy retrieval task the ranking-rule projection used 80/128 dimensions, reducing memory by 37.5%, but reduced Recall@10 from 1.00 to 0.631 and Recall@1 to 0.303, so the proposed compression did not deliver the promised fixed-quality win.
- Confidence: 9/10
- Limitations: This was a small synthetic clustered retrieval benchmark with d=128, 4,000 indexed items, and 300 queries, not the proposed 100k-item d=768 benchmark or FAISS implementation. Only random Gaussian projections and squared-Euclidean retrieval were tested; no learned projections, real embeddings, top-q asymptotic agreement study, confidence intervals, GPU execution, or large-scale latency/memory profiling was evaluated.

## Artifacts

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

## Disclaimer

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