기술 요약: 알고리즘적 추론에 있어 코드가 언어보다 더 나은가?

문제 정의

도구 증강 언어 모델(LLM) 시스템에서, 문제를 실행 가능한 코드(외부 도구로 실행을 위임)로 변환하는 것이 복잡한 알고리즘 작업에서 엔드투엔드 자연어(NL) 추론보다 성능이 우수하다는 점은 잘 알려져 있습니다. 그러나 이러한 성능 향상의 원인은 모호합니다. 이전의 비교 연구들은 두 가지 별개의 요인을 혼재하여 다루었습니다:

1. 중간 표현(Intermediate Representation): 자연어 추적(trace)에서 코드 추적으로의 변화.
2. 실행 메커니즘(Execution Mechanism): LLM 기반 시뮬레이션(순전파)에서 결정론적인 외부 실행(예: Python 런타임)으로의 변화.

기존 연구들은 "자연어 추론"을 "코드 + 외부 실행"과 직접 비교했기 때문에, 개선의 원인이 코드의 구조적 특성 때문인지, 아니면 신뢰할 수 있는 외부 실행기 때문인지, 혹은 둘 다인지 분리해낼 수 없었습니다. 본 논문은 다음과 같은 연구 질문을 다룹니다: 코드 표현 자체가 알고리즘적 추론에 있어 본질적으로 우월한 것인가, 아니면 이점의 주된 동력이 신뢰할 수 있는 외부 실행에 있는 것인가?

방법론: 3개 경로 프레임워크 (The Three-Route Framework)

저자들은 표현과 실행을 분리하기 위해, 추론 파이프라인을 **추적 생성(Trace Generation)**과 **실행(Execution)**의 두 단계로 분해하는 체계적인 3개 경로 프레임워크를 제안합니다.

• 경로 1 (직접 NL): LLM이 자연어 사고 사슬(Chain-of-Thought) 추적을 생성하고, 이후 동일한 LLM을 사용하여 추론을 시뮬레이션하여 정답을 도출합니다.
  • 추적(Trace): 자연어.
  • 실행기(Executor): LLM (자연어 시뮬레이션).
• 경로 2 (코드 + NL 시뮬레이션): LLM이 코드 추적(예: Python)을 생성하지만, 이를 외부에서 실행하는 대신, 동일한 LLM이 코드를 자연어로 시뮬레이션하여 정답을 도출합니다.
  • 추적(Trace): 코드.
  • 실행기(Executor): LLM (코드 시뮬레이션).
• 경로 3 (코드 + 솔버 실행): LLM이 경로 2와 동일한 코드 추적을 생성하지만, 이 코드는 결정론적인 외부 Python 런타임에 의해 실행됩니다.
  • 추적(Trace): 코드.
  • 실행기(Executor): 외부 솔버 (결정론적).

실험 설정:

• 벤치마크: 산술, 동적 계획법(DP), 그래프 알고리즘, 문자열 조작, 기하학, 정렬, NP-난해 최적화를 포함하는 40개 작업의 검증 가능한 알고리즘 벤치마크.
• 데이터: 3개의 무작위 시드에 걸친 1,113개의 고유한 문제 인스턴스, 6개의 모델(GPT-4o-mini와 같은 폐쇄형 및 Mixtral-8x22b와 같은 오픈 소스 포함)에서 평가.
• 지표: 0–1 손실 하의 최종 작업 정확도, McNemar 쌍체 통계 테스트 및 클러스터-부트스트랩 신뢰 구간을 통해 분석.

주요 기여

1. 요인의 경험적 분리

이 프레임워크는 특정 변수를 격리하는 쌍별 비교를 가능하게 합니다:

• 경로 1 vs. 경로 2 (표현 격리): LLM 실행기를 고정하고 추적 양식(NL vs. 코드)만 변경함으로써, 저자들은 코드 표현 자체가 이점을 제공하는지 테스트합니다.
• 경로 2 vs. 경로 3 (실행 격리): 코드 추적을 고정하고 실행기(LLM 시뮬레이션 vs. Python 런타임)만 변경함으로써, 저자들은 실행 메커니즘이 성능의 동인인지 테스트합니다.

2. 이론적 정형화 (의사결정 이론 모델)

저자들은 코드가 자연어의 "정규화(canonicalization)"라는 직관을 정형화합니다. 그들은 다음과 같은 선형 모델을 제안합니다:

• 두 추적은 모두 결정에 유의미한 알고리즘 정보(예: 재귀 관계)를 담고 있는 **핵심(core, $B$)**을 공유합니다.
• 자연어 추적은 정답을 바꾸지는 않지만 의역, 장황함, 문체적 선택과 같은 추가적인 **불필요한 변이(nuisance variation, $\eta_N$)**를 포함합니다.
• 정리: 이 모델 하에서, 코드는 표현 측면에서 자연어에 비해 열등하지 않습니다(representation-non-inferior). 자연어의 추가적인 불필요한 변이는 추가적인 신호를 제공하지 않으면서 유한 샘플 학습자의 위험(오류)을 증가시킵니다. 따라서 핵심 정보가 보존된다면 표현을 바꾸는 것만으로는 유의미한 이득을 얻을 수 없습니다.

3. 재구성 개입 (Reconstruction Intervention)

이론을 경험적으로 검증하기 위해, 저자들은 모델이 생성한 코드 추적을 고정된 변환을 사용하여 자연어로 다시 번역하는 "재구성 개입"을 수행합니다. 그 결과, 이 번역된 NL 추적이 원래의 NL 추적과 대등한 성능을 회복한다는 것을 발견했습니다. 이는 코드가 모든 결정 유의미한 정보를 유지하고 있으며, NL 추론에서의 "손실"이 누락된 알고리즘 콘텐츠 때문이 아니라 불필요한 변이의 존재 때문임을 확인시켜 줍니다.

결과

성능 비교

40개 작업 벤치마크에 대한 결과는 다음과 같습니다:

• 경로 1 (NL + NL): 17.21% 정확도.
• 경로 2 (코드 + NL 시뮬레이션): 17.37% 정확도.
• 경로 3 (코드 + Python 실행): 48.84% 정확도.

통계적 결과:

• 경로 1 vs. 경로 2: 차이는 **+0.15 퍼센티지 포인트(pp)**이며, 95% 신뢰 구간은 $[-0.30, +0.61]$ pp ($p=0.39$)입니다. 이는 실행기가 동일한 LLM일 때 자연어 추론과 코드 시뮬레이션 사이에 통계적으로 유의미한 차이가 없음을 나타냅니다.
• 경로 2 vs. 경로 3: 차이는 +31.47 pp이며, 95% 신뢰 구간은 $[+29.20, +33.71]$ pp ($p < 0.001$)입니다. 이는 코드 추적이 동일하더라도 결정론적인 외부 실행이 LLM 시뮬레이션에 비해 압도적이고 통계적으로 유의미한 우위를 가짐을 나타냅니다.

난이도 스케일링

작업 난이도(자릿수나 행렬 크기와 같은 파라미터로 제어됨)가 높아짐에 따라, 경로 3은 높은 정확도를 유지하는 반면 경로 1과 2는 크게 저하됩니다.

회복 분석 (Recovery Analysis)

저자들은 경로 2(시뮬레이션)가 성공했지만 경로 3(실행)은 실패한 경우("회복 질량")를 분석합니다.

• 회복 질량 (Recovery Mass): 1.61% (LLM이 결함이 있는 코드를 올바르게 시뮬레이션하거나 실행 실패를 무시하는 경우).
• 실행 승리 질량 (Execution-Win Mass): 33.08% (실행은 성공했으나 LLM 시뮬레이션은 실패한 경우).
  이는 LLM이 실행 오류를 보완하는 경우가 드물다는 것을 확인시켜 줍니다. 반대로, 외부 솔버는 LLM의 코드 시뮬레이션 능력보다 일관되게 우수한 성능을 보입니다.

의의 및 주장

본 논문은 평가된 설정의 알고리즘적 추론에 대해 다음과 같이 주장합니다:

1. 표현은 병목이 아니다: 중간 단계에서 코드 추적을 사용하는 개입은 실행 메커니즘이 LLM으로 남아있는 한 자연어 추적에 비해 성능을 유의미하게 개선하지 못합니다. 경로 1과 경로 2 사이의 성능 격차는 미미합니다.
2. 실행이 병목이다: 도구 증강 시스템에서 관찰되는 성능 향상의 주된 동력은 코드 표현 자체의 구조적 특성이 아니라 신뢰할 수 있는 외부 실행기입니다.
3. 도구 사용의 메커니즘: 코드 기반 도구 사용의 이점은 생성된 추적을 결정론적인 솔버로 전달할 수 있게 해준다는 점에서 발생합니다. 코드 표현은 그 자체로 우월한 추론 기질로서 작용하기보다는, 신뢰할 수 있는 실행을 가능하게 하는 매개체 역할을 수행합니다.

저자들은 검증 가능한 답이 있는 알고리즘 작업의 경우, 도구 사용의 핵심적인 이점은 자연어보다 코드 형식이 본질적으로 우월하기 때문이 아니라, 결정론적인 환경에 실행을 위임할 수 있는 능력에 있다고 결론짓습니다.