arXiv preprint ·
CoWalk: Cooperative Walks for Agentic Batch Queries on Disk-Resident Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Databases
LASSO: An LLM-Agent Synthesized System for SQL Validation
Rebuilding a Field's Open-Problem Catalog from the Literature: A Two-Layer Knowledge Graph, and Why Status Must Stay Proposed
Manifest-Assisted Retrieval in Artificial Intelligence Search: Evidence Gaps and a Security Evaluation
When Imputation Changes the Nearest Neighbor: Exact Certification of Similarity Retrieval for Incomplete Sensor Time Series
SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits
Get the few papers worth your time in Databases every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.