Learning Which Tiny Code Fragments to Retrieve, as a Set

Code assistants retrieve context from the rest of a repository before completing code, and they almost always retrieve whole functions, classes, or blank-line-delimited chunks. Much of the useful reuse in real code happens at a smaller scale: micro-clones, repeated fragments of fewer than ten lines, such as a particular database-access pattern, a logging call, or a guard around an API. These fragments are exactly what current tools skip. Clone detectors drop methods under 50 tokens, and retrievers bury the fragments inside larger chunks. Shrinking the retrieval unit to single statements and blocks makes a different problem worse, though. At that size the index fills with near-identical fragments and generic idioms, like a null check or a loop header, that look similar to everything. A retriever that ranks fragments one at a time by similarity will spend its context budget on idioms, and on five copies of the same useful line.

This note proposes training a fragment retriever that chooses a set of micro-fragments, rewarded by how much the whole set helps a frozen code model predict the true continuation. Training uses Group Relative Policy Optimization (GRPO), a reinforcement learning method that scores each sampled action against the other actions sampled for the same input, so no separate value network is needed. The design keeps the usual costs of reinforcement learning low. The policy is a scoring encoder, so sampling a set is a draw from a softmax rather than token-by-token generation. The reward is a single teacher-forced likelihood pass of the frozen generator, with no decoding and no test execution. The central empirical claim is falsifiable: learning at the level of sets beats scoring fragments independently, and the advantage grows as the retrieval unit shrinks toward micro-clone size. If the claim fails, the honest conclusion is that micro-clone retrieval needs no reinforcement learning at all.

Core Claim

The difficulty of retrieval at micro-granularity is mostly combinatorial rather than representational. Two sources of evidence motivate this. The adverse effects of code duplication in machine learning models of code shows that duplication at the scale of a few lines is pervasive enough to inflate reported accuracy, with JavaScript identifier prediction dropping 51.4% after deduplication. The same paper leaves open how to tell a genuine duplicate apart from a standard idiom. Mining the Relationship between Object-Relational Mapping Performance Anti-patterns and Code Clones finds over 90% of database-access performance problems inside cloned fragments. Together these say that micro-fragments carry real signal but arrive in redundant families mixed with idioms.

A retriever that scores each fragment independently cannot see redundancy. A reward on the whole set can see it, because a second copy of an already-included fragment adds nothing to the generator's likelihood of the target. The prediction follows. At function granularity, where candidates are rarely redundant, set-level training should roughly tie independent scoring. At statement and block granularity, set-level training should pull ahead, and the gap should widen as the number of retrieved fragments $k$ grows.

Research Program

We index each repository into AST-derived spans: single statements, control-flow blocks, and contiguous windows of one to ten lines. An AST (abstract syntax tree) is the parse tree of the code, so these spans follow the code's syntactic structure. For a completion point with left context $x$ and true continuation $y$, a first stage built from BM25 and a dense retriever proposes $M\approx 200$ candidate spans. The candidate pool also includes an empty "stop" option, following the stop signal of RLCoder.

The policy is a bi-encoder initialized from a code encoder pretrained with MGS3-style multi-granularity contrastive learning. It assigns each candidate a score $s_\theta(x, c)$. A set $S$ of up to $k$ spans is drawn by sequential sampling without replacement, known as the Plackett–Luce model. Under this model, the log-probability of the set is the sum over steps of the log-softmax of the chosen span among the spans still remaining.

The reward is the likelihood gain the set provides to a frozen code generator $p$:

$$r(S) = \log p(y \mid S, x) - \log p(y \mid x).$$

We weight tokens toward identifiers and API calls, as in RLCoder's weighted perplexity. The empty set therefore earns exactly zero. Idioms that tell the generator nothing new earn about zero, and redundant copies earn nothing beyond the first copy. All retrieved sets share a fixed token budget, so micro-spans cannot win simply by fitting more text into the prompt.

For each $x$ we draw a group of $G$ sets and compute the GRPO advantage $A_i = (r_i - \bar r)/(\sigma_r + \epsilon)$, where $\bar r$ and $\sigma_r$ are the group's mean and standard deviation. We then apply a clipped policy-gradient update with a KL penalty toward the initial encoder. The reward is continuous, so the zero-variance groups that stall GRPO on binary rewards should be rare. We will log how often they occur.

Each training step costs $G$ parallel teacher-forced forward passes of the generator plus one encoder pass. There is no autoregressive rollout, no value network, and no sandbox. We will measure this cost directly against the three overhead sources the literature identifies: generation in the loop, hosting several models at once, and execution latency.

This design differs from its closest relatives in specific ways. RLCoder supplies the likelihood-based reward and the stop candidate. As the file describes it, though, RLCoder trains with PPO over mini-block chunks aggregated to a token limit, ranks candidates individually, and never looks below the chunk. GRAPE and Less Is More (CORE-RAG) use GRPO for image-retrieval query rewriting and for compressing natural-language RAG context. Both policies generate text autoregressively, and neither selects structured code spans. GRAPE also warns that rewarding raw similarity scores gets exploited by generic tokens; our likelihood-gain reward is designed to deny that exploit to idiomatic code. QueCos rewrites queries against method-level code search using a REINFORCE-style policy gradient. CoRet retrieves function and class chunks with call-graph context but has no utility reward. Oreo constrains our design: its filters discard fragments under 50 tokens because token statistics are too sparse there, which is why we use the generator's likelihood rather than token distributions to judge tiny spans.

Baselines

The naive reference points are completion with no retrieval, and BM25 over RLCoder-style chunks. CROSSCODEEVAL reports that in-file-only StarCoder reaches 8.8% exact match on Python and that BM25 often rivals dense retrievers. For that reason we also run BM25 over our micro-span index. This separates the effect of granularity alone from the effect of learning. All baselines use the same frozen generator, the same repositories, and the same token budget for retrieved context.

The strongest existing learned method is an RLCoder-style retriever, reimplemented on both its native chunks and our micro-spans with the same reward and encoder initialization. The file reports that it achieves a 12.2% improvement in exact match over RepoCoder on CrossCodeEval Python. That figure is relative; the file gives no absolute exact-match value for RLCoder, and we will report both from our runs. The file also has no reported result on Lacuna for RepoEval or GitHubEval.

We add an MGS3-style contrastive retriever that uses MaxSim, which scores a query against its single best-matching sub-span. Its reference number is 38.9 MRR on the block-level XLCoST-BL benchmark with CodeBERT, from MGS3.

The most important competitor is single-span gain distillation. We compute $r(\{c\})$ for every one of the $M$ candidates offline and train the encoder with a listwise KL loss toward the softmax of those gains. This uses the same reward information with no reinforcement learning. It receives an equal compute budget, counted in generator forward passes and matched against GRPO's $G$ passes per example.

Two ablations isolate what matters. GRPO with $k=1$ should collapse to the level of distillation. GRPO at function granularity should likewise show a small gap if the claim is right. Beating the baselines means a statistically reliable improvement in exact match and edit similarity over both RLCoder-on-micro-spans and gain distillation at $k\ge 3$ and statement or block granularity, while training wall-clock stays within a small multiple of distillation.

Why not just…?

Why not just run BM25 over micro-spans? It costs nothing to train and may catch literal micro-clones well. It has no notion of idioms or redundancy, however, so we expect it to fill the budget with boilerplate and near-duplicate copies. We will measure this directly as the idiom rate and the pairwise similarity among the spans selected for each query. If BM25 over micro-spans matches the learned retrievers, then granularity is the whole story, and that is a publishable negative result.

Why not just use a contrastive fine-grained encoder like MGS3 or CCT-Code? CCT-Code reaches 96.73% MAP on POJ-104 with hard-negative contrastive training, so similarity-based encoders are strong. Their objective, though, rewards resemblance rather than usefulness. The idiom-versus-duplicate ambiguity that Allamanis flags is exactly the case where resemblance and usefulness diverge. We use MGS3 as our initialization, so any gain over it is attributable to the reward.

Why not just distill single-span likelihood gains without reinforcement learning? This is the real threat. For $k=1$, the two approaches should be nearly equivalent, because the reward is cheap and candidate-local. Reinforcement learning earns its place only if interactions within a set matter. The granularity-by-$k$ experiment below is designed to settle this. We commit to reporting it either way, and if distillation ties at every granularity we will recommend it over our method.

Why not just use PPO as RLCoder does, or SFT on synthetic query–fragment pairs from a teacher model? PPO adds a value network, which competes for memory with the long repository contexts. We will report memory use and throughput for both. Synthetic SFT pairs give no signal about which fragments help the generator. DeepRetrieval and CORE-RAG both found SFT insufficient compared with reward-driven training, but in text retrieval, so we include SFT at matched data scale.

Proposed Experiments

The main evaluation is CrossCodeEval across Python, Java, TypeScript, and C#, plus RepoEval. We train on a disjoint set of repositories, split by repository. Following Allamanis, we deduplicate at the fragment level between training and test repositories, so that gains cannot come from memorized cross-set copies.

The decisive experiment is a grid over three granularities (function, block, and statement or window) and $k \in \{1, 3, 5, 8\}$ under a fixed token budget, comparing GRPO against gain distillation. The claim survives only if the GRPO advantage is near zero at $k=1$ or at function level, and grows at micro level with larger $k$.

A second check is diagnostic. On held-out queries, we measure the fraction of selected spans that are idioms, defined as spans whose normalized form appears in many unrelated repositories. We also measure within-set redundancy, and how often the model chooses the stop option when retrieval would hurt.

A third check covers transfer and cost. We use the trained encoder zero-shot on XLCoST-BL to test whether usefulness-driven training harms similarity-based code search. We also report GPU-hours, peak memory, and the share of time spent computing rewards, against both the PPO variant and a variant whose reward requires decoding a completion and checking exact match. The last comparison tests whether the teacher-forced reward is both cheaper and about as informative as a reward that requires generation.