Evolving Semantic Indexes for Generative Retrieval

A small retriever can cheaply evaluate semantic-index programs proposed by an LLM, making it practical to search for better identifiers for generative retrieval. The paper holds the final generator and its training recipe fixed. It asks whether changing what the generator must learn can improve retrieval. Its most useful result is a boundary: proxy-selected index changes transfer, while proxy-selected training objectives can make the target model worse.

1. Problem and motivation: identifiers shape the search

Generative retrieval predicts a document identifier from a query, one token at a time. A semantic ID is a short code derived from document content. Documents with the same prefix share early decoding decisions; pruning that prefix removes every document beneath it.

A typical index quantizes document embeddings in stages and appends a token to distinguish documents that receive identical codes. Index construction and collision handling are coupled: changing the partition also changes which documents need disambiguation. Reconstruction error, balanced code usage and low collision rates are imperfect substitutes for downstream retrieval quality. Random codes can look balanced without being useful.

Training the target generator for every candidate index is expensive. The paper instead uses a tiny generator to rank candidates, then trains the target only for selected programs.

2. Method: mutate code and evaluate executable indexes

The outer loop maintains a population of programs, selects parents and asks a locally served open-weight LLM for edits. The inner loop executes each proposal, checks its output and collision rate, and trains a proxy only after the program passes those gates. Failed proposals receive execution diagnostics for revision.

The program interface stays fixed: document embeddings, query embeddings and training relevance pairs go in; aligned integer document IDs come out. The implementation can change quantization, clustering or initialization. The final generator receives query text and learns to predict the resulting codes.

The proxy has about one million non-embedding parameters. Original training relevance pairs are split between proxy training and search feedback. The split is by query–document pair, so different answers to the same query can occur on both sides. Held-out test queries remain inaccessible to search.

After selection, the winning program is rebuilt with all original training pairs and a 1B target generator is trained. Final public-dataset training additionally uses synthetic queries; the proxy–target calibration experiment does not. Their absolute scores therefore should not be compared as if they came from the same recipe.

A proxy evaluation takes roughly twenty minutes, versus five hours for a target run. That comparison excludes mutation, index construction and failed executions; it is not an end-to-end pipeline speedup.

3. Contribution: coordinate semantic codes and collision suffixes

The strongest NQ program retains residual quantization. It chooses codes by direction, using cosine similarity, while subtracting unnormalized code vectors so that magnitude still affects the next residual. It also increases codebook capacity and introduces several training stabilizers. The gain cannot be assigned to a single change.

Query supervision makes the reconstructed document embedding align with the mean embedding of its relevant training queries. The index therefore reflects how people look for a document, rather than preserving only its original content representation.

Collision suffixes gain a shared meaning. Non-colliding documents receive zero. Within a collision group, documents are ordered by similarity to the group's centroid. Smaller suffixes then consistently indicate more central documents, rather than arbitrary database order.

4. Results: useful index search, unreliable broader search

The table reports target-model Recall@100 on NQ320K. Changes are absolute percentage points.

Joint index search adds 4.75 points of recall on NQ. MSMARCO and the private multilingual commerce dataset also improve, although early-rank commerce gains are within one standard deviation. The paper does not establish that generative retrieval dominates dense or lexical retrieval: BM25 remains stronger on several MSMARCO metrics.

Across twenty-one calibrated index programs, proxy and target recall have a Spearman rank correlation of 0.90. Accurate absolute prediction is unnecessary if candidate preferences transfer.

Changing the training objective breaks that logic. Objectives affect how a model learns and interact with architecture, pretraining and optimization. An objective tuned to a tiny model can harm a larger pretrained model. Five observed objective or full-pipeline programs improved proxy fitness while reducing target recall. That small sample illustrates a failure mode rather than establishing a broad statistical law.

5. Limitations

Search scopes use different starting points, budgets and gates. Joint search beating sequential search is therefore not a controlled intervention on coordination alone. Several index changes occur together, limiting attribution to individual mechanisms.

The private commerce evaluation withholds absolute scores and provides no online A/B result. Purchases are also different labels from answer relevance or community-content satisfaction. The public collections are reduced subsets, not evidence of unrestricted web-scale deployment.

Proxy evaluation still requires final target-model checks. Mutation failures and index rebuilding add cost. The experiments also leave incremental document insertion and migration of existing identifiers unresolved.

6. Practical implications

A team with a generative retriever can freeze its encoder, generator and data, then compare alternative index programs. Measure agreement between proxy and target rankings on the same programs, rather than relying only on collision rate or code balance.

For short community text, a concrete experiment is to construct codes using query–clicked-document pairs alongside content. This transfers the paper's query-aware indexing idea; click bias and noisy short text remain separate data problems. The paper does not report UGC production results.

Collision suffixes are another inspectable component. If they encode database order, the generator learns arbitrary distinctions. Giving suffixes a consistent geometric interpretation may make that final token easier to learn. Keep automated search focused on shared index structure and verify the selected result with the real target retriever.