기술 요약: REACOMP

문제 정의

대형 언어 모델 (LLM) 은 프로그램 합성 작업, 특히 예제 기반 프로그래밍 (PBE) 패러다임 내에서 뛰어난 능력을 입증해 왔습니다. 그러나 대규모 조합 탐색이 필요한 어려운 인스턴스에서는 심각한 비효율성과 신뢰성 부족을 겪습니다. 분석 결과, 더 어려운 인스턴스는 구성적 일반화 실패와 비효율적인 탐색 전략 (예: 루핑, 중복 탐색) 으로 인해 불균형하게 높은 토큰 사용량과 여러 번의 시도를 유발하는 것으로 나타났습니다. 기존 접근법은 학습된 라이브러리나 도구를 LLM 에 결합하려 시도하지만, 이러한 방법들은 종종 추론 시 반복적 추론과 도구 호출에 의존하여 계산 예산에 민감하게 반응하며, 인스턴스 간에 학습된 구조를 일관되게 재사용하지 못합니다. 결과적으로 LLM 은 여전히 솔루션 공간에서 largely 비구조화된 탐색을 수행하여 솔루션 길이가 증가함에 따라 계산 자원이 낭비됩니다.

방법론: REACOMP

저자들은 LLM 추론을 직접 개선하는 대신, LLM 추론 흔적 (traces) 을 재사용 가능한 심볼릭 솔버로 컴파일하는 REACOMP 프레임워크를 제안합니다. 이 접근법은 두 가지 명확한 단계로 구성됩니다:

1. 오프라인 솔버 유도

이는 한 번 수행되는 절차로, 코딩 에이전트가 LLM 추론 흔적에서 반복되는 전략과 실패 모드를 추출하여 제한된 도메인 특화 언어 (DSL) 위에서 작동하는 독립형 심볼릭 프로그램 합성기로 정제합니다.

• 흔적 데이터셋: LLM(예: gpt-oss-120b) 이 벤치마크 작업의 작은 하위 집합을 해결하는 과정에서 생성된 추론 흔적 데이터셋을 구성합니다. 이러한 흔적에는 중간 단계, 후보 프로그램, 그리고 결과가 포함되며, 난이도와 성공/실패가 균형을 이루도록 구성됩니다.
• 코딩 에이전트 유도: 코딩 에이전트 (예: Claude Code 또는 Qwen + OpenHands) 는 흔적 데이터셋과 읽기 전용 검증기를 포함하는 샌드박스 환경 내에서 작동합니다. 에이전트는 워크스페이스를 반복적으로 편집하여 솔버 구현체 (예: SOLVER.py) 를 구축합니다.
• 프로세스: 에이전트는 코드 편집을 제안하고 실행한 후, 흔적 데이터셋에서의 성능을 기반으로 솔버를 정제합니다. 에이전트는 테스트 시점에 이용 가능한 입력 - 출력 예제만 관찰하므로, 유도된 솔버는 추론 중 LLM 호출이 필요 없는 독립형 시스템이 됩니다.
• 출력: 독립형 Python 솔버 및 알고리즘 설명 파일.

2. 효율적인 하이브리드 추론

테스트 시, 시스템은 효율성과 정확성의 균형을 맞추기 위해 2 단계 전략을 사용합니다:

1. 심볼릭 1 차 통과: 유도된 심볼릭 솔버 ($S_\phi$) 가 주어진 작업 $D$에 대한 후보 집합을 제안합니다. 만약 후보가 완벽한 보상 ($R=1$) 을 달성하면, LLM 추론 비용이 전혀 들지 않고 즉시 반환됩니다.
2. LLM 폴백: 심볼릭 솔버가 완벽한 솔루션을 찾지 못하면, 시스템은 나머지 "어려운" 사례를 해결하기 위해 표준 LLM 탐색 절차 (Best-of-K 샘플링 또는 직접 피드백 반복 정제) 로 폴백합니다.

이 구조는 솔버의 소규모 1 회성 구축 비용을 많은 0 토큰 실행에 걸쳐 분산시켜, 고비용 LLM 추론을 잔여 사례에만 할당합니다.

주요 기여

1. 유도 방법론: 코딩 에이전트를 사용하여 LLM 추론 흔적에서 재사용 가능한 심볼릭 솔버를 유도하는 새로운 방법. 비구조화된 탐색 흔적을 구조화된 독립형 합성기로 변환합니다.
2. 강력한 독립형 성능: 유도된 솔버들이 강력한 독립형 시스템으로 기능하며, PBEBench-Hard 와 같은 어려운 인스턴스에서 LLM 테스트 시간 확장 (test-time scaling) 을 능가하고 작업당 LLM 추론 비용이 0 임을 입증했습니다.
3. 파레토 우위 하이브리드 파이프라인: 토큰 사용량을 최대 78% 까지 획기적으로 줄이면서 최첨단 결과를 달성하는 신경 - 심볼릭 하이브리드 파이프라인. 각 작업에 코딩 에이전트를 직접 적용하는 기존 접근법을 효과적으로 압도합니다.
4. 제로샷 일반화: 유도된 대부분의 솔버가 실제 세계 분포 (특히 음운 변화의 전방 복원을 다루는 역사 언어학 사례 연구) 에 제로샷으로 일반화됨을 입증했습니다.

실험 결과

저자들은 PBEBench(문자열 변환) 와 SLR-Bench(귀납적 논리 프로그래밍) 에서 REACOMP 를 평가했습니다.

• PBEBench-Lite: 심볼릭 솔버 앙상블은 **91.3%**의 정확도를 달성하여 LLM 베이스라인과 일치하거나 능가했습니다. 하이브리드 추론 (심볼릭 + LLM 폴백) 은 최대 정확도 (93.9%) 를 유지하면서 토큰 사용량을 36% 감소시켰습니다.
• PBEBench-Hard: 장거리 캐스케이드 합성에서 LLM 테스트 시간 확장 (Best-of-K) 은 68.4% 의 정확도를 달성했습니다. 유도된 심볼릭 솔버는 이를 크게 능가하여 "All Symbolic" 앙상블이 **84.7%**의 정확도 (16.3% 포인트 향상) 를 기록했으며, 이는 LLM 추론 비용이 0 입니다. 하이브리드 추론은 이를 **85.8%**까지 추가로 향상시켰으며, LLM 만 사용하는 베이스라인 대비 토큰 사용량을 78% 감소시켰습니다.
• SLR-Bench: 가장 어려운 티어에서 CC 심볼릭 솔버는 **46.8%**의 정확도를 달성하여 o3, GPT-5 와 같은 최첨단 모델과 동일한 성능을 보였으며 추론 비용은 0 이었습니다. 하이브리드 접근법 (DF + CC) 은 하드 티어 정확도를 **58.0%**로 끌어올려 기존 보고된 모든 베이스라인을 능가했습니다. 최상의 하이브리드 (DF + CC + QO) 는 최첨단 모델 비용의 일부만으로 전체 정확도 **86.7%**를 달성했습니다.
• 효율성: 심볼릭 솔버는 매우 효율적이며, 순수 Python 으로 1,000 개 이상의 작업에 대한 추론을 5 분 미만으로 완료하는 반면, LLM 기반 방법은 약 2 일이 소요됩니다.
• 실제 세계 전이: 역사 언어학의 음운 변화 예측을 위한 전방 복원 작업에서, 유도된 솔버는 앙상블 하에 **80.1%**의 정확도를 달성하여 재학습 없이 타당한 언어 규칙을 복원했습니다.

중요성과 주장

이 논문은 REACOMP 가 도메인 일반 솔버 유도를 위한 확장 가능한 경로를 보여준다고 주장합니다. 추론 흔적을 재사용 가능한 심볼릭 구조로 컴파일함으로써, 이 접근법은 독립적인 LLM 샘플링과 장거리 구성 작업 사이의 근본적인 불일치를 해결합니다. 저자들은 다음과 같이 주장합니다:

• 포화 상태 하의 효율성: LLM 정확도가 포화 상태에 근접하는 영역에서 솔버 유도는 정확도보다 효율성 측면에서 주요 이점을 제공합니다.
• 어려운 작업에서의 상호 보완성: 어렵고 장거리인 작업에서 LLM 이 실패하는 부분 (구조화된 탐색 부족) 을 심볼릭 솔버가 탁월하게 수행하고, LLM 은 나머지 작업을 처리하여 상호 보완적인 하이브리드 시스템을 형성합니다.
• 분산 비용: 소규모 1 회성 구축 비용을 많은 0 토큰 실행에 분산시켜, 인스턴스별로 코딩 에이전트를 적용하는 것보다 훨씬 더 파레토 효율적입니다.
• 일반화: 솔버가 보지 못한 분포 (예: 실제 언어 데이터) 로 제로샷 전이할 수 있는 능력은 유도된 알고리즘이 단순한 암기가 아닌 일반화 가능한 구조적 통찰을 포착했음을 시사합니다.

저자들은 솔버 품질이 코딩 에이전트의 능력과 사용된 DSL 의 특정 성질에 민감하다는 한계를 지적합니다. 또한 솔버가 타당한 규칙을 복원하지만, 때로는 컴팩트하고 일반화 가능한 구조보다 검증자를 만족시키는 솔루션을 선호하는 경향이 있어, 향후 보상 함수 정렬 및 솔버 유도 탐색 전략에 대한 연구가 필요하다고 관찰합니다.