Reverse-Reachable Context Selection for Code Models Across Languages

When a code-writing language model has to finish a line that depends on a class defined in another file, something must decide which pieces of the repository go into its limited prompt. Today that choice is made by keyword search, by a fixed "neighbors within k steps" rule on a parser-built graph, or by a learned classifier tuned to one language. We propose treating the choice as an influence-maximization problem: pick the small set of code chunks that "reaches" the completion site most, in the same sense that viral-marketing work picks the seed users whose messages spread furthest. The tool that makes this tractable is the reverse reachable (RR) set, a random set of nodes found by walking backward from a target over randomly kept edges. RR sets turn spread estimation into a coverage problem that a greedy algorithm solves with a provable near-optimality guarantee. The dependency graph we walk is built from identifier tokens alone, with no language-specific parser. The same pipeline should therefore run on Python, Java, TypeScript and C# without being rebuilt.

The opportunity is that three facts sit in separate literatures. Greedy selection is provably good when the objective has diminishing returns. Backward slicing in code is structurally the same operation as RR-set sampling on a reversed graph. Structural code tools lose portability because they depend on parsers. Combining them gives a context selector whose objective is explicit, whose redundancy handling is principled, and whose only per-language component is a list of roughly ten definition keywords. The guarantee holds only for a stand-in objective. A second contribution is therefore to measure how far real completion quality departs from diminishing returns, which tells us when the guarantee means anything.

Core Claim

Cross-file context selection for a fixed token budget can be cast as maximizing the expected number of backward random walks from the completion site that the selected chunks intercept, on a parser-free "use → candidate definition" graph. This objective is monotone and submodular because it is a coverage function over sampled RR sets. Greedy selection therefore achieves a $(1-1/e-\epsilon)$ fraction of the best possible surrogate value under a cardinality budget, in the spirit of Maximizing Social Influence in Nearly Optimal Time, which converts influence estimation into maximum coverage over sampled RR sets. Under a token (knapsack) budget, a cost-scaled greedy with a best-single-item check keeps a constant-factor guarantee.

We claim three things. First, this selector beats plain lexical retrieval and heuristic graph expansion on cross-file completion at matched budgets. Second, it does so with hyperparameters tuned on one language and frozen for the others. Third, the gain comes specifically from marginal-gain selection over multi-hop backward reachability. Similarity diversity alone does not produce it, and neither does reachability ranking alone.

Relation to Prior Work

The closest work is IDEAL. It builds a k-nearest-neighbor graph over sentence embeddings and runs forward Independent Cascade diffusion (each newly activated node gets one chance to activate each neighbor). It then greedily picks a query-independent set of examples to annotate for in-context learning, with a $(1-1/e)$ bound. We reuse its central move: diffusion coverage as a submodular stand-in for prompt utility, which IDEAL shows correlates with downstream accuracy. Everything else differs. Our selection is per query, made backward from a specific completion site. Our graph is directed from uses to likely definitions rather than built from symmetric embedding similarity. Our ground set is code chunks bundled with their lexical prerequisites rather than isolated sentences.

Repository-level selectors motivate the problem but do not optimize an objective.

  • RepoGraph builds a line-level graph with tree-sitter and returns a fixed k-hop neighborhood of the target. It was tuned for Python.
  • Repoformer learns when to retrieve, and reports that retrieved snippets fail to help or actively hurt in up to 80% of queries. That is direct evidence that redundant or irrelevant context is costly.
  • RLPG classifies among 63 Java-specific prompt proposals.
  • GMLLM extracts subgraphs with a supervised graph-network explainer on Python.

None of these scores a set for its joint coverage. All except plain lexical retrieval carry language-specific machinery. We replace both the heuristic and the parser.

Two papers on portability constrain the design.

  • The Code Transformer shows that random-walk structure (Personalized PageRank) transfers across five languages, while raw token sequences did not transfer. This warns us that a purely lexical graph may be too weak, so we include a parser-based graph as an ablation.
  • MOAD infers probabilistic dependencies without parsers by deleting statements and running tests. It shows that language-agnostic dependency estimates can approach a static tool's precision, but it needs runnable tests, which we deliberately avoid.

The main threat to the method's premise comes from A Dense Subset Index for Collective Query Coverage. It stresses that retrieved items often must "collaborate". In code, a call may be useless without both the import and the definition, which is a complementarity that breaks diminishing returns. We take this head on, through bundling and through direct measurement.

Research Program

Graph construction. We split each repository into chunks (functions, or windows of about 20 lines). We extract identifier tokens with one regular expression shared across languages. A chunk is a candidate definer of identifier $x$ if $x$ occurs within a few tokens after a per-language definition keyword such as def, class, function, interface or struct. These keyword lists are the only language-specific artifact. For a chunk $u$ that uses $x$ and $m_x$ chunks that may define it, we add edges $u \to v$ with keep-probability

$$p_{u,v} = \min\Big(1,\ \sum_{x \in \mathrm{use}(u)\cap \mathrm{def}(v)} \frac{\mathrm{idf}(x)}{m_x \, Z_u}\Big),$$

where $\mathrm{idf}(x)$ is the inverse document frequency of $x$ across chunks and $Z_u$ normalizes $u$'s outgoing mass so that weights stay bounded. Rare, uniquely defined identifiers thus carry strong edges; common names like get carry weak ones.

Selection. For a completion site $q$, we sample $R$ walks. Each walk starts at $q$'s chunk, keeps each outgoing use→definition edge independently with probability $p_{u,v}$, and records every reached chunk as one RR set. A candidate set $S$ is scored by $\hat f(S)$, the fraction of RR sets it intersects. Standard concentration arguments for RR sampling give the $\epsilon$ term.

The ground set is not individual chunks but bundles. A bundle is a chunk plus the highest-probability definer of each identifier it needs that is not already in the prompt. Bundling is how we absorb the AND-style complementarity: an import and its definition enter together. Greedy then adds the bundle with the best marginal coverage per token until the budget is spent. When cost and coverage must be traded off explicitly, we compute the full budget–coverage curve using the approach of Computing Approximate Pareto Frontiers for Submodular Utility and Cost Tradeoffs.

Measuring diminishing returns. The guarantee is about $\hat f$, not about completion quality. On small candidate pools of about 12 bundles per query, we compute the true utility $g(S)$, defined as the model's log-probability of the gold completion given context $S$, for many subsets. From these values we estimate a submodularity ratio $\gamma$: the worst-case ratio of the sum of single-item gains to the joint gain. When $\gamma$ is near 1, greedy on $g$ itself is nearly safe. We estimate $\gamma$ separately with chunk-level and bundle-level ground sets.

If bundling raises $\gamma$ substantially, the bundling design is justified empirically. If $\gamma$ stays low, that is a substantive negative finding about code context. It would point toward the almost-submodular treatments in Influence Maximization with ε-Almost Submodular Threshold Functions.

Baselines

The naive reference point is in-file context only, with the same completion model and the same left/right file window. CrossCodeEval reports StarCoder at 8.8% exact match on Python in this setting, and we use StarCoder so that this number anchors our runs. Random cross-file chunks up to the budget form a second floor. RepoBench reports that random context already beats in-file context, so a method must clear random to show that selection matters.

The strongest language-agnostic competitor is BM25 retrieval of top chunks against the lines around the completion site, filled to the same token budget. It is the strongest because CrossCodeEval found keyword matching outperformed dense neural retrievers for cross-file completion, and it needs no parser. CrossCodeEval reports that adding retrieved context roughly doubles to quadruples exact match. However, no reported per-model BM25 exact-match number was found on Lacuna for CrossCodeEval, so we rerun it ourselves on identical chunks. The same applies to retrieval: we take InstructOR's reported RepoBench-R Easy Python result (above 28% acc@1, above 62% acc@3) from RepoBench as the bar to clear there.

The strongest structural competitor is RepoGraph's k-hop expansion, reimplemented with tree-sitter grammars for all four languages and truncated to the budget by hop distance. RepoGraph reports 29.67% resolved on SWE-bench Lite inside Agentless, but no reported RepoGraph number on CrossCodeEval exact match was found on Lacuna in the file. We therefore rerun it. Note that giving it multilingual grammars is a generous porting effort beyond what the original paper did.

Three ablations isolate the key ingredients.

  • Diversity without the graph: greedy facility-location coverage over BM25 similarities, a submodular objective with no reachability. If it matches our method, the dependency graph adds nothing.
  • Reachability without greedy: rank chunks by how often they appear in RR sets and take the top ones. This removes marginal-gain redundancy control, testing the effect Kempe et al. report on co-authorship graphs, where greedy beat high-degree selection by 18% in spread (Maximizing the spread of influence through a social network).
  • Parser graph instead of lexical graph: our selector run on the tree-sitter graph. This prices the portability we gain.

All methods share the following, so that differences come from selection alone:

  • the same chunking;
  • the same completion model;
  • the same token budgets;
  • a tuning budget of equal size spent only on the Python development split.

Why not just…?

Why not just use BM25, which is already parser-free and strong? BM25 scores chunks one at a time. It cannot reach a definition two hops away whose name never appears near the completion site, and it fills the budget with near-duplicates of the best match. RLPG found BM25 inferior to structure-aware proposals on Java. Even so, BM25 is a real threat because exact identifiers are such a strong signal. The decisive comparison is stratified by hop distance between the completion site and its gold definition, which we compute from the parser graph used only for analysis. We expect parity at one hop and gains at two or more. If the gains do not appear there, the method has no reason to exist.

Why not just add diversity to BM25 (maximal marginal relevance or facility location) and keep the guarantee without any graph? This is the most dangerous alternative, because it delivers the greedy guarantee and redundancy control at almost no cost. It is our first ablation. If it ties our method across budgets and languages, we will report that the useful ingredient is diminishing-returns selection itself, not influence structure, and the influence framing should be dropped.

Why not just use tree-sitter, which already supports many languages? A grammar gives syntax, not cross-file resolution rules. RepoGraph's Python-specific filtering and scoping logic is exactly the part that must be rewritten for each language. The parser-graph ablation measures what our keyword-list graph loses. A small loss, with zero per-language engineering beyond about ten keywords, is the portability claim. A large loss would mean the Code Transformer's warning applies and lexical structure is too coarse.

Why not just put the whole repository in a long context window? GMLLM reports attention drift on whole projects alongside a reduction to about 640 tokens without losing recall, and Repoformer reports that unnecessary context hurts. We nonetheless include a long-context run at the largest affordable budget as an upper reference. We report where our selector at 2,048 tokens sits relative to it.

Proposed Experiments

Main benchmark. The primary test is CrossCodeEval in all four languages (Python, Java, TypeScript, C#), reporting exact match and edit similarity at budgets of 512, 1,024, 2,048 and 4,096 tokens.

Portability test. The leave-language-out protocol is central. Edge-weight smoothing, chunk size and the number of RR samples $R$ are tuned on Python alone and frozen for the other three languages. The portability claim holds if our margin over BM25 on Java, TypeScript and C# stays within half of the Python margin, with no retuning.

Retrieval quality. We use RepoBench-R (Python and Java, Cross-File-First and Cross-File-Random settings) to measure whether the gold snippet lands in the selected set, reporting acc@1 and acc@3 against InstructOR's reported figures.

Diagnostic for the guarantee. On a 300-query subsample we estimate the submodularity ratio $\gamma$ at chunk level and bundle level. We correlate the surrogate $\hat f(S)$ with gold log-probability across sampled subsets, as IDEAL did for in-context learning accuracy.

Decisive checks. The proposal succeeds if three things hold together:

  • our selector beats BM25 and the facility-location ablation at two or more hops, with confidence intervals from a paired bootstrap over queries;
  • the margin survives the language switch;
  • bundling measurably raises $\gamma$.

It fails informatively if the facility-location ablation ties us, or if $\gamma$ stays low under bundling. Either outcome would say which part of the influence-maximization view actually carries over to code.