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

arXiv: https://arxiv.org/abs/2410.09662 · HTML: https://mlsanity.com/paper/2410.09662/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RAG for code, one of 15 directions in Retrieval-augmented generation.
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 12 Oct 2024.

## Placed in

- Retrieval-augmented generation / [RAG for code](https://mlsanity.com/rag/rag-for-code/)

## Builds on (most cited first, 24 of 24)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (2023)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [CodeBLEU: a Method for Automatic Evaluation of Code Synthesis](https://mlsanity.com/paper/2009.10297/) (2020)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [UniXcoder: Unified Cross-Modal Pre-training for Code Representation](https://mlsanity.com/paper/2203.03850/) (2022)
- [LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression](https://mlsanity.com/paper/2403.12968/) (2024)
- [Pretrained Transformers for Text Ranking: BERT and Beyond](https://mlsanity.com/paper/2010.06467/) (2020)
- [Learning to Mine Aligned Code and Natural Language Pairs from Stack Overflow](https://mlsanity.com/paper/1805.08949/) (2018)
- [DocPrompting: Generating Code by Retrieving the Docs](https://mlsanity.com/paper/2207.05987/) (2022)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Evaluating Retrieval Quality in Retrieval-Augmented Generation](https://mlsanity.com/paper/2404.13781/) (2024)
- [Blended RAG: Improving RAG (Retriever-Augmented Generation) Accuracy with Semantic Search and Hybrid Query-Based Retrievers](https://mlsanity.com/paper/2404.07220/) (2024)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [How Many Demonstrations Do You Need for In-context Learning?](https://mlsanity.com/paper/2303.08119/) (2023)
- [What Makes Good In-context Demonstrations for Code Intelligence Tasks with LLMs?](https://mlsanity.com/paper/2304.07575/) (2023)
- [On Learning Meaningful Assert Statements for Unit Test Cases](https://mlsanity.com/paper/2002.05800/) (2020)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [The Chronicles of RAG: The Retriever, the Chunk and the Generator](https://mlsanity.com/paper/2401.07883/) (2024)

## Built on by (most cited first, 2 of 2)

- [NasZip: Software and Hardware Co-Design to Accelerate Approximate Nearest Neighbor Search with DIMM-Based Near-Data Processing](https://mlsanity.com/paper/2605.21952/) (2026)
- [Retrieval-Oriented Code Representations in Agentic Bug Localization](https://mlsanity.com/paper/2607.11046/) (2026)

## Abstract (arXiv)

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.