CoWalk makes related agent searches faster—but random batches erase the gain

Agent retrieval systems often treat every vector query as an independent search. CoWalk tests a different assumption: when an agent produces several searches from one intent, the storage engine can execute those graph walks cooperatively. On three workloads, that assumption produced meaningful gains—but the paper’s own negative control shows exactly where they stop.

What the benchmark measures

The evaluation uses three batches of semantically related queries: OpenResearcher deep-research trajectories, QuAC questions rewritten by CANARD, and NarrativeQA questions grouped by narrative. Their mean batch sizes are 33.5, 7.2 and 29.7 queries. Within each workload, same-batch query pairs are 58.5%, 52.3% and 21.0% closer in cosine distance than random query pairs, respectively.

All systems use the same disk-resident Vamana graph and I/O engine. CoWalk is compared with PipeANN, which processes queries independently, and GLRU, a PipeANN variant with a batch-scoped 32,768-page cache. Tests ran on one server with dual AMD EPYC 9754 CPUs, 1.5 TB of DDR5 memory and a Huawei eKitStor Xtreme 116P PCIe 5.0 SSD.

At Recall@10 = 0.95, single-thread CoWalk completed a batch in 62 ms on OpenResearcher, 25 ms on QuAC+CANARD and 71 ms on NarrativeQA. PipeANN took 115, 45 and 116 ms on those same splits. That is a 1.9×, 1.8× and 1.6× latency reduction. CoWalk issued 901, 1,849 and 5,007 I/Os per batch; PipeANN issued 6.9×, 2.9× and 2.8× as many.

The server result is larger. At each system’s knee thread count and the same 0.95 recall target, CoWalk served 17.4K, 10.0K and 11.1K queries per second—6.9×, 4.0× and 3.0× PipeANN—while batch latency stayed between 0.74× and 1.08× PipeANN’s.

Why caching alone is not enough

GLRU removes repeated page reads, yet its single-thread curves nearly overlap PipeANN. The paper finds that PipeANN waits on I/O for only 13%–21% of its time because computation overlaps outstanding reads. CoWalk’s important step is instead to let every query rank the full-precision vectors fetched by its batch-mates. At 0.95 recall, that reduces the candidate-list length from 184 to 70 on OpenResearcher, 688 to 304 on QuAC+CANARD, and 464 to 248 on NarrativeQA.

An ablation reinforces the mechanism: removing exact-distance sharing while retaining page sharing raises latency by 1.6×–1.9× and lowers throughput by 1.9×–2.2×.

The boundary matters

This is not a general replacement for per-query ANN. When the authors randomly regroup queries, CoWalk reads at most 14% fewer pages per query instead of 65%–88% fewer. At 0.95 recall it becomes 1.2×–2.5× slower per query on one thread, depending on batch size. Four idle PipeANN threads also beat single-thread CoWalk on every workload.

The result therefore supports a routing rule, not a universal default: cooperative walks are useful when a system can identify genuinely related searches and values throughput or I/O efficiency. The implementation also shares only the read path; concurrent inserts and deletes fall back to PipeANN’s per-query update path. Independent reproduction on other SSDs and live mixed-query traffic is still missing.