MRVQ: One Resident Index for Dimension- and Rate-Elastic Vector Search
Sean Culatana, Shang-En Huang, Kang Li
cs.AI, cs.IR
2026-10-03
MRVQ stores one 16-byte code that truncates to any dimension and rate. It uses 17.8–22.0× less RAM than three QINCo2 indices, trailing by 0.026–0.107 nDCG@10 on FiQA.
In a RAG or agent stack, resident memory is mostly the document vectors and the index. One 768- to 1024-d fp32 embedding already occupies 3–4 KB before any index structure. A deployment also wants a menu. Dimension elasticity keeps a prefix of a Matryoshka embedding, a nested vector whose leading coordinates already work as a shorter embedding, and trades quality for query compute and bandwidth. Rate elasticity stores a shorter document code and trades quality for storage.
Training a separate quantizer for each rate gives the best quality, and the retrieval tier then keeps several code streams and several model states hot. On FiQA at 768 dimensions, the 4-, 8-, and 16-byte streams sum to 28n code bytes plus three quantizer states, 228.9 MiB. MRVQ folds that menu into one maximum-rate code and the same ledger drops to 12.88 MiB, 17.8× less. The code term alone only moves from 28n to 16n, a 1.75× gap once the corpus is large.
MRVQ fits a residual vector quantizer after the fact on frozen embeddings. The encoder is left alone. Stacked codebooks eat the error one stage at a time. With L=16 stages and K=256 codewords each, every stage index is one byte, so the first b stages are a b-byte code. One 16-byte code truncates on two axes. Dropping later residual stages sets the rate to 8 or 4 bytes. Dropping later coordinates sets the dimension to that model's prefix. The six candidate widths are 128, 256, 384, 512, 768, and 1024, and each family keeps its own subset. Serving a pair of dimension and rate is a decode. Nothing is re-encoded, and no second document code is stored.
Codebooks are fit on every prefix that will actually be served. Reconstruction error is averaged uniformly over those prefixes, and the 16 stages are weighted equally. Short prefixes are what get searched. Fit the full vector only, and the error on the dropped coordinates never enters the loss, so the short dimensions slip first. Queries stay in floating point and only documents are quantized, the same asymmetric distance used by PQ, OPQ, and RaBitQ. PQ is product quantization with a small codebook per subvector. RaBitQ is approximate nearest neighbor search with a random rotation and low-bit codes.
The memory ledger counts parameter and code bytes: 4LKD+16n for MRVQ. The per-rate baseline keeps one QINCo2 model and one code stream at each rate. QINCo2 is a neural quantizer trained for a single target rate. The shared-model baseline is the leanest single model in the comparison, including narrower width and fp16. The code stream saves 1.75× in the large-n limit. At the corpora actually tested, the large ratio comes from not copying the quantizer parameters.
PCA-scalar is a separate cheap build. Rotate with PCA, hand each coordinate a number of scalar bits proportional to its variance, and quantize coordinates independently. One eigendecomposition, no iterative codebook training, and it is excluded from the MRVQ memory table. AdANNS only makes search adapt to dimension. MatQuant nests the precision of model weights.
The sets are FiQA (57,638 documents, 648 queries) and NFCorpus (3,633 documents, 323 queries) from BEIR. Embeddings are MPNet, Nomic, and BGE at 768 dimensions, plus Mxbai at 1024. Codes are 4, 8, or 16 bytes per vector, 1/192 to 1/1024 the size of the fp32 vector. The metric is nDCG@10, a top-10 ranking score. Learned baselines share the fitting budget. Paired bootstrap uses 5000 resamples, and 10000 on the RaBitQ study.
Among the designs compared, MRVQ is the lowest-RAM point for all four families on both corpora, 12.06 to 16.88 MiB. Families that share a width share a row. Ratios are against MRVQ.
| Setting | MRVQ | Three QINCo2 | Shared QINCo2 |
| FiQA, D=768 | 12.88 MiB | 228.9 MiB (17.8×) | 25.17 MiB (1.95×) |
| FiQA, D=1024 | 16.88 MiB | 354.6 MiB (21.0×) | 31.85 MiB (1.89×) |
| NFCorpus, D=768 | 12.06 MiB | 227.4 MiB (18.9×) | 24.34 MiB (2.02×) |
| NFCorpus, D=1024 | 16.06 MiB | 353.2 MiB (22.0×) | 31.03 MiB (1.93×) |
At matched code length, per-rate QINCo2 beats MRVQ in every FiQA family and rate by 0.026 to 0.107 nDCG@10. The shared model costs about 1.9× the RAM, and its quality was not measured. Against fixed-code quantizers at the same byte budget, MRVQ is ahead by about 0.06 to 0.07 nDCG@10 over per-prefix OPQ and 0.10 to 0.12 over PQ. It wins every cell against AdANNS-OPQ, and that gap is not given as a number. The low-RAM result holds for all four families on NFCorpus.
The ratio shrinks with corpus size. Versus three per-rate models it is about 18× near the tested collections and falls toward 1.75× as n grows. Versus the shared model it is already under 1.1× at 7.3 million vectors.
PCA-scalar is compared with RaBitQ and Extended-RaBitQ at a nominal 1, 2, and 4 bits per dimension. The RaBitQ side is charged an extra 8, 20, or 20 bytes per vector, so the byte count is strict on PCA-scalar. Pooled nDCG@10 deltas, PCA-scalar minus RaBitQ, are +0.0076, +0.0029, +0.0010 and -0.0009, +0.0012, +0.0006. Every absolute gap is under 0.008, and one Mxbai 1-bit cell favors RaBitQ by 0.0039. That is a tie. On three held-out BEIR corpora, 18 cells, and 8 CPU threads, PCA training is 420× faster than matched OPQ fitting at the median and 686× at the mean, across a 47–1967× spread: 0.17–6.95 seconds against 72–416 seconds.
Two negative results were judged against thresholds fixed beforehand. On NFCorpus at 16 stages, per-rate QINCo2 converges in validation MSE and then collapses at retrieval, with nDCG@10 below half of MRVQ. All 3 BGE seeds collapse, the best at 0.035, and 1 of 3 Nomic seeds collapses. The best surviving Nomic seed is not monotone in rate: 0.294 at 16 stages and 0.320 at 8. Those runs stay in the tables. A parameter-free predictor based on residual energy points the right way and misses its bar: pooled rank correlation 0.825 against a required 0.85, and a non-empty bound on 72% of cells against a required 90%.
MRVQ is the low-memory corner and per-rate QINCo2 is the high-quality corner. Neither takes both. If the dimension-and-rate menu has to stay up and RAM is the binding constraint, one MRVQ artifact is the smallest resident state in this comparison. The 18–22× figure belongs to corpora where quantizer parameters outweigh the code stream: on-device indexes and per-tenant shards at this scale. Past a few million vectors the ledger slides toward the 1.75× code-stream gap.
At the same byte budget MRVQ still beats PQ, OPQ, and AdANNS-OPQ. The saving is duplicated quantizer state. PCA-scalar answers a rebuild question. It ties RaBitQ on quality and fits 420× faster than OPQ at the median. That result does not belong in the memory claim.
The quality study is two modest BEIR corpora and four embedding families, published as a NeurIPS 2026 MLForSys workshop paper. It measures the byte ledger and nDCG@10. It does not measure end-to-end latency, recall–throughput, or build energy. Less RAM is not a faster query. Shorter coordinates should cut distance arithmetic, and no query-time number is reported.
On a larger corpus the edge over a shared model narrows the way the formula says. The ledger omits optimizer state and runtime buffers, and it is not measured RSS, so a live process will show a smaller ratio.
The closer memory opponent is the shared model, only about 1.9× more RAM, and its nDCG was never run. The 17.8–22× claim assumes three full models stay resident. The 0.026–0.107 gap is FiQA only. On NFCorpus, 16-stage QINCo2 collapses for some seeds, and MRVQ is the system that still retrieves there. Prefix weights are uniform across stages, and the main text never ablates a codebook fit on the full dimension alone.