Skip to content

Retrieval-Conditioned Topology Selection with Provable Budget Conservation for Multi-Agent Code Generation

🕒 Published (v1): 2026-05-07 04:18 UTC · Source: Arxiv · Venue: NEURIPS 2026 · link

Why this paper was selected

NEURIPS; retrieval-conditioned topology selection for code-generation multi-agent routing

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

RGAO (Retrieval-Guided Adaptive Orchestration) closes the loop between code retrieval and multi-agent orchestration by extracting a five-dimensional structural complexity vector \(\mathbf{c} = (d_{dep}, n_f, n_s, h_t, \rho_x)\) from a hierarchical code index before routing each task to one of four topologies. It pairs this routing with a formally verified budget algebra that guarantees resource conservation in \(O(|V|+|E|)\) before any LLM call. The system reduces proxy-measured misrouting from 30.1% to 8.2% over regex baselines, though full SWE-bench runs are deferred to a follow-up.

Problem

Existing multi-agent code-generation orchestrators (regex classifiers, RL policies, VAE-based difficulty estimators) select topology from query-text features alone, ignoring the structural complexity of the repository being modified. A single-file fix and a cross-module refactor may share identical prompt text yet require radically different agent configurations. Additionally, formal budget-conservation guarantees in prior systems (Agent Contracts, AOrchestra) are enforced at runtime—after resources are already consumed—rather than statically before dispatch.

Method

Retrieval-to-routing loop (RGAO): After an initial retrieval pass, a CodeIndexTree (Root→Directory→File→Symbol via tree-sitter) constructs a hierarchical repository index. Five structural signals are read from tree metadata in \(<1\,\text{ms}\): \(d_{dep}\) (max dependency chain depth), \(n_f\) (file count), \(n_s\) (symbol count), \(h_t\) (tree traversal depth), \(\rho_x\) (cross-module coupling ratio). A deterministic threshold classifier over \(\mathbf{c}\) selects one of four topologies: FAST PATH (monolithic), SUBAGENT (single specialist), MULTI AGENT (DAG/swarm), or DEEP RESEARCH (multi-stage retrieval-heavy).

Retrieval engine: Queries are classified into five types (identifier, exact, conceptual, dependency, structural). Conceptual queries activate three parallel strategies—LATTICE path-score calibration, KohakuRAG multi-query reformulation, and PageIndex LLM-guided beam search—fused via RRF, then reranked and expanded with 1-hop RepoGraph typed dependency edges.

Budget algebra: Each sub-agent is governed by a formal \(\langle I, C, T, M\rangle\) contract with \(\mathbf{B} \in \mathbb{N}^6\) (iterations, calls, tokens, seconds, retries, handoffs). Parallel composition is \(\mathbf{B}_1 \oplus \mathbf{B}_2 = (B_{1,i}+B_{2,i})_{i=1}^6\). Theorem 1 (proved by structural induction over the delegation forest) guarantees total resource consumption \(\leq \mathbf{B}_{root}\) regardless of retries or interventions, verified statically via VERIFY_CONSERVATION in a single topological-order DAG pass.

Compositional safety (Proposition 1): Independently verified sub-DAGs \(G_1, G_2\) compose as \(G_1;G_2\) (sequential, \(\mathbf{B}_1 \otimes \mathbf{B}_2\)) or \(G_1 \| G_2\) (parallel, \(\mathbf{B}_1 \oplus \mathbf{B}_2\)) without re-verification.

Key Contributions

  • Complexity-conditioned topology router: maps retrieval-derived \(\mathbf{c} \in \mathbb{R}^5\) plus query to four orchestration topologies; reduces misrouting 30.1%→8.2% (73% relative) over regex (McNemar \(\chi^2=43.6\), \(p<10^{-6}\), 150-task held-out eval set)
  • Budget conservation theorem: structural-induction proof (Theorem 1) over delegation forests; static \(O(|V|+|E|)\) pre-execution verifier, contrasted with runtime-only guarantees in prior work
  • Hierarchical code retrieval engine: five-type query classifier routing to LATTICE + KohakuRAG + BM25/vector hybrid + PageIndex, fused via RRF, with RepoGraph 1-hop typed expansion
  • CODE-AGENT framework: six built-in sub-agent factories (\(\approx 1.1\,\mu\text{s}\) instantiation), three-gate pre-execution protocol, SwarmArtifact typed O(k) passing (vs. O(n²) transcript sharing), intervention state machine extending DoVer
  • Formal composition necessity (Proposition 2): proof that neither retrieval-conditioned routing alone nor static budget verification alone satisfies joint property \(\mathcal{P}\)

Results

  • Routing accuracy: misrouting 30.1% [26.4, 34.1] → 8.2% [6.1, 10.9] (95% Wilson CI) on 150-task held-out eval set; Fleiss' \(\kappa=0.78\) on 3-annotator labels
  • Microbenchmarks (n=20 pytest-benchmark rounds, GC disabled):
  • DAG construction: \(<0.01\,\text{ms}\)
  • Tree index build (200 files, 2002 nodes): \(11.1\,\text{ms} \pm 0.4\,\text{ms}\)
  • Contract factory instantiation: \(1.10\,\mu\text{s} \pm 0.03\,\mu\text{s}\)
  • Budget-tracker overhead: \(0.65\,\mu\text{s} \pm 0.02\,\mu\text{s}\)
  • Routing decision: \(0.11\,\text{ms} \pm 0.02\,\text{ms}\)
  • 4-path RRF retrieval: \(0.90\,\text{ms} \pm 0.08\,\text{ms}\)
  • Pipeline correctness (proxy harness): 100% on 5 compound pipelines (including 2 intervention injections) at \(\sim6{,}000\) tokens/pipeline mean
  • Proxy SWE-bench: 40% pass@1 on 10-issue synthetic set; 8–20Ă— token reduction vs. unconstrained monolithic agents (50–120k tokens/task)
  • All evaluation via proxy harness (evals/swebench_proxy.py); full SWE-bench Verified/Pro runs deferred

Limitations

  • Conservation theorem (Theorem 1) assumes deterministic tool costs (A1), bounded retrieval depth (A2), and finite action space (A3); stochastic temperatures relax this to an expected-budget guarantee with an Azuma–Hoeffding tail bound only sketched in Appendix H
  • Topology router uses hand-tuned thresholds over a 250-instance routing set; a learned classifier (logistic regression / MLP) is future work
  • No full SWE-bench Verified or SWE-bench Pro runs; all end-task numbers are proxy-harness measurements, precluding direct comparison with published leaderboard results
  • Complexity vector \(\mathbf{c}\) omits cyclomatic complexity, test-coverage density, and language-specific idioms (e.g., C++ template depth)
  • Performance degrades under distribution shift (unfamiliar repos, languages outside tree-sitter grammar coverage)

Relevance to Harnesses / Meta-Harnesses

RGAO is explicitly a meta-harness: it sits above the individual sub-agent harnesses and selects which orchestration harness to invoke based on retrieved codebase signals, making topology selection itself a managed, inspectable pipeline stage. The static budget-conservation verifier (VERIFY_CONSERVATION) is a formal harness-level contract that enforces resource bounds before delegation, directly addressing a key failure mode of multi-agent harnesses (unbounded resource blowup at runtime). The evals/swebench_proxy.py proxy harness pattern—separating structural pipeline validation from benchmark execution—is itself a meta-harness design worth noting, as it lets the system prove pipeline correctness independently of the expensive, contamination-prone end benchmark. The compositional safety proposition (Proposition 1) enables modular harness design where verified sub-harnesses compose without re-verification, which is a direct architectural primitive for building layered meta-harnesses.