PaperlayerView exact revision on arXiv

Source-linked AI summary

Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval

Peichun Hua, Yunming Xiao

arXiv:2609.07276v1cs.IRcs.AIcs.LG

TL;DR

Full-precision vectors make retrieval indexes costly, and nested binary codes face a trade-off between short-prefix and full-width quality. MHR separates full-width code learning from prefix organization; across seven zero-shot datasets it outperforms compact baselines at every budget.

  • Problem

    Full-precision vectors dominate index cost as corpora grow, while nested binary training can improve short prefixes at the expense of full-width quality.

    Source: §1 · p. 1

  • Method

    MHR first learns a full-width binary code, then freezes the encoder and trains residual adaptors with prefix supervision to organize directly searchable nested codes.

    Source: §1 · p. 2

  • Results

    Across seven zero-shot datasets MHR outperforms compact baselines at every budget; at 32 bytes it improves macro NDCG by .032 and Recall by .016 over JPQ-FT.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    The same code supports compact-latency FastScan and IVF, improves graph pruning, and enables an 8-byte coarse filter for near-float reranking quality.

    Source: §5 · p. 8

    The study focuses on in-memory CPU search; GPU flat and IVF kernels and disk-resident graph search remain future extensions.

    Source: §5 · p. 8

Abstract

from arXiv · show

Retrieval-augmented generation (RAG) depends on dense retrieval: each document is stored as a learned vector, and a query is answered by finding its nearest neighbors in that vector space. Keeping one full-precision vector per document is the dominant index cost at corpus scale, so retrieval systems replace each vector with a short code of a few bytes---a step called quantization. Standard quantizers such as product quantization (PQ) pick the code that reconstructs the original vector most closely. A single code is even more useful if it serves several byte budgets at once: when its short prefixes are each directly searchable, a deployment can 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. Quantization to low-bit representation, such as binary codes, further sharpens the conflict. 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 additional zero-initialized residual code adaptors for directly searchable prefixes. Documents are stored at one bit per coordinate, while queries keep continuous logits like PQ to attain sufficient expressivity. We implement the search process with FAISS FastScan. Trained on MS MARCO and zero-shot transferred to seven BEIR datasets, MHR reaches .5561 NDCG@10 and .6535 Recall@100 at 32 bytes, surpassing the best baseline of the same budget. The advantage is more pronounced in lower budgets. The same code also strengthens two common pipelines: shortlisting candidates for full-precision reranking, and pruning a low-storage graph index such as LEANN.

1 Introduction

Dense retrieval makes full-precision vectors a dominant index cost, while nested codes offer searchable prefixes but create a full-width–prefix trade-off, especially for binary representations. MHR separates full-width code learning from prefix organization and targets compact retrieval and common deployment pipelines.

1 Introduction

  • Full-precision vectors dominate index cost as corpora grow, while reconstruction-focused PQ and OPQ may spend capacity on embedding variation that does not change top retrieved documents.Nested coding can let one stored representation serve multiple searchable prefixes without maintaining an index for every width.Source: §1 · p. 1
  • Direct nested binary training places ranking losses at every width, so early bits face competing objectives and short-prefix gains can come at full-width quality’s expense.Because stored bits are coordinate signs, competing widths can flip early bits back and forth rather than settle.Source: §1 · pp. 1–2
  • MHR first learns a 256-bit hash code, then freezes the encoder and trains residual adaptors to organize nested 64-, 128-, and 256-bit codes.Full-width rank distillation anchors the source code, while prefix ranking losses organize adapted logits; documents use binary codes and queries retain continuous logits.Source: §1 · p. 2
  • MHR leads every compact baseline in macro NDCG@10 and Recall@100 across seven BEIR datasets at all budgets.The framework also supports flat and IVF indexes, candidate shortlisting for full-precision reranking, and graph-index pruning.Source: §1 · p. 2

2 Related Work

Prior work covers real-valued nested representations, supervised multi-length hashing for image retrieval, and compact semantic retrieval codes. MHR differs by using hard one-bit nested prefixes and learning query–document ordering for source-trained transfer to unseen corpora.

2 Related Work

  • Real-valued Matryoshka methods supervise vector prefixes or add truncatability, whereas MHR allocates hard one-bit coordinates to nested, searchable low-bit prefixes.The cited methods include MRL, AdANNS, Matryoshka-Adaptor, and SMEC.Source: §2 · p. 2
  • JMH, MAH, and Nested Hash Layer target supervised image retrieval, while MHR learns fine-grained query–document ordering for text corpora without target relevance labels.The related methods use class or pair labels to define semantic neighborhoods.Source: §2 · p. 2
  • MHR learns a discrete representation once on source data and retrieves on unseen corpora, alongside post-hoc compression and learned compact-retrieval alternatives.The passage situates it among PQ/OPQ, RaBitQ, IKE, discrete retrievers such as JPQ and RepCONC, and other learned codes.Source: §2 · p. 2

3 Matryoshka Hash Representations

MHR addresses the full-width–prefix conflict in direct nested binary training by separating full-width source-code learning from prefix adaptation. It produces searchable prefixes from frozen encoder logits and scores hard document codes with continuous queries.

3.1 Problem and Nested Binary Codes

  • With the target corpus unavailable during training, MHR produces 64/128/256-bit ordered prefixes from one 256-bit code; one pass supplies structurally nested budgets.The prefixes let an index store a chosen width or retain the longest code and truncate it at query time.Source: §3.1 · p. 2

3.2 Stage I: Single-Width Model Training

  • Stage I optimizes only the 256-bit code using hard-document relevance ranking, teacher distillation, MiniLM ordering, and code-balance regularization.Documents use hard signs in the forward pass while queries remain continuous, matching the asymmetric scoring used at deployment.Source: §3.2 · p. 3

3.3 Stage II: Prefix Adaptation

  • Stage II freezes the encoder, LoRA update, and hash head, then applies two zero-initialized residual adaptors to fixed logits without changing initial Stage-I scores.The cascade redistributes capacity across coordinates without replacing the source hash space or adding width-specific parameters.Source: §3.3 · p. 3

3.4 Source-Only Prefix Objective

  • Stage II combines deployment-matched asymmetric prefix ranking with full-width self-distillation, MiniLM relevance, and balance and uniformity regularizers.The full-width distillation term penalizes drift in the 256-bit code, while shorter-prefix terms transfer its ranking to lower-capacity codes.Source: §3.4 · pp. 3–4

3.5 Asymmetric Search and FastScan

  • MHR scores continuous query logits against hard document bits, storing m/8 bytes per document; FAISS FastScan uses analytic lookup tables without fitted centroids.The same packed payload supports flat and IVF scanning, graph pruning, and coarse-to-fine reranking.Source: §3.5 · p. 4

4 Experiments

Across seven zero-shot BEIR datasets, MHR organizes searchable prefixes without sacrificing the full-width code, and it improves compact retrieval and two downstream search pipelines. The experiments evaluate its quality, component contributions, search efficiency, graph pruning, and float-reranked filtering.

4.1 Protocol

  • The protocol trains on MS MARCO and tests source-only transfer across seven heterogeneous BEIR datasets, with no target corpus used for fitting or checkpoint selection.The evaluation includes duplicate detection, question answering, entity retrieval, and fact verification.Source: §4.1 · pp. 4–5

4.2 Zero-Shot Quality

  • At 32 bytes, with JPQ-FT trained directly rather than truncated, MHR improves macro NDCG/Recall from .524/.638 to .556/.653; it has the best compact-baseline macro scores at every budget.At 16 bytes, MHR reaches .502 NDCG versus .404 for JPQ-FT.Source: §4.2 · p. 5

4.3 Ablation by Component

  • Removing the full-width source anchor degrades mean NDCG by .133 and mean Recall by .125; continuous query scoring recovers most quality at no storage cost.Width gradients remain positively aligned; the authors attribute the trade-off to exposure asymmetry and sign-boundary sensitivity, while a third adaptor block does not help quality.Source: §4.3 · p. 6

4.4 Scan Efficiency

  • MHR FastScan is 8.7× / 7.5× faster than source-fitted PQ flat on Quora / TREC-COVID, while IVF-MHR beats IVF-PQ in NDCG across eight equal-storage operating points.IVF-MHR is at most 11.9% faster; the flat-search speedup is attributed to FAISS’s register-blocked SIMD lookup kernel.Source: §4.4 · pp. 6–7

4.5 Graph-Guided Selective Recomputation

  • At 25% graph retention, MHR preserves 99.6–100.0% of unpruned NDCG@10 and 97.4–99.8% of Recall@100 while reducing exact distance evaluations by 66.6–68.6%.It outperforms both PQ controls on Quora and NQ and ties target-fitted PQ on TREC-COVID despite never seeing that target corpus.Source: Table 5 · p. 7, §4.5 · p. 7

4.6 Compact Coarse Filtering with Reranking

  • At K = 100, 8-byte MHR reaches .561 macro NDCG versus .185 for PQ as a coarse filter, while 32-byte MHR reaches .629, near the .637 float ceiling.The 8-byte MHR filter exceeds its 32-byte compact score of .552 at K = 100.Source: Table 6 · p. 7, §4.6 · p. 7

5 Concluding Remarks

MHR improves on compact baselines across seven zero-shot datasets and supports graph pruning and reranking pipelines. This study focuses on in-memory CPU search; GPU and disk-resident extensions remain future work.

5 Concluding Remarks

  • At 32 bytes, MHR improves macro NDCG by .032 and Recall by .016 over JPQ-FT at a 96× payload reduction.Across seven zero-shot datasets, MHR outperforms compact baselines at every budget.Source: §5 · p. 8
  • 8-byte MHR codes improve LEANN-HNSW graph pruning over source-fitted PQ while staying near the unpruned ceiling, and an 8-byte coarse filter recovers near-float quality after reranking.FastScan and IVF keep the gains at compact-index latency.Source: §5 · p. 8
  • The study evaluates in-memory CPU search; FAISS-style GPU kernels and disk-resident graph search are left as next steps.The authors also suggest MHR could adapt privacy-computing systems to different quality-privacy-efficiency operating points.Source: §5 · p. 8

Related papers

Loading 2609.07276v1…