TL;DR
CARET is a training-free framework that boosts repository-level code completion by scaling compute at test-time across both retrieval and generation. By routing between different retrieval contexts based on model agreement and using a "reverse-context" likelihood to verify candidates, CARET achieves a +10.8 point average improvement in Exact Match (EM) while keeping compute costs near a single-pass baseline.
What Problem Does This Paper Address?
Repository-level code completion is a high-stakes task for modern IDEs. Unlike standard completion, the "correct" next line often depends on identifiers or APIs defined in entirely different files. While Retrieval-Augmented Generation (RAG) is the standard solution, most research focuses solely on the Retrieval (R) stage—finding the best snippets to put in the prompt—and then settles for a single greedy Generation (G) pass.
The authors argue that this leaves significant performance on the table. Greedy decoding is brittle, and no single retrieval strategy works for every scenario. Furthermore, even though the "right context" (the code appearing after the cursor) is usually available in the editor, standard causal language models ignore it during generation. CARET aims to bridge this gap by using test-time scaling to optimize the entire pipeline without requiring expensive retraining or human labels.
Methods
CARET introduces a two-stage pipeline designed to be efficient enough for real-time use in an IDE:
- Retrieval & Routing (R): Instead of committing to one retrieval strategy, CARET uses Agreement-Gated Cascade Routing. It assembles two different context types: a "structural" fused context (dataflow and call sites) and a "lexical" context (BM25 sliding window). It samples $N$ candidates from the primary context; if the model's samples show low "agreement" (i.e., they are scattered and inconsistent), it cascades to the alternative context.
- Generation & Selection (G): To keep costs down, CARET uses Cache-Aware Sampling. By caching the long retrieved prompt prefix, it can generate $N$ candidates for roughly $1.1\times$ the cost of a single greedy pass, rather than $N\times$.
- RCV Selector: To pick the winner, CARET employs Reverse-Context Verification (RCV). It uses the model to "read ahead" and calculate the likelihood of the existing code after the cursor, given a specific candidate. A correct completion should make the subsequent code more probable. This score is blended with the vote frequency to select the final output.
Datasets
The authors evaluated CARET across three major benchmarks:
- CrossCodeEval: A diverse, multilingual benchmark (Python and Java) specifically constructed to require cross-file information.
- RepoEval-Line: 1,600 tasks focused on next-line completion.
- RepoEval-API: 687 tasks focused on API-invocation completion.
The study utilized six open-source LLMs ranging from 1.1B to 7B parameters, including the DeepSeek-Coder and StarCoder families.
Key Insights and Ideas
- No Single Retriever Wins: The authors found that structural and lexical retrievers often solve disjoint sets of problems. A per-task "oracle" that could choose the better retriever would gain up to +6.0 EM over a fixed choice.
- Agreement is a Signal: The "agreement" of a model's samples (the fraction matching the most common candidate) is a highly calibrated proxy for correctness. When agreement is $>0.9$, the model is usually right; when it's $<0.2$, it's almost certainly wrong.
- The "Right Context" is a Free Verifier: In mid-file completion, the code following the cursor is a powerful, unused signal. Using the model itself to score how well a candidate fits with the following code acts as a training-free verifier.
- Compute Substitutes for Parameters: A smaller 1.3B model equipped with CARET can outperform a 6.7B model using standard greedy decoding, suggesting that a small budget spent on test-time scaling is more efficient than simply increasing model size.
Key Results
- Accuracy Boost: CARET improved Exact Match (EM) scores in all 18 model-benchmark combinations tested. On average, it outperformed greedy decoding by 10.8 points and self-consistency (majority voting) by 5.3 points.
- Efficiency: Despite sampling multiple candidates, CARET's token-level compute multiplier stays near 1.45$\times$ a single generation. This is achieved through prefix caching and "fast-path" rules that skip expensive scoring when the model is already highly confident.
- State-of-the-Art: CARET's strongest configuration (DeepSeek-Coder-6.7B) reached 47.74 EM on RepoEval-API, surpassing every existing retrieval baseline by at least 7.6 points.
Limitations and Future Work
- Granularity: CARET is optimized for line and API-level completion. The authors note that its mechanisms (like string-based agreement) do not transfer well to long function bodies, which require semantic verification (e.g., unit tests).
- Language Specifics: While the core logic is language-agnostic, the "structural" retrieval component currently relies on Python-specific dataflow extractors.
- Future Directions: The authors suggest exploring learned routing signals and extending the framework to handle broader code generation tasks beyond simple line completion.
Summary updated