Procedural Refinement by LLM-driven Algorithmic Debugging for ARC-AGI-2

1. 연구 배경 및 문제 정의 (Problem)

• LLM 의 코드 생성 및 수정 한계: 대규모 언어 모델 (LLM) 은 논리적으로 일관된 코드를 생성할 수 있지만, 복잡한 알고리즘 작업에서 발생하는 오류를 스스로 수정하는 능력은 제한적입니다. 기존 LLM 기반의 코드 수정은 주로 "합리적 추론 (plausible reasoning)"이나 대화형 피드백에 의존하며, 이는 형식적인 알고리즘 디버깅 절차를 따르지 않습니다.
• 수정 실패의 원인: 연구에 따르면 LLM 은 대화형 피드백만으로는 오류를 견고하게 수정하지 못하며, 오히려 수정 후 결과가 초기 응답보다 나빠지는 경우가 많습니다. 체인 오브 씽킹 (Chain-of-Thought) 이나 외부 컴파일러를 추가하더라도 반복적인 수정 시도에서 성능이 급격히 저하됩니다.
• ARC-AGI-2 의 도전: ARC-AGI-2 는 시각적 추상화, 심볼릭 추론, 그리고 알고리즘적 추론을 소수의 예시만으로 수행해야 하는 벤치마크로, LLM 이 초기 가설을 잘못 세우면 이를 체계적으로 수정하기 매우 어렵습니다.

2. 제안된 방법론: ABPR (Methodology)

저자들은 Udi Shapiro 의 알고리즘 프로그램 디버깅 (Algorithmic Program Debugging, APD) 이론을 기반으로 한 신경 - 심볼릭 (Neuro-Symbolic) 접근법인 Abduction-Based Procedural Refinement (ABPR) 를 제안합니다.

• 핵심 개념:

  • APD 프레임워크: 프로그램 수정을 임의의 수정 시도가 아닌, 명시적인 절차적 세분화 (Procedural Refinement) 과정으로 정의합니다.
  • 선언적 실행 추적 (Declarative Execution Traces): LLM 이 생성한 코드 (Prolog) 를 메타 인터프리터 (Meta-interpreter) 를 통해 실행하여, 단순한 출력뿐만 아니라 트리 구조의 선언적 실행 로그를 생성합니다.
  • 귀납적 추론 (Abduction) 기반 디버깅:
    1. 오류 국소화 (Bug Localisation): 실행 트리에서 잘못된 노드 (Buggy Node) 를 식별합니다. LLM 을 '오라클 (Oracle)'로 사용하여 특정 서브트리의 논리적 유효성을 검증합니다.
    2. 절차적 세분화 (Procedural Refinement): 식별된 오류 노드에 대해 최소한의 가설 수정 (Abductive Hypothesis Revision) 을 수행하여 다음 단계의 프로그램을 생성합니다.
  • 확률적 탐색: LLM 의 생성 과정에 내재된 확률적 특성을 활용하여, 최적의 수정 경로를 탐색하는 확률적 상태 전이 (Stochastic Transition) 로 모델링합니다.

• 구현 세부사항:

  • 타겟 언어: 선언적 의미론을 가진 Prolog를 사용하며, 이는 APD 프레임워크와 자연스럽게 호환됩니다.
  • 시스템 구조:
    1. Neural Generation: LLM 이 초기 프로그램 (Hypothesis) 을 생성합니다.
    2. Symbolic Verification: Prolog 메타 인터프리터가 실행 트리를 생성하고 오류를 포착합니다.
    3. Algorithmic Debugging: LLM 이 실행 트리를 분석하여 오류 원인을 추론하고 수정된 코드를 생성합니다.
    4. Ensemble Strategy: 여러 병렬 스레드에서 탐색을 수행하고, 다양성을 고려한 투표 (Voting) 를 통해 최종 결과를 도출합니다.

3. 주요 기여 (Key Contributions)

1. 형식적 디버깅과 LLM 의 통합: LLM 의 생성 능력과 고전적인 심볼릭 AI 의 형식적 디버깅 (APD) 을 결합하여, LLM 의 "블랙박스"식 수정을 검증 가능한 (Auditable) 절차적 과정으로 전환했습니다.
2. 선언적 추적의 중요성 입증: 단순한 대화형 피드백이 아닌, **트리 구조의 실행 로그 (Execution Traces)**가 오류 국소화와 수정 효율성을 극적으로 높인다는 것을 실험적으로 증명했습니다.
3. ARC-AGI-2 에서의 SOTA 성능 달성: LLM 이 일반적으로 약한 것으로 알려진 Prolog 언어를 사용했음에도 불구하고, 최신 LLM(Gemini-3-Flash 등) 과 결합하여 ARC-AGI-2 벤치마크에서 기존 최첨단 방법론을 능가하는 성능을 기록했습니다.

4. 실험 결과 (Results)

• 성능 지표 (Pass@2):
  • Gemini-3-Flash 모델과 ABPR 을 결합했을 때, **56.67%**의 Pass@2 점수를 기록했습니다.
  • 이는 수정 없이 생성만 하는 경우 (34.03%) 나, 선언적 추적 없이 대화형 자기 수정 (Self-correction) 만 사용하는 경우 (49.17%) 보다 월등히 높은 성능입니다.
  • GPT-5.2의 경우에도 낮은 추론 모드에서 8.33% 에서 30.00% 로 크게 향상되었습니다.
• 성분 분석 (Ablation Study):
  • 초기 가설의 질: 강력한 초기 가설 (Strong Initialisation) 이 제공될 때 ABPR 의 수정 루프가 가장 효과적으로 작동함을 보였습니다.
  • 선언적 추적의 영향: 실행 트리를 제거하고 대화형 피드백만 사용할 경우 성능이 10% 이상 하락하여, 구조화된 피드백의 핵심적 역할을 입증했습니다.
• 비용 효율성: 고비용의 "Deep Thinking" 모델 없이도, 비용 효율적인 모델 (Flash) 에 심볼릭 스캐폴딩 (Scaffolding) 을 적용하여 동급 이상의 성능을 달성했습니다.

5. 의의 및 결론 (Significance)

• 검증 가능한 AI (Auditable AI): ABPR 은 LLM 이 생성한 답에 대한 **명시적인 논리적 증거 (Prolog 증명 트리)**를 제공하므로, 의료, 법률, 과학 연구 등 고위험 분야에서 AI 의 의사결정 과정을 검증하고 설명할 수 있는 새로운 패러다임을 제시합니다.
• 신경 - 심볼릭 AI 의 실용화: 순수 신경망 기반의 접근법과 심볼릭 논리 기반의 접근법의 장점을 결합하여, LLM 의 환각 (Hallucination) 문제와 논리적 일관성 부족을 해결하는 실용적인 방안을 제시했습니다.
• 민주화 (Democratization): 막대한 컴퓨팅 자원을 요구하는 거대 모델에 의존하지 않고도, 상대적으로 저렴한 모델을 심볼릭 도구와 결합하여 최첨단 추론 성능을 달성할 수 있음을 보여줌으로써 AI 연구의 진입 장벽을 낮췄습니다.

이 논문은 LLM 기반 코드 생성의 한계를 극복하기 위해 **형식적 방법 (Formal Methods)**을 도입한 신경 - 심볼릭 접근법의 유효성을 입증한 중요한 연구로 평가됩니다.