Bits, Bytes & Vision

Exploring the intersection of high performance computing, modern C++, computer vision, and storage systems. Deep technical insights into building performant software systems, optimizing databases, and implementing efficient computer vision algorithms.

Project maintained by sam-herman Hosted on GitHub Pages — Theme by mattgraham

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

Samuel Herman

arXiv preprint · cs.IR (Information Retrieval) · August 2026

TL;DR: Embedding models are trained and benchmarked as if retrieval were exact, but in production they sit behind approximate indexes—HNSW, IVF, product quantization, or the fixed-dimensional encodings of late-interaction models—whose recall the benchmarks never measure. This paper shows that an index’s behavior is predictable before anything is built, from label-free statistics of the raw embeddings: closed-form moment statistics for fixed-grid quantizers, a generative “synthetic twin” of the corpus for partition indexes, and size-extrapolated twins for graph indexes. Predictions land within 0.03 of measured recall on an unseen million-document corpus, and the same geometry is trainable: targeting the score margin lifts recall for every index family at once.

The paper's two headline facts: the fidelity/efficiency trade for PQ and FDE corrections, and synthetic-twin recall predictions for HNSW and IVF across 17 encoders The paper’s two headline facts, from measured data. Left pair: the fidelity/efficiency trade drawn as a before→after move; each panel starts at its corpus’s native baseline (open square). On the dense corpus the correction is free: the OPQ rotation gains 0.16 efficiency with fidelity kept. On the late-interaction corpus the correction costs fidelity and pays: centering spends 0.08 fidelity for 0.42 efficiency, while whitening (dashed) buys the same gain for 0.15. Right: recall simulated on a cluster-matched synthetic twin—built purely from label-free statistics, with no real index—predicts measured recall for both HNSW and IVF across 17 encoders with zero fitted parameters.

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.

Keywords: approximate nearest neighbor search, vector databases, embedding geometry, synthetic twin corpora, anisotropy, product quantization, MUVERA, fixed-dimensional encodings, HNSW, whitening, exact-neighborhood preservation, recall–compute trade-off.

At a Glance

The paper builds a ladder of instruments, each matched to what an index family actually consumes from the embedding distribution:

Closed-form moment statistics for fixed-grid quantizers—product quantization and the fixed-dimensional encodings used to index late-interaction models.
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 such as IVF.
Size-extrapolated, lightly calibrated twins for graph indexes such as HNSW at million-document scale.

Predictions land within 0.03 of measured recall on an unseen million-document corpus. The same geometry is also trainable: targeting the score margin—the one statistic no post-hoc transform can move—lifts recall for every index family at once.

The three core instruments: fidelity, efficiency, and score margin The three core instruments, schematically. (a) A corrective transform moves points, so the transformed space’s own exact top-k (filled) is no longer the original top-k (rings): the overlap is fidelity p. (b) Within the transformed space, an index at a fixed budget scans only part of the corpus (ringed): the fraction of the space’s own top-N it finds is efficiency s, and end-to-end recall obeys r ≥ p + s − 1 at matched depth. (c) The score margin—the gap between the k-th exact score and the deeper field—is the ranking’s tolerance to the score noise an index injects; the two strips use the paper’s measured margins (native 0.069 vs. margin-sharpened 0.193, same top-10), and survival rises with the margin-to-noise ratio.

Read the Paper

arXiv abstract page: arxiv.org/abs/2609.00364
PDF: arxiv.org/pdf/2609.00364
HTML (experimental arXiv rendering): arxiv.org/html/2609.00364
DOI: 10.48550/arXiv.2609.00364

Cite

Shmuel Herman. Closed Forms and Synthetic Twins: Predicting Approximate Nearest Neighbor Recall from Embedding Statistics. arXiv:2609.00364 [cs.IR], 2026. https://doi.org/10.48550/arXiv.2609.00364

@misc{herman2026closedformssynthetictwins,
      title={Closed Forms and Synthetic Twins: Predicting Approximate Nearest Neighbor Recall from Embedding Statistics},
      author={Shmuel Herman},
      year={2026},
      eprint={2609.00364},
      archivePrefix={arXiv},
      primaryClass={cs.IR},
      url={https://arxiv.org/abs/2609.00364},
}

The blog posts below cover the ground this paper builds on—embedding geometry, quantization behavior, and the index families whose recall the paper predicts:

This work is licensed under CC BY 4.0.