[논문리뷰](25.05) DARS: Dynamic Action Re-Sampling to Enhance Coding AgentPerformance by Adaptive Tree Traversal

 

한 때 SWE-Bench의 SOTA를 달성했던 논문. SWE-Bench의 상위권들은 공개를 안하기에 상위권은 어떻게 문제를 풀어갔는지 볼 수 있는 소중한 논문

• 3.2에 예시 작성 - 이 부분만 살펴봐도 충분
• 3.3에 더 자세한 예시 작성

 

Abstract

• 기존 접근법들은 Agent가 차선의 선택을 하는 어려움이 있었으며, 넓은 범위의 수동 개입, 비효율적인 compute scaling 전략을 사용함.
• Coding agent 성능을 향상시키기 위해, coding agent를 위한 새로운 inference time compute scaling 접근법인 DARS제시
  • baseline들에 비해 차선의 결정에서 최선으로 복구하는 데 빠르고 효과적임.
  • 전통적인 agent들이 선형 trajectory를 따르거나 compute scaling을 위해 random sampling에 의존하는 반면
  • DARS는 특정 핵심 결정 지점에서 trajectory를 branching하는 방식으로 작동한다. 이는 trajectory의 history와 해당 지점에서 진행했던 이전 시도들에서 execution feedback을 받아 다른 행동을 하도록 한다.

 

1. Introduction

• 소프트웨어 엔지니어링(SWE)은 중요해지고 있으며, 개발자들은 코드 작성, 검토, 유지보수에 무수한 시간을 소비하고 있어 생산성 향상을 위한 자동화가 중요해 지고 있음
• LLM은 좋은 자동화 도구로 등장했으며, SWE-bench와 같은 곳에서 실험 및 발전함
• LLM을 기반으로 한 SWE agent는 세가지 방법이 있음.
  1. SWE-Agent와 OpenDevin과 같은 agent들이 개발 도구와 상호작용하고 execution feedback을 통합하여 예측을 개선하는 순차적 ReAct loop을 따르는 것
  2. temperature 기반 sampling을 사용하여 여러 해결책을 생성한 다음 ranking이나 majority voting을 통해 최고를 선택
  3. SWE-Search 해결 공간을 체계적으로 탐색하기 위해 Monte Carlo Tree Search (MCTS)를 활용
• 각 방법의 한계점
  • (1) Sequential agent들은 context length 제약으로 인해 차선의 결정에서 최선의 결정으로 돌아가기 어렵다
  • (2) Multi-solution 접근법들은 생성된 해결책들 간의 지식 공유가 어렵다.
  • (3) SWE-Search와 같은 tree search 방법들은 scalar value function에 의존하고 실행 속도가 느려 long-horizon planning에 효과적이지 않다.
• 이러한 한계점을 극복하기 위한 DARS를 제안한다. 
  • 여러 독립적인 trajectory를 생성하기보다, 핵심 결정 지점에서 선택적으로 branching하며, trajetory를 branching하기 전에 완탐하는 depth-first전략을 사용함.
  • 이는 두가지 장점이 있음
    • Long Horizon Feedback: branching 전에 완전한 trajectory feedback을 제공하여 pass@1 rate가 향상됨을 보임
    • Efficiency: Depth-first search는 미래 상태를 시뮬레이션하지 않고 현재 환경 상태를 재사용함으로써 메모리 오버헤드를 줄임 -> 가지를 동시에 엄청 많이 생성하지 않음.
    • 가장 좋은 해결책을 찾기 위해 proprietary model, preference-optimized model을 사용하는 Selection을 진행함.

 

2. Related Work

• LLM Agent for Software Engineering: 
  • Tool: 코드 편집, 검색, 탐색, 실행을 통합
    • diff기반 편짐, jupyter&웹 검색을 갖춘 실행, 최적화된 repository 검색 포함
  • 샘플링:
    • 250개의 샘플링 -> 250%의 정확도 향상 (허나 너무 비효율적임)
    • 비효율을 완화하기 위해 MCTS 도입

 

3. Our DARS Method

• 목표: redundancy를 최소화, 차선의 결정에서 -> 최선으로 회복하고 학습할 수 있는 능력을 향상시키는 것
  1. 액션 최적화: 하지만 trajectory를 확장할 때 오류도 함께 증가하기 때문에, 먼저 backbone인 SWE-Agent의 편집 능력을 개선하는것을 먼저 수행함.
  2. Expansion: 그 다음 resolve rate의 증가와 해당 지점에서 trajectory를 branching하는 사이의 trade-off를 최적화하여 가장 유망한 액션 유형들을 식별함. 이러한 tree branching 과정을 expansion이라고 정의함.
  3. 마지막으로 모든 시도 중에서 가장 유망한 trajectory를 선택함

3.1 Improving the Base SWE Agent

3.1.1 Editing Capabilities

• ReAct loop을 사용하여 반복적으로 생각과 행동을 생성하고 sandbox 환경으로부터 피드백을 받는 SWE-Agent를 기반으로 구축
  • 에이전트는 편집의 시작과 끝 라인 번호와 편집 내용을 생성해야 하는 whole style의 편집을 사용
    • 이러한 유형의 편집은 에이전트가 대상 코드와 인접한 코드를 모두 고려하지 못하여 indentation 오류와 같은 문제를 발생시킴(수많은 syntax 및 semantic 오류).
      • 해결:
        • diff-based tool인 Aider를 사용하여 편집의 품질을 향상시킴.
        • 이 접근법에서 에이전트는 교체될 내용과 그 대체 내용을 모두 생성.
        • 교체 없이 내용 추가를 용이하게 하기 위해 Aider는 두 가지 새로운 액션인 append와 insert를 도입
          • Append는 파일 끝에 내용을 추가하고, Insert는 라인 번호와 해당 특정 위치에 삽입될 내용을 필요로 함.
          • 이 접근법은 모델이 기존 코드를 더 잘 고려하도록 함.
          • 더 나아가, 에이전트가 to_replace와 replace_with 내용을 모두 출력하고, 각각 뒤에 $ 문자를 붙여 특수 문자들 (예: newlines, quotes)을 적절히 escape하도록 하여 편집 과정을 향상킴(Section A.14.1).

3.1.2 New Actions

새로운 액션들 도입함

• Execute Server: Sandbox에서 작동하여 (시간 제한, 메모리 초기화, 등)으로 인해 버그를 재현하려면 매우 비효율적임.
  -> 백그라운드에서 돌아가는 서버처럼 구현함.
• Execute IPython: IPython환경에서 Python코드 실행할 수 있게 함.
• Search Repo: cached RepoGraph(Ouyang et al., 2024)를 사용함.
  • 노드-코드 정의, 엣지-이들간의 의존성을 나타냄.
  • sub-graph retrieval알고리즘 활용하여 필요한 context를 불러옴.
• Undo Edit: LLM은 Syntax 실수를 많이 하는데 -> 이를 완화하기 위해 undo edit을 제공함(Anthropic, 2024b)

 

3.2 DARS Scaling

• 루트 노드(Bug 발생)로부터 관련된 노드(코드)들을 불러오면서 진행
• 예시) 
  
  • Start (depth=0)
                           |
                     Search repo (depth=1)
                       /       \
                Find bug.py     Find test.py (depth=2)
               (depth=2)           |
                   |                      Open test.py
              Open bug.py      (depth=3)
              (depth=3)           |
                   |                      Read test
              Read code        (depth=4)
              (depth=4)
                   |
              Edit function
              (depth=5)
    
    
    1. Trajectory를 선형으로 실행
    - Start → Search repo → Find bug.py → Open bug.py → Edit function → Submit
    
    2단계: 실행하면서 중요한 지점들을 기록 함
    - Search repo(depth=1)는 중요한 결정 → Priority Queue에 저장
    - Find bug.py(depth=2)도 중요한 결정 → Priority Queue에 저장  
    - Edit function(depth=5)도 중요 → Priority Queue에 저장
    
    Start(0) → Search_repo(1) → Find_bug.py(2) → Open(3) → Read(4) → Edit(5) → Submit(6)
                                ↓                          ↓                                                                ↓
                    기록: depth=1           기록: depth=2                                       기록: depth=5
    
    Priority Queue에 저장: [Search_repo(1), Find_bug.py(2), Edit(5)]
    
    3단계: Termination state도달
      (첫 번째 trajectory가 끝난 후에 Priority Queue에서 하나씩 꺼내서 확장:)
    Start(0) → Search_repo(1) 
               ├── "bug" (원래 경로 - 이미 실행됨)
               └── "error" (새로운 선택) → Find test.py(2) → Open test.py(3) → ... → Submit
    
    3.1단계: 이 단계에서도 중간 중간에 중요한 결정인 것을 판별하면 Priority Queue에 저장.
• Expansion: submit명령, 혹은 미리 정의한 최대 depth에 도달하면 확장 진행
  • 확장 중에는 K개의 대안 액션을 샘플링하고 최고의 것을 선택함.

3.2.1 Branching Strategy

SWE-AGENT의 기본 액션들은 (Search Dir, Insert, Search File. Open. Goto, Find File, Append, Edit)인데, DARS에서는 Create, Append, Edit, Submit을 선별함. 이들만이 유요하게 효과적이라는 것을 분석했고, 논문에서는 이유에 대해서 서술하고 있음.

 

3.2.2 Expansion Strategy

위 예시를 보면 expansion이 Priority Queue를 통해서 이루어짐을 알 수 있음.

 

3.3 Best Trajectory Selection

1. Trajectory Pruning:

• Trajectories에서 생성된 모든 패치들을 수집
• bug fix부분만 남기고 나머지들은 제거함
• 정리된 patch들 중 동일한 것들을 중복 제거함. -> n개의 유니크한 patch들

2. Trajectory Selection -> 이 부분은 실제로 제출 해봐야 얻을 수 있는 정보: 실제 inference상황에서는 얻기 힘든 정보일 수 있음.

• 각 patch를 3가지 기준(reproduction, fix, regression risk)으로 평가
  • Reproduction: 문제를 얼마나 잘 재현했는가?
  • Fix: 문제를 얼마나 잘 해결했는가?
  • 새로운 bug 도입 가능성: 수정사항이 다른 문제를 야기할 위험은 얼마나 되는가?
• 가장 높은 점수를 받은 패치 선택

 

문제가 있다. 논문에서는 이 그림에 나온 모든것을 다 서술하지 않음.

그래도 유추해보자면,,

1. Generate
   1. Phase 1: 
      1. Reproduction:
         1. Test Script생성: reproduction script생성함.
         2. Execute: execute_server로 스크립트 실행
         3. Reproduce: 필요시 append 액션으로 스크립트 개선
         4. Feedback: 실행 결과과 실제로 재현되는지 검증
      2. Localization:
         1. Search Repo: 관련 함수/클래스 검색
         2. Localize to classes & functions: RepoGraph를 활용한 의존성 분석
         3. Search File: 특정 파일 내 키워드 검색.
         4. Localize to edit locations: 실제 수정이 필요한 구체적인 위치 특정(Fault Location)
      3. Bug Fixing
         1. Edit: edit으로 코드 수정
         2. Execute 수정된 코드 실행하여 작동하는지 테스트
         3. Valildation: 수정이 올바른지 검증
         4. Feedback: 결과 확ㅇ니하여 추가 수정 필요성 판단
      4. 중간 중간 중요한 부분인지 판단(?) -> Priority Queue에 저장
   2. Phase 2(Feedback - Expansion인 것 같음):
      1. Key Decision Points 식별: Phase1에서 실행되었다고 가정함
      2. Priority Queue에서 가지 분할 지점 선택
      3. Generator LLM으로 가지 생성: 이전 sibling action과 달라야함. 이전 액션을 대체해야함. 이전 액션보다 더 효과적이여야함.
      4. Selector LLM으로 가지 선택.
2. Evaluation
   1. Patch Generation & Cleaning 
   2. Patch Analysis
   3. Best Patch Selection