PaperlayerView exact revision on arXiv

Source-linked AI summary

Ghost Vectors: Soft-Deleted Embeddings Remain Reconstructible in HNSW Vector Databases

Chandranil Chakraborttii, Jackeline García Alvarado, Sitora Abdulofizova, Shivanshu Dwivedi

arXiv:2606.18497v1cs.CRcs.AIcs.DB

TL;DR

Soft deletion can suppress API results while leaving embeddings in storage, creating a gap between functional deletion and storage-layer erasure. The paper tests raw-index extraction and Vec2Text reconstruction across data types, and introduces Epoch Key Rotation. Deleted vectors were recoverable in the evaluated settings, while the defense reduced observed PII recovery to 0%.

  • Problem

    Query-side embedding transformations apply to active queries but do not protect vectors once they enter secondary storage, where soft-deleted records may remain physically present.

    Source: §I · p. 1

  • Method

    The paper extracts soft-deleted vectors from raw index files, applies a pretrained Vec2Text corrector, and proposes encrypting vectors with AES-256-CTR before discarding the key.

    Source: §I · p. 1, D. Inversion Model & Evaluation Metrics · p. 4

  • Results

    Deleted vectors were recoverable across text and image evaluations; Epoch Key Rotation reduced observed PII recovery to 0%.

    Source: §I · p. 2, §X · p. 11

  • Takeaways & Limitations

    Epoch Key Rotation also generates an ECDSA-signed cryptographic proof for auditable erasure workflows.

    Source: §I · p. 2

    Clinical reconstruction was limited by the Wikipedia-style corrector’s poor generalization to clinical terminology, with MIMIC-III ROUGE-L of 0.009.

    Source: §VIII · p. 10

Abstract

from arXiv · show

Retrieval-augmented generation (RAG) allows large language models to access external and private corpora for factual, domain-specific responses. Modern RAG pipelines use hierarchical navigable small world (HNSW) vector databases for efficient similarity search. When a user requests data deletion, the systems typically only mark the record as deleted, leaving the embedding on disk physically unchanged. This soft-delete operation raises compliance concerns under data-erasure and retention requirements such as GDPR Article 17 and HIPAA. Analysis on three HNSW implementations confirms that deleted vectors remain physically recoverable by accessing the raw index files at the storage layer, bypassing API access. Using the Vec2Text inversion model without domain-specific fine-tuning, we show this vulnerability on multiple real-world datasets and data modalities. On Wikipedia biographical living persons dataset (BLP), we successfully recover 25.5% of exact person names and 46.4% of geographic locations (ROUGE-L 0.185). Recovery reaches 100% for both patient age and gender markers (ROUGE-L 0.290) on highly structured, sensitive data (NIH Synthea dataset). On soft-deleted image embeddings, we show 100% tissue classification on histopathology patches (p=1.02e-07) and top-1 identity recovery reaches 99% on facial embeddings (p<0.01). This work introduces Epoch Key Rotation, which encrypts vectors and discards the key upon deletion. Epoch key rotation reduces observed PII recovery to 0% and completes in 2.5 ms for 500 deleted vectors (approximately 0.005 ms/record). Additionally, it generates an ECDSA-signed cryptographic proof as an auditable record of the deletion event.

I. INTRODUCTION

Soft deletion can hide records from API queries while leaving their embeddings on disk, raising erasure and retention concerns. The paper examines this storage-layer gap and reports recoverability across text and image data, alongside a key-rotation defense.

I. INTRODUCTION

  • Soft deletion changes metadata rather than storage, so API silence does not establish that the embedding has been erased from disk.The paper frames this as a concern under GDPR erasure and data-minimization requirements.Source: §I · p. 1, §II · p. 2
  • The attack reads raw HNSW storage and applies a pretrained Vec2Text corrector without fine-tuning; the threat model assumes raw-storage access.The proposed Epoch Key Rotation encrypts vectors and discards the key.Source: §I · p. 1
  • On Wikipedia BLP, 25.5% of person names and 46.4% of locations were recovered, with ROUGE-L = 0.185 ± 0.062.On Synthea, recovery reached 100% for age and gender markers; MIMIC-III reconstruction remained low, with ROUGE-L < 0.010.Source: §I · p. 1
  • Backup snapshots preserve the attack opportunity, and Vec2Text transfer across three surrogate models does not require knowledge of the victim’s embedding model.The reported ROUGE-L was 0.207 for backup snapshots and at least 0.19 across surrogate models.Source: §I · p. 1
  • 100% tissue-class accuracy and 99% top-1 facial identity accuracy were reported for soft-deleted image embeddings; Epoch Key Rotation reduced observed PII recovery to 0%.The defense also generates an ECDSA-signed proof for auditable erasure workflows.Source: §I · p. 2

II. BACKGROUND

  • HNSW systems use metadata flags for deletion, while prior Vec2Text work had not studied soft-deleted records inside a live vector database.The paper describes metadata-level deletion as a design trade-off and notes that query-side embedding transformations do not protect vectors in secondary storage.Source: §I · p. 1, §II · p. 2

III. THREAT MODEL

The threat model gives an adversary read access to raw storage after a controller treats API silence as erasure. The formal analysis frames soft-delete as recoverable and epoch rotation as secure under cryptographic and key-disposal assumptions.

A. System and Adversary Model

  • The model distinguishes a data subject requesting erasure, a controller issuing soft-delete, and a breach adversary acting after deletion.The threat window can persist in backups until storage is physically destroyed or cryptographically overwritten.Source: A. System and Adversary Model · p. 2
  • The breach adversary can read the raw storage directory after deletion but lacks access to plaintext, decryption keys, and API endpoints.The controller treats the API’s lack of results as evidence of erasure without checking storage.Source: A. System and Adversary Model · p. 2

B. Formal Security Analysis

  • Semantic Recovery Advantage (SRA) expresses the analysis of recoverable information after deletion and its removal under epoch rotation.The stated meaningful-recovery threshold is θ = 0.2, and the plaintext record is denoted x.Source: B. Formal Security Analysis · p. 3
  • Soft-delete leaves recoverable semantic information because the original embedding persists in raw storage; the cited surname-recovery example is 0.499.The analysis states that epoch rotation makes semantic recovery advantage negligible under its assumptions.Source: B. Formal Security Analysis · p. 3
  • The epoch-rotation security claim assumes AES-256-CTR and securely managed, irrecoverably deleted keys; the proof reduces meaningful recovery to distinguishing ciphertext from random.The guarantee fails if a decryption key remains accessible on disk; SQLite DELETE can leave key material recoverable from free pages.Source: B. Formal Security Analysis · p. 3

IV. GHOST VECTOR ATTACK SETUP

The experiments assess attacks on three HNSW implementations and use scripts that read on-disk index files directly rather than querying the database API.

IV. GHOST VECTOR ATTACK SETUP

  • Vector extraction reads on-disk index files directly and does not touch the database query API or defenses layered on top of it.The paper evaluates the attack across three HNSW implementations and multiple text and multimodal datasets.Source: A. Threat Environment and Setup · p. 3
  • The experiments were conducted with PyTorch 2.0 on a dedicated node with an AMD Ryzen 7960X, 96GB RAM, and an NVIDIA RTX A6000 with 48 GB VRAM.Source: A. Threat Environment and Setup · p. 3
  • Figure 1 presents the storage-layer extraction and Vec2Text inversion attack alongside the epoch key rotation defense.Source: A. Threat Environment and Setup · p. 3

B. Evaluated Systems

The evaluation combines text and image datasets with pretrained inversion and downstream classifiers, then tests whether soft-deleted vectors remain extractable from HNSW storage.

1) Text Datasets::

  • The text evaluation includes 5,000 Wikipedia records, a 98-record BLP subset, 1,000 synthetic clinical records, 1,000 Synthea records, and 100 MIMIC-III Demo notes.The synthetic clinical records included abbreviation transformations in 58.8% of records.Source: 1) Text Datasets · p. 4

2) Multimodal Datasets::

  • The image benchmarks use 4,324 LFW images across 158 identities and 1,000 PathMNIST images, embedded with CLIP ViT-H/14.A k-NN classifier with k = 5 and cosine distance handles downstream evaluation.Source: 2) Multimodal Datasets · p. 4

D. Inversion Model & Evaluation Metrics

  • Vec2Text uses a pretrained gtr-base corrector with beam_width=4 and n_steps=20; clinical entity recovery requires an exact string match after lemmatization.ROUGE-L measures text overlap, while BERTScore F1 measures semantic preservation.Source: D. Inversion Model & Evaluation Metrics · p. 4

A. Storage-Layer Persistence

  • The storage-persistence setup inserts 5,000 Wikipedia records and soft-deletes 10% using a fixed random seed before extracting vectors from the index.FAISS uses reconstruct_n(), while ChromaDB uses hnswlib get_items().Source: A. Storage-Layer Persistence · p. 4
  • All 500 soft-deleted ChromaDB vectors were extracted, and their cosine similarity to the original embeddings exceeded 0.999.The directory size was unchanged, and the API hid deleted records even though hnswlib get_items() returned their vectors.Source: A. Storage-Layer Persistence · p. 4
  • FAISS retains all 5,000 IndexHNSWFlat vectors because it has no deletion method; inversion of extracted vectors yielded ROUGE-L = 0.167.Weaviate’s disk size grew from 52.5MB to 55.4MB after logical deletion, while its API returned no results for removed IDs.Source: A. Storage-Layer Persistence · p. 4

B. Reconstruction Results (Text)

Soft-deleted Wikipedia embeddings preserve reconstructible text and identifying information, while AES encryption with key discard eliminates the reported recovery. Synthetic clinical records also expose personal and medical information, although some fields remain unrecovered.

1) Baseline Extraction (BLP and Wikipedia):

  • 500 soft-deleted Wikipedia records yielded ROUGE-L 0.207 (±0.07) and BERTScore F1 0.858, while AES encryption with key discard yielded ROUGE-L 0.000.97.8% of soft-deleted reconstructions scored above 0.1 on ROUGE-L.Source: 1) Baseline Extraction (BLP and… · p. 4
  • On 98 BLP records, recovery reached 46.4% for locations, 44.7% for affiliations, 25.5% for person names, and 6.2% for organizations, with ROUGE-L 0.185 (±0.062).Hard deletion produced 0% recovery across entity categories; 18% of entities were recovered among 50 records whose entities were absent from live data.Source: 1) Baseline Extraction (BLP and… · p. 5

2) Clinical Extraction on Structured Data:

  • In 1,000 noisy synthetic clinical records, gender was recovered in 73.4% of cases, first names in 65.0%, last names in 49.9%, diagnoses in 28.0%, and physicians’ names in 6.2%.The records included abbreviations, shorthand, or typos in 58.8% of cases.Source: 2) Clinical Extraction on Structured… · p. 5
  • 49.9% of soft-deleted clinical records yielded the correct surname, versus no matching surnames among random-noise outputs; the random-baseline upper confidence bound was 3%.Some fields, including medical record numbers, drug codes, and dates of birth, were not recovered; AES/hard deletion reduced reported PII recovery to 0%.Source: 2) Clinical Extraction on Structured… · p. 5

3) The Corrector Bottleneck:

Clinical reconstruction quality depends on alignment between the corrector and the data: zero-shot recovery on MIMIC-III is weak, but adaptation improves it. Reconstructions also transfer across tested embedding architectures.

3) The Corrector Bottleneck:

  • Zero-shot gtr-base reconstruction on 100 MIMIC-III records produced ROUGE-L scores near 0.005, while the Faker dataset approximated an upper bound under better corrector alignment.The reported comparative weakness on real clinical notes is attributed to corrector-model limitations, not the storage system.Source: 3) The Corrector Bottleneck · p. 5
  • Figure 2 compares BERTScore F1 distributions for AES-encrypted and soft-deleted Wikipedia embeddings across 500 records.The supplied caption identifies the comparison and sample size but does not state the plotted values.Source: Figure 2 · p. 6
  • Fine-tuning raised MIMIC-III ROUGE-L from 0.005 to 0.077, and beam search raised it to 0.232 on retained records.With beam search, 95% of retained records exceeded ROUGE-L 0.10 and 85% exceeded 0.15.Source: 3) The Corrector Bottleneck · pp. 5–6
  • Across three surrogate embedding models, Wikipedia reconstructions maintained ROUGE-L 0.190 and cosine similarity from 0.86 to 0.90.The passage reports transfer across MiniLM, MPNet, and multilingual-MPNet rather than the original gtr-t5-base target model.Source: 3) The Corrector Bottleneck · p. 6

1) Persistence under quantization:

Soft-deleted vectors remain recoverable across compression settings and modalities, and ghost nodes remain active in HNSW traversal. Tests report preserved identity and tissue-class information as well as measurable search effects.

1) Persistence under quantization:

  • SQ8 and PQ32 preserved between 78% and 93% of original reconstruction quality, so tested quantization did not eliminate storage-layer recovery.The passage also reports partial attack effectiveness under binary, PQ32, and SQ8 quantization.Source: 1) Persistence under quantization · p. 6

2) Cross-Modality Persistence:

  • 99.17% top-1 identity recovery was achieved on soft-deleted LFW facial embeddings, versus a 0.63% random baseline.Ghost embeddings retained cosine similarity 1.000; the reported Wilcoxon test was p < 10^-12.Source: 2) Cross-Modality Persistence · p. 6
  • PathMNIST ghost embeddings retained 100% tissue-class accuracy and cosine similarity 1.000, while specialized-model classifiers failed to separate classes effectively at inter-class cosine similarity ≥0.98.The passage also reports physically present soft-deleted chest radiographs.Source: 2) Cross-Modality Persistence · pp. 6–7

D. Structural Persistence and Side Channels

  • Soft-deleted nodes remain linked to HNSW neighbors and are visited during greedy traversal, even though they are filtered from query output.This structural persistence can create a query-level side channel.Source: D. Structural Persistence and Side… · p. 7

1) Ghost Traversal Cost:

  • Soft deletion left query latency at 34.8 µs, whereas true deletion reduced it to 33.3 µs, a 4.3% reduction (p = 0.025).Soft deletion also left distance computations nearly unchanged from baseline at 672.7 per query (p = 0.97).Source: 1) Ghost Traversal Cost · p. 7

2) Result-Set Drift:

Ghost nodes can change live-query neighbor sets and expose deletion status through latency differences. The proposed defense separates vector-content erasure from graph repair, while a single inversion step achieves near-plateau quality.

2) Result-Set Drift:

  • 95% of top-K neighbor sets differed between soft-delete and true-deletion conditions, with ghost nodes potentially guiding the greedy walk as structural hubs.The passage states that deleted records can influence other users’ live-query results.Source: 2) Result-Set Drift · p. 7

3) API-Layer Side Channel:

  • True deletion reduced latency by 4.3%, creating a timing side channel through which an API-query attacker could attempt to infer whether a node was soft-deleted or removed.The inference is described as an attempt based on comparison with a pre-deletion latency baseline.Source: 3) API-Layer Side Channel · p. 7

4) Defense Requirements:

  • Epoch key rotation addresses vector content, but a more complete defense also requires graph repair by reconnecting deleted nodes’ predecessors to their successors.The passage distinguishes cryptographic content erasure from structural repair.Source: 4) Defense Requirements · p. 7

5) Adversary Cost:

  • One Vec2Text inference step recovered ROUGE-L 0.204 at 30.7 ms per record, achieving 98.4% of plateau quality.At 10 steps, ROUGE-L reached 0.2073; the passage extrapolates single-pass inversion of one million records to about 8.5 hours on one GPU.Source: 5) Adversary Cost · p. 7, Figure 4 · p. 8

A. Formal Specification

  • Epoch key rotation uses a fresh per-user epoch key, encrypts vectors, and can produce a signed proof object; the key store must be separate from the HNSW binary.The proof is described as an SHA-256 event hash signed with ECDSA-SHA256 and verifiable with a registered public key.Source: A. Formal Specification · pp. 7–8

B. Failure of Prior Defenses

Query-side embedding transformations do not protect vectors from storage-layer adversaries who can extract and reverse the transformation. Epoch key rotation instead destroys the AES key on rotation.

B. Failure of Prior Defenses

  • Query-side transformations fail against storage-layer adversaries because they can extract T and apply T ⊤.The paper describes this as a representative query-side defense proposed against embedding inversion.Source: B. Failure of Prior Defenses · p. 8
  • 0.215 ROUGE-L after reversing the transformation nearly matches the 0.207 baseline, showing that an extracted orthogonal transform does not stop storage-layer inversion.Before reversal, ROUGE-L was 0.073; the persistent transformation key can be extracted from server configuration files.Source: B. Failure of Prior Defenses · p. 8
  • Epoch key rotation prevents this vulnerability by cryptographically destroying the AES key on rotation.The result depends on the key no longer being recoverable.Source: B. Failure of Prior Defenses · p. 9

C. Evaluation

Across the evaluated deletion strategies, epoch key rotation combines zero observed recovery with a cryptographic proof and lower runtime than full index rebuild or per-record AES. Its measured encryption time scales approximately linearly with record count.

C. Evaluation

  • 2.48 ms at N = 500 and 24.93 ms at N = 5,000 correspond to approximately 0.005 ms per record for AES-256-CTR.The measured runtime is 0.51 ms at N = 100; extrapolation to N=100,000 gives about 550 ms for encryption, with ∼3 ms added for ECDSA proof generation.Source: C. Evaluation · p. 9
  • Full index rebuild takes 2,250ms and leaves ROUGE-L=0.207, while per-record AES takes 8 ms and yields ROUGE-L=0.000 without proof.A binary copied before rebuild achieves identical reconstruction quality to soft-delete.Source: C. Evaluation · p. 9
  • 2.5 ms at N = 500, ROUGE-L=0.000, and cryptographic proof π make epoch key rotation faster than full index rebuild and per-record AES.The reported speedups are ∼300× versus full index rebuild and 53× versus an insert-only rebuild at N = 100,000; end-to-end runtime including proof generation is about 553 ms.Source: C. Evaluation · p. 9

D. Why Differential Privacy Fails

Differential privacy noise reduces embedding similarity without eliminating Vec2Text text overlap, while noise sufficient to suppress recovery also makes retrieval unusable. The discussion relates this tradeoff to storage-layer erasure and auditability, and frames accumulating recoverable records as compliance debt.

D. Why Differential Privacy Fails

  • ROUGE-L remains around 0.073–0.083 across tested ϵ values even as cosine similarity falls, so differential privacy suppresses semantic recovery but does not eliminate text overlap.At ϵ = 10, cosine similarity is 0.079 and ROUGE-L is 0.082; at ϵ = 0.1, cosine similarity is 0.001 while ROUGE-L remains around 0.073.Source: D. Why Differential Privacy Fails · p. 9
  • ROUGE-L below 0.05 would require noise that destroys retrieval utility; recall@10 ≥0.8 requires cosine similarity > 0.85 and σ < 0.02, corresponding to ϵ > 200.The paper contrasts this tradeoff with epoch rotation, which reports ROUGE-L = 0.000 at minimal utility cost for remaining records.Source: D. Why Differential Privacy Fails · p. 10
  • Figure 5 plots ϵ on a log-scale x-axis and ROUGE-L and cosine similarity on separate y-axes to compare recovery with embedding utility.The x-axis indicates privacy increases right-to-left.Source: Figure 5 · p. 10

VII. DISCUSSION

  • Article 17 requires verifiable erasure, and soft-delete raises compliance concerns when deleted vectors remain recoverable from storage.The discussion states that epoch key rotation destroys the needed keys and generates auditable ECDSA proofs.Source: §VII · p. 10
  • The compliance scope includes personal data in RAG corpora and multimodal Article 9 data; storage-layer persistence is independent of transient reconstruction quality.The discussion also states that deletion must extend to storage layers including backup snapshots.Source: §VII · p. 10
  • Compliance debt names the accumulating burden created when each deletion request can leave another recoverable storage-layer record.Epoch key rotation addresses this burden under the stated assumptions and generates a signed proof π.Source: §VII · p. 10

VIII. LIMITATIONS AND FUTURE WORK

The paper identifies limits in corrector generalization, evaluation scale, and the software prototype’s key-isolation assumptions, while discussing related work at distinct system boundaries. Its conclusion reports that epoch key rotation reduces observed recovery to 0% under the stated assumptions and produces a signed proof.

VIII. LIMITATIONS AND FUTURE WORK

  • Clinical evaluation uses synthetic records, raw MIMIC-III reconstruction reaches ROUGE-L 0.009, and experiments span 103 to 105 records rather than production-scale 107 to 1010.Fine-tuning on 43,324 MTSamples pairs raises MIMIC-III ROUGE-L from 0.009 to 0.052; evaluation of Pinecone and Qdrant is left for future work.Source: §VIII · p. 10
  • The software prototype trusts the host OS, and a root-level adversary could potentially extract active AES-256 epoch keys from RAM before rotation.Vectors copied before rotation remain invertible, a forward-secrecy limitation the paper describes as fundamental to the design.Source: §VIII · p. 11

IX. RELATED WORK

  • Machine unlearning and membership-inference work address different threat surfaces, while earlier secure-expiration systems used time-bounded cryptographic keys.The paper positions epoch key rotation as adapting that idea to vector databases and storage-layer deletion.Source: §IX · p. 11

X. CONCLUSION

  • Under the paper’s assumptions, epoch key rotation completes in 2.5 ms for 500 deleted vectors, reduces observed recovery to 0%, and generates signed proof π.The conclusion describes this as storage-layer erasure that can be verified cryptographically.Source: §X · p. 11

Related papers

Loading 2606.18497v1…