betaFeedback

WorksComputer Science

Nonreciprocal Spherical Attention and Retrieval: Sharp Coarsening Clocks and Certified Score Correction

Abstract

We develop nonreciprocal spherical attention as a mathematical framework for coarsening and compressed nearest-neighbor retrieval. For two shrinking acute blocks whose centers have zero skew pairing and whose total mass ratio is subexponential in inverse temperature, we prove lim⁡β→∞β−1log⁡Tβ=1−cos⁡ϕ\lim_{β\to\infty}β^{-1}\log T_β=1-\cosϕ, without restricting particle-count growth. An explicit three-body flow has two rigorously separated metastable exponents. For finite compression, mass centering yields a sharp O(r2)O(r^2) attention-output error bound at fixed temperature, with an explicit spherical-normalization correction. We formulate skew query-side score calibration as a strictly convex moment problem and derive a unique normal equation, residual-based optimization certificates, and bounded low-rank projections. A norm-aware margin objective calibrates native squared-distance rankings. Experiments use semantic retrieval data, one million visual descriptors with three codebook seeds, and a ten-million-vector FAISS IVF-PQ index with recomputed exact cosine ground truth. On SIFT1M, skew margin calibration raises native-L2 hit@10 from 0.8926 to 0.8948; symmetric calibration reaches 0.8996. The ten-million-vector index reaches 0.8827 hit@10 at 0.1794 ms per query in a four-thread batch benchmark, while validation selects no skew update. Exact streamed attention over ten million keys evaluates compressed memory on 1,024 held-out queries. Independent matrix solves, automatic differentiation, finite differences, interval arithmetic, full-flow tests, and nine Rocq-checked algebra lemmas support reproducibility. Directionality alone does not establish retrieval superiority.

Introduction

Dense retrieval ranks document embeddings xi∈Sd−1x_i \in S^{d-1} by q⊤xiq^\top x_i. Compression replaces those vectors by a smaller index; success requires ranking quality at a stated byte budget, not merely visually separated clusters. This distinction is essential because attention-induced clustering is already well studied [1, 2, 3, 4], and representation collapse can harm useful information [9].

We investigate three questions: whether directionality helps retrieval at a fixed budget, whether it attenuates a specified representation perturbation, and what mathematical guarantees survive nonreciprocity. The initial centroid-only hypothesis fails against competitive quantization. That failure motivates a second, explicit hypothesis: constrained skew score calibration may correct task-relevant quantization errors without the ill-conditioning allowed by a general symmetric metric.

The analysis provides three connected results: a sharp metastability exponent controlled by block mass even under exponential particle growth; a second-order attention compression estimate obtained by mass centering; and a unique skew score-correction equation with a computable optimization residual bound. Experiments evaluate both semantic retrieval and geometric nearest-neighbor search, including a ten-million-vector visual-descriptor index. The scalar probability inequalities and standard convex optimization tools used in the derivations are attributed to their established sources.

Related Work

Spherical attention and clustering. The cluster formation, cone-collapse, and metastability results of [1, 2, 3] are the closest mathematical predecessors. The cone argument in [2 Lemma 4.2 and its proof] explicitly extends beyond symmetric query–key matrices. The acute consensus estimate used here is a quantitative specialization of that established positive-interaction argument. Directional mean shift [10, 11] and diffusion condensation [12] supply related density-based and time-inhomogeneous clustering formulations. Directed-sphere consensus has its own established literature [13, 14].

Directionality and skew geometry. Symmetry and directionality during transformer training are analyzed in [6]. Routing/filtering separation [7] and orthogonal attention [8] use skew structure for different objectives. The latter exponentiates a token interaction operator; our finite retrieval adapter perturbs query–document scores. These token-space operators differ from the descriptor-space correction optimized here against compressed retrieval scores. Symmetric spectral selection [5] has different assumptions from the directed barrier clocks studied here.

Compression and asymmetric retrieval. Two-level softmax size and dispersion corrections are studied in [36]. Here the aggregation analysis controls a vector-valued attention output with skew bilinear scores and explicitly accounts for spherical normalization, rather than claiming size correction as new. Product quantization [18], anisotropic vector quantization [19], query-aware quantization [20], and reduced-rank score regression [21] are essential comparators. Joint query-encoder and quantizer optimization is studied in [34]. Our correction leaves the descriptor extractor fixed, constrains the score operator to a skew subspace, and solves a convex moment equation before rank compression. Low-rank score approximation and query-aware compression are established components. Asymmetric hashing [16, 17] also shows that asymmetry requires a precise task setting; its presence alone does not establish an advantage. Learned rotations for quantization predate this work [22]. Token merging [15] supplies a practical precedent for mass-aware aggregation, but reducing tokens inside a transformer and compressing an external retrieval index are distinct tasks.

The structural Gram identities and exact duplicate aggregation are supporting lemmas. The analytic contribution concerns shielded directed event selection and a two-cluster metastability exponent under a vanishing-skew restriction. For compressed retrieval, the contribution is a constrained score-correction formulation with explicit conditioning, optimization residual, and attention aggregation error bounds. These results distinguish the scope of the present model from general spherical consensus, generic asymmetric retrieval, and unconstrained low-rank regression.

Spherical Interaction Model and Retrieval Formulation

For positive masses mjm_j, skew AT=−AA^{\mathsf{T}}=-A, M=I+εAM=I+\varepsilon A, and β>0\beta>0, the continuous model is

u˙i=(I−uiuiT)∑jpijuj,pij=mjeβuiTMuj∑kmkeβuiTMuk.(1)\dot{u}_i=\left(I-u_i u_i^{\mathsf{T}}\right)\sum_j p_{ij}u_j,\qquad p_{ij}=\frac{m_j e^{\beta u_i^{\mathsf{T}} M u_j}}{\sum_k m_k e^{\beta u_i^{\mathsf{T}} M u_k}}. \tag*{(1)}

For A=0A=0 and equal masses, (1) is the normalized spherical self-attention flow studied in [1, 3]; general query–key bilinear scores are formulated in [2 Section 2.2]. The exponential dot-product kernel is also related to directional mean shift [10, 11], although the projected continuous dynamics here are distinct from its discrete mode-seeking iteration. Its directed barrier is gij=1−uiTMujg_{ij}=1-u_i^{\mathsf{T}}Mu_j, with gij−gji=−2εuiTAujg_{ij}-g_{ji}=-2\varepsilon u_i^{\mathsf{T}}Au_j. Appendix § 11 gives closed ordinary/skew Gram dynamics, a shielded first-event theorem, an explicit inversion of nearest-pair order, and rotating triangles that exclude unconditional coarsening. Self-edges are explicitly excluded from the corridor’s positive external-barrier condition. Figure 1 fixes the geometric notation and distinguishes the two directed barriers between neighboring caps.

Figure 1. Our geometric notation: caps on the unit circle, with directed interactions and unequal barriers. The cap construction is visually motivated by Figure 1 of [3]; this drawing is original.

The same skew form measures cycle directionality. For Hij=uiTAujH_{ij}=u_i^{\mathsf{T}}Au_j, the three-cycle log affinity is 2βε(Hab+Hbc+Hca)2\beta\varepsilon(H_{ab}+H_{bc}+H_{ca}). For the planar rotation A=JA=J, it equals −4βε-4\beta\varepsilon times the signed triangle area, as shown in Figure 2. Masses and row normalizers cancel exactly; the full derivation is in Appendix § 11.

Directed signed area of a triangle under skew interaction

Figure 2. The skew interaction measures the directed signed area of a triangle. The figure represents a two-dimensional linear plane; the vertices may also be constrained to a unit circle.

The first ML pilot uses a finite algorithm: ui+=normalize⁡(ui+h(I−uiuiT)∑jpijuj)u_i^{+}=\operatorname{normalize}\left(u_i+h\left(I-u_i u_i^{\mathsf{T}}\right)\sum_j p_{ij}u_j\right). We take β=12\beta=12, h=0.25h=0.25, and two or four steps selected on validation. This is not an exact ODE solver and does not invoke a recursive-merger theorem. Spherical Lloyd clustering of the final vectors selects a partition with K∈{128,256,512}K\in\{128,256,512\}; prototypes average the original vectors.

Document scores are prototype scores expanded through an assignment array. All documents in a cluster therefore tie, resolved by a fixed lexicographic ID order. The pilot also compares a positive-pair-moment skew learned only from fitting queries, its sign reversal, random skew, reciprocal flow, and ordinary spherical clustering. A supervised symmetric-moment control was added after the initial pilot and is labeled exploratory.

Proposition 3.1 (A centroid-only ranking obstruction). If distinct unit vectors xi,xjx_i,x_j share a reconstructed vector, there is a unit query for which their exact score gap is ∥xi−xj∥\lVert x_i-x_j\rVert while their compressed scores tie. No centroid-only representation of that cluster preserves every query’s strict pairwise ordering.

Proof. Take q=(xi−xj)/∥xi−xj∥q=(x_i-x_j)/\lVert x_i-x_j\rVert. The exact score difference is the stated norm; the reconstructed difference is zero. A fixed tie-break cannot recover both this ordering and its reversal under −q-q.

This is a standard distortion obstruction applied to the pilot. Improving the dynamics alone cannot restore discarded within-cluster information.

Certified Nonreciprocal Score Correction

Let X,X^∈RN×dX,\widehat{X}\in\mathbb{R}^{N\times d} contain original and compressed document vectors, and let Q∈Rs×dQ\in\mathbb{R}^{s\times d} contain fitting queries. Score approximation as multivariate regression is established in LoRANN [21 Sections 3.1–3.2]; score-sensitive quantizer losses are developed in [19 Section 3, Theorem 3.2] and [20]. Here the codebook is fixed and the regression variable is restricted to a skew query-side residual. The resulting retrieval distortion is

J(A)=∥QAX^T−Q(X−X^)T∥F22sN+λ2∥A∥F2,AT=−A,λ>0.(2)\mathcal{J}(A)=\frac{\lVert Q A\widehat{X}^{\mathsf{T}}-Q(X-\widehat{X})^{\mathsf{T}}\rVert_{F}^{2}}{2sN}+\frac{\lambda}{2}\lVert A\rVert_{F}^{2},\qquad A^{\mathsf{T}}=-A,\quad\lambda>0. \tag*{(2)}

Thus the target is the uncompressed score, rather than a geometric reconstruction loss that weights every direction equally. Define

C=QTQ/s,H=X^TX^/N,D=(X−X^)TX^/N,E=(X−X^)T(X−X^)/N,C=Q^{\mathsf{T}}Q/s,\qquad H=\widehat{X}^{\mathsf{T}}\widehat{X}/N,\qquad D=(X-\widehat{X})^{\mathsf{T}}\widehat{X}/N,\qquad E=(X-\widehat{X})^{\mathsf{T}}(X-\widehat{X})/N,

and write Π−(B)=(B−BT)/2\Pi_{-}(B)=(B-B^{\mathsf{T}})/2. These moments are sufficient to fit the correction without storing a query-by-document score matrix.

Theorem 4.1 (Unique calibrated skew solution and residual certificate). Problem (2) has a unique minimizer A∗A_{\ast}, characterized by

T(A∗):=Π−(CA∗H)+λA∗=Π−(CD).(3)\mathcal{T}(A_{\ast}):=\Pi_{-}(CA_{\ast}H)+\lambda A_{\ast}=\Pi_{-}(CD). \tag*{(3)}

On the real skew subspace, T\mathcal{T} is self-adjoint and positive definite, with eigenvalues in [λ,L][\lambda,L], where L=λ+∥C∥op∥H∥opL=\lambda+\lVert C\rVert_{\mathrm{op}}\lVert H\rVert_{\mathrm{op}}. For any skew approximation BB, put RB=Π−(CBH−CD)+λBR_B=\Pi_{-}(CBH-CD)+\lambda B. Then

∥B−A∗∥F≤∥RB∥F/λ,(4)\lVert B-A_{\ast}\rVert_{F}\leq\lVert R_B\rVert_{F}/\lambda, \tag*{(4)}
0≤J(B)−J(A∗)≤∥RB∥F2/(2λ).(5)0\leq\mathcal{J}(B)-\mathcal{J}(A_{\ast})\leq\lVert R_B\rVert_{F}^{2}/(2\lambda). \tag*{(5)}

In particular A∗=0A_{\ast}=0 if and only if Π−(CD)=0\Pi_{-}(CD)=0. The bound certifies the convex problem, not global optimality of a subsequent rank restriction.

Proof. Expanding the squared norm gives

2J(A)=tr⁡(CAHAT)−2⟨CD,A⟩F+tr⁡(CE)+λ∥A∥F2.2\mathcal{J}(A)=\operatorname{tr}(CAHA^{\mathsf{T}})-2\langle CD,A\rangle_{F}+\operatorname{tr}(CE)+\lambda\lVert A\rVert_{F}^{2}.

For skew variations ZZ, differentiation yields dJ(A)[Z]=⟨CAH−CD+λA,Z⟩F\mathrm{d}\mathcal{J}(A)[Z]=\langle CAH-CD+\lambda A,Z\rangle_{F}. The orthogonal projection onto admissible variations gives (3). For skew Z,WZ,W, symmetry of C,HC,H and cyclicity of trace imply ⟨Z,TW⟩F=⟨TZ,W⟩F\langle Z,TW\rangle_{F}=\langle TZ,W\rangle_{F}. Moreover

⟨Z,TZ⟩F=∥C1/2ZH1/2∥F2+λ∥Z∥F2.\langle Z,TZ\rangle_{F}=\lVert C^{1/2}ZH^{1/2}\rVert_{F}^{2}+\lambda\lVert Z\rVert_{F}^{2}.

References

  1. [1]B. Geshkovski, C. Letrouit, Y. Polyanskiy, and P. Rigollet. The emergence of clusters in self-attention dynamics. NeurIPS, 2023. https://arxiv.org/abs/2305.05465.
  2. [2]B. Geshkovski, C. Letrouit, Y. Polyanskiy, and P. Rigollet. A mathematical perspective on Transformers. Bulletin of the AMS 62, 427–479, 2025. https://arxiv.org/abs/2312.10794.
  3. [3]B. Geshkovski, H. Koubbi, Y. Polyanskiy, and P. Rigollet. Dynamic metastability in the self-attention model. 2024. https://arxiv.org/abs/2410.06833.
  4. [4]P. Rigollet. The Mean-Field Dynamics of Transformers. 2025; revised 2026. https://arxiv.org/abs/2512.01868.
  5. [5]C. Kuehn and J. Yoon. Spectral Selection in Symmetric Self-Attention Dynamics. 2026. https://arxiv.org/abs/2604.26085.
  6. [6]M. Saponati, P. J. Sager, P. V. Aceituno, T. Stadelmann, and B. F. Grewe. The underlying structures of self-attention: symmetry, directionality, and emergent dynamics in Transformer training. ICML, PMLR 267, 52958–52994, 2025. https://proceedings.mlr.press/v267/saponati25a.html.
  7. [7]S. Jamil and R. Kapadia. The Routing and Filtering Structure of Attention. 2026. https://arxiv.org/abs/2605.18826.
  8. [8]L. Zhang and J. Martens. Orthogonal Self-Attention. 2026. https://arxiv.org/abs/2602.05996.
  9. [9]Y. Dong, J.-B. Cordonnier, and A. Loukas. Attention is not all you need: pure attention loses rank doubly exponentially with depth. ICML, 2021. https://arxiv.org/abs/2103.03404.
  10. [10]Y. Zhang and Y.-C. Chen. Kernel Smoothing, Mean Shift, and Their Learning Theory with Directional Data. JMLR 22(154), 1–92, 2021. https://jmlr.org/papers/v22/20-1194.html.arxiv.org/abs/2010.13523
  11. [11]Y. Zhang and Y.-C. Chen. The EM Perspective of Directional Mean Shift Algorithm. 2021. https://arxiv.org/abs/2101.10058.
  12. [12]G. Huguet et al. Time-inhomogeneous diffusion geometry and topology. SIAM Journal on Mathematics of Data Science, 2023. https://arxiv.org/abs/2203.14860.
  13. [13]J. Markdahl, J. Thunberg, and J. Goncalves. Almost global consensus on the n-sphere. IEEE Transactions on Automatic Control, 2018. https://arxiv.org/abs/1609.04885.
  14. [14]J. Thunberg, J. Markdahl, F. Bernard, and J. Goncalves. A lifting method for analyzing distributed synchronization on the unit sphere. 2018. https://arxiv.org/abs/1805.02528.
  15. [15]D. Bolya et al. Token Merging: Your ViT But Faster. ICLR, 2023. https://arxiv.org/abs/2210.09461.
  16. [16]A. Shrivastava and P. Li. Asymmetric LSH for sublinear time maximum inner product search. NeurIPS, 2014. https://arxiv.org/abs/1405.5869.
  17. [17]B. Neyshabur and N. Srebro. On Symmetric and Asymmetric LSHs for Inner Product Search. ICML, 2015. https://proceedings.mlr.press/v37/neyshabur15.html.
  18. [18]H. Jegou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE TPAMI 33(1), 117–128, 2011. https://doi.org/10.1109/TPAMI.2010.57.
  19. [19]R. Guo et al. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. ICML, 2020. https://proceedings.mlr.press/v119/guo20h.html.
  20. [20]J. Zhang, D. Lian, H. Zhang, B. Wang, and E. Chen. Query-Aware Quantization for Maximum Inner Product Search. AAAI 37(4), 4875–4883, 2023. https://doi.org/10.1609/aaai.v37i4.25613.
  21. [21]E. Jaasaari, V. Hyvonen, and T. Roos. LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search. NeurIPS, 2024. https://arxiv.org/abs/2410.18926.
  22. [22]Y. Gong and S. Lazebnik. Iterative Quantization: A Procrustean Approach to Learning Binary Codes. CVPR, 2011. https://doi.org/10.1109/CVPR.2011.5995432.
  23. [23]N. Thakur, N. Reimers, A. Ruckle, A. Srivastava, and I. Gurevych. BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. 2021. https://arxiv.org/abs/2104.08663.
  24. [24]N. Muennighoff, N. Tazi, L. Magne, and N. Reimers. MTEB: Massive Text Embedding Benchmark. EACL, 2023. https://arxiv.org/abs/2210.07316.
  25. [25]Sentence Transformers. all-MiniLM-L6-v2 model card. Full pinned revision recorded in the dataset manifests. https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2.
  26. [26]Lean reference manual. Axioms and trusted assumptions. https://lean-lang.org/doc/reference/latest/Axioms.
  27. [27]The Rocq Prover. Core language and kernel. https://rocq-prover.org/doc/v9.2.0/refman/language/core/index.html. The executable used here is Rocq 9.1.1.
  28. [28]W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association 58(301), 13–30, 1963. https://doi.org/10.1080/01621459.1963.10500830.
  29. [29]Y. Yuan and K. Zuo. Least-squares symmetric and skew-symmetric solutions of the generalized Sylvester matrix equation. Applied Mathematics and Computation 265, 370–379, 2015. https://doi.org/10.1016/j.amc.2015.05.035.
  30. [30]J. Zhang and X. Luo. Optimization methods for solving matrix equations. 2024. https://arxiv.org/abs/2404.06030.
  31. [31]T. Ge, K. He, Q. Ke, and J. Sun. Optimized Product Quantization for Approximate Nearest Neighbor Search. CVPR, 2946–2953, 2013. https://www.cv-foundation.org/openaccess/content_cvpr_2013/html/Ge_Optimized_Product_Quantization_2013_CVPR_paper.html.DOI
  32. [32]M. Douze et al. The Faiss library. 2024; revised 2025. https://arxiv.org/abs/2401.08281.
  33. [33]ANN-Benchmarks contributors. Public SIFT-128 benchmark data and dataset description. https://github.com/erikbern/ann-benchmarks.
  34. [34]J. Zhan, J. Mao, Y. Liu, J. Guo, M. Zhang, and S. Ma. Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance. 2021. https://arxiv.org/abs/2108.00644.
  35. [35]L. Moreau. Stability of multiagent systems with time-dependent communication links. IEEE Transactions on Automatic Control 50(2), 169–182, 2005. https://doi.org/10.1109/TAC.2004.841888.
  36. [36]W. Bendada and G. Salha-Galvan. Two-Level Softmax Sampling Done Right: Correcting Bias from Size Imbalance and Dispersion. NeurIPS, 2026. https://arxiv.org/abs/2610.10483.
  37. [37]M. R. Hestenes and E. Stiefel. Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards 49(6), 409–436, 1952. https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf.DOI
  38. [38]C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218, 1936. https://doi.org/10.1007/BF02288367.

Paper details

vlnc:W_r9w2ntye
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents