Accelerating Graph-Based RAG Retrieval via Locality-Aware Device-Cloud Collaboration
Open Access
- 8 August 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 839-850
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.Keywords
Funding Information
- National Natural Science Foundation of China (62402267)
- National Natural Science Foundation of China (62432004)
- National Natural Science Foundation of China (62302207)
- National Natural Science Foundation of China (62572496)
- Fundamental Research Funds for the Central Universities (2026300278)
- Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (JYB2025XDXM122)
- Guangdong Natural Science Foundation (2026A1515011265)
- Shenzhen Science and Technology Program (JCYJ20250604175500001)
- China Postdoctoral Science Foundation (2025M771499)
This publication has 4 references indexed in Scilit:
- Chameleon: A Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language ModelsProceedings of the VLDB Endowment, 2024
- Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data SegmentProceedings of the ACM on Management of Data, 2024
- Billion-Scale Similarity Search with GPUsIEEE Transactions on Big Data, 2019
- Fast approximate nearest neighbor search with the navigating spreading-out graphProceedings of the VLDB Endowment, 2019