Accelerating Graph-Based RAG Retrieval via Locality-Aware Device-Cloud Collaboration

Abstract

Retrieval-Augmented Generation (RAG) grounds large language models in external knowledge and has become a key technique for knowledge-intensive tasks. As knowledge bases continue to scale, however, the retrieval stage increasingly dominates end-to-end latency, limiting the responsiveness of RAG systems. In this paper, we identify and empirically validate a previously underexplored property of RAG workloads: strong per-user query locality, where individual users' queries concentrate on a small subset of the knowledge space. Motivated by this observation, we propose Lever, a locality-aware collaborative retrieval framework that exploits query locality to accelerate graph-based RAG retrieval. Lever maintains compact, personalized subgraph indexes on user's local devices as auxiliary structures to guide retrieval toward semantically relevant regions of a global index, enabling more efficient graph traversal without sacrificing coverage. To sustain effectiveness over time, Lever further incorporates adaptive resampling mechanisms that align on-device indexes with evolving query patterns. Extensive experiments on multiple RAG benchmarks demonstrate that Lever significantly reduces retrieval latency and improves throughput while preserving retrieval quality, highlighting query locality as a powerful and complementary lever for scalable RAG retrieval.