Deleted Documents Explained — 5 Reasons They Still Appear in Search Results

TL;DR: Treat deletion as a distributed state transition, not a successful call to a vector index. A property document is erased from semantic search only when every chunk is unreachable, every read path rejects its stable document ID, and a later ingestion job cannot recreate it. Put a deny-on-delete filter in front of retrieval immediately, process physical deletion asynchronously, then prove both absence and non-resurrection before closing the erasure request.

This distinction matters in property management because one product-content record can fan out into descriptions, amenity summaries, translated passages, and embeddings. Removing the source row while one derived chunk remains searchable can ground an answer in content the system has promised to forget. Retrieval-augmented generation combines a generator with retrieved external memory; stale retrieval therefore remains consequential after the source page vanishes.

No single delete acknowledgement proves the outcome.

Why does a deleted document still appear in search results?

The usual failure is an identity mismatch. The application deletes document_id=lease-guide-184, while the index contains chunk IDs such as lease-guide-184:en:7 and lease-guide-184:es:3. If deletion targets one point ID, the other children survive. Re-embedding makes this worse when each run assigns fresh random IDs: the source has one identity, but its derivatives have no stable lineage.

A second failure is ordering. Consider a bounded production sequence: an indexing worker reads revision 12, an erasure request records a tombstone, the vector delete completes, and then the delayed worker writes revision 12 back into the index. Every individual operation succeeded. The final state is still wrong. The invariant exposed by that incident shape is stronger than "delete eventually runs": a write for a document must be rejected when its revision predates the current erasure generation.

There are other read surfaces. A query-result cache may hold chunk IDs or rendered snippets. A lexical index may coexist with the vector index for hybrid retrieval. A replica can lag. An answer cache can return text without performing retrieval at all. Backups may retain data under a separate policy even after it is no longer in the serving system. Those stores do not share one consistency model, so a deletion API cannot be used as a proxy for end-to-end erasure.

The debugging order should follow the read path:

1. Capture the stable document ID and current erasure generation from the system of record.
2. Query through the same hybrid retrieval and cache path used by the application, including tenant filters.
3. Enumerate every derived object by lineage rather than guessing chunk IDs.
4. Check jobs accepted before the tombstone but completed after it.
5. Repeat the probe after cache TTLs and replica-lag bounds have elapsed.

That sequence separates a serving leak from index residue. It also avoids the weak test of searching for the exact title once and declaring success. Semantic retrieval can surface a surviving paragraph for a paraphrased query even when an exact-name query returns nothing.

Make deletion a fenced workflow

Model an erasure request as a small state machine: requested, read_blocked, physical_delete_pending, verified, or failed. The first transition belongs in the authoritative metadata store and must be durable before the caller receives success. Retrieval then anti-joins candidates against that metadata, or applies an equivalent mandatory filter, so a deleted document is denied while downstream cleanup is incomplete.

This is the safety mechanism. Physical deletion is reclamation.

Use a stable parent ID on every derivative, plus a monotonically increasing generation. A chunk identity can be deterministic over tenant, parent, revision, locale, and chunk ordinal; the exact encoding matters less than reproducibility and lineage. Every indexing message carries the generation it observed. Before upsert, the consumer compares that value with the current document record. A tombstone or newer generation turns the message into a no-op.

The same fence belongs on bulk rebuilds. Reindexing from an old export is an ordinary resurrection path because the job often bypasses the live write path. A rebuild must consult the erasure ledger before publishing its new index, and the ledger must be retained long enough to cover the oldest permitted backup or snapshot that can feed a rebuild. Retention duration is a governance decision, not a magic number.

For GDPR-driven work, keep the audit record narrow: request identifier, tenant, stable document ID, state transitions, generations, timestamps, and verification result. Do not copy the erased content into the audit log. Article 17 defines the right to erasure, while Article 5 includes storage limitation and accountability principles; a proof system that preserves the content it was meant to remove defeats its purpose.

The preventative Go path

The smallest useful implementation puts the generation check at the last responsible moment before an upsert. These interfaces assume the metadata read is authoritative for the tenant and that the index supports deletion by a parent-ID filter; otherwise, the lineage catalog must enumerate every child ID.

package retrieval

import (
    "context"
    "errors"
    "fmt"
)

var ErrErased = errors.New("document has been erased")

type DocumentState struct {
    Generation uint64
    Erased     bool
}

type Metadata interface {
    State(ctx context.Context, tenantID, documentID string) (DocumentState, error)
}

type VectorIndex interface {
    Upsert(ctx context.Context, tenantID, documentID string, generation uint64, chunks []Chunk) error
}

type Chunk struct {
    ID   string
    Text string
}

type IndexJob struct {
    TenantID   string
    DocumentID string
    Generation uint64
    Chunks     []Chunk
}

func ApplyIndexJob(ctx context.Context, meta Metadata, index VectorIndex, job IndexJob) error {
    state, err := meta.State(ctx, job.TenantID, job.DocumentID)
    if err != nil {
        return fmt.Errorf("read document state: %w", err)
    }
    if state.Erased || job.Generation != state.Generation {
        return ErrErased
    }
    if err := index.Upsert(ctx, job.TenantID, job.DocumentID, job.Generation, job.Chunks); err != nil {
        return fmt.Errorf("upsert chunks: %w", err)
    }
    return nil
}

There is a race between the metadata read and upsert unless the systems share a transaction, which they usually do not. Close it with a second control: retrieval must enforce the authoritative tombstone, and deletion reconciliation must scan for objects whose generation is no longer live. If the index supports conditional writes tied to a generation, use them; otherwise accept asynchronous physical convergence and make the read fence non-optional.

Error handling should distinguish an expected stale job from infrastructure failure. ErrErased is acknowledged and counted as a fenced write, not retried forever. Metadata read failure is fail-closed because proceeding would permit resurrection. Index failure remains retryable with an idempotency key derived from tenant, document, and generation.

Keep the code boring. The difficult part is maintaining the contract across importers, administrative tools, scheduled refreshes, and disaster recovery.

What evidence closes the request?

A credible verifier works from the deletion ledger and produces evidence independent of the delete worker. For each stable document ID, it checks all serving indexes, cache namespaces, and lineage records. It issues representative semantic and exact-match probes through the application read path and confirms that any stale candidate is removed by the tombstone filter before context assembly. The verifier records identifiers and counts, not document text.

Five proofs form a useful closure rule:

• The authoritative record is tombstoned at generation N.
• No serving derivative with that parent ID remains reachable.
• Hybrid retrieval and caches cannot return the content.
• Pre-N indexing work is rejected after the tombstone.
• A rebuild fixture containing the old record cannot republish it.

Measure this workflow as an SLO. time_to_read_block covers the interval from accepted request to enforced denial and should be the tight safety objective. time_to_physical_purge tracks downstream convergence. Also count stale writes fenced, orphan derivatives found, verifier failures, and requests stuck in each state. Averages conceal the request waiting behind a poisoned queue item; use percentile distributions and an age-of-oldest gauge. Alert on the age bound mapped to the erasure policy.

Capacity planning starts with fan-out and arrival bursts. If one source produces C chunks across L locales and I serving indexes, a request can require roughly C × L × I derivative operations before cache invalidations and verification reads. Do not publish a universal throughput number. Measure your distributions, reserve deletion capacity apart from ordinary ingestion, and test the backlog created by a bulk tenant request. A queue sharing all capacity with reindexing can meet normal latency while missing the only deadline that matters during a surge.

Buy, build, and know the boundary

The decision is less about feature checkboxes than ownership of the proof. A managed index may reduce patching and operational toil, but the platform team still owns identity, tombstones, cache behavior, rebuild fencing, and the evidence shown to compliance. Self-hosting exposes more internals and can simplify bespoke verification, while adding upgrades, replication, backups, and on-call load. Neither model removes the distributed-systems problem.

A proof of concept should include deletion before relevance tuning. Load a fixture with several chunks and locales, start an intentionally delayed indexing job, erase the parent, and release the job. Then restore an older snapshot into an isolated environment and attempt a rebuild against the current ledger. This test exercises the failure boundary the system actually owns.

This advice does not apply unchanged to immutable legal holds, where deletion may be prohibited and access restriction follows a separately authorized policy. It also does not mean backups must be edited in place; backup handling needs a documented retention and restore-fencing design consistent with legal obligations. Resolve those cases with counsel and data governance, while keeping held records out of ordinary product search.

Close an erasure request on evidence, not intent. Stable lineage finds every derivative, a read fence stops immediate disclosure, generations prevent resurrection, and an independent verifier proves the result across the whole retrieval path.

References

• Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks: https://arxiv.org/abs/2005.11401
• Regulation (EU) 2016/679, Article 5: https://eur-lex.europa.eu/eli/reg/2016/679/art_5/oj
• Regulation (EU) 2016/679, Article 17: https://eur-lex.europa.eu/eli/reg/2016/679/art_17/oj