TL;DR
CoWalk is a novel vector search system designed for the "agentic" era, where LLMs issue batches of semantically related queries. By running these queries as "cooperating walks" on a single thread, CoWalk shares I/O and distance computations across the batch, achieving up to 1.9x lower latency and 6.9x higher throughput than state-of-the-art systems.
What Problem Does This Paper Address?
Modern AI agents don't just ask a single question; they often perform "query rewriting" (generating multiple paraphrases), "deep research" (decomposing tasks into sub-queries), or use reinforcement learning techniques like GRPO that sample multiple search rollouts. These patterns create batches of queries that are extremely close to each other in embedding space.
Existing disk-resident Approximate Nearest Neighbor (ANN) systems, like DiskANN or PipeANN, process these queries independently. This leads to massive redundancy: between 31% and 67% of the data read from an SSD for a batch is simply re-reading pages that a "batch-mate" already fetched. Even adding a simple shared page cache doesn't solve the problem—while it reduces I/O, it doesn't change the "walk" path of the search, meaning the system still wastes time on redundant distance computations.
Methods
CoWalk moves away from independent searches and introduces Cooperative Walks. Instead of running $B$ queries on $B$ threads, it runs them as a single coordinated process on one thread.
Key innovations include:
- I/O Sharing: If multiple queries in a batch want to visit the same node in the graph, the page is read from the SSD exactly once.
- Exact Distance Sharing: When a page is fetched, CoWalk computes the exact distance between that node and every query in the batch. This is done using a high-performance cross-query SIMD kernel.
- Global Ranking: Because every query ranks every node the batch has fetched, a query often discovers its true neighbors "for free" from nodes its batch-mates requested. This allows each query to reach its target recall with a much shorter candidate list ($L$), significantly reducing the total number of nodes that need to be explored.
- Pipelined Execution: It uses
io_uringto keep multiple I/Os in flight across the entire batch, ensuring the CPU stays busy with computation while waiting for the SSD.
Datasets
The authors evaluated CoWalk on three workloads representing real-world agentic behavior:
- OpenResearcher: A deep-research benchmark with 97,630 multi-turn trajectories.
- QuAC+CANARD: A conversational QA workload where follow-up questions drill into specific Wikipedia articles.
- NarrativeQA: A reading-comprehension workload based on books and movie scripts.
As shown in the paper's analysis, queries within these batches are significantly closer in embedding space (up to 2.4x tighter) than random query pairs.
Key Insights and Ideas
- Caching is a Half-Measure: A shared page cache (the authors' "GLRU" baseline) only provides a 1.1x–1.2x speedup. This is because, on a single thread, the bottleneck is the computation of distances, not just the I/O latency.
- The Power of Cooperation: The "aha moment" is that a node fetched for Query A is often a great candidate for Query B. By allowing Query B to rank that node immediately, Query B's search path becomes more efficient.
- Graph > Cluster for Batches: The authors demonstrate that graph-based indexes are fundamentally better for batched queries than cluster-based indexes (like SPANN). Cluster indexes read too much irrelevant data (entire clusters) when deduplicating across a batch, whereas graph walks are more "surgical."
Key Results
At a high-accuracy target (recall@10 of 0.95):
- Latency: CoWalk is 1.6x to 1.9x faster than PipeANN on a single thread.
- I/O Efficiency: It issues 2.8x to 6.9x fewer I/Os per batch.
- Throughput: On a server setting, CoWalk serves 3.0x to 6.9x more queries per second than the baseline.
- Cost-Effectiveness: CoWalk provides up to 7x more queries per dollar when accounting for cloud compute and storage costs.
Limitations and Future Work
- Unrelated Queries: CoWalk's benefits rely on semantic similarity. If a batch contains totally unrelated queries, CoWalk can actually be slower than independent processing because the overhead of sharing distances outweighs the I/O savings.
- Read-Only Focus: The current implementation focuses on the "read path." While it supports concurrent updates by falling back to standard per-query paths, a fully integrated "cooperative update" path is left for future research.
- Parameter Sensitivity: The optimal number of threads per batch ($k$) depends on the specific hardware and batch size, requiring some tuning for peak performance.
Summary updated