Where to Repair? When the Root Cause Is Not the Best Target in Multi-Agent Workflows

Recovering failed multi-agent workflows is essential for reliable Artificial Intelligence (AI) automation: an error passed between agents can prevent an entire task from succeeding. Existing work diagnoses causes and tests repairs, yet diagnosis alone does not determine which permitted change best restores task success. One challenge is to identify feasible recovery choices beyond the error source under permission and budget constraints. Another is to compare interacting repairs under matched conditions, separating the effect of repair locations from search quality. We propose a Cross-Surface Constrained Recovery Model that represents source repairs, communication changes, and downstream checks in one constrained action space. We implement the model with Feasibility-Gated Joint Replay Search through three modules: candidate representation specifies actions, gated joint replay evaluates compatible combinations, and selection and loss audit selects repairs and measures value excluded by location restrictions. On our controlled recovery suite (study identifier: CRPA-R1), full candidate access improves mean recovery-rate Lower Confidence Bound (LCB) by $0.135229$ over exhaustive root-only repair across 96 repairable-root traces; on 27 AgentRx retail calibration cases with three seeds, changing only the recovery rule improves executable recovery by $19.75$ percentage points over root-following continuation. These findings support designing recovery systems that use diagnosis to guide a broader search for feasible changes that restore task success.