A dynamic vector index is the part of an AI search system that has to keep working while the data underneath it changes. Researchers at KAIST in South Korea say they have built one that does this much better than current designs. Their index, CONDA (Connectivity-Aware Dynamic Index), keeps the search paths between stored records intact as new records arrive and old ones are deleted, so an AI system can still find information that is technically in the database.
The work, by Darae Lee and Professor Min-Soo Kim of KAIST’s School of Computing, is published in Proceedings of the VLDB Endowment, one of the main journals for database research. KAIST says CONDA improves search accuracy by up to 24.5% over existing methods and update throughput by up to 1.90 times, and that it held the best latency and accuracy in a six-hour test on 100 million vectors. Tech Xplore reported it on 6 October 2026.
Below we explain the problem in plain terms, show how today’s vector databases deal with deletes, walk through how this dynamic vector index works, and read the results closely, including the places where CONDA is not the fastest. We finish with what it means for teams running retrieval-augmented generation (RAG) on data that never stops changing.
Table of contents
- What the CONDA Dynamic Vector Index Is
- Why Vector Search Breaks When Records Change
- How a Dynamic Vector Index Handles Deletes Today
- How CONDA Keeps a Dynamic Vector Index Connected
- Testing the Dynamic Vector Index: Results Read Carefully
- The Limits of This Dynamic Vector Index
- What a Dynamic Vector Index Means for RAG Teams
- From Paper to Product: A Dynamic Vector Index for AkasicDB
- Dynamic Vector Index: Frequently Asked Questions
- References
What the CONDA Dynamic Vector Index Is
CONDA is a graph-based dynamic vector index for approximate nearest neighbour search, the technique that lets a vector database find the stored items most similar to a query in milliseconds rather than comparing against every record.
The paper and the team
The full title is “CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data”, in PVLDB volume 19, issue 11, pages 3357 to 3370. Darae Lee is the first author and is now at NAVER; Min-Soo Kim is the corresponding author. KAIST says the work was presented at VLDB 2026.
The headline claims
Three numbers headline the KAIST announcement. Each comes with conditions that the paper spells out and the press release does not.
| Claim | Figure | Where it comes from |
|---|---|---|
| Search accuracy gain | Up to 24.5% | Wikipedia 1M dataset, sliding window, against FreshVamana |
| Update throughput | Up to 1.90 times | Best case stated in the paper’s abstract |
| Average accuracy gain | 4.3% | Paper’s conclusion, across update tests |
| Average update-time saving | 20.5% | Paper’s conclusion |
| Isolated records | 94.7% fewer on average | Paper’s conclusion |
| Large-scale test | 100 million vectors, 6 hours | MS SpaceV 100M, concurrent reads and writes |
Open code you can read
The authors have published the C++ code on GitHub under the MIT licence, which means anyone can test this dynamic vector index on their own data. The paper itself is open access under a Creative Commons BY-NC-ND licence.
Why Vector Search Breaks When Records Change
To see what CONDA fixes, it helps to know how a graph index finds things. The explanation takes three steps and no maths.
How a graph index searches
A graph index links every stored vector to a handful of near neighbours, like a map where each town has roads to a few nearby towns. A search starts at one entry point and keeps stepping to whichever neighbour is closer to the query, until it can get no closer. The method, called greedy search, is fast because it visits only a tiny fraction of the records.
Why links get pruned
Each record can only keep a fixed number of links, 32 in the paper’s tests, to keep memory under control. When a record has too many candidate links, a pruning rule drops the ones that look redundant because a shorter route seems to exist through another neighbour. The common rule judges this on distance alone.
Connectivity collapse
That shortcut assumption is where things break. The paper shows that when records are inserted and deleted one by one, the pruning rule often cuts links that were the only route to part of the graph. The authors call the result connectivity collapse. A record can end up with no incoming links at all, so no search can ever reach it, even though it is still stored.
How much it costs in accuracy
The damage is measurable. In the paper’s tests on the MS Turing 10M dataset, a 1% share of isolated records cost the FreshVamana index 5.1% of its recall, and a 0.5% share cost IPVamana 2.6%. Recall here means the share of true nearest neighbours a search actually returns.
Bar width equals recall. The 16 to 63 and 64 to 127 groups both scored 97% in the paper, so we merged them into one bar.
Too few links and too many
The chart shows two failure modes. Records with few incoming links, which the paper calls antihubs, are hard to find. Records with very many, superhubs, also do worse, because searches tend to stop at them too early. As updates pile up, the paper finds both groups growing while the healthy middle shrinks. A dynamic vector index has to stop that drift.
How a Dynamic Vector Index Handles Deletes Today
Deletes are the hard part of any dynamic vector index. The paper groups today’s approaches into three families, and most production systems use one of the first two.
| Approach | How a delete works | The catch |
|---|---|---|
| Soft deletion | Record is marked as a tombstone and filtered out of results | Tombstones still use search effort, so recall falls and latency rises over time |
| Out-of-place rebuilds | Changes go to side segments that are merged into a rebuilt index later | Rebuilds are expensive and compete with live queries |
| In-place updates | Only the neighbourhood around the change is repaired | Repairs can cut vital links, and many need periodic whole-graph scans |
Soft deletion in practice
Soft deletion is common because it is simple. The popular hnswlib library, for example, offers a mark_deleted call that “marks the element as deleted, so it will be omitted from search results”. The record stays in the graph, though, and the paper shows that searches keep spending their limited budget walking past such tombstones.
What rebuilds cost
Rebuilding avoids tombstones but at a price. The paper cites figures for the billion-vector BIGANN dataset: 1.1 TB of memory and 48 hours on 32 virtual CPUs to build a DiskANN index, or 475 GB and 90 hours on one machine for HNSW. Even PostgreSQL’s pgvector notes that vacuuming “can take a while for HNSW indexes” and suggests reindexing first.
Where CONDA fits
CONDA belongs to the third family, in-place updates, alongside FreshVamana, IPVamana and Wolverine. Its aim as a dynamic vector index is to keep the low cost of local repairs while removing their two weaknesses: cut links and the periodic whole-graph scans that deletions require. If it works, a dynamic vector index would need neither tombstone clean-ups nor scheduled rebuilds.
How CONDA Keeps a Dynamic Vector Index Connected
CONDA changes three things about how an in-place dynamic vector index handles updates. Each is small on its own; together they target connectivity collapse directly.
A pruning rule that checks the actual graph
The new rule, CRNG, drops a link only if the graph really offers a short route instead. Before pruning a link from record P to record V, it checks that V is reachable from P in two hops through a neighbour that is closer to V. If no such route exists, the link stays, whatever the distances suggest.
Fixing detours as it goes
CRNG handles a third case too. If V is reachable in two hops but only by a route that moves away from it first, CRNG adds the direct link and removes the longer one. Over time this keeps the links short and the routes monotonic, meaning each step gets closer to the target.
Reinforcing links in both directions
When a new record joins, CONDA links it to its neighbours and asks them to link back. If a neighbour has to drop the new record during its own pruning, CONDA widens the search for another record that can link back instead. A tuning value of 0.25 controls how wide that widening goes.
Lazy deletion
Deleting is where CONDA saves the most work. It repairs the neighbourhood it finds with a quick local search, but instead of scanning the whole graph to find every link pointing at a deleted record, CONDA writes a marker value into the record’s vector and leaves those links in place. When a later search meets the marker, it removes the dead link on the spot. The freed memory slot is reused for the next insert.
Locks for live traffic
Searches take shared locks, and updates lock only the records they change. Because each update touches a bounded neighbourhood, the paper says contention stays low even with many threads writing at once. That is what allows this dynamic vector index to keep serving queries during heavy update traffic.
Testing the Dynamic Vector Index: Results Read Carefully
The paper’s evaluation of this dynamic vector index is extensive. It uses six real datasets, three update patterns from the NeurIPS 2023 BigANN benchmark, and four rival in-place indexes. The details matter, because the headline figures are best cases.
The test set-up
The datasets are MS Turing, MS SpaceV, Wikipedia, BIGANN, Text-to-Image and YFCC, covering text embeddings, computer vision features from images, and mixed data. The update patterns are a sliding window (2% of records replaced per step), expiry (random lifespans, about 4% churn per step) and clustered bursts. Everything ran on a server with two Intel Xeon Gold 6326 processors and 512 GB of memory.
Accuracy against each rival
Across five one-million-record datasets under the sliding window, CONDA’s average recall gain varied a lot by rival. The 24.5% headline is a single dataset, Wikipedia 1M, against the weakest rival; on the hardest 5% of Wikipedia queries the gain over FreshVamana rose to 31.3%.
Bars use a 0 to 10 scale, so each width is the gain multiplied by 10. The paper reports these as average improvements in recall across the five datasets.
Update speed against each rival
Under the sliding window, CONDA cut total update time by 26.8% against FreshVamana, 21.4% against IPVamana and 35.8% against Wolverine+. It did not beat Wolverine++, which updated fastest of all, but the paper shows Wolverine++ paying for that speed with steadily falling accuracy.
Where the savings come from
The deletion change does most of the work. On MS SpaceV 1M, CONDA’s clean-up cost was 0.013 seconds per step, against 0.41 seconds for FreshVamana and 0.19 seconds for IPVamana. That is roughly 31 times less than FreshVamana (0.41 divided by 0.013) and 15 times less than IPVamana (0.19 divided by 0.013).
Clustered bursts tell a mixed story
Bursts of similar records are the hardest pattern for a dynamic vector index, and here the picture is less one-sided. On MS Turing 10M, CONDA ran 1.42 to 1.57 times more queries per second than every rival at the same 0.80 recall. Its update time, though, was slower than three of them.
| Total update time (seconds) | FreshVamana | IPVamana | Wolverine+ | Wolverine++ | CONDA |
|---|---|---|---|---|---|
| MS Turing 10M | 213.0 | 296.2 | 238.0 | 135.2 | 260.3 |
| MS Turing 30M | 1,148.0 | 1,391.2 | 1,322.7 | 528.8 | 1,025.4 |
On the 10M set CONDA ranked fourth of five for update time; on the 30M set, with smaller batches, it ranked second. The authors explain that bursts of similar records trigger repeated re-pruning. None of the rivals reached 0.85 recall on either set, while CONDA did.
The real-world simulations
Two simulations aimed closer to production. On 84 million YFCC images, FreshVamana’s share of isolated records rose to nearly 40%, while CONDA’s stayed near zero. In the six-hour test on 100 million MS SpaceV vectors, with five insert, five delete and five search threads running at once, CONDA had the lowest tail latency and the highest recall throughout.
The Limits of This Dynamic Vector Index
The paper is candid about what the CONDA dynamic vector index does not yet do. Anyone weighing it against a production system should read these alongside the gains.
In memory only
The CONDA dynamic vector index keeps its graph in main memory. Billion-scale deployments often keep the index on disk to save cost, and the authors list a disk-resident version as future work. Until then, CONDA suits datasets that fit in server memory.
Stale links can linger
Lazy deletion trades a little search quality for speed: dead links stay until a search happens to walk past them. The repair step also uses a local search, so it can miss some records that pointed at a deleted one. The authors say these stale edges “can affect search performance over long-running updates”.
Rivals not in the test
The paper compares CONDA with other in-place graph indexes, not with commercial vector databases running their own segment-and-rebuild schemes. Two related methods, Greator and CleANN, were left out because they target different problems, and the authors say they could be combined with CONDA.
Best cases in the headlines
The press figures are real but selective. A 24.5% gain on one dataset against one rival is not what a typical system will see; the paper’s own average across tests is 4.3%. That is still a meaningful improvement for a dynamic vector index, just a smaller one than the headline implies.
What a Dynamic Vector Index Means for RAG Teams
RAG systems retrieve documents from a vector store and pass them to a large language model to ground its answer. If the right document cannot be retrieved, the model answers without it. “The key value of retrieval-augmented generation (RAG) is that it allows large language models to find and use the latest information,” Kim said in KAIST’s announcement.
Measure recall over time, not once
Most teams test retrieval quality when they build an index and never again. Under constant updates, recall drifts. Keep a fixed set of test queries with known answers, run it every week, and plot the result. A slow decline is the signature of the problem this dynamic vector index was built to fix.
Watch your delete rate
The paper’s tests used churn of 2% to 4% of records per step. If your knowledge base replaces documents at anything like that rate, through news feeds, product catalogues or expiring records, deletion handling matters. A store that only ever grows is far less exposed.
Ask your vendor three questions
Ask how their dynamic vector index handles deletes (tombstones, rebuilds or in-place repair), how often the index is rebuilt and what that does to latency, and whether they measure unreachable records. Our guide to choosing a vector database covers the wider selection, and our comparison of HNSW and IVF indexes explains the index families.
Fix the data before the index
Even the best dynamic vector index cannot rescue poor content. Duplicate documents, stale versions and badly split text cause more retrieval failures than graph connectivity does. Our RAG chunking and parsing guide deals with that layer, and our data management team can help audit a knowledge base before any index change.
From Paper to Product: A Dynamic Vector Index for AkasicDB
The research behind this dynamic vector index is already heading into a product. KAIST says CONDA will be built into AkasicDB, the database product of GraphAI, an AI data infrastructure company Kim founded, with a commercial release scheduled for the fourth quarter of 2026.
What to test before adopting it
For teams that want to try the approach sooner, the MIT-licensed code allows a direct comparison. A fair trial replays a week of your real inserts and deletes against both your current index and CONDA, measuring recall on the same fixed query set at each step. That is the test that shows whether this dynamic vector index helps your workload specifically.
Why database researchers care
Kim framed the result as infrastructure for keeping AI current: a way for AI “to accurately leverage up-to-date knowledge over extended periods, even as data changes continuously”. The work was funded by the National Research Foundation of Korea and the IITP SW Star Lab programme.
Dynamic Vector Index: Frequently Asked Questions
What is a dynamic vector index?
A dynamic vector index is a search structure for embeddings that supports inserting and deleting records while it continues to answer queries, without needing a full rebuild. CONDA is one design for this.
What is connectivity collapse?
It is the gradual loss of links in a graph index as records change, until some records have no incoming links and cannot be found by any search, even though they are still stored.
How much does CONDA improve accuracy?
Up to 24.5% in its best case, on Wikipedia data against FreshVamana. Across the paper’s update tests the average gain is 4.3%.
Is the CONDA code available?
Yes. The authors have published the C++ implementation on GitHub under the MIT licence, and the paper is open access.
Will CONDA work with my vector database?
Not directly today. CONDA is a research dynamic vector index that keeps its graph in memory. KAIST says it will ship inside GraphAI’s AkasicDB in the fourth quarter of 2026.
