Research map / Learning theory and algorithms / Sample complexity
Bottleneck-Minimal Indexing for Generative Document Retrieval
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes bottleneck-minimal indexing (BMI), which reformulates generative document retrieval via information bottleneck theory and builds document IDs by hierarchical k-means over mean BERT embeddings of generated queries rather than documents.
Problem
Generative document retrieval (GDR) designs document ID strings using only document structure, ignoring the query distribution that the autoregressive retriever must map to those IDs.
Approach
Applies information bottleneck theory to GDR, showing k-means indexing is a bottleneck-minimal solution under Gaussian assumptions, and proposes clustering the mean BERT embeddings of queries associated with each document (real, generated, and document-segment queries) instead of document embeddings.
Key results
- With T5-mini on MARCO Lite, BMI improves Rec@1 from 7.09 (hierarchical k-means) to 13.54.
- With T5-base on NQ320K, BMI reaches Rec@1 66.69 vs 65.43 for hierarchical k-means.
- Reports Rec@1 of 67.8 on NQ320K with finetuned docT5query, competitive with GENRET (68.1) and NOVO (69.3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace document-embedding clustering with query-embedding clustering | Hierarchical k-means indexing with T5-mini · NQ320K test | Rec@1: 41.43 -> 48.49 | Helped |
| Replace document-embedding clustering with query-embedding clustering | Hierarchical k-means indexing with T5-mini · MARCO Lite test | Rec@1: 7.09 -> 13.54 | Helped |
| Replace document-embedding clustering with query-embedding clustering | Hierarchical k-means indexing with T5-small · NQ320K test | Rec@1: 58.94 -> 58.61 | Hurt |
| Replace document-embedding clustering with query-embedding clustering | Hierarchical k-means indexing with T5-small · MARCO Lite test | Rec@1: 22.35 -> 26.71 | Helped |
| Replace document-embedding clustering with query-embedding clustering | Indexing with T5-base · NQ320K test | Rec@1: 65.85 -> 66.69 | Helped |
| Replace document-embedding clustering with query-embedding clustering | Hierarchical k-means indexing with T5-base · MARCO Lite test | Rec@1: 41.48 -> 45.20 | Helped |
| Add GenQ queries to document-embedding indexing (ablation) | Indexing with T5-mini · MARCO Lite test | Rec@1: 7.09 -> 9.24 | Helped |
| Add GenQ queries to document-embedding indexing (ablation) | Indexing with T5-small · MARCO Lite test | Rec@1: 22.35 -> 22.74 | Helped |
| Add GenQ queries to document-embedding indexing (ablation) | Indexing with T5-base · MARCO Lite test | Rec@1: 41.48 -> 39.04 | Hurt |
| Add RealQ queries to GenQ-based indexing (ablation) | Indexing with T5-mini · MARCO Lite test | Rec@1: 9.24 -> 10.03 | Helped |
| Add RealQ queries to GenQ-based indexing (ablation) | Indexing with T5-small · MARCO Lite test | Rec@1: 22.74 -> 25.25 | Helped |
| Add RealQ queries to GenQ-based indexing (ablation) | Indexing with T5-base · MARCO Lite test | Rec@1: 39.04 -> 39.43 | Helped |
Surprising findings
- Hierarchical random indexing with T5-base on MARCO Lite (Rec@1 39.00) is close to k-means (41.48), and on NQ320K random clustering slightly beats k-means at T5-base scale.
- Ablation shows GenQ-only queries (average 5.5 words) already beat document-based indexing with smaller T5 models.
Limitations
- Theory relies on Gaussian assumptions for p(Q|X) and p(Q|T) that may not hold in practice, making k-means suboptimal in multimodal cases.
- Only BERT used for embeddings, and experiments limited to two datasets with NCI architecture.
- Mean BERT query embedding estimator assumes i.i.d. queries; quality depends on generated query quality (docT5query).
Experimental setup
Datasets: NQ320K MS MARCO Lite
Benchmarks: NQ320K MS MARCO Lite
Metrics: Rec@1 Rec@10 Rec@100 MRR@100
Baselines: Hierarchical random indexing Locality-sensitive hashing indexing Hierarchical k-means indexing (NCI) GENRET NOVO
Builds on: differentiable search index neural corpus indexer information bottleneck docT5query hierarchical k-means
Closest papers by meaning
- Information-Theoretic Generative Clustering of Documents (AAAI 2025 · similarity 0.85)
- Generative Retrieval Meets Multi-Graded Relevance (NeurIPS 2024 · similarity 0.85)
- Learning to Rank in Generative Retrieval (AAAI 2024 · similarity 0.85)
- DOGR: Leveraging Document-Oriented Contrastive Learning in Generative Retrieval (AAAI 2025 · similarity 0.84)
- Descriptive and Discriminative Document Identifiers for Generative Retrieval (AAAI 2025 · similarity 0.83)
- Sparse Meets Dense: Unified Generative Recommendations with Cascaded Sparse-Dense Representations (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.