기술 요약: Rover: LLM 을 활용한 컨텍스트 인식 충돌 해결

1. 문제 제기

대규모 소프트웨어 프로젝트에서의 코드 병합은 심각한 병목 현상이며, 종종 병합 충돌을 해결하기 위해 광범위한 수동 개입이 필요합니다. 기존 솔루션은 다음과 같은 치명적인 한계에 직면해 있습니다:

• 텍스트 및 구조적 병합: 전통적인 도구 (예: Git, 구조적 병합 도구) 는 종종 개발자의 의도를 추론하거나 복잡한 의미론적 종속성을 처리하는 능력이 부족하여, 잘못된 병합이나 수동 수정이 필요한 해결되지 않은 충돌을 초래합니다.
• 머신러닝 접근법: 이전 머신러닝 모델 (예: MergeGen) 은 종종 특정 언어나 충돌 패턴으로 제한되며, 작업별 사전 학습이 필요합니다.
• LLM 기반 접근법: 대규모 언어 모델 (LLM) 은 잠재력을 보이지만, 충돌의 즉각적인 주변을 넘어선 복잡한 코드 종속성이 관련된 충돌에는 어려움을 겪습니다. 기존 방법들은 일반적으로 인접한 코드 블록을 컨텍스트로 의존하는데, 이는 변수 정의나 파일 간 상호작용과 같은 진정한 의미론적 종속성을 포착하기에 종종 불충분합니다.
• 에이전트 기반 접근법: 에이전트는 컨텍스트를 찾기 위해 저장소를 탐색할 수 있지만, 비결정성, 높은 계산 오버헤드, 그리고 실패 원인을 누락된 컨텍스트인지 추론 오류인지 구분하기 어렵다는 문제점을 겪습니다.

핵심적인 도전 과제는 LLM 이 여러 파일이나 추상화 수준에 걸친 코드 종속성에 대한 컨텍스트 인식이 부족하다는 점이며, 기존 종속성 분석 도구들은 언어 중립적이지 않거나 코드 여러 버전 간의 종속성을 포착하지 못한다는 것입니다.

2. 방법론: Rover 시스템

Rover 는 프로그램 분석과 **대규모 언어 모델 (LLM)**을 통합한 새로운 자동 충돌 해결 시스템입니다. 이 시스템의 설계는 휴리스틱 탐색이나 단순한 인접 코드 윈도우가 아닌, 종속성 분석에서 도출된 원칙적이고 분석 가능한 컨텍스트 개념이 효과적인 해결에 필요하다는 통찰에 기반합니다.

2.1 다층 코드 속성 그래프 (MtCPG)

포괄적인 종속성 분석의 부재를 해결하기 위해 Rover 는 코드 속성 그래프 (CPG) 프레임워크 (특히 Joern 사용) 를 기반으로 구축된 새로운 표현 방식인 MtCPG를 도입합니다.

• 아키텍처: MtCPG 는 TypeDef, MethodDef, GlobalVarDef, ImportDef와 같은 고층 노드와 MemberDef, MethodStmt, MethodVarDef와 같은 저층 노드를 가진 계층적 구조를 도입함으로써 원본 CPG 를 확장합니다.
• 엣지 유형:
  • 크로스레이어 엣지: 고층 정의와 내부 저층 구성 요소를 연결하여 세밀한 추론을 가능하게 합니다.
  • 파일 간 엣지: ImportDef 노드를 통해 다른 소스 파일의 노드 간의 종속성을 명시적으로 모델링하여, 소스 파일을 평탄화하지 않고도 파일 간 종속성 분석을 가능하게 합니다.
• 장점: 표준 CPG 와 달리 MtCPG 는 파일 간 종속성과 정의 수준의 추상화를 포착하여, 여러 파일에 걸치거나 다른 위치에 있는 타입 정의와 관련된 충돌을 이해하는 데 필수적인 정보를 제공합니다.

2.2 그래프 - 텍스트 정렬을 통한 컨텍스트 생성

Rover 는 Git 병합 결과에서 나온 코드 변경 사항의 텍스트 표현을 MtCPG 구조와 정렬하여 의미론적으로 의미 있는 컨텍스트를 생성합니다.

• 그래프 - 텍스트 정렬: 줄 번호 기반의 세그먼트 트리를 사용하여 코드 변경 블록 (diff) 을 MtCPG 의 특정 노드에 매핑하는 "색칠" 메커니즘을 적용합니다.
• 컨텍스트 클러스터링: Rover 는 충돌 노드에서 시작하여 MtCPG 위에서 다중 소스 너비 우선 탐색 (MS-BFS) 알고리즘을 사용합니다. 이는 가변 깊이 $k$까지 종속성을 탐색하여 관련 코드 블록을 "컨텍스트"로 그룹화합니다.
• 버전 간 통합: 컨텍스트는 병합되는 두 버전 각각에 대해 독립적으로 생성된 후, 양쪽 버전의 모든 관련 종속성이 포착되도록 불연속 집합 합집합 (disjoint-set union) 방식을 사용하여 병합됩니다.

2.3 해결책 생성

최종 해결책은 구조화된 프롬프트에 의해 안내되는 LLM (예: Qwen3-30B-A3B) 에 의해 생성되며, 이 프롬프트는 다음을 포함합니다:

1. 작업 정의: 역할과 목표에 대한 명확한 지시사항.
2. 생각의 사슬 (CoT): LLM 이 근본 원인을 분석하고, 두 버전의 의도된 논리를 추론하며, 최상의 병합 전략을 결정하도록 요구하는 3 단계 추론 과정.
3. 입력/출력 형식: 간소화된 처리를 위한 "diff" 형식 사용.
4. 컨텍스트 입력: MtCPG 에서 검색된 의미론적으로 관련 있는 컨텍스트와 결합된 충돌 코드.

3. 주요 기여

본 논문은 다음과 같은 기여를 주장합니다:

1. MtCPG: 표준 CPG 의 한계를 극복하고 파일 간 및 계층 간 관계를 포함한 모든 코드 구성 요소에 대한 포괄적인 종속성을 포착하는 새로운 표현 방식.
2. 컨텍스트 분류 방법론: MtCPG 연결성을 기반으로 코드 블록을 분류하는 원칙적인 접근 방식으로, 단순한 인접 코드 윈도우보다 코드 의존성 평가에 더 적합한 컨텍스트를 생성합니다.
3. Rover 시스템: MtCPG 를 통합한 LLM 기반 충돌 해결 도구의 구현. ConGra 데이터셋에서 평가되었으며, 단독 LLM 및 베이스라인 도구보다 우수한 성능을 입증했습니다.

4. 실험 결과

저자들은 ConGra 데이터셋 (도구 성숙도 문제로 C++ 제외) 과 WizardMerge 데이터셋의 서브셋 (C 기반) 을 사용하여 Rover 를 평가했습니다. 평가 지표로는 편집 거리 (ED), Winnowing 유사도 (WS), 코사인 유사도 (CS) 가 포함되었습니다.

• MtCPG 대 CPG: MtCPG 는 원본 CPG 대비 그래프 노드 수를 약 3.4%, 엣지 수를 약 25% 증가시켜, 훨씬 더 풍부한 종속성 정보를 포착했습니다.
• 베이스라인 대비 성능:
  • 단독 LLM: Rover 는 단독 LLM (Qwen3-30B-A3B) 보다 13.29% (WS), 10.46% (ED), **9.79% (CS)**만큼 우수한 성능을 보였습니다.
  • 머신러닝 베이스라인: MergeGen 과 비교하여 Rover 는 17.72% (WS), 15.90% (ED), **9.10% (CS)**만큼의 개선을 달성했습니다.
  • 도구 지원 LLM: Rover 는 LLM 과 WizardMerge 의 조합을 3.82% (WS), 1.85% (ED), **4.07% (CS)**만큼 능가했습니다.
• 컨텍스트 민감도: 연구에 따르면 컨텍스트 크기 (인접 줄 또는 그래프 깊이 $k$) 를 늘리는 것이 성능을 선형적으로 향상시키지는 않습니다. 최적의 $k$ (예: $k=4$) 가 존재하며, 이를 넘어서면 관련 없는 먼 종속성이 모델을 혼란시켜 성능을 저하시킵니다.
• 커버리지: Rover 는 WizardMerge 데이터셋에서 98.83% 의 충돌 커버리지를 달성하여, WizardMerge 의 90.67% 보다 훨씬 높았습니다. 이는 Rover 가 전체 프로젝트 컴파일이 필요 없는 소스 코드 수준에서 작동하기 때문입니다.
• 모델 의존성: Rover 의 효과성은 LLM 에 따라 달라졌습니다. 더 큰 모델 (gpt-oss-20b) 에서는 성능이 향상되었지만, 더 작은 모델 (Llama-3.1-8B) 에서는 성능이 저하되었는데, 이는 작은 모델이 길고 복잡한 컨텍스트를 해석하는 데 어려움을 겪는 "추론 병목" 현상을 시사합니다.

5. 중요성 및 주장

본 논문은 Rover 를 완전 자동화된 컨텍스트 인식 충돌 해결을 향한 중요한 단계로 위치시킵니다.

• 결정론적 컨텍스트: 에이전트 기반 시스템과 달리 Rover 는 LLM 주도 탐색의 비결정성을 피하고 컨텍스트 선택을 위한 결정론적이고 분석 가능한 기반을 제공합니다.
• 격차 해소: 종속성을 이해하지만 생성 능력이 부족한 프로그램 분석과, 코드를 생성할 수 있지만 깊은 컨텍스트 인식이 부족한 LLM 간의 격차를 성공적으로 해소합니다.
• 실용성: 컴파일러 기반 분석 (WizardMerge 등) 에 의존하는 도구보다 소스 코드 수준에서 작동하고 전체 프로젝트 컴파일이 필요 없으므로, Rover 는 실제 세계의 병합 시나리오에 더 강력하고 적용 가능합니다.
• 약간의 한계: 저자들은 MtCPG 가 현재 특정 언어별 기능 (예: C 의 인라인 어셈블리, 복잡한 예외 처리) 에 한계가 있으며, 문자열 기반 지표가 기능적 정확성을 완전히 보장하지는 않지만, 수동 샘플링 검증을 통해 지표 점수와 해결책 수용 간에 강한 양의 상관관계가 있음을 인정합니다.

저자들은 원칙적인 종속성 분석에서 도출된 적절한 컨텍스트 정보가 LLM 기반 충돌 해결을 개선하는 데 필수적이며, Rover 가 이를 효과적으로 입증한다고 결론지었습니다.