기술 요약: CodeRescue: 코딩 에이전트를 위한 예산 보정형 복구 라우팅 (Budget-Calibrated Recovery Routing for Coding Agents)

1. 문제 정의

본 논문은 실행 가능한 환경에서 작동하는 코딩 에이전트의 배포 과제를 다룹니다. 이 환경에서 실패한 시도는 단순히 틀린 출력을 내는 것이 아니라, 실행 가능한 피드백(예: 컴파일러 에러, 테스트 실패, stderr 트레이스)을 생성합니다. 기존의 비용 인식 시스템은 모델의 실패를 이진 결정(binary decision)으로 취급하여, 즉시 더 강력하고 비싼 모델로 에스컬레이션(escalate)하는 경레가 있습니다.

저자들은 이러한 접근 방식이 코딩 작업에는 최적이 아니라고 주장합니다. 왜냐하면 실행 피드백이 있다면 저렴한 모델의 추가 시도가 가치가 있을 수 있기 때문입니다. 이는 **예산이 책정된 배포 문제(budgeted deployment question)**를 생성합니다. 즉, 에이전트가 실패했을 때, 솔루션을 수정(reflect)하거나 재계획(replan)하기 위해 저렴한 컴퓨팅 자원을 더 사용할 것인지, 아니면 더 강력한 모델로 에스컬레이션할 것인지를 결정해야 합니다.

이 문제는 **사후 실패 복구 라우팅(post-failure recovery routing)**으로 정식화됩니다. 저렴한 모델의 초기 시도가 실패한 경우, 시스템은 세 가지 이질적인 행동 중 하나를 선택해야 합니다:

1. 성찰 (Reflect): 실행 피드백을 사용하여 기존 솔루션을 수정합니다.
2. 재계획 (Replan): 저렴한 모델을 사용하여 다른 계획으로부터 새로운 솔루션을 생성합니다.
3. 에스컬레이션 (Escalate): 문제를 (피드백과 함께) 더 강력하고 비싼 모델로 넘깁니다.

목표는 사용자 지정된 평균 복구 예산($B$)을 준수하면서 **해결률(solve rate)**을 극대화하는 것입니다. 이때 매번 새로운 예산 제약에 맞춰 정책을 재학습할 필요가 없어야 합니다.

2. 방법론

2.1 지도 학습 기반 복구 라우터 (Supervised Recovery Router)

핵심 구성 요소는 오프라인 실행 롤아웃(rollouts)을 통해 학습된 지도 학습 기반 라우터입니다.

• 입력: 복구 컨텍스트 $x = (q, v_0, e_0)$로, 문제 문구, 실행 결과(verdict), 그리고 stderr 트레이스로 구성됩니다.
• 레이블링: 각 실패 사례에 대해, "오라클(oracle)" 레이블은 해당 인스턴스를 해결하는 행동 집합 $S(x)$ 중 가장 저렴하게 성공하는 행동($a^\dagger$)으로 정의됩니다. 어떤 행동도 성공하지 못하는 인스턴스는 제외됩니다.
• 학습: 언어 모델(예: Qwen3.5-4B)을 크로스 엔트로피를 통해 파인튜닝하여 가장 저렴하게 성공하는 행동을 예측하도록 학습시킵니다. 라우터는 로그 확률(log-probabilities)을 기반으로 행동 점수를 매기고 소프트맥스(softmax)를 통해 정규화합니다.

2.2 비용 정규화 정책 (Cost-Regularized Policy)

새로운 예산 제약에 따라 재학습 없이 다양한 예산 하에서 배포할 수 있도록, 저자들은 비용 페널티 $\lambda \ge 0$를 도입합니다. 정책 $\pi_\lambda(x)$는 다음을 최대화하는 행동을 선택합니다:
$$s_\theta(a | x) - \lambda c(a, x)$$
여기서 $s_\theta$는 라우터의 점수이고, $c(a, x)$는 추정된 배포 비용입니다.

• $\lambda$가 증가함에 따라, 정책은 더 저렴한 행동(성찰/재계획) 쪽으로 이동합니다.
• 이를 통해 단일 학습된 라우터로부터 유도된 이산적인 운영 지점들(비용-품질 프런티어)을 생성합니다.

2.3 컨포멀 예산 보정 (Conformal Budget Calibration, CRC)

특정 사용자 예산 $B$에 대해 통계적 보장을 제공하며 적절한 $\lambda$를 선택하기 위해, 저자들은 **컨포멀 리스크 제어(Conformal Risk Control, CRC)**를 적용합니다.

• 메커니즘: 홀드아웃(held-out) 보정 세트를 사용하여 다양한 $\lambda$ 값에 대한 경험적 평균 비용을 계산합니다.
• 선택 규칙: 유한 샘플 예산 제약을 만족하는 가장 완화된(least restrictive) 페널티 $\hat{\lambda}$를 선택합니다:
  $$\frac{n \hat{C}_n(\lambda) + c_{\max}}{n + 1} \le B$$
  여기서 $c_{\max}$는 알려진 비용 상한이며, 가산 항은 리브-원-아웃(leave-one-out) 컨포멀 보정을 제공합니다.
• 보장: 교환 가능성(exchangeability) 가정 하에, 이 절차는 향후 테스트 데이터에 대한 배포 정책의 기대 평균 복구 비용이 $B$를 초과하지 않음을 보장합니다. 결정적으로, 이 보장은 해결률이 아닌 비용에 적용되며, 이는 행동 간의 비단조적(non-monotone) 성공 패턴을 허용합니다.

3. 주요 기여

1. 사후 실패 복구 라우팅: 본 논문은 코딩 에이전트의 복구를 단순한 강력한 모델로의 계층적 이동이 아닌, 이질적인 행동(성찰, 재계획, 에스컬레이션)에 대한 라우팅 문제로 정식화했습니다.
2. 예산 제어 가능 배포: CRC로 보정된 비용 페널티를 도입하여, 단일 학습된 라우터가 다양한 예산 지점에서 동작할 수 있게 함으로써, 서로 다른 예산 제약에 따라 재학습해야 하는 번거로움을 제거했습니다.
3. 경험적 복구 트레이드오프: 연구는 저렴한 복구와 모델 에스컬레이션이 상호 보완적인 성공 패턴(즉, 어떤 실패는 저렴한 행동으로만 해결 가능하고, 어떤 것은 에스컬레이션으로만 가능하며, 어떤 것은 둘 다로 가능함)을 보인다는 경험적 증거를 제공하며, 이들이 이산적인 비용-품질 프런티어를 형성함을 보여줍니다.

4. 실험 결과

시스템은 GPT-5.4-NANO를 저렴한 모델로, GPT-5.4를 강력한 모델로 사용하여 5개의 코딩 벤치마크(APPS, TACO, BigCodeBench, LiveCodeBench, CodeContests)에서 평가되었습니다.

• 라우터 효능: 학습된 라우터는 고정된 행동 베이스라인보다 성능이 우수했습니다. 제약 없는 학습된 라우터는 평균 비용 5.51 m$에서 **81.7$에서 68.6%를 기록했습니다.
• 상호 보완성: "오라클" 최저 비용 행동 분석 결과, 실패 사례의 28%는 저렴한 행동으로만 해결 가능했고, 45%는 에스컬레이션으로만 가능했으며, 27%는 둘 다로 가능했습니다. 이러한 이질성은 고정된 캐스케이드 대신 라우터가 필요한 이유를 정당화합니다.
• 예산 보정: CRC로 보정된 프런티어는 예산이 **2.56 m$**일 때 시스템이 71.7%의 해결률을 달성함을 보여주었습니다. 이는 "항상 에스컬레이션" 베이스라인(68.6%)을 능가하면서도, 해당 전략의 평균 비용의 35%만을 사용한 결과입니다.
• 베이스라인: 학습된 라우터는 프롬프트 전용 라우터(제로샷 LLM이 라우터 역할을 수행) 및 이진 캐스케이드 베이스라인보다 뛰어난 성능을 보였으며, 이는 라우팅 신호가 단순한 프롬프트 엔지니어링이 아닌 롤아웃으로부터의 학습을 필요로 함을 확인시켜 줍니다.

5. 의의 및 주장

본 논문은 코딩 실패를 단순한 능력 격차가 아닌 **진단 가능한 수리 문제(diagnosable repair problem)**로 취급하는 것이 더 효율적인 자원 할당을 가능하게 한다고 주장합니다. CRC를 통해 라우터의 학습과 배포 예산을 분리함으로써, 시스템은 **예산 제어 가능한 추론(budget-controlled inference)**을 위한 실질적인 메커니즘을 제공합니다.

저자들은 본 방식이 해결률을 컨포멀하게 제어한다고 주장하는 것이 아니라, 비용 보장을 제공하며 해결률의 개선은 경험적인 관찰임을 강조합니다. 이 연구는 코딩 에이전트에게 있어 "가장 저렴하고 유용한 다음 단계"는 항상 가장 강력한 모델이 아니라, 실패 모드에 맞춤화된 특정 복구 행동일 수 있으며, 이 결정이 엄격한 예산 제약 하에서 동적으로 이루어질 수 있음을 시사합니다.

저자가 언급한 한계점:

• 복구는 단일 사후 실패 결정으로 모델링되었으나, 실제 에이전트는 여러 라운드를 반복할 수 있습니다.
• "가장 저렴하게 성공하는" 레이블은 대리 지표(proxy)이며 보정된 확률 추정치는 아닙니다.
• CRC는 기대 비용을 제어하며 해결률을 제어하는 것이 아니므로, 품질 개선은 여전히 경험적인 관찰입니다.