EdgeRAG: Online-Indexed RAG for Edge Devices

Korakit Seemakhupt, Sihang Liu, Samira Khan · 2024

Read EdgeRAG: Online-Indexed RAG for Edge Devices by Korakit Seemakhupt, Sihang Liu, Samira Khan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-21023.txt.

Description

Abstract Deploying Retrieval Augmented Generation (RAG) on resource-constrained edge devices is challenging due to limited memory and processing power. In this work, we propose EdgeRAG which addresses the memory constraint by pruning embeddings within clusters and generating embeddings on-demand during retrieval.

Catalog record

CREATORKorakit Seemakhupt, Sihang Liu, Samira Khan
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-21023

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

EdgeRAG: Online-Indexed RAG for Edge Devices Korakit Seemakhupt, Sihang Liu, Samira Khan Abstract Deploying Retrieval Augmented Generation (RAG) on resource-constrained edge devices is challenging due to limited memory and processing power. In this work, we propose EdgeRAG which addresses the memory constraint by pruning embeddings within clusters and generating embeddings on-demand during retrieval. To avoid the latency of generating embeddings for large tail clusters, EdgeRAG pre-computes and stores embeddings for these clusters, while adaptively caching remaining embeddings to minimize redundant computations and further optimize latency. The result from BEIR suite shows that EdgeRAG offers significant latency reduction over the baseline IVF index, but with similar generation quality while allowing all of our evaluated datasets to fit into the memory. 1 Introduction Large Language Models (LLMs) enable new applications such as smart assistants ( Google 2024 ; Microsoft ) . The processing of these powerful LLMs is usually offloaded to the datacenter due to the enormous resources required. However, the latest mobile platforms enable smaller LLM to run locally. These lightweight models cannot directly compare with the state-of-the-art hundred-billion parameter LLMs. To enhance these models to process users’ custom data and applications, a promising solution is to build a compounding system. By integrating LLMs with Retrieval Augmented Generation (RAG), these smaller models can leverage local personal data to generate high-quality responses. Even though RAG removes the requirement for a heavy-weight LLM for generation, retrieval still has a high overhead. The core of a RAG system is a vector database that enables vector similarity search. Different from LLMs, the overhead of RAG mainly comes from its memory footprint. For example, a Flat Index stores and sequentially searches every vector representation of the data chunks to identify the closest match to the query. For example, in fever ( Thorne et al. 2018 ) dataset, a vector database that holds 5.23 million records has an index size of 18.5 GB. In comparison, mobile devices tend to have 4-12 GB of main memory ( Wiens 2024 ; Sam 2024 ) . Thus even using the whole memory on a mobile platform is not sufficient to run a large vector database. On the other hand, storing the vector database on disk introduces substantial access latency, impacting performance. Our research focused on the challenges of implementing Retrieval Augmented Generation (RAG) on edge systems—mainly the overhead of the vector similarity search. We find that naively keeping the entire index in the main memory would not fit into the memory of mobile platforms. A Flat index which performs sequential search of all embeddings not only expensive in term of computation, but also trash memory leading to poor performance. On the other hand, Two-level Inverted File (IVF) index clusters embeddings of data chunks into centroids. The retrieval process first searches for the closest centroid and then performs a second search within the cluster. Thus, avoid expensive sequential search of all embeddings. However, keeping all embeddings in memory still leads to excessive memory thrashing and increased latency. Thus, keeping the first-level centroid in memory and generating the second level online can be a promising solution. Through further profiling the RAG on mobile platforms using widely-used RAG benchmarks ( Thakur et al. 2021 ) , we find that both the data access pattern and the access latency are highly skewed. First, most of the embedding vectors are not searched during the retrieval process. Second, the cost of generating the embedding vector is not the same for all clusters and has an extreme tail distribution. These skewness leave space for further optimizations. In this work, we develop a mobile RAG system, EdgeRAG that enables RAG-based LLM on mobile platforms, by fitting the vector database in the limited mobile memory while ensuring that the response time meets the service level objectives (SLOs) of mobile AI assistant applications. Based on these observations, our key ideas are the following: First, we prune the vector embedding of the data embeddings within centroid clusters which are only used for second-level search to save the memory capacity. EdgeRAG then generates the vector embedding online during the retrieval process. However, due to limited computing on edge systems, generating vector embedding online could suffer from long embedding generation latency from large tail clusters. To overcome this challenge, our second solution is to pre-compute and store the embeddings of large tail clusters to avoid long tail latency of generating vector embeddings of data within those tail clusters. Then, EdgeRAG can adaptively cache the remaining vector embeddings to minimize redundant computation and improve overall latency, based on the spare memory capacity and SLO requirements. We evaluate EdgeRAG on a mobile platform based on Nvidia Jetson Orin Nano equipped with 8 GB of shared main memory, similar to a mobile edge platform that has neural processing capabilities ( Sam 2024 ) . We use 6 workloads from the BEIR benchmark suite ( Thakur et al. 2021 ) and tune the retrieval hyperparameters to normalize the recall against the Flat index baseline. We also evaluate the generation quality using GPT-4o ( OpenAI ) LLM as an LLM evaluator ( Saad-Falcon et al. 2023 ) . We use the time-to-first-token (TTFT) latency as the main metric. The result shows that EdgeRAG offers 1.8 \times faster TTFT over the baseline IVF index on average and 3.82 \times for larger datasets. At the same time, EdgeRAG maintains a similar generation quality with recall and generation scores within 5 percent of the Flat Index baseline while allowing all of our evaluated datasets to fit into the memory and avoid memory thrashing. In summary, the contributions of this work are the following: • We identify two key challenges of implementing RAG on edge devices: First, limited memory capacity does not allow loading large embedding vector database in the memory leading to memory thrashing and poor performance. Although only a small subset of embeddings are searched for two-level IVF index. Second, limited computing power of edge devices which slows down online embedding generation especially on few large tail and repeatedly used clusters. • To enable scalable and memory-efficient RAG on edge systems, we propose EdgeRAG which improves upon IVF index by pruning second-level embeddings to reduce memory footprint and generate the embedding online during retrieval time. EdgeRAG mitigates long tail latency from generating the embeddings of heavy cluster by pre-computing and storing those tails. To further optimize latency, EdgeRAG selectively caches generated embeddings to reduce redundant computation while minimizing memory overhead. • We implement EdgeRAG on Jetson Orin edge platform and evaluate our system with datasets from BEIR benchmark. The results show that EdgeRAG significantly improves the retrieval latency of large datasets with embedding sizes larger than the memory capacity by 131% with slight reduction in retrieval and generation quality. 2 Background 2.1 Retrieval Augmented Generation Retrieval Augmented Generation (RAG) ( Lewis et al. 2020 ) is a technique used to improve the accuracy of the Large Language Model (LLM) by integrating an external knowledge base with the LLM. Instead of retraining the entire LLM with new information, RAG adds new data to the database. The RAG consists of two parts: Indexing and Lookup. Indexing: Adding new data to the database involves a process called indexing, illustrated in Figure 1(a) .

Read the complete text