diffctx: Budgeted Typed-Graph Retrieval for Diff-Aware Code Context Selection

Retrieving optimal context for Large Language Models to understand code changes is a critical challenge in automated software engineering. Current approaches rely on naive windowing or purely lexical retrieval, missing complex structural dependencies. We formulate diff-aware code context selection as budgeted utility maximization over multi-resolution fragments on a typed dependency graph. The deployed system maximizes a monotone submodular concept-coverage objective (concave saturation over per-concept relevance derived from the diff) with lazy-greedy budgeted selection and engineering heuristics; a modular cost-penalized (Boltzmann) ranking variant is available as an opt-in ablation, and we identify clean analyzable variants whose approximation guarantees are known. Two structural components ground the framework: (i) a partition matroid over multi-resolution fragments enforcing structural non-redundancy, and (ii) a pluggable relevance signal ŵ(f, ∆) instantiated via three families—bounded ego-network expansion (the deployed default), Personalized PageRank, and BM25 lexical retrieval. The framework is evaluated by file-level recall against annotated golden contexts at a fixed token budget across three multi-language software-engineering benchmarks (1500 instances total; consolidated rerun, v4-calibrated). At an 8000-token budget under bounded ego-network scoring, diffctx achieves pooled file recall 0.919 [95% CI 0.908, 0.929], with per-benchmark recall 0.998 on SWE-bench Verified, 0.942 on PolyBench-500, and 0.816 on ContextBench Verified. Decomposing recall into changed-file retention and genuine context retrieval reveals that only ContextBench Verified carries gold files beyond the input diff; on that retrieval subset (213 instances), the internal BM25 lexical mode is the strongest single signal (0.402 nontrivial recall) versus 0.352 for the deployed graph-lexical mixture and 0.244 for PPR; the signals are complementary, and a runnable score-free union of the two modes’ selections reaches 0.473 nontrivial and 0.870 headline recall at a measured deduplicated cost of 6.1k mean tokens — within the same budget for 91.5% of instances — making calibrated in-scorer combination the highest-leverage open item. A within-framework scoring-mode ablation (EGO vs. PPR vs. internal BM25), operational ablations (lexical component, relatedness bonus, adaptive stopping, Boltzmann objective), trivial floors (changed-files-only, random packing), and budget-grid sweeps over {0, 8k, 16k, 32k, 64k, 128k, −1} are reported in Section 6. Against same-budget external baselines, paired both-OK deltas all favor diffctx: +0.371 [+0.350, +0.392] over whole-file BM25 packing, +0.423 [+0.399, +0.447] over Aider repo-map (fair-input), and +0.410 [+0.385, +0.434] over the Aider oracle-mentioned upper bound (permutation p = 10^-5 throughout); unlike the previous snapshot, external BM25 no longer overtakes diffctx at any measured budget.