CoWalk: Cooperative Walks for Agentic Batch Queries on Disk-Resident Graphs

Qiao Liang, Zhiguang Chen, Yue Yu, Nong XiaoarXiv 2026 · arXiv

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_uring to keep multiple I/Os in flight across the entire batch, ensuring the CPU stays busy with computation while waiting for the SSD.
The CoWalk architecture: sharing candidate lists and exact distances across a batch on a single thread.

Datasets

The authors evaluated CoWalk on three workloads representing real-world agentic behavior:

  1. OpenResearcher: A deep-research benchmark with 97,630 multi-turn trajectories.
  2. QuAC+CANARD: A conversational QA workload where follow-up questions drill into specific Wikipedia articles.
  3. 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.

Figure 2. Pairwise cosine distance between queries of the same batch and between 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.
Throughput comparison at the "knee" thread count for different recall levels.

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

Abstract

Workloads such as query rewriting, deep research and group-relative policy optimization (GRPO) issue batches of semantically related vector queries. Existing disk-resident approximate nearest neighbor (ANN) systems process these queries independently. On three workloads, 31 to 67 percent of the I/Os of a batch fetch a page that another query of the batch has already fetched. A page cache shared by the batch removes these I/Os, yet it makes a single-thread search only $1.1$ to $1.2{\times}$ faster, because the search time goes to distance computation and the cache does not change the walk of any query. We present CoWalk, which runs the queries of a batch as cooperating walks on one thread. Every query keeps its own candidate list, a page is read once per batch, and the full-precision vector on every fetched page is ranked by every query of the batch. A query therefore reaches the target recall with a shorter candidate list, which computes fewer distances and issues fewer I/Os. At recall@10 of 0.95, CoWalk answers a batch on one thread $1.6$ to $1.9{\times}$ faster than the fastest per-query baseline and issues $2.8$ to $6.9{\times}$ fewer I/Os. On a server it serves $3.0$ to $6.9{\times}$ the throughput of that baseline at a similar batch latency.
BibTeX
@misc{liang2026cowalk,
  author = {Qiao Liang and Zhiguang Chen and Yue Yu and Nong Xiao},
  title = {{CoWalk: Cooperative Walks for Agentic Batch Queries on Disk-Resident Graphs}},
  year = {2026},
  eprint = {2610.38404},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38404},
}
Figure