CS Paper Radar

MRVQ: One Resident Index for Dimension- and Rate-Elastic Vector Search

Sean Culatana, Shang-En Huang, Kang Li

cs.AI cs.IR ·submitted 2026-10-02 17:33 UTC · v1

Abstract

Dense-retrieval services must switch among embedding-prefix dimensions and index bit rates as latency, quality, and memory budgets change. Tuning a quantizer separately for each rate gives the best quality, but the retrieval tier then holds several code streams and quantizer states at once. We introduce Matryoshka Residual Vector Quantization (MRVQ), a post-hoc residual quantizer for frozen embeddings. Its maximum-rate code can be truncated two ways: dropping residual stages lowers the rate, and dropping embedding coordinates lowers the dimension. One resident artifact therefore serves every (dimension, rate) pair we evaluate. Across FiQA and NFCorpus, four embedding families, and {4, 8, 16}-byte codes, MRVQ is the lowest-RAM design we evaluate. It uses 17.8-22.0x less memory than three separately trained QINCo2 indices, and 1.89-2.02x less than a lean shared-model steelman. The saving is not free: per-rate QINCo2 is 0.026-0.107 nDCG@10 better on FiQA. But MRVQ beats PQ, OPQ, and AdANNS-OPQ at matched code size. We also evaluate a low-build-cost PCA-scalar design that attains quality comparable to RaBitQ and its extension while fitting 420x faster at the median. Finally, we report two negative results: QINCo2 collapses when trained at high rates, and a ranking-bound hypothesis misses its pre-specified acceptance criteria. MRVQ is therefore a low-memory operating point for elastic retrieval, not a universal quality winner.

Closest papers

Nearest neighbours by meaning across the whole index.

MiSTiQ: MicroScaling Trellis Quantization for Extreme KV Cache Compression

cs.LG ·2026-11-16 ·Ofir Gordon, Lior Dikstein, Paul Balanca, Idan Achituve, Douglas Orr +1 more
similarity 0.73
Abstract · 26 Pages, 7 Figures, 7 Tables

Modern large language models (LLMs) increasingly support longer contexts and serve more concurrent requests, increasing both sequence lengths and batch sizes. Both trends increase KV-cache size and memory traffic during inference. KV-cache quantization reduces these costs, with recent approaches using codebook-based vector quantization to achieve extremely low bit widths. However, hardware constraints limit codebook size, and most methods reconstruct the cache in higher-precision floating-point formats for attention, limiting the computational benefits of quantization. To address these limitations, we introduce MiSTiQ, a drop-in replacement for codebook-based vector quantizers that combines trellis-coded storage with microscaling (MX) formats for low-precision computation. We combine trellis quantization with beam search to encode the KV cache over large reconstruction spaces without large codebooks. To support MX computation, we derive MX-Hash functions that generate reconstruction values directly in the target MX element format. These functions use the scale-conditioned marginal distribution of block-normalized Gaussian inputs. On Llama3 and Qwen3, MiSTiQ achieves lower WikiText perplexity and higher GSM8K accuracy than the evaluated baselines across several block-scale formats at approximately 1.25 effective bits per element. With NVFP4, it also achieves the highest LongBench average on both models.

0.20

Quantization Beyond Uniform Bit Allocation

cs.IR cs.DB ·2026-08-19 ·K. S. Sreeramji, Sabyasachi Basu, Ravishankar Krishnaswamy, Kirankumar Shiragur, Yujia Wang
published similarity 0.70
Abstract · Accepted at the 2nd Workshop on Vector Databases (VecDB), part of 52nd International Conference on Very Large Data Bases (VLDB 2026)

Quantization is a fundamental technique to handle the growing sizes of embeddings generated by modern models. Existing quantization schemes are largely embedding agnostic and allocate bits uniformly across dimensions. However, recent models produce embeddings with significant geometric structure. In this work, we investigate whether a variable bit allocation scheme can improve quantization quality under a fixed memory budget. We propose a simple variable bit allocation framework that partitions an embedding into contiguous buckets and allocates storage non-uniformly across them. Using a greedy allocation strategy, we instantiate this framework for both Product Quantization (PQ) and Scalar Quantization (SQ). We perform a series of experiments on embeddings known to have the Matryoshka property (MRL), and consistently observe that non-uniform allocations outperform uniform baselines at identical storage budgets. The largest improvements occur in the low-bit regime, where uniform allocation is particularly inefficient for MRL embeddings. At the same compression rates, variable allocation improves recall by up to 8\% for PQ and up to 18\% for SQ. Our results suggest a new direction for structure-aware compression and indexing techniques for large-scale retrieval systems.

0.25

Tailoring the Quantization Space for 1-Bit KV Cache Compression

cs.LG cs.AIcs.CL ·2026-10-02 ·Minsoo Cheong, Donghyun Son, Sungjoo Yoo
similarity 0.70
Abstract

The key-value (KV) cache becomes a major memory bottleneck in long-context LLM inference, placing substantial pressure on memory capacity and bandwidth. To mitigate this bottleneck, vector quantization (VQ) has emerged as a promising approach for aggressive KV cache compression. However, existing VQ methods degrade substantially in the 1-bit regime. At such extreme compression, each codebook must represent a larger group of channels with a limited set of centroids, making effective use of its capacity increasingly challenging. To address this, we introduce $\textbf{TaSQ}$, which tailors the VQ target space by combining query-guided channel weighting, cross-head normalization, and covariance-aware channel grouping to better reflect the error sensitivity and statistical structure of cached activations. Since these transforms are RoPE-compatible and can be easily merged into projection weights and codebooks, TaSQ preserves the conventional VQ lookup structure and adds negligible serving overhead. Across general, long-chain-of-thought reasoning, and long-context retrieval benchmarks, TaSQ consistently outperforms existing low-bit KV cache VQ baselines while preserving reasoning stability. On a single RTX 6000 Ada GPU, its SGLang implementation supports up to $14\times$ larger batch sizes and achieves $1.87\times$ higher peak throughput compared to the BF16 baseline.

0.38

Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval

cs.IR cs.AIcs.LG ·2026-09-07 ·Peichun Hua, Yunming Xiao
similarity 0.68
Abstract · 12 pages, 2 figures, 12 tables

Retrieval-augmented generation (RAG) depends on dense retrieval: each document is stored as a learned vector, and queries are answered by nearest-neighbor search. Keeping one full-precision vector per document dominates index cost at corpus scale, so systems replace each vector with a short code of a few bytes (quantization). Standard quantizers such as product quantization (PQ) pick the code that best reconstructs the original vector, but reconstruction is only a proxy for retrieval: at a few bytes per document, a model-aware code trained on the retriever's ranking signal uses the budget better. A single code is even more useful if its short prefixes are each directly searchable, letting a deployment set its efficiency-quality operating point without re-encoding the corpus. But training all prefixes under one objective makes the early bits a compromise across budgets: short codes improve while the full-width code degrades. Binary codes sharpen the conflict, since a gradient step either flips a stored bit or leaves it unchanged. We introduce Matryoshka Hash Representations (MHR), a two-stage procedure that separates full-width training from prefix organization. MHR first learns a longer binary code, then freezes the model and trains zero-initialized residual code adaptors for directly searchable prefixes. Documents are stored at one bit per coordinate, queries keep continuous logits as in PQ, and search runs on FAISS FastScan. Trained on MS MARCO and zero-shot transferred to seven BEIR datasets, one MHR code reaches 0.502 NDCG@10 at 16 bytes and 0.556 at 32 bytes, against 0.404 and 0.524 for the best compact baselines; the gains hold across training seeds, on all 13 public BEIR datasets, and against off-the-shelf binary Matryoshka embeddings with stronger backbones. The same code also helps shortlist candidates for reranking and prune low-storage graph indexes such as LEANN.

0.53

Extreme Compression of Per-Layer Embeddings via Cross-Layer Latent Vector Quantization

cs.LG ·2026-10-22 ·Jiacheng Liu, Yaxin Luo, Xiaohan Zhao, Peng Sun, Xinyi Shang +3 more
code/data similarity 0.68
Abstract · Code at https://github.com/VILA-Lab/optic

Scaling embedding capacity alongside Transformer computation is an emerging trend in language models. This trend makes high compression rates increasingly useful. Hence, we study extreme compression of Per-Layer Embeddings (PLE), which follow this trend and account for 35.2% of the parameters of Gemma 4 E4B. At such rates, conventional quantizers give each token-layer vector its own code of only a few bytes. We instead develop OPTIC (Output-Path-fitted, Token-shared Indexed Codes), which stores one quantized code tuple per token and decodes it at every layer with a layer-specific affine decoder. Codes and decoders are fitted to the PLE output path rather than to the stored vectors. At about $100\times$ PLE compression of bfloat16 (BF16) E4B, OPTIC retains an aggregate 97.8% of the uncompressed model's performance across seven benchmarks, whereas product quantization, the strongest of six conventional baselines, retains 66.3%. At $594\times$ and $1,002\times$ PLE compression of BF16 E4B, OPTIC retains 90.5% and 84.1%. On the official E4B release with 4-bit linear weights and 16-bit activations (W4A16), OPTIC retains 96.9% at about $100\times$ PLE compression. During inference at about $100\times$ PLE compression, BF16 E4B uses 29.7% less GPU memory than with uncompressed PLE at the same key-value cache size, while running at most 0.40% slower.

0.33

Where Post-Training Quantization Breaks Text Embedders: A Measured Map Across Four Embedder Families

cs.IR cs.CL ·2026-09-14 ·Hyojung Han
code/data similarity 0.67
Abstract · 24 pages, 3 figures, 10 tables. Measurements, ledger and analysis code: https://github.com/ThakiCloud/skillret-ptq-measurements

Weight-only post-training quantization is the cheapest way to shrink a retrieval embedder, and the received advice for applying it -- protect the embedding table, allocate bits by module sensitivity, prefer a ranking-aware objective over weight reconstruction -- was carried into LLM quantization largely intact. We test that advice on retrieval embedders directly, quantizing five checkpoints from four architecture families across a grid of bit widths and group sizes, and isolating the embedding, attention and feed-forward blocks at each width. Every heuristic fails to transfer as stated. The embedding table never emerges as the dominant isolated protection priority in any family, despite being the largest tensor in several of them. Module sensitivity does not survive as a transferable ordering: at INT4/g16 the spread between modules is too small to allocate against, at INT3 the ordering becomes family-dependent and joint damage stops being the sum of its parts, and at INT2 comparable reconstruction error accompanies retention ranging from 1.3 to 65.9 percent of full precision. A cheap reconstruction proxy is useful for screening uniform bit widths but substantially less reliable for choosing which tensors to protect; its apparent strength across the whole grid is a range-extension artifact. A distilled 109M student at INT3 holds 78.04 NDCG@10 in 68.4 MB and dominates the extreme-PTQ arm of its own 0.6B teacher, 297.9 MB at 64.46, on both size and quality -- but only inside the task it was distilled for. Sizes are byte counts of files that exist rather than arithmetic estimates, and the measurement repository carries the byte provenance for every one of them.

0.31

UBASE: An AI Search Engine for Trillion-Scale Vector Data Management at ByteDance

cs.DB ·2026-08-31 ·Yao Tian, Yuncheng Lu, Liyao Xiong, Yuming Xu, Hao Zhang +7 more
similarity 0.67
Abstract · ATC26 UBASE with Appendix

Since 2016, UBASE has been the foundation of ByteDance's search infrastructure, scaling to more than 7,000 clusters and 300 PB of indexed data. Driven by the demands of AI workloads, UBASE has evolved from a text search engine into a unified AI search system supporting vector retrieval, lexical matching, and predicate filtering. Its largest deployment indexes nearly one trillion high-dimensional vectors. This scale exposes two central bottlenecks in AI-era retrieval: memory-intensive graph-index construction under sustained ingestion, and the prohibitive cost of keeping vector indexes entirely in memory. UBASE addresses these bottlenecks with two techniques. First, it introduces a quantization-aware vector kernel based on SymRaBitQ, a new symmetric quantization scheme with tight theoretical guarantees that allows index construction to run directly in the quantized space accurately and efficiently without retaining a copy of full-precision vectors. Second, it provides a hybrid storage engine that supports memory-resident, hybrid, and SSD-resident deployments, with fine-grained record-level caching to trade memory for latency under operational control. On large-scale benchmarks, UBASE improves throughput by up to 3x, reduces indexing memory by 80%, and lowers serving cost by up to 99.4% compared with prior systems, while supporting trillion-vector scale, write-heavy or latency-sensitive workloads in production.

0.24

E8 Lattice Key Quantization for Low-Bit KV-Cache Compression

cs.LG cs.AI ·2026-10-11 ·Sasho Nedelkoski, Alexander Acker, Soeren Becker, Dominik Scheinert, Odej Kao
similarity 0.66
Abstract

Compressing the key-value (KV) cache is essential for serving long-context large language models (LLMs) under memory constraints. While current scalar quantization methods achieve significant compression, they typically face a quality-fidelity trade-off, either suffering from performance instability at 2-bit precision or necessitating 3-bit keys to maintain model quality. In this work, we demonstrate that a uniform low-bit k2v2 configuration (2-bit keys and 2-bit values) can preserve near-baseline quality by using vector quantization (VQ) based on the $E_8$ lattice for KV keys. We show that structured VQ exploits correlations across adjacent dimensions to achieve signal-to-quantization-noise ratios (SQNR) higher than those of independent scalar quantization at the same key payload rate. To ensure practical utility, we adapt a table-based asymmetric scoring algorithm that avoids explicit codebook dequantization during attention computation and preserves decode-throughput parity with scalar baselines. Across five LLM families, our $E_8$ k2v2 approach yields \textasciitilde$6\times$ KV compression, roughly 20\% smaller than scalar k3v2 (3-bit keys and 2-bit values), while retaining near-baseline long-context perplexity. In our full-suite perplexity evaluation, $E_8$ improves over scalar k3v2 in 80\% of model--dataset--context settings. These results indicate that $E_8$ lattice VQ improves quality per byte while keeping throughput at parity, suggesting that structured key quantization is a useful primitive for KV-compression stacks. Overall, our work provides a low-overhead primitive for expanding the quality-memory frontier in long-context LLM inference.

0.20