Ranking-Aware Projection Dimension Rule
Implementation & benchmark of arXiv:2609.02155 — Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
Source paper: Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models arXiv:2609.02155 ⓘ · analyzed Sep 3, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
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.
Formulas
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.
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
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 9/10
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.
- Agent confidence
- 9/10
- Baseline
- JL-style sizing: m=128/128, memory ratio=1.000, Recall@1=1.000, Recall@10=1.000, top-20 Kendall=1.000, query time=0.746 s
- Idea
- Ranking rule: m=80/128, memory ratio=0.625, Recall@1=0.303, Recall@10=0.631, top-20 Kendall=0.410, query time=0.562 s; calibration tau=0.574 at m=80
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.
How to run: python3 experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Artifacts
- experiment.py 5.2 KB View Raw
- report.md 1.6 KB View
- results.json 2.4 KB View Raw