CS Paper Radar

Closed Forms and Synthetic Twins: Predicting Approximate Nearest Neighbor Recall from Embedding Statistics

Shmuel Herman

cs.IR ·submitted 2026-08-31 20:58 UTC · v1

Abstract

Embedding models are trained and evaluated as if retrieval were exact; in production they serve behind approximate indexes -- HNSW, IVF, product quantization, or the fixed-dimensional encodings (FDEs) of late-interaction models -- whose behavior the encoder's benchmarks never see: one modern encoder recovers just 14% of its exact top-10 through its raw FDE index. Such failures surface only after an index is built, and the standard patches -- corpus-fitted transforms such as whitening -- must be fitted, stored, and refit as the corpus changes, and can silently rewrite what the encoder returns. This paper shows that index behavior is predictable before anything is built, from label-free statistics of the raw embeddings, through a ladder of instruments matched to what each index family consumes: (1) closed-form moment statistics for the fixed-grid quantizers (PQ, FDE); (2) simulation on a synthetic twin corpus -- cluster statistics made generative, on which any index, composed production systems included, can be built and tested -- for partition indexes; (3) size-extrapolated, lightly calibrated twins for graph indexes at million-document scale. Predictions land within 0.03 of measured recall on an unseen million-document corpus. The same geometry is trainable: targeting the one statistic no post-hoc transform can move -- the score margin -- lifts recall for every index family at once, at a small measured task cost. The result: index choice, correction pricing, and production recall forecast from one cheap measurement pass, on new corpora and new indexes alike; serving without per-corpus transform machinery, suited to continuously changing corpora; and a recall-compute frontier pushed by adapting encoders to geometry rather than coupling them to any single index.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantize by Drift: Label-Free Mixed-Precision Post-Training Quantization for Text Embedders

cs.IR cs.CLcs.LG ·2026-10-06 ·Hyojung Han, Jongmin Kim, Seung-Hun Jeon
hot direction similarity 0.64
Abstract · 26 pages, 22 tables, 4 figures

Mixed-precision post-training quantization needs a per-module sensitivity signal; for a text embedder the obvious one -- the retrieval quality a module costs when quantized -- needs relevance labels that deployments rarely have. We measure a label-free substitute: quantization-induced representation drift, obtained by quantizing one module, re-encoding the corpus, and recording how far the output embeddings moved from their full-precision positions. What is specific is the observable: the deployed output representation a dense retriever ranks with. Across five development embedders, configuration-level drift orders sampled mixed-precision plans against held-out retrieval quality at a macro Spearman of 0.911, the sensitivity transports across calibration corpora and retrieval domains in the usable regime, module drifts compose rank-consistently but not numerically, and relevance-derived sensitivity adds no consistent value. The method is one additive allocation under a hard packed-byte budget, with no labels and no search. On three embedders held untouched until method, baselines and hypotheses were frozen and sealed, the pre-registered directional hypothesis against the prior LieQ criterion holds (3/3 at the main budget, no collapse) and drift scores above a two-sided LieQ steelman in 2/3; but at the main budget drift is numerically lower than same-budget uniform precision on all three (-0.99, -0.85, -1.01 points), having reduced module and whole-model drift as designed. Output drift is thus a robust coarse sensitivity signal, not a universally optimal allocation objective: it avoids the catastrophic failures of the transferred signed-geometry adaptation and can remain usable at stressed budgets where uniform collapses, but fine-grained redistribution around a strong uniform operating point remains unresolved.

0.31

Balancing hierarchical representation and quantization: A performance trade-off in text embeddings

cs.CL cs.IRcs.LG ·2026-11-04 ·Kai Ponel, Marco Polignano, Erasmo Purificato, Aylin Julia Temizkan, Marco Levantesi +2 more
publishedbenchmark similarity 0.61
Abstract · 29 pages. Authors' version of the open access article published in Information Sciences (CC BY 4.0). This version corrects the second affili…

Hierarchical text embedding models offer variable-length representations, while quantization reduces numerical precision; both aim to improve computational efficiency. This work is an empirical benchmark study of how these two orthogonal, already-established techniques interact. We evaluate 38 tasks from the Massive Text Embedding Benchmark (MTEB) using four transformer-based embedding models, covering 1D and 2D hierarchical representations combined with 32-bit, 8-bit, and binary quantization, for 168 configurations per task. We report each efficiency dimension separately: theoretical per-vector storage and end-to-end evaluation time. Under a Friedman test with Nemenyi post-hoc analysis, int8 quantization is statistically indistinguishable from float32 for pair classification and re-ranking and costs at most 1.5 percentage points overall, whereas binary quantization is significantly worse across every task category. Halving the embedding dimension once is not statistically detectable above $m=16$; two successive halvings always are. Combining an 8x dimensionality reduction with int8 yields a 32x reduction in per-vector storage at 94.4% of baseline effectiveness. Because evaluation times were measured once, we treat them as indicative: we find no evidence that quantization speeds up evaluation, whereas sampling from intermediate layers shortens it substantially. Retrieval degrades far faster than every other category, so we report findings per task category.

0.31

Semantically Rich, Metrically Affect-Blind: A Geometric Blind Spot in Modern Text Embedders

cs.CL cs.LG ·2026-10-23 ·Mahdi Naser Moghadasi
code/data similarity 0.61
Abstract · 6 pages, 2 figures, 3 tables. Code: https://github.com/mahdinaser/sent2vec-sise

We report a systematic dissociation in modern text embedders: sentiment is almost perfectly decodable from their embeddings, yet almost entirely absent from their metric. Across eleven frozen encoders spanning 2021 to 2026, including 2026-generation models and the 4B-parameter LLM embedder Qwen3-Embedding-4B, a linear probe recovers sentence polarity at up to 91.3% accuracy while cosine similarity separates polarity by a margin of only 0.003-0.064. Qwen3-Embedding-4B, the strongest probe in the panel, reaches 91.3% probe accuracy but only 64.3 retrieval MAP. Because retrieval, clustering, deduplication, and retrieval-augmented generation operate on the metric rather than on a trained probe, these systems are effectively blind to information their encoder demonstrably contains. A task-conditioning control suggests this reflects the pretraining objective rather than a prompting artifact: conditioning Jina-v5 on its classification task rather than its retrieval task recovers only about half of the MAP gain that injection achieves on the same weights (63.2 to 73.8, versus 85.1), and leaves the alignment gap essentially unchanged. Sentiment-Injected Sentence Embeddings (SISE) train a small (0.13M-0.69M-parameter) supervised-contrastive head on a frozen encoder in seconds on a CPU, using the labelled training set. The head improves every encoder released since 2022 on full-data probe accuracy (up to +5.8 points), retrieval MAP (up to +26.0) and polarity margin (7-61x). This is a specialization, not a free gain: the compact 128-d head loses 38-41 Spearman points on STS-B, while a fused variant that concatenates it with the base embedding loses 2.4-12.0. With the head, a 0.6B encoder at 128 dimensions matches a 4B encoder given the same head (91.8 vs. 90.3 MAP). We release a CPU-reproducible pipeline and a reusable diagnostic, the Attribute Alignment Gap.

0.44

The COUNT: Counting N-grams Unlocks Scaling on Host Memory and Training-Free Adaptation

cs.CL cs.LG ·2026-10-14 ·Ian Magnusson, Noah A. Smith, Pang Wei Koh
similarity 0.60
Abstract

The scaling relationship of compute and performance for language models (LMs) has been extensively studied; more recently, models are being designed to scale memory use, as well. In particular, adding embeddings for n-grams scales memory separately from compute use, because each pass only processes individual embedding rows, which are much smaller than the storage used for the whole embedding table. However, existing methods train embeddings from scratch, which needs expensive GPU memory for fast reading and writing. Meanwhile, the ordinary memory of the host system is cheap and underutilized by these training methods. To scale on host memory, we introduce COUNT (Counting Offline Unlocks N-gram Transformers), which builds n-gram embeddings without adding learned parameters by storing precomputed n-gram counts on host. We use the corpus frequencies to weight together the LM's own unembeddings of the next tokens most often following the current n-gram history. At a fixed compute budget, COUNT can be added as an additional input embedding for pretraining 1B-parameter LMs to improve validation loss as much as an LM with 57% more compute. If GPU memory is limited, using COUNT to let backbone parameters fill GPU memory gives better performance than splitting memory with additional learned n-gram embeddings. Beyond efficiency, COUNT allows switching in a different table of n-gram counts from a domain-specific corpus at inference time to adapt to a new task without any training.

0.25

RSLM: Training-Free Vector Quantization for Approximate Nearest Neighbor Search

cs.LG cs.IR ·2026-08-31 ·Rastislav Lenhardt, Teodora Dobos, Thomas Vecchiato, Jiri Isa, Igor Ginzburg
benchmark similarity 0.59
Abstract · 14 Pages, 3 Figures, Preprint

By introducing RSLM (Rotated Scaled Lloyd-Max), a family of training-free vector quantization codecs compressing embeddings to 1--4 bits per dimension, we reduce memory cost and memory bandwidth of a typical large-scale Approximate Nearest Neighbor (ANN) search system, while reducing its complexity and keeping or improving recall across multiple benchmark datasets. State-of-the-art systems filter candidates using coarse partitions, approximately score them to narrow the set, and then rescore the best with higher precision representations (often >=8 bits per dimension). Our relativized codecs can bring this down to 2--4 bits per dimension. We use the properties of the ANN system to encode residual vectors instead of full vectors, both for the approximate scoring phase and the rescoring phase. Since Maximum Inner Product Search (MIPS) is very sensitive to vector norms, we correct the $L_2$ norms of quantized vectors. Our major innovation is that we correct the $L_2$ norm of the final reconstructed vector rather than just the residual. Our rescaling replaces more complicated schemes, such as Anisotropic loss. The residualization scheme gives us a more favorable quality vs size trade-off than generic quantization methods. Our high-performance implementation leverages a block-wise cascaded Fast Walsh-Hadamard Transform (FWHT) with linear-like complexity, AVX SIMD-optimized codebooks, and a steganographic encoding of scaling factors for perfect cache-line alignment.

0.36

N-Gram Memories at Two Bits: Quantizing Lookup Tables in Large Language Models

cs.LG cs.CL ·2026-10-15 ·Donghoon Han, Minseop Jung, Dong Woo Kwak, SeungJae Lee, Junhoo Lee
similarity 0.59
Abstract

Conditional memory expands language-model capacity through selective lookup, but the full embedding table must remain available for every possible input. We introduce Conditional Program (CP), a compressed representation that reconstructs only the rows an input requests. CP represents each row by a short code and a local scale, with a reconstruction program shared across the table. We instantiate this representation with a Gaussian trellis, norm restoration and independently decodable row records. CP's two-bit code lowers output KL by 41--63\% relative to 2-bit round-to-nearest. Analysis across three trained n-gram memory families shows that Gaussian-like coordinate statistics coexist with learned relationships among rows; at matched storage budgets, the shared trellis outperforms the fitted codebooks and low-rank residual variants we test. For DeepSeek, it reduces table storage from 203GB to 51GB, leaving room for larger workloads when the table is kept on GPU.

0.47

UIBK-Embedding: Effective Text Retrieval by Unifying Dense and Late-Interaction Retrieval

cs.IR ·2026-10-19 ·Abdelrahman Abdallah, Mohammed Ali, Adam Jatowt
code/data similarity 0.59
Abstract

Dense bi-encoders and late-interaction retrievers are usually treated as alternatives, yet they fail on different queries: one vector captures what a text is about, token-level matching finds its exact entities and phrases. Using both today means two models, two indexes and a score-fusion step. We present UIBK-Embedding-v1, a 179M-parameter English encoder that produces both representations in one pass and scores them with one unmodified MaxSim. The dense embedding is written into the list of token vectors as three extra vectors, and a one-dimensional tag keeps the two kinds of vectors from matching each other, so that plain MaxSim equals the token-level MaxSim plus a weighted dense cosine. The model therefore runs in a standard late-interaction index without changes; we test it with PLAID. A shared 18-layer trunk with a separate 4-layer top per head, and a cross-encoder distilled into the fused score, turn the two heads into one retriever. On BEIR, UIBK-Embedding-v1 reaches 59.79 nDCG@10. This is 2.57 points above LateOn, the strongest model of its size, and 2.10 points above it when both models read documents of the same length; UIBK-Embedding-v1 is ahead on all 15 datasets. On a decontaminated version of BEIR it stays ahead on average (61.55 against 60.36) and on 8 of 12 datasets. Among the 156 models with complete BEIR results in the MTEB results repository, only models with at least 1.5B parameters score higher. Code, model weights, and a technical blog post are available at https://github.com/DataScienceUIBK/uibk-embedding , https://huggingface.co/DataScience-UIBK/uibk-embedding-v1 , and https://huggingface.co/blog/abdoelsayed/uibk-embedding-v1 .

0.33

Computation Over Geometry: Meaning Identity Is Computed, Not Shipped in the Embeddings

cs.CL ·2026-09-23 ·Jiaqi Deng
similarity 0.59
Abstract · 12 pages, 2 figures. Code to be released

Meaning identity (whether two sentences say the same thing after wording changes) is treated in retrieval and RAG as a geometric fact about independently encoded sentence vectors. We show that, for frozen off-the-shelf encoders and language models, it is not: identity is computed when both sentences share one forward pass, and is not a property of the embedding geometry those systems ship. On overlap-matched PAWS-X, purpose-built encoders (BGE, E5, GTE, MiniLM, E5-Mistral-7B) reach English confirm AUC only 0.55-0.65 (dense peak 0.70). Independently encoded last-token states of Llama 3, Mistral, and Qwen do no better; late fusion of the two vectors stays near chance. The same probe on a joint forward pass reaches 0.90-0.96 from 1.5B to 32B, collapses under partner shuffle, is mid-depth, saturates near 0.94 by 3B, and appears more weakly in GPT-2 XL (0.76). The gap holds beyond Llama-style models on other causal LMs, bidirectional encoders (DeBERTa, RoBERTa), and encoder-decoders (Flan-T5, T5, BART). Fixed or linear readers over frozen independent encodings never unlock identity; nonlinear pair readers recover part of it only on the full 49k-pair PAWS train split (0.68-0.87). Off-the-shelf rerankers split: BGE-reranker-large reaches 0.94, while MS-MARCO and Jina stay at 0.55-0.64. Independently trained families compute the same relation and a 1.5B joint reader can distill it from unlabelled teacher scores, while no linear function of the teachers own independent vectors can. Bi-encoders can be fine-tuned to fit PAWS (0.87-0.93), but transfer and STS-B suffer. Cosine compares wording neighbourhoods; identity is a cheap computed operator, not a property of either sentence vector.

0.50