Reasoning Models Lose their Way with Long Deduction

Motivation

• Known: 기존 연구(RuleTaker, ProofWriter, ProntoQA)는 자연어 기반 규칙-사실 query answering 벤치마크를 통해 proof depth가 증가할수록 모델 성능이 저하됨을 보였으나, 최대 depth가 5 정도로 얕은 수준에 그쳤다. 또한 LongBench-v2, RULER, HELMET 같은 long-context 벤치마크는 retrieval과 QA를 주로 다루며 reasoning과 retrieval을 독립적인 축으로 취급했다.
• Gap: 기존 벤치마크들은 얕은 reasoning depth(최대 5)에 머물러 있어 frontier LLM의 진정한 long-horizon deductive reasoning 한계를 드러내지 못했고, long-context 벤치마크는 모든 정보가 필수적으로 사용되는 설정이 아니어서 reasoning과 retrieval을 동시에 스트레스 테스트하지 못했다. 또한 자연어 기반 벤치마크는 모델이 사전 지식(content effects)에 의존할 수 있어 순수한 추론 능력 평가에 한계가 있었다.
• Why: reasoning model들이 수학·코딩 등에서 인상적인 성능을 보이는 상황에서, 이들이 단순 검색을 넘어 실제로 긴 문맥에서 깊은 연역적 추론을 수행할 수 있는지 밝히는 것은 LLM의 근본적 추론 능력의 한계와 스케일링 특성을 이해하는 데 중요하다.
• Approach: Prolog 스타일 논리 프로그램에서 query가 증명 가능한지 여부를 묻는 합성 문제를 생성하는 프레임워크를 구축하여, reasoning depth와 context length를 정밀하게 통제하며 8개 frontier reasoning model의 성능을 체계적으로 평가한다.

Achievement

Figure 3. Model accuracy deteriorates with longer depths, with most models sharply declining after depth 10. Random chan

1. ProloNg 벤치마크 구축: depth 0-22에 걸쳐 2,400개의 Prolog 논리 프로그램 문제를 생성했으며, 최대 문맥 길이는 62k 토큰에 달한다.
2. 정밀한 복잡도 제어 프레임워크: GENERATERULE 알고리즘을 통해 DAG 구조의 논리 프로그램을 depth와 breadth를 독립적으로 통제하며 생성하고, swi-prolog 인터프리터로 정답 레이블의 정확성을 검증했다.
3. 체계적 실패 패턴 발견: Claude-Opus-4.7, GPT-5.5, GPT-5.4-mini, DeepSeek-V4-Pro, Kimi-K2.6, Qwen3.6-27B, Qwen3.5-27B, Qwen3.5-4B 등 8개 frontier reasoning model을 평가한 결과, 최고 성능 모델인 GPT-5.5조차 depth-20에서 67%로 저하되었고, 대부분의 모델이 depth-10을 넘어서면 chance 수준 이하로 떨어짐을 보였다.

How

Figure 1. Example problem of depth-4, with an excerpt from the

• Prolog 스타일 definite logic program을 DAG로 표현하고, 술어(predicate)의 arity를 최대 2로, 각 술어는 하나의 규칙으로만 정의하도록 제한하여 단일 체인 형태의 추론 경로를 보장함
• GENERATERULE 함수를 재귀적으로 호출하여 목표 predicate로부터 규칙과 최소한의 사실 집합을 생성하고, Poisson(λ=2.5) 분포로 각 규칙의 breadth를 샘플링
• provable query와 대응하는 unprovable query(사실 하나를 변형하여 생성)를 짝지어 균형 잡힌 데이터셋을 구성
• depth당 100개 프로그램(각 provable/unprovable 샘플 포함, 총 200개 샘플)을 depth 0부터 22까지(홀수 depth 제외) 생성하여 총 2,400개 샘플 확보
• swi-prolog 인터프리터로 레이블 정확성을 검증하고, canonical shape 표현으로 문맥 구조적 다양성을 확인
• 5개 모델 패밀리에 속한 8개 reasoning model(Claude, GPT, DeepSeek, Kimi, Qwen 계열)을 대상으로 depth별 정확도, 답변 추출 비율, provability별 정확도 등을 분석

Originality

• 자연어 대신 Prolog를 사용하여 모델이 사전 지식이나 content effect에 의존하지 않고 순수한 형식적 추론만으로 문제를 풀도록 설계한 점
• reasoning depth와 context length를 동시에 정밀하게 통제할 수 있는 생성 프레임워크(GENERATERULE 알고리즘)를 제안한 점
• 기존 벤치마크(최대 depth 5)보다 훨씬 깊은 depth 22까지 확장하여, 모든 규칙과 사실이 증명에 필수적인(불필요한 정보가 없는) 설정에서 long-context reasoning과 retrieval을 동시에 스트레스 테스트한 점

Limitation & Further Study

• 논리 프로그램이 arity 2 이하, 규칙당 단일 정의, 루프/재귀 없음 등으로 제한되어 있어 실제 응용에서 나타나는 복잡한 backtracking이나 다중 규칙 정의 상황을 다루지 못함
• 문제의 난이도가 depth 외에 breadth, shape 다양성 등 다른 요인에도 영향을 받을 수 있으나 이에 대한 세밀한 통제나 분석이 제한적으로 보임
• 합성 데이터이기 때문에 실제 자연어 기반 태스크나 실세계 reasoning 문제로의 일반화 가능성에 대한 추가 검증이 필요함
• 발췌된 내용상 실패의 구체적 원인(예: variable binding 오류, subgoal tracking 실패 등)에 대한 세밀한 오류 분석이 본문에서 충분히 다뤄지지 않은 것으로 보이며, 후속 연구에서는 이러한 실패 모드를 세분화하여 분석할 필요가 있음

Evaluation

총평: 단순하지만 정교하게 통제된 합성 벤치마크를 통해 frontier reasoning model들의 long-horizon deductive reasoning의 근본적 한계를 명확히 드러낸 의미 있는 연구이며, 향후 reasoning model 개발과 평가에 중요한 진단 도구로 활용될 수 있다.