Evaluating the Effectiveness and Efficiency of Demonstration Retrievers in RAG for Coding Tasks

Retrieval-Augmented Generation (RAG) enhances Large Language Models (LLMs) by integrating external knowledge bases, achieving state-of-the-art results in various coding tasks. The core of RAG is retrieving demonstration examples, which is essential to balance effectiveness (generation quality) and efficiency (retrieval time) for optimal performance. However, the high-dimensional nature of code representations and large knowledge bases often create efficiency bottlenecks, which are overlooked in previous research. This paper systematically evaluates the efficiency-effectiveness trade-off of retrievers across three coding tasks: Program Synthesis, Commit Message Generation, and Assertion Generation. We examined six retrievers: two sparse (BM25 and BM25L) and four dense retrievers, including one exhaustive dense retriever (SBERT's Semantic Search) and three approximate dense retrievers (ANNOY, LSH, and HNSW). Our findings show that while BM25 excels in effectiveness, it suffers in efficiency as the knowledge base grows beyond 1000 entries. In large-scale retrieval, efficiency differences become more pronounced, with approximate dense retrievers offering the greatest gains. For instance, in Commit Generation task, HNSW achieves a 44x speed up, while only with a 1.74% drop in RougeL compared with BM25. Our results also show that increasing the number of demonstrations in the prompt doesn't always improve the effectiveness and can increase latency and lead to incorrect outputs. Our findings provide valuable insights for practitioners aiming to build efficient and effective RAG systems for coding tasks.