Dynamic Graph Indexing for Label-Filtered Approximate Nearest Neighbor Search

A support assistant searches for a repair procedure. The closest documents discuss the right fault, but belong to another customer or apply to equipment sold in another region. Removing those documents after retrieval leaves an incomplete answer. Increasing the number retrieved may help, but also increases work and gives no fixed guarantee that enough eligible documents will appear.

DYLAN studies this problem inside the vector index. Each record has a vector and a set of labels. A query asks for nearby vectors whose labels satisfy a predicate. The index organizes label sets in a trie, a tree of shared label prefixes, and attaches graph indexes to selected regions. At search time, it identifies the eligible regions and searches their graphs together, using selected ancestor graphs to connect regions that would otherwise be isolated.

The design supports insertion and uses lazy deletion. Its experiments report higher throughput on the evaluated filtered-search workloads, but the measurements are single-threaded and in memory. They do not establish distributed serving behavior or a complete authorization system.

One phrase needs care: the paper's graph is initially a “2-approximate index,” with a relaxed bound during insertion maintenance. That describes how many objects a covering graph can contain relative to one trie region. It says nothing by itself about nearest-neighbor recall. A larger graph can cover a small region without the search finding every desired neighbor.

Filtered vector search appears in tenant-specific support, product catalogs, regional documentation and document collections with category restrictions. A retrieval failure in these systems can look like a weak embedding model even when the embedding places the right record nearby. The search may simply fail to reach enough eligible candidates.

Before replacing the model, compute exact nearest neighbors within the allowed records for a representative query sample. Compare the approximate results with that reference. Keep semantic relevance evaluation separate: even exact vector neighbors may be poor evidence for the user's question.

DYLAN gives you a concrete architecture to investigate when label-filtered retrieval is the bottleneck. It also gives you sharper questions for a database vendor: how are disconnected eligible regions searched, what happens when labels change, and which update costs are absent from the throughput chart? The vector database survey provides the broader context for that discussion.