Deleting Documents from Generative Retrievers That Name Documents in Words

Generative retrieval replaces a search index with a single sequence-to-sequence model: given a query, the model writes out the identifier of the relevant document. The field has moved from arbitrary numeric identifiers toward semantic identifiers, meaning short natural-language strings such as URLs, keyword sentences, summaries, or distinctive n-grams. Language models retrieve far better when they can write words instead of memorizing codes. The same move quietly changes what it means to delete a document. When a document's identifier is a compressed description of its content, a retriever that can still produce that identifier is still disclosing the document, whatever the decoding filter allows. The identifier's words are also shared with thousands of other documents, so erasing them bluntly damages retrieval of everything nearby.

We propose to study and solve document deletion for semantic-identifier generative retrievers. Deletion here covers retracted, legally removed, and superseded documents. Our method, discriminative-token forgetting with redirection, trains the model on two things. First, queries that used to reach a deleted document should now reach the best remaining document, or its designated replacement. Second, likelihood should be pushed down only on the tokens of the deleted identifier that distinguish it from its retained neighbours. Tokens it shares with living documents are left alone. The central empirical question is whether this matches retraining from scratch on the retained corpus, at a small fraction of the cost. We will also test whether the simple fix, removing the identifier from the decoding filter, is enough. We expect it to be enough for numeric identifiers but not for semantic ones.

Core Claim

Existing work on changing corpora in generative retrieval only adds documents. Continual Learning for Generative Retrieval over Dynamic Corpora (CLEVER) keeps old identifiers stable while indexing new sessions and explicitly leaves deletions and modifications to future work. IncDSI and DSI++ likewise bind new identifiers while protecting old ones. Replication and Exploration of Generative Retrieval over Dynamic Corpora avoids weight updates entirely by editing the prefix tree that restricts decoding to valid identifiers. That approach leaves the model's internal associations untouched. On the forgetting side, U-CAN shows that gradient ascent on a forget set can collapse a generative recommender. Its explanation is that individual neurons carry both the forgotten items and general ability. U-CAN addresses this with soft attenuation of adapter weights, but only for item-recommendation sequences with categorical outputs.

Our claim is narrower and testable. For semantic identifiers, the collateral damage of unlearning is concentrated in the tokens a deleted identifier shares with retained identifiers. What leaks after deletion is concentrated in the tokens that make it distinctive. A loss that treats these two token classes differently should therefore beat both whole-sequence unlearning and pure decoding-filter edits. We predict the advantage will be largest when deletions cluster by topic, because that is where token sharing is heaviest. We predict it will largely disappear for numeric identifiers, and that control is what makes the claim falsifiable.

Research Program

We build on two semantic-identifier retrievers from the file. The first uses D2Gen n-gram identifiers, chosen by attention-based relevance and low overlap with the rest of the corpus. The second uses ZeroGR-style keyword-sentence identifiers. A numeric-identifier DSI model, following Transformer Memory as a Differentiable Search Index, serves as the control.

For each deleted document $d$ we generate pseudo-queries $Q_d$, in the way CLEVER and DSI++ generate queries for replay. We choose a redirect target $r(q)$ for each query. For a superseded document this is its replacement. Otherwise it is the highest-ranked retained document under a frozen copy of the original model with $d$ masked. Let $y_1,\dots,y_T$ be the tokens of $d$'s identifier. Let $S_d$ be the positions whose token (or n-gram) does not appear in any retained identifier among $d$'s top-$k$ decoding neighbours. The update is

$$ \mathcal{L} = \sum_{q \in Q_d}\Big[-\log p_\theta(r(q)\mid q) + \lambda \sum_{t\in S_d} \max\big(0,\ \log p_\theta(y_t \mid y_{<t}, q) - \log\tau\big)\Big] + \beta\,\mathrm{KL}\big(p_{\theta_0}\,\|\,p_\theta\big)_{Q_{\text{keep}}}, $$

where $p_\theta$ is the model being edited and $p_{\theta_0}$ the model before deletion. $\tau$ is a probability floor: the hinge stops pushing once a distinctive token's likelihood drops below it, which avoids the unbounded ascent that U-CAN identifies as the cause of collapse. $\lambda$ and $\beta$ are weights. $Q_{\text{keep}}$ is a replay set of pseudo-queries for retained documents in $d$'s neighbourhood. Updates are confined to adapter weights, and we optionally add U-CAN's contrastive attenuation on top, so the two contributions can be separated.

A second, smaller thread handles the fact that deletion changes which neighbouring identifiers count as distinctive. D2Gen scores distinctiveness against the whole corpus, so removing documents shifts those scores. We will measure how often retained identifiers become needlessly long or ambiguous after deletion. We will test a local re-scoring restricted to deleted documents' neighbours, so that distinctiveness can be recomputed without re-indexing the full corpus.

Baselines

The naive reference is decoding-filter pruning: remove the deleted identifier from the prefix tree and change nothing else. This is the approach implied by the dynamic-corpora replication study, and it costs nothing. It is the strongest competitor for retained-document accuracy, and it achieves perfect forgetting under constrained decoding by construction. We run it on the identical trained checkpoints. To beat it, we must show two things: a meaningful gap in leakage under unconstrained decoding and hidden-state probes, and a retained-accuracy gap on queries whose original answer was deleted.

The gold standard is retraining from scratch on the retained corpus with the same architecture, identifiers, and pseudo-query budget. It defines both the target leakage level and the target retained accuracy. Beating it means coming within a small tolerance on both at a fraction of its cost, which we fix before running at under 5% of the retraining GPU-hours.

The strongest existing parametric unlearner is U-CAN (U-CAN), ported unchanged to the same adapters and given the same forget and retain pseudo-queries. On ML-100k with a 25% forget set, it reports Trade-off@10 of 29.45, against −3.82 for gradient ascent and 17.49 for LLM-Eraser. We also run whole-sequence gradient ascent and CLEVER-style rehearsal fine-tuning on the retained corpus only. The rehearsal baseline tests whether simply training on what remains causes forgetting on its own. For additive updates, CLEVER reports MRR@10 of 43.75% on CDI-MS against 34.93% for naive fine-tuning. We found no reported result on Lacuna for document deletion in any generative retriever, so all deletion numbers will be new.

All methods get the same pseudo-queries, adapter rank, and step budget, and each gets the same hyperparameter search of 20 trials, selected on a held-out validation deletion set.

Two ablations isolate the key ingredient. One applies the hinge to all identifier tokens rather than only the distinctive set $S_d$. The other drops redirection and keeps only suppression.

Why not just…?

Why not just prune the decoding filter? This is the real threat, and we treat it as a hypothesis to test rather than dismiss. The file argues that strong internal associations with a masked path trap probability mass and degrade the remaining beam. That argument is plausible but not directly measured for deletion. The measured evidence is indirect: the replication study found that frozen models favour originally trained documents, with DSI-SE falling from 0.718 Hit@10 on initial documents to 0.205 on added ones. For semantic identifiers, the stronger argument is leakage. The model can still write the deleted document's summary or keyword sentence whenever it is decoded without the filter, used for question answering as in UniGen, or probed. If our experiments show that retained accuracy under filter pruning matches retraining and that unconstrained leakage is negligible, then filter pruning wins for staleness-driven deletion. We would then narrow the claim to privacy-driven deletion.

Why not just run gradient ascent on the deleted query–identifier pairs? U-CAN's recommendation results show gradient ascent collapsing to a negative trade-off. Semantic identifiers make this worse, because ascent on the word "vaccine" in one identifier also lowers it for every retained identifier that contains the word. The full-token ablation measures exactly this, and the topic-clustered deletion condition should show it most sharply.

Why not just retrain periodically? For small corpora, or when deletions can wait for a batched rebuild, retraining is simple and exact. We will report the cost crossover: how many deletions per rebuild interval our method can absorb before its cumulative drift from the retrained model exceeds the tolerance. Legal takedowns that must happen within hours are the case where retraining falls short.

Why not use a dense retriever, where deletion means dropping a vector? For many deployments that is the right answer, and we say so. The question only arises for systems that keep generative retrieval for its accuracy or its integration with a language model. D2Gen reports Recall@1 of 0.513 on MS300k, and ZeroGR reports an average Acc@1 of 41.1 on MAIR against 36.1 for BM25. We include a dual-encoder reference with vector deletion so readers can see what generative retrieval gains or loses once deletion is required.

Proposed Experiments

We construct deletion benchmarks on NQ320k and MS300k, D2Gen's corpora, and on the CDI-MS session splits from CLEVER, so that additions and deletions can be interleaved. There are three deletion regimes, each at 1% and 5%. The first deletes documents at random. The second deletes topical clusters, meaning neighbours in embedding space, where identifier tokens overlap heavily. The third replaces documents with rewritten versions that stand in for superseded ones, with queries expected to move to the replacement.

Retention is measured by Recall@1 and Recall@10 on retained documents' real queries. Queries whose gold document was deleted are scored by whether the model returns the redirect or replacement target. Forgetting is measured in three ways:

  1. the rank and exact-match rate of the deleted identifier under unconstrained beam decoding;
  2. ROUGE overlap between freely generated identifiers and the deleted document's text, as a direct measure of content leakage;
  3. a linear probe on encoder and decoder hidden states, following the concern in Unlearning Isn't Forgetting that output suppression can hide intact representations.

Every forgetting metric is reported relative to the retrained model. This follows Evaluating Inexact Unlearning Requires Revisiting Forgetting: absolute suppression is not the right target, because a document the model never saw still gets some probability.

Three results would settle the claim.

The first is the numeric-identifier control. If filter pruning already matches retraining on leakage and retained accuracy for DSI numeric codes but falls behind for D2Gen and ZeroGR identifiers, that confirms that semantic identifiers create the problem.

The second is the distinctive-token ablation under topic-clustered deletion. If restricting suppression to $S_d$ does not improve retained Recall@1 over full-token suppression at equal leakage, the core mechanism is wrong.

The third is the sequential stress test on CDI-MS with interleaved additions and deletions. Here we track drift from a model retrained on the current corpus after every session. The test shows whether cheap edits accumulate into a model worse than periodic rebuilding, and it gives the cost crossover practitioners need.