CS Paper Radar

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

Faruk Alpay, Taylan Alpay

cs.LG cs.IRmath.DS ·submitted 2026-11-01 21:58 UTC · v1
benchmarktheory

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_{β\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(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.

Comment
42 pages, 9 figures, 10 tables. Includes mathematical appendices and ancillary reproducibility code

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Fusion of Softmax Attention Heads Can Require Exponentially Many Atoms

cs.LG cs.NEstat.ML ·2026-11-02 ·Hiroyasu Usami, Keisuke Hara, Ayato Tsuboi, Naohiko Matsuda
theorycode/data similarity 0.61
Abstract · 9 pages, 3 figures. Code and reproducibility materials: https://github.com/usamihiroyasu/attention-head-fusion

Fusing independently normalized attention heads can increase the number of explicit key-value entries, or atoms, needed to preserve their output. We prove a sharp separation for $W_d(q)=\sum_{j=1}^dσ(q_j)$: its $d$ two-atom heads use $2d$ head-atom terms, whereas its minimum single-head representation has exactly $2^d$ atoms, even with arbitrary fixed replacement keys, scalar values, and positive masses. The same lower bound holds for every fixed uniform error below $1/2$ on $\mathbb R^d$, and the threshold is sharp. The proof uses exposed-key normal cones; exact equality on any nonempty open query domain inherits the bound. The resulting atom bound for a fixed head count is tight when that count divides $d$. A normalized family retains its exponential exact minimum while approaching a constant on fixed-radius query balls. For pretrained-model caches, a classical affine-rank bound and a certified instance exclude exact vector preservation at a specified atom count. Learned-cache comparisons on two disjoint banks of 64 contexts show budget-dependent reversals and calibration effects.

0.33

Beyond Multiplicity Correction: Sharp Retrieval Thresholds for Attention with Correlated Distractors

cs.LG math.PR ·2026-10-26 ·Heehyun Park
similarity 0.60
Abstract · 42 pages, 2 figures, 3 tables

Redundant context affects attention in two distinct ways: multiplicity adds normalization mass, while score variation within correlated groups can produce extreme individual scores. We separate these effects in a planted retrieval model with exponentially many Gaussian distractors organized into supplied clusters whose number and size both grow exponentially with dimension. The model is a two-level generalized random energy model, whose classical free energy yields exact retrieval thresholds. Gaussian interpolation further shows that increasing positive correlation at fixed token count lowers the distractor free energy, unlike adding duplicates. Our main result establishes a sharp limitation of count correction, which subtracts the log cluster size from pre-softmax scores: this correction removes multiplicity but retains within-cluster extremes. Even when the inverse temperature is chosen after observing all scores, count correction requires a signal at least $\sqrt{2α_1}$, where $α_1$ is the exponential growth rate of the number of clusters. By contrast, averaging scores before exponentiation suppresses token-level fluctuations and lowers the optimal signal threshold to $\sqrt{2ρα_1}$, where $ρ$ is the within-cluster correlation. This gap persists after adding exponentially many singleton distractors, so group size alone does not identify the target, and extends, under explicit cumulant regularity assumptions, to fixed finite hierarchies of independent-increment scores. Finite-sample, stability, and participation results complement the asymptotic analysis. A controlled retrieval experiment with frozen sentence embeddings illustrates both sides of the distinction: averaging helps when the relevant item is a singleton, but can discard useful evidence when a relevant group contains multiple matching items.

0.21

Magnitude Profile Pruning: Calibration-Free Structured Attention Head Removal for Transformer Compression

cs.CL cs.AIcs.LG ·2026-08-11 ·Kasun Dewage, Marianna Pensky, Heranga K. Rathnasekara, Suranadi De Silva
published similarity 0.60
Abstract · Accepted as a regular paper at IEEE ICMLA 2026; to appear in the conference proceedings

Structured pruning of attention heads provides a hardware-friendly way to compress Transformer language models. However, existing methods for measuring head-level importance require calibration data, gradient computation, or Hessian estimation. These requirements add extra overhead and make the methods depend on the data. Our work presents Magnitude Profile (MP) scoring, a training-free criterion for head importance that identifies dispensable heads through statistical outlier detection on weight row norms. Heads whose projection weights fall within the population bulk are pruned, while heads exhibiting outlier norms, which carry disproportionate representational capacity, are preserved. Our work further gives MP-G, a variant that handles Grouped Query Attention (GQA) by distributing shared key-value group scores across associated query heads. Across five models evaluated on WikiText-2 perplexity at 12.5%-50% head sparsity, MP-G achieves the best perplexity on OPT-6.7B at all sparsity levels (18.46 at 12.5%, 27.87 at 25%, 152.0 at 50%). MP-G also gives the best results on RoBERTa-large at 12.5% and 25% sparsity, with perplexity values of 7.27 and 10.28, outperforming calibration-dependent baselines including Wanda-Head, SparseGPT-Head, and Gradient-Head. It requires zero forward passes, calibration samples, or gradient computation. At 50% sparsity, head pruning yields up to 16% parameter reduction with 50% attention FLOP savings. Our results show that weight-only statistical scoring can match or outperform data-dependent methods for structured head pruning, providing a practical, zero-cost criterion for Transformer compression.

0.17

Riemann GeoResolver: A Non-Euclidean Attention Framework from Euclidean Resolver to Hyperbolic-Spherical Geometry

cs.DS cs.AIcs.CLcs.LG ·2026-08-11 ·Liangchen Ge
theory similarity 0.60
Abstract · 37 pages, no figures, theoretical paper

We present a theoretical foundation for inverse-distance attention, from its Euclidean prototype (Resolver) to its non-Euclidean realization (Riemann GeoResolver). The Euclidean part establishes three core theorems: (1) circuit separation---IDA achieves exact retrieval with $\mathcal{O}(1)$ resources while softmax requires $Ω((\log n)^2)$ width; (2) a Polyak--Lojasiewicz inequality with $Ω(e^{Δ^2/\sqrt{d}}/Δ^2)$ stronger constant than softmax, implying linear convergence, $\mathcal{O}(\log n)$ Lipschitz scaling under a low-rank/clustering assumption, $Θ(1)$ Hessian spread, and absence of spurious local minima; (3) a width-independent effective rank bound that limits noise memorization---softmax memorizes arbitrary labels when $d_h\ge n$, while IDA limits test error to $\mathcal{O}(η^2)$. The non-Euclidean extension then builds upon this prototype, replacing Euclidean distance with hyperbolic geodesic distance for storage and spherical geodesic distance for routing. The Riemann GeoResolver framework comprises ten integrated modules: four HIDA operators spanning $Θ(n^2)$ to $Θ(1)$ per token; Hyperbolic Curvature Compression (HCC) with provable error bounds; HyperGate with gradient lower-bound theorem; Spherical Inverse Distance Attention (SIDA) with sphere-analog PL inequalities; Dynamic Memory Genesis (DMG) with $\mathcal{O}(\log T)$ regret bounds; and Geodesic Sparse Routing (GSR) with quality and communication bounds. The Euclidean theorems are proved in full; the non-Euclidean extension theorems are proved with analogous arguments. This work establishes a theoretical arc: from Euclidean attention as a special case, to hyperbolic memory, to spherical retrieval.

0.38

HCC+: Hyperbolic Guarding for Certified Attention Retrieval

cs.DS cs.LG ·2026-08-25 ·Liangchen Ge
theory similarity 0.59
Abstract · 9 pages, no figures, theoretical paper

We study the Lipschitz stability of attention retrieval in hyperbolic spaces. Existing methods lack deterministic guarantees on attention-weight preservation under finite-precision representations. We introduce HCC+, a theoretical framework exploiting three properties of the Poincaré ball: exponential volume growth enabling query-independent boundary truncation; logarithmic covering radius of hyperbolic 1-centers enabling dimension-independent critical-key identification; and a packing bound with constants independent of the embedding dimension. We prove two deterministic guarantees: for exact retrieval, the per-layer attention deviation is bounded by 10\% of its ideal value; for soft attention, the total variation distance decays as $O(1/\sqrt{n})$, the rate of finite-sample variance. As a consequence of the guarding mechanism, the framework achieves a storage reduction factor of $6.1\times$ relative to FP16. We provide the first deterministic, query-independent retrieval certificate in non-Euclidean geometry.

0.27

Spherical Interpolation for Backward-Compatible Multimodal Representations

cs.CV cs.LG ·2026-09-30 ·Simone Ricci, Niccolò Biondi, Federico Pernici
top venuecode/data similarity 0.58
Abstract · Accepted at NeurIPS 2026

Contrastive vision-language models map visual and textual representations into a shared normalized embedding space, making cosine similarity the natural metric for cross-modal retrieval. A practical challenge arises during model upgrades: independently trained models generally produce incompatible representation spaces, so replacing a deployed model typically requires recomputing embeddings for the entire gallery, which is prohibitively expensive at scale. Orthogonal post-hoc alignment can partially mitigate this problem by mapping new-model queries into the old-model gallery space. However, because independently trained models can differ in fine-grained representation structure, the orthogonal alignment remains approximate, leaving a residual angular discrepancy between the old-model query and the aligned new-model query. We study whether interpolation along the spherical geodesic between these two normalized query representations can improve retrieval without re-indexing the gallery. We characterize when this path contains an interior query direction closer to an idealized retrieval-optimal direction than either endpoint, and connect this characterization to Recall@$K$ through a local margin-based certification result. Experiments across multiple benchmarks and model families show that post-alignment spherical interpolation improves over orthogonal alignment alone, recovering backward-compatibility in most evaluated settings. Consistent with our geometric characterization, per-query oracle analysis shows that retrieval-favorable interior points occur frequently in practice. Code is available at https://github.com/miccunifi/SLERP_backward_compatibility .

0.75

Beyond Sparse Weights: When Is Attention Compressible?

cs.LG cs.CL ·2026-08-21 ·Chiwun Yang, Xiaoyu Li
similarity 0.58
Abstract · 37 pages, 9 tables, 11 figures

KV-cache compression is often justified by attention maps with a few large weights. This is incomplete: large weights may not contain most of the mass, omitted values can cancel, and preserving the attention output may not preserve the task. We separate these questions. Global score gaps -- not threshold counts -- determine how many tokens are needed to retain a target mass. For a realized row, the weighted sum of omitted values is the exact missing statistic. A controlled retrieval--aggregation model explains when truncation helps and when it hurts. These results motivate CertKV, a training-free compressor that reserves one tail-summary slot per head and allocates the rest by value dispersion. Under matched budgets, CertKV is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype. Compressibility depends on the mass, values, future queries, and task -- not on a sparse-looking map alone.

0.34

Sliced Wasserstein Sketches with Error Certificates

cs.LG ·2026-10-14 ·Elaheh Akbari, James Liu, Keaton Hamm, Soheil Kolouri
similarity 0.57
Abstract

Compact representations that support geometrically meaningful comparisons are valuable for learning from probability distributions. We study optimal, free-weight $M$-atom quantization of one-dimensional probability measures in quadratic Wasserstein distance and extend it to higher dimensions via slicing. Using $L$ shared projections yields a sketch with $O(LM)$ comparison time. Our main result is an exact decomposition of squared distance error into residual and partition-mismatch terms, yielding computable certificates for arbitrary centroid sketches. For optimal sketches, a finite $(2+δ)$ moment for some $δ>0$ guarantees $O(M^{-1})$ error in the finite-direction sliced distance, while equal-mass sketches can converge more slowly. Each slice preserves its mean, while storing residual energies enables covariance recovery from sufficiently many generic directions. Experiments on document, point-cloud, and flow-cytometry benchmarks show that optimal sketches substantially reduce storage while preserving the classification performance of uncompressed sliced distances. They also improve generalization from few labelled subjects and support end-to-end learning as compact pooling layers.

0.23