APR-Router: Complexity-Aware Cascade Routing for Cost-Effective LLM-Based Program Repair

Abstract

LLM-based automated program repair (APR) encompasses strategies ranging from lightweight zero-shot prompting to costly agentic workflows, yet most systems apply a fixed strategy to every defect. Through a systematic empirical study, we establish three new findings. First, no single repair strategy dominates across all complexity levels. Second, repair success depends on domain-specific code characteristics. Third, a cascade of just three attempts closes most of the repair gap left by any single strategy, with sharply diminishing returns beyond. Based on these observations, we propose APR-Router, a complexity-aware routing framework that formulates APR strategy selection as a sequential repair problem. APR-Router operates in three stages. First, it extracts a 114-dimensional feature vector spanning five families. Second, it predicts per-strategy repair effectiveness with a LambdaRank-based ranker and per-strategy token costs with independent regressors. Third, it executes strategies in decreasing order of a repair efficiency index grounded in sequential search theory, stopping at the first success. Extensive experiments demonstrate that APR-Router improves pass rate by +8.7 to +17.4 percentage points and Aggregate Intelligence Quotient by +8.3% to +22.3% over the strongest APR baseline, and consistently outperforms adapted generic LLM routing methods, with routing overhead less than 0.1% of a single LLM inference call.