One Code, Three Budgets

TL;DR for operators

A semantic-search service may want different retrieval budgets for different workloads: a cheap first-stage filter, a moderate-cost interactive search path, and a higher-quality path when more compute is available. Maintaining a separately encoded corpus for each operating point adds storage, indexing, and deployment complexity.

Matryoshka Hash Representations (MHR) address that problem with one nested binary document code whose 8-, 16-, and 32-byte prefixes are independently searchable.¹ The crucial detail is that these prefixes are not obtained by simply chopping bits off a conventionally trained 256-bit hash. The authors first train the 256-bit representation on MS MARCO, freeze it, and then train residual adaptors to reorganize the prefixes while preserving the full-width solution.

Across seven zero-shot BEIR datasets, MHR reports macro NDCG@10 / Recall@100 of .376 / .518 at 8 bytes, .502 / .616 at 16 bytes, and .556 / .653 at 32 bytes. At the same budgets, the ranking-aware JPQ-FT baseline reaches .217 / .342, .404 / .537, and .524 / .638.

For operators, the interesting possibility is therefore not merely smaller vectors. It is one document representation with several usable retrieval operating points. The same compact code is also tested for CPU scanning, graph pruning, and filtering before full-precision reranking. Whether those systems benefits transfer to other encoders, languages, domains, GPUs, or disk-resident indexes remains untested.

Training every width together damages the representation you most want to preserve

Suppose a retrieval service wants one stored code that can run at 64, 128, or 256 bits. The natural implementation is to train all three prefixes jointly.

Binary codes make that approach less benign than it sounds.

A coordinate near the beginning of the code participates in every prefix that contains it. A later coordinate participates in fewer objectives. Formally, the paper describes the gradient on coordinate $j$ under direct multi-width training as

Early bits therefore receive pressure from more width-specific ranking objectives. That matters because document storage ultimately keeps only their signs. A small compromise around zero is not a small numerical perturbation after binarization: it flips the stored bit in every prefix containing that coordinate.

The experiments reflect this tension. Direct nested training improves the shorter operating points but weakens the strongest full-width representation. The problem is not that nested codes are impossible; it is that jointly asking the same binary coordinates to satisfy several ranking objectives can destroy part of the solution already available at 256 bits.

MHR separates learning the best code from reorganizing its prefixes

MHR changes the optimization sequence.

Stage I learns a strong 256-bit retrieval code from MS MARCO using a BGE-based encoder, LoRA, a hash head, relevance supervision, distillation signals, and balance regularization. That solution is then frozen.

Stage II does not retrain the base representation from scratch. Instead, zero-initialized residual adaptors are trained over the fixed logits. The adapted representation supplies literal nested prefixes:

where $m$ is 64, 128, or 256 bits.

The distinction matters. An 8-byte MHR representation is not simply the first 64 bits of an otherwise untouched 256-bit code. Stage II deliberately reshapes how information is distributed into those early coordinates while using the frozen Stage-I ranking behavior as an anchor.

The ablation makes that anchor the clearest design lesson in the paper. On the five-dataset Stage-II ablation, the selected model averages .498 NDCG across widths. Removing the full-width source-distillation term reduces that mean to .365, far more than removing the other tested objective components. This is an ablation rather than a second headline benchmark, but it supports the proposed mechanism: prefix adaptation works substantially better when it is constrained not to drift far from the strong full-width solution.

Compress the corpus, not necessarily the query

Document embeddings are expensive because they are persisted across the corpus. Query representations are transient.

MHR exploits that asymmetry. Documents are stored as hard one-bit coordinates, but query logits remain continuous:

The design preserves more query-side information without adding document-storage cost.

The comparison with hard-signing queries shows that this is not cosmetic. Replacing the continuous query logits with hard binary signs lowers macro NDCG by .033 to .088, depending on code width.

For retrieval architecture, this suggests a broader rule: representation symmetry is not automatically desirable when the two sides have different cost structures. If the corpus dominates persistent storage while queries exist only during execution, compressing both identically can discard information without solving an equivalent resource problem.

One compact code can play several roles in the retrieval pipeline

The benchmark results establish retrieval quality, but the systems experiments show why nested compact codes may matter beyond a leaderboard.

In single-thread CPU flat search, 32-byte MHR with FAISS FastScan reaches 0.538 ms/query on Quora, versus 4.704 ms for source-fitted PQ flat, while also producing higher NDCG. On TREC-COVID the corresponding figures are 0.202 ms versus 1.504 ms. These are roughly 8.7× and 7.4× latency differences in the tested implementation, not universal hardware speedups.

The 8-byte code is also used as a cheap decision signal inside LEANN-HNSW. At 25% retention, MHR preserves 99.6–100.0% of unpruned NDCG@10 and 97.4–99.8% of Recall@100 across the reported datasets while reducing exact full-vector distance evaluations by roughly two thirds.

A third use is coarse filtering. With full-precision reranking of only the top 100 candidates, the 32-byte MHR filter reaches .629 macro NDCG@10, compared with .637 for the full-precision BGE reference. Even the 8-byte filter reaches .561 after reranking, versus .363 when used alone.

These experiments test different deployment roles, not interchangeable claims. Flat search examines scan efficiency. LEANN tests whether the compact code can guide selective recomputation. The reranking experiment asks whether it can cheaply preserve a good candidate set for a more expensive second stage.

The business case is fewer representations to operate

The paper directly shows that one source-trained nested code can support three tested document budgets and several retrieval architectures.

Cognaptus’ inference is that this could simplify services whose retrieval budget changes by workload. A RAG platform might use an 8-byte prefix for broad candidate generation, a 16-byte prefix for a tighter interactive path, and the full 32-byte code where compact retrieval quality matters more—all without maintaining three independent document encodings.

That could reduce corpus duplication, re-encoding work, and configuration drift between service tiers. The pruning and reranking results also suggest the representation can be treated as an inexpensive routing signal rather than only as a substitute for the full embedding.

The economic value, however, depends on the actual bottleneck. If document memory, memory bandwidth, or exact-vector evaluation dominates cost, compact nested codes have a plausible role. If encoder inference, network transfer, GPU scheduling, or another stage dominates end-to-end latency, smaller codes alone may move little of the total bill.

The demonstrated range is narrower than the architectural idea

The evidence is strong within the benchmark the authors ran, but the tested envelope is specific.

Both training stages use MS MARCO, followed by zero-shot evaluation on seven BEIR datasets. The main representation range is 64 to 256 bits. Systems latency is measured on single-thread CPU search using FAISS-specific implementations. GPU kernels and disk-resident graph retrieval are left for future work.

The compact representation also does not eliminate the quality gap to full precision. At 32 bytes, MHR reaches .556 macro NDCG@10 against .637 for float BGE in the main seven-dataset comparison.

The right conclusion is therefore narrower than “one tiny code replaces full embeddings.” The paper demonstrates that careful staged training can make one binary representation operate effectively at several budgets, and that those codes can serve multiple roles inside a retrieval stack. Whether the same design remains attractive across larger encoders, different languages, more severe domain shifts, longer codes, GPU search, or disk-based indexes is still an engineering and empirical question.

For semantic-search and RAG operators, that is already a meaningful change in the design space. Compression no longer has to mean committing the corpus to one fixed operating point.

Cognaptus: Automate the Present, Incubate the Future.