Dynamic Graph Indexing for Label-Filtered Approximate Nearest Neighbor Search: what it means for business leaders

DYLAN is a vector index that keeps filtered similarity search fast when records carry many tags, and it absorbs new data without rebuilds, though so far only as single-threaded, in-memory research code.

1. What the method is

DYLAN is an in-memory index for label-filtered approximate nearest neighbor search: finding the vectors closest to a query among only those objects whose labels satisfy a filter. It supports containment filters (the object carries every query label), overlap filters (it carries at least one), and combinations of these joined by AND and OR. The structure is a composite. A trie organizes objects by their label sets, with labels ordered from most to least frequent, and HNSW-style proximity graphs are built over selected regions of that trie, not over every node. Each object appears in only logarithmically many graphs, so total index size stays near-linear, while every trie region is covered by a graph at most a constant factor larger than the region itself. The index accepts insertions and deletions without full rebuilds, which most label-aware competitors do not.

2. Why the method was developed

Filtering by labels and searching by vector similarity want different data structures, and the simple ways of combining them fail in opposite directions. Filtering first leaves a large candidate set to scan without an index; searching first forces heavy over-retrieval to keep recall. Filtering during graph traversal, as ACORN and NaviX do, breaks down when a selective filter removes most edges and leaves qualifying objects unreachable. The label-aware designs each cover part of the problem: Filtered-DiskANN handles overlap filters but does poorly on containment; RWalks encodes labels in a way that inflates memory as label types multiply; UNG builds one graph per distinct label set, which fragments the space and makes new label sets expensive to add; UniFilter caps its label index, so new labels are only partly absorbed; Curator relies on a clustering index that the authors describe as weaker than graphs for search. None combines all filter types, updates and a large label vocabulary.

3. Who should care

This matters to anyone on our side who runs retrieval with metadata constraints: retrieval-augmented generation restricted to approved sources, product search limited to categories, recommendations scoped by tenant, region or permission tags. Platform and infrastructure engineers who choose or operate a vector database should read it as a marker of where filtered-search performance is heading, and as a set of questions to put to vendors about selective filters, containment queries and live updates. Product owners should care because filter-heavy queries are where latency and missed results show up for users. Finance and capacity planners should note that the gains come with a larger memory footprint on label-rich data. Data teams that tag content gain an argument for richer label schemes, since the method is built for vocabularies of thousands of labels or more, where current indices degrade.

4. How the method works

Labels are sorted by frequency and each object's label set becomes a path in the trie, so a node stands for all objects sharing a label prefix. A node gets its own graph only when the logarithm of its region's size differs from its parent's; otherwise it shares the parent's graph, which bounds the extra vertices any search must wade through. A query first finds, through inverted lists on the trie, a set of disjoint regions that exactly covers the objects passing the filter. It then adds the graphs of common ancestors of those regions, whose edges bridge areas that would otherwise be disconnected, and runs one joint search across all selected graphs, computing distances only for neighbors that pass the filter. Vectors are stored once and referenced by ID. On insertion, a shared graph is rebuilt only when its size drifts past a threshold from its region, which the authors prove keeps amortized insertion cost bounded and each index within a factor of four of its region. Deletions are marks that search skips.

5. How it was evaluated

The authors tested on six real datasets, five from a standard filtered-search benchmark: TripClick (about 1.06 million medical text vectors, 29 labels), LAION1M (image vectors, 30 labels), YFCC (1 million vectors, 181,931 labels), and YouTube audio (5 million vectors) and video (1 million) sets with 3,862 labels each. They added Yelp1M, one million review chunks tagged with 1,227 business categories, as a stand-in for retrieval-augmented workloads. Baselines were ACORN, NaviX, Filtered-DiskANN, RWalks, UNG, UniFilter, Curator and exact pre-filtering, each with build parameters tuned per dataset for throughput at 0.9 recall. Queries covered containment and overlap filters across a range of selectivities, plus disjunctions of two containment filters. Everything ran single-threaded and in memory on one Xeon server with 1 TB of RAM, measuring queries per second against recall, memory, build time and insertion time, including a workload that inserts 20 percent of the data and deletes another 20 percent. The text we had is truncated, and its rendering dropped several figures.

6. How it performed

DYLAN had the best overall throughput at matched recall on all six datasets. The margin is modest on the two datasets with about 30 labels and large on label-rich ones: a factor of three to five on YFCC, where no other method handled both filter types well, and about two orders of magnitude on YouTube audio, where at 0.9 recall it visited 38.6 times fewer points and computed 75.5 times fewer distances than UNG. Insertions were three to five times faster than Filtered-DiskANN, and an index that had taken updates searched about as well as one built fresh. The limits are real: Curator matches it on YouTube video, UNG matches it on very selective LAION queries, build time is slower than UNG and RWalks, memory is higher on label-rich data, and the code is single-threaded, in-memory only and untested beyond 5 million vectors. Our call is to watch: raise it with our vector database vendors and revisit when a parallel, production-grade implementation exists. (Source: arXiv 2611.12539, 2026)