Topology aware attacks expose risks in large scale document search systems
Poisoning the Neighborhood: A Topology-Aware Topic-Level Attack on Large-Scale HNSW-based RAG Systems
Cryptography and Security
Summary
Large language models use external documents to improve responses, but those documents can be tampered with in attacks. The authors found that in big systems using a special graph-based search method called HNSW, attackers can arrange fake documents cleverly to trick searches and promote false information. Their technique uses a network-like setup called Hub-Satellite to spread poisoned documents widely and reliably, affecting many related queries. This weakens current defenses and shows that the structure of these search systems creates new vulnerabilities.
What this means in practice
- •For security engineers: Test and improve defenses for graph-based document retrieval against advanced poisoning attacks that exploit graph topology.
- •For search system engineers: Design more robust large-scale search systems by accounting for poisoned document clustering and local graph dynamics in approximate nearest neighbor indexes.
Authors
Yufei Chen, Yao Wang, Haibin Zhang
Abstract
Retrieval-augmented generation (RAG) mitigates hallucinations and knowledge staleness in large language models using external knowledge. However, ingestion from public and third-party sources exposes RAG systems to poisoning attacks. Existing attacks are designed and evaluated under exact retrieval, where poisoned documents participate in global ranking. Deployment-scale systems instead rely on approximate nearest-neighbor (ANN) indexes such as hierarchical navigable small world (HNSW), where limited search budgets, graph-search reachability, and local benign-document competition invalidate this assumption and degrade existing attacks. We present a topology-aware topic-level poisoning attack against large-scale HNSW-RAG that generalizes to unseen topic queries. We organize poisoned documents into a Hub-Satellite structure: Satellites provide competitive entry points across semantic regions, while Hubs strengthen local cohesion and facilitate cascading retrieval. For generation, we propose an entity-claim promotion attack combining evidence anchoring and entity-claim coupling to promote the target entity via a target claim across different query regions. On 2M-document Wikipedia, our attack maintains over 72% retrieval success and reaches 31.29% attack success, substantially outperforming baselines; domain-specific experiments further support its effectiveness. Structural analyses show that the Hub-Satellite topology forms in HNSW, indicating that graph structure contributes to improved poisoned-document retrieval. Existing poisoning defenses cannot mitigate the attack, exposing graph-structural risks in HNSW-RAG systems.