PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphCoder: Enhancing Repository-Level Code Completion via Code Context Graph-based Retrieval and Language Model

Wei Liu, Ailun Yu, Daoguang Zan, Bo Shen, Wei Zhang, Haiyan Zhao, Zhi Jin, Qianxiang Wang

arXiv:2406.07003v2cs.SE

TL;DR

Repository-level code completion is challenged by code LLMs’ lack of repository-specific knowledge, and adding entire repositories can introduce irrelevant context. GraphCoder retrieves repository snippets using code context graphs and a coarse-to-fine process. It reports higher exact-match results than RAG baselines on average, with less retrieval time and database storage space.

  • Problem

    Code LLMs lack repository-specific knowledge such as code style and intra-repository API usage, while concatenating whole repositories can add irrelevant information that degrades completion.

    Source: §1 · pp. 1–2

  • Method

    GraphCoder uses statement-level code context graphs with control-flow and dependence edges, then performs coarse-to-fine retrieval of repository snippets.

    Source: §1 · p. 2, §3.1 · p. 3, §3.2 · p. 3

  • Results

    +6.06 in code exact match and +6.23 in identifier exact match on average versus RAG baselines, with less retrieval time and database storage space.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GraphCoder combines structural context with retrieval to locate repository snippets for code completion.

    Source: §1 · p. 2

    The evaluation focuses on open-source Python and Java repositories, so the reported results are limited to that scope.

    Source: §7 · p. 11

Abstract

from arXiv · show

The performance of repository-level code completion depends upon the effective leverage of both general and repository-specific knowledge. Despite the impressive capability of code LLMs in general code completion tasks, they often exhibit less satisfactory performance on repository-level completion due to the lack of repository-specific knowledge in these LLMs. To address this problem, we propose GraphCoder, a retrieval-augmented code completion framework that leverages LLMs' general code knowledge and the repository-specific knowledge via a graph-based retrieval-generation process. In particular, GraphCoder captures the context of completion target more accurately through code context graph (CCG) that consists of control-flow, data- and control-dependence between code statements, a more structured way to capture the completion target context than the sequence-based context used in existing retrieval-augmented approaches; based on CCG, GraphCoder further employs a coarse-to-fine retrieval process to locate context-similar code snippets with the completion target from the current repository. Experimental results demonstrate both the effectiveness and efficiency of GraphCoder: Compared to baseline retrieval-augmented methods, GraphCoder achieves higher exact match (EM) on average, with increases of +6.06 in code match and +6.23 in identifier match, while using less time and space.

1 INTRODUCTION

Repository-level completion is difficult because code LLMs lack repository-specific knowledge, while supplying entire repositories can add irrelevant context. GraphCoder uses statement-level code context graphs and coarse-to-fine retrieval to locate relevant snippets.

1 INTRODUCTION

  • Code LLMs perform less satisfactorily on repository-level completion because they lack repository-specific knowledge, including code style and intra-repository API usage.This gap is especially relevant to newly created, personal, or confidential repositories.Source: §1 · p. 1
  • Concatenating all repository files into a prompt can introduce irrelevant information that confuses LLMs and degrades completion performance.Source: §1 · p. 2
  • +6.06 in code exact match and +6.23 in identifier exact match on average versus RAG baselines, with less retrieval time and database storage space.Experiments covered 8,000 real-world repository-level completion tasks.Source: §1 · p. 2
  • GraphCoder represents completion context with a statement-level multi-graph whose edges encode control flow and data and control dependence.This structured representation is intended to capture relevant statements more accurately than sequence-based context.Source: §1 · p. 2
  • GraphCoder retrieves snippets through coarse-to-fine matching that combines structural and lexical context and weights context by dependence distance.Source: §1 · p. 2

2 RELATED WORK

Prior repository-level completion methods inject repository knowledge through fine-tuning, token-frequency adjustment, or retrieval-augmented generation. Retrieval approaches vary in how they represent context and generate outputs, with sequence-based methods overlooking code structure and per-token retrieval increasing cost.

2 RELATED WORK

  • Fine-tuning methods use in-file and cross-file context, but face limitations with closed-source LLMs and repositories that change during development.Source: §2 · p. 2
  • Token-frequency post-processing adjusts next-token probabilities using repository frequencies, but is sensitive to manually selected interpolation weights.Source: §2 · p. 2
  • Most retrieval methods use the last few lines as sequence context, while method-level graph approaches still omit statement-level structure relevant to completion semantics.CoCoMIC [6] and RepoHyper [28] use method-level graphs.Source: §2 · p. 2
  • Per-token retrieval obtains snippets for each generated token, increasing retrieval time and limiting compatibility with closed-source LLMs; per-output retrieval uses one snippet set for the whole sequence.The per-output mode is described as improving retrieval efficiency and facilitating closed-source compatibility [24] [28] [44].Source: §2 · pp. 2–3

3 BASIC CONCEPTS

GraphCoder uses code context graphs and bounded graph slices to represent a completion target’s relevant code context. The graph combines control-flow and dependence relations, while slicing selects a local subgraph around a statement of interest.

3 BASIC CONCEPTS

  • A code context graph is a structured representation of code statements and their relationships, and a CCG slice extracts a subgraph around a statement of interest.Source: §3 · p. 3

3.1 Code Context Graph

  • A code context graph superimposes control-flow, control-dependence, and data-dependence graphs, with vertices representing statements or predicates.Control-flow edges represent execution transitions; control-dependence edges capture effects on execution, and data-dependence edges connect definitions to uses.Source: §3.1 · p. 3

3.2 CCG Slicing

  • CCG slicing extracts an induced subgraph using control-flow neighbors within a hop limit and their data- and control-dependence in-neighbors, subject to a maximum vertex count.The resulting vertex set combines the selected control-flow, control-dependence, and data-dependence vertices.Source: §3.2 · p. 3
  • The illustrated one-hop slice includes the statement of interest, its control- and data-dependence context, and dependencies of its control-flow in-neighbor.Source: §3.2 · p. 3

4 GRAPHCODER

GraphCoder represents statement context with CCG slices, retrieves repository snippets through coarse-to-fine stages, and supplies retrieved code alongside the completion context to an LLM. [p43]

4.1 Overview

  • The workflow builds a statement-slice database, retrieves similar snippets through coarse-to-fine search, and sends them with the completion context to an LLM.The framework has database construction, code retrieval, and code generation steps.Source: §4.1 · p. 4

4.2 Database Construction

  • For each repository statement, the database key is its CCG slice and the value is its centered forward and backward code lines.The stored lines surround the statement represented by the key.Source: §4.2 · p. 4

4.3 Code Retrieval

  • GraphCoder first retrieves candidates by sequence-slice similarity, then reranks them using decay-with-distance subgraph edit distance.The retrieval step comprises query CCG construction, coarse-grained retrieval, and fine-grained reranking.Source: §4.3 · pp. 4–5
  • To form the query CCG, GraphCoder adds a dummy predicted statement after the context’s last statement and slices from that target.The construction assumes a control-flow edge from the last context statement to the statement being predicted.Source: §4.3 · p. 4

4.4 Code Generation

  • The generation prompt places retrieved snippets in ascending similarity order with their source paths, followed by the completion context for the LLM.The retrieved snippets and context are concatenated into the final prompt.Source: §4.4 · p. 5

5 EXPERIMENTAL SETUP

The experimental setup evaluates repository-level completion across languages, task types, LLMs, and retrieval baselines, using an updated dataset and code- and identifier-matching metrics.

5 EXPERIMENTAL SETUP

  • The evaluation asks about effectiveness, generalizability across models and repositories, component ablations, and resource consumption.These are the study’s four research questions.Source: §5 · p. 5

5.1 An Updated Dataset: RepoEval-Updated

  • RepoEval-Updated refreshes RepoEval to reduce leakage from older training data and adds open-source Java repositories alongside Python repositories.The update removes repositories created before March 31, 2022, and adds repositories created after January 1, 2023.Source: §5.1 · p. 5
  • The benchmark distinguishes line-level tasks from API-level tasks, the latter requiring the removed line to contain an invocation of an intra-repository API.Tasks are sampled at 2,000 per task level and programming language, for 8,000 total.Source: §5.1 · pp. 5–6

5.2 Evaluation Metrics

  • Code match uses exact match and edit similarity, while identifier match uses exact match and F1 over extracted predicted and reference identifiers.Exact match is binary for code equality; identifier scores compare the extracted identifiers directly.Source: §5.2 · p. 6

5.3 Methods for Comparison

  • The comparison methods are no RAG, vanilla sliding-window RAG, shifted-window RAG, and iterative RepoCoder [44].Shifted RAG is also mentioned in ReAcc [24].Source: §5.3 · p. 6

5.4 Implementation Details

  • Retrieval comparisons use Jaccard similarity over bag-of-words tokens, 20-line windows with stride 1, and GraphCoder settings of 5 maximum hops and 20 maximum statements.The decay-with-distance factor is 0.1; CCG construction uses tree-sitter for ASTs and analyzes control flow and dependencies.Source: §5.4.1 · p. 6

5.4.1 Code Retrieval.

  • The experiments select five eligible LLMs and divide each model’s context window equally between retrieved snippets and completion context.The models include GPT-3.5-Turbo-Instruct, StarCoder 15B, and CodeGen2 models; Python and Java are the proof-of-concept languages.Source: §5.4.2 · p. 6

5.4.2 Code Generation.

  • Reported values are percentages, and RepoCoder results are taken after three iterations.Experiments use Python and Java as proof-of-concept languages for the language-agnostic CCG approach.Source: §5.4.2 · pp. 6–7

6 EXPERIMENTAL RESULTS

GraphCoder outperforms baseline retrieval-augmented methods on repository-level completion, with qualitative analyses highlighting the value of structural alignment and the risk of misleading retrieved snippets.

6.1.1 Quantitative analysis of effectiveness.

  • GraphCoder outperforms the other baselines across LLMs on API- and line-level tasks, with RAG benefits more evident on harder API-level tasks.Shifted RAG’s shifting approach does not necessarily improve No RAG performance, and shifting snippets without regard to content may retrieve irrelevant code.Source: §6.1.1 · p. 7

6.1.2 Qualitative analysis of effectiveness.

  • GraphCoder uniquely completes the most tasks among the compared methods on Java and API-level Python, with its structural alignment locating deeply matched snippets.The Figure 5 example shows a GraphCoder-retrieved snippet better aligned with the completion context than RepoCoder’s, providing more relevant information for generating the next statement.Source: §6.1.2 · p. 7, Figure 4 · p. 7, Figure 5 · p. 8
  • Very similar retrieved contexts can mislead LLMs into copying a continuation without adapting it to small differences in the current context.Source: §6.1.2 · p. 8

6.1 RQ1: Effectiveness

  • On 8,000 tasks, GraphCoder’s average EM gains over baseline RAG methods are +6.06 for code match and +6.23 for identifier match.GraphCoder also exceeds vanilla RAG in code match by +4.58 on API-level and +7.90 on line-level tasks, on average.Source: §6.1.1 · p. 7, §6.1.2 · p. 8

6.2 RQ2: Generalizability

GraphCoder’s performance advantage persists across the examined model sizes and repositories, and is larger in repositories with less code duplication.

6.2 RQ2: Generalizability

  • Across CodeGen2 sizes, GraphCoder consistently performs best among the four RAG methods, while No RAG does not follow a scaling law on repository-level tasks.The results average line- and API-level tasks in Python and Java; performance improvement from 7B to 16B is limited, and the authors suggest 7B as a cost-effective balance.Source: §6.2.1 · p. 8, Figure 6 · p. 8

6.2.2 Generalizability across repositories of various duplication ra-

  • GraphCoder outperforms other RAG methods in 15 of 20 repositories, with stronger gains when code duplication is below 40%.Against the best baseline, it leads by 9.13% below 40% duplication and by 5.25% above 40%.Source: Figure 7 · p. 8, §6.2.2 · p. 9
  • The reported results indicate greater GraphCoder effectiveness in repositories with lower repetition.Source: §6.2.2 · p. 9

6.3 RQ3: Ablation Study

Ablations identify the control-flow graph and coarse retrieval as especially important, while performance remains robust to the tested dependence-distance shrink settings.

6.3.1 Ablation study of components in CCG.

  • Removing CFG causes the largest component-ablation decline: average relative reductions of 19.82% in code match EM and 15.64% in identifier match EM.CFG provides the basis for integrating CDG and DDG through traversal; removing it leaves a one-hop local subgraph, with the largest drop on API-level Java tasks.Source: §6.3.1 · p. 9, Table 3 · p. 9

6.3.2 Ablation study for coarse-to-fine steps.

  • GraphCoder outperforms variants using only coarse or only fine retrieval, and coarse retrieval contributes more than fine retrieval.Compared with the only-fine variant, the only-coarse variant improves code match EM, ES, identifier match EM, and F1 by 2.34, 1.15, 2.41, and 1.08, respectively.Source: §6.3.2 · p. 9, Figure 8 · p. 9

6.3.3 Hyper-parameter sensitivity.

  • Performance is robust to changes in γ from 0.1 to 0.9, although the best γ depends on task characteristics.γ is the dependence-distance shrink factor in fine-grained retrieval; lower values emphasize local structure.Source: §6.3.3 · p. 9, Figure 9 · p. 10

6.4 RQ4: Cost

GraphCoder reduces retrieval time and database storage relative to sliding-window methods without consuming more tokens, according to the reported comparisons.

6.4.1 Time efficiency of retrieval.

  • GraphCoder is more time-efficient than sliding-window methods, and its fine-grained step accounts for only 3.06% of total retrieval time.Its retrieval time also increases more slowly with repository code-line count.Source: §6.4.1 · p. 10, Table 4 · p. 10, Figure 10 · p. 10

6.4.2 Database storage.

  • GraphCoder’s statement-level database has 79.5% fewer entries than sliding-window methods and remains smaller as repository line counts grow.Sliding-window database size increases linearly with repository lines, while GraphCoder’s database remains smaller despite storing graph structures.Source: §6.4.2 · p. 10, Table 4 · p. 10, Figure 10 · p. 10

6.4.3 Number of tokens.

  • GraphCoder uses fewer input/output tokens on average than the other three RAG methods, though the difference is not significant.The methods use the same prompt template and organization for retrieved results.Source: §6.4.3 · p. 10, Table 5 · p. 10

6.4 RQ4: Cost

  • GraphCoder does not consume more tokens than sliding-window RAG methods, while being more efficient in time and space through its statement-level database.Source: §6.4.3 · p. 10

7 THREATS TO VALIDITY

The authors identify internal-validity risks in baseline implementation and model selection, and limit external-validity claims to open-source Python and Java repositories. Low code duplication may also reduce GraphCoder’s retrieval recall.

Internal validity

  • Internal validity is constrained by baseline implementations and the selection of code LLMs used in experiments.RepoCoder’s implementation was used for its own baseline; Vanilla RAG and Shifted RAG were implemented by the authors using RepoCoder’s implementation to mitigate potential bugs.Source: §7 · pp. 10–11

External validity

  • External-validity evidence covers open-source Python and Java repositories; low duplication in downstream repositories may reduce retrieval recall.The authors describe migration to other languages using tree-sitter ASTs, while identifying reduced retrieval recall as a potential boundary for low-duplication repositories.Source: §7 · p. 11

8 CONCLUSION

GraphCoder uses a code context graph and coarse-to-fine retrieval for repository-level completion. Across the evaluated tasks, it improves completion accuracy with less retrieval time and space overhead.

8 CONCLUSION

  • Across 8,000 tasks from 20 repositories using five LLMs, GraphCoder improves code completion accuracy with less retrieval time and space overhead.The conclusion describes the accuracy gain as more exactly matched code for generation.Source: §8 · p. 11
  • GraphCoder represents completion context as a statement-level multi-graph with control-flow, data-dependence, and control-dependence edges.It retrieves by filtering candidate snippets and reranking them with a structural-similarity measure that decays with dependence distance.Source: §8 · p. 11
  • After retrieving snippets, GraphCoder uses pretrained language models to generate the next lines of code.The snippets are retrieved from the current repository based on the completion target’s context.Source: §8 · p. 11
Loading 2406.07003v2…