Index-Level Attacks: Exploiting Approximate-Index Knobs for Denial and Eviction

When engineers reason about retrieval security they usually picture the query: a prompt goes in, documents come back, and the risk is that the wrong documents come back. But the documents that come back are chosen by a data structure, not by a search over the whole corpus. That structure is an approximate index, and its correctness is probabilistic by design. An approximate index promises to return the true nearest neighbors most of the time, for most queries, given enough search effort. Every word in that promise — most of the time, most queries, enough effort — is a knob, and every knob an attacker can influence becomes a lever on what a downstream model is allowed to see.

The index is the real decision-maker

A vector store answers a query by finding the k stored vectors closest to the query vector under some metric, typically cosine similarity or Euclidean distance. Computing this exactly means comparing the query against every stored vector, which is linear in corpus size and infeasible at scale. So systems use approximate nearest-neighbor (ANN) search, which builds an auxiliary structure that lets a query visit only a small, cleverly chosen subset of vectors and still usually find the true neighbors.

The dominant structure in practice is the Hierarchical Navigable Small World graph introduced by Malkov and Yashunin. HNSW arranges vectors as nodes in a layered proximity graph: upper layers are sparse and let a search take long hops across the space, lower layers are dense and let it refine locally. A query greedily walks the graph from an entry point toward its nearest neighbor, and the quality of the answer depends entirely on whether that walk can reach the true neighbors before it stops.

This is the crucial security observation. Retrieval is not a scan that could in principle see everything and merely ranks results; it is a traversal that only ever visits a fraction of the corpus. If an attacker can shape the graph so that a target document is hard to reach, that document effectively does not exist for a large class of queries — no error is raised, no log line is written, the answer is simply built from whatever was reachable instead.

The knobs, and what each one silently controls

HNSW exposes a small set of parameters that jointly determine recall, latency, and memory. M is the maximum number of neighbors each node keeps per layer — the graph degree — and it governs how richly connected, and therefore how reachable, the space is. efConstruction is the size of the candidate list used while inserting a node, controlling how good that node's neighbor choices are. efSearch is the size of the candidate list at query time, controlling how hard a query looks before it gives up. Lower values are faster and cheaper; higher values are more accurate.

These are ordinarily framed as a pure performance trade-off. Reframed adversarially, each is a reachability control. A node inserted with a starved efConstruction gets poor outgoing edges and becomes hard to reach. A corpus served with a starved efSearch stops walking early and misses neighbors it could have found. A low M produces a sparse graph where a few well-placed nodes dominate the traversal paths. None of these are bugs; they are the documented behavior of the structure, which is exactly what makes them dangerous — the attack hides inside normal tuning.

The threat model that follows assumes the weakest useful attacker: someone who can add or update documents in a shared index (a multi-tenant SaaS corpus, a user-contributed knowledge base, a crawled web source) but cannot change server-side efSearch or read other tenants' data. Even this attacker can influence graph structure through the content and order of what they insert.

Attack tree: denying retrieval without touching the query

The attacker's goal is availability denial of a specific document or topic: make legitimate content unreachable so the model answers from a poisoned or empty context. This is distinct from poisoning, which adds attractive malicious content; here the attacker suppresses honest content. The two combine well — evict the truth, then dominate the gap — but suppression alone is enough to cause a model to hedge, refuse, or hallucinate.

The tree below decomposes that goal into three practical sub-goals reachable by an insert-only attacker: crowd the victim's neighborhood so honest documents fall out of the top-k, degrade the graph so the victim node is hard to reach at any efSearch, and amplify cost so operators lower efSearch defensively and widen the blind spot. Each leaf is an ordinary index operation used against its purpose.

Primitive 1: neighborhood crowding and eviction

Top-k retrieval returns a fixed number of results. If an attacker inserts many vectors that sit closer to a target query region than the honest document, the honest document is pushed past rank k and never enters the context. Because embeddings of paraphrases cluster tightly, generating many near-duplicates that hug a chosen point is cheap and does not require inverting the model — the attacker only needs text that embeds near the target region, which they can obtain by paraphrasing around the topic.

Formally, let q be a query, d the honest document, and let the attacker insert a set A of vectors. The honest document is evicted when at least k members of A are closer to q than d. The attacker does not need to know q exactly; it suffices to cover a region of likely queries, which is why crowding is effective against a whole class of related questions rather than a single string.

The defense is not to widen k — that invites more attacker content into the context — but to constrain who can place content near whom. Per-tenant or per-source indexes prevent one principal's inserts from ever competing in another's neighborhood, and diversity-aware retrieval that de-duplicates near-identical results blunts the flood even within a shared index.

# DEFENSIVE ILLUSTRATION ONLY — models when an honest doc falls out of top-k
function is_evicted(query, honest_doc, attacker_vectors, k):
    closer = 0
    for a in attacker_vectors:          # near-duplicates around a region
        if sim(query, a) > sim(query, honest_doc):
            closer += 1
    return closer >= k                  # honest doc pushed past rank k

# Blue-team check: run this over canary queries after every bulk ingest
# and alert if a known-good doc's rank degrades.

Primitive 2: graph degradation and starved reachability

Crowding fights within the top-k; graph degradation attacks reachability itself. Because HNSW inserts nodes incrementally and connects each new node to the neighbors it can find given efConstruction, the structure of the graph depends on what has been inserted and in what order. An attacker who controls ingestion order or who inserts a large volume of low-quality nodes can bias which nodes become well-connected hubs and which become peripheral.

The victim node's fate is decided at insert time: if the graph around it is dense with attacker nodes, its own edges are spent connecting to attacker content, and later honest queries that walk the graph are steered through attacker regions and may terminate before reaching it. This is why a starved efConstruction or a poisoned build order is more insidious than crowding — the document is not merely outranked, it is off the traversal path, and raising efSearch at query time only partially recovers it.

Deletion makes this worse. Many production stores implement deletion as tombstoning — marking a vector as deleted without removing it from the graph — and reclaim space only during periodic compaction. A tombstone storm (mass insert-then-delete) leaves the graph full of dead nodes that traversals still traverse, inflating latency and lowering effective recall until a rebuild. The defense is disciplined index lifecycle management: bounded ingestion, deterministic or randomized build order that no client can steer, and scheduled compaction with recall verification after each rebuild.

Primitive 3: cost amplification and the defensive-tuning trap

The third primitive is economic. Query cost in an approximate index is dominated by efSearch: a larger candidate list visits more nodes and costs more time and memory. An attacker who can submit queries — or who can shape the corpus so that honest queries become worst-case walks — drives up tail latency and cost. Operators under load respond exactly as the attacker wants: they lower efSearch to protect throughput, which shrinks how hard every query searches and widens the reachability blind spot the attacker created in primitives one and two.

This coupling is the trap. Availability pressure and recall are in tension through a single shared knob, so a cost attack silently becomes a recall attack. Defending it requires decoupling the two: bound per-caller query cost with fair scheduling and quotas so no principal can inflate global tail latency, and set efSearch from a recall objective rather than from instantaneous load, treating a recall drop as an incident rather than an acceptable degradation.

The measurement discipline matters as much as the controls. Because none of these primitives raise errors, the only way to see them is to continuously measure recall against a fixed set of canary queries with known correct answers, and to alarm on regressions the same way you would alarm on a rising error rate.

Why this is an AI-agent risk, not just an infrastructure one

An autonomous agent that plans over retrieved context inherits every reachability defect of its vector store. If an attacker can make a policy document, a safety instruction, or a factual record unreachable, the agent will plan as though it does not exist — and unlike a human operator, it will not notice the absence, because the absence is indistinguishable from the fact simply not being in the corpus. Suppression attacks are therefore especially potent against agents that treat retrieval as ground truth.

OWASP's LLM Top 10 names vector and embedding weaknesses (LLM08) and sensitive information disclosure (LLM06) as first-class risks, and NIST's adversarial machine-learning taxonomy classifies availability and integrity violations of the data pipeline as core attack categories. Index-level attacks sit precisely there: they are integrity and availability attacks on the retrieval substrate that an agent trusts implicitly. Framing retrieval recall as a security SLO — measured, alarmed, and owned — is what turns this from an invisible failure mode into a defended one.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

# DEFENSIVE HARNESS SKELETON
canaries = load_canary_queries()   # {query: expected_doc_id}

function check_recall(index, canaries, k, recall_floor):
    hits = 0
    for (query, expected_id) in canaries:
        results = index.search(query, k)      # normal read path
        if expected_id in ids(results):
            hits += 1
        else:
            log_regression(query, expected_id) # doc fell out of top-k
    recall = hits / len(canaries)
    assert recall >= recall_floor, "BLOCK PROMOTION: recall below SLO"
    return recall

# Run on a schedule AND after every bulk ingest / compaction.

ingestion_policy:
  isolation: per_tenant_index        # no shared neighborhood across tenants
  rate_limit:
    docs_per_minute: 200
    burst: 500
  dedup:
    near_duplicate_cosine: 0.98      # collapse clones on ingest
    max_docs_per_region: 50          # cap density near any centroid
  index_params:
    efSearch: server_controlled       # never client-supplied
    efConstruction: server_controlled
    M: server_controlled
  deletion:
    strategy: tombstone
    max_tombstone_ratio: 0.2          # auto-compact above this

Glossary

Approximate nearest-neighbor (ANN) search

Retrieval that returns the true nearest vectors with high probability by searching a small subset of the corpus instead of all of it.

HNSW

Hierarchical Navigable Small World graph, a layered proximity-graph index that answers similarity queries by a greedy graph walk.

M (graph degree)

The maximum number of neighbor edges each node keeps per layer in an HNSW graph, governing connectivity and reachability.

efConstruction

The candidate-list size used while inserting a node, controlling how good the new node's neighbor edges are.

efSearch

The candidate-list size used at query time, controlling how thoroughly a query searches before it stops.

Tombstoning

A deletion strategy that marks a vector as removed without deleting it from the graph, deferring reclamation to a later compaction.

Recall

The fraction of true nearest neighbors an approximate index actually returns for a query.

Eviction

Pushing an honest document past rank k by inserting vectors closer to the query region, so it never enters the retrieved context.

References

1. Malkov & Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using HNSW (arXiv 1603.09320)
2. Morris et al., Text Embeddings Reveal (Almost) as Much as Text (arXiv 2310.06816)
3. Song & Raghunathan, Information Leakage in Embedding Models (ACM CCS 2020)
4. OWASP Top 10 for LLM Applications (LLM06 Sensitive Information Disclosure; LLM08 Vector and Embedding Weaknesses)
5. NIST AI 100-2 e2023, Adversarial Machine Learning: A Taxonomy and Terminology