State Representation and Termination for Recursive Reasoning Systems

Recursive reasoning systems alternate between acquiring new evidence and refining an accumulated understanding. Two design choices are typically left implicit: how to represent the evolving reasoning state, and when to stop iterating. This paper addresses both. We represent the reasoning state as an epistemic state graph encoding extracted claims, evidential relations, open questions, and confidence weights. We define the order-gap as the distance between the states reached by expand-then-consolidate versus consolidate-then-expand; a small order-gap suggests that the two orderings agree and further iteration is unlikely to help. Our main result gives a necessary and sufficient condition for the linearised order-gap to be non-degenerate near the fixed point, showing when the criterion is informative rather than algebraically vacuous. This is a local condition, not a global convergence guarantee. We apply the framework to recursive reasoning systems and sketch its application to agent loops, tree-of-thought reasoning, theorem proving, and continual learning.

📋 한 줄 요약

**[추론 시스템/이론]** 재귀적 추론 시스템에서 "지금 상태를 어떻게 표현할 것인가"와 "언제 멈출 것인가"를 epistemic state graph와 order-gap 개념으로 정형화한 이론 프레임워크 제시.

🎯 핵심 기여도

재귀 추론의 상태를 주장(claims), 증거 관계, 미해결 질문, 신뢰 가중치로 구성된 epistemic state graph로 표현
expand-then-consolidate와 consolidate-then-expand의 결과 차이를 "order-gap"으로 정의
작은 order-gap이 추가 반복 불필요성을 시사한다는 종료 기준 제시
선형화된 order-gap이 고정점 근처에서 비퇴화(non-degenerate)일 필요충분조건을 증명

💡 핵심 아이디어

재귀 추론 시스템은 (1) 새 증거를 획득하는 expand 단계와 (2) 누적된 이해를 정리하는 consolidate 단계를 교차한다. 두 단계의 순서를 바꿨을 때 결과가 거의 같다면(작은 order-gap) 시스템은 의미 있는 고정점에 가까워졌다고 볼 수 있어, 이를 자연스러운 종료 신호로 사용할 수 있다.

🔬 기술적 접근법

**모델/방법론**: Epistemic State Graph — 추출된 주장·증거 관계·열린 질문·신뢰 가중치를 노드/엣지/속성으로 인코딩
**핵심 기법**: (1) order-gap 정의: 두 가지 단계 순서(expand→consolidate vs consolidate→expand)의 상태 거리, (2) 고정점 근처에서 선형화된 order-gap의 비퇴화 필요충분조건 증명 — 종료 기준이 대수적으로 자명하지 않고 정보를 갖는 조건을 규명
본 정리는 지역적(local) 조건이며 전역 수렴 보장은 아님을 명시

📊 주요 결과

order-gap의 선형화 비퇴화 조건을 필요충분조건으로 정리 — 종료 기준이 실효성을 갖는 영역 규명
적용 사례 스케치: 에이전트 루프, tree-of-thought 추론, 정리 증명, 연속 학습(continual learning)
상태 표현과 종료 기준을 명시적으로 분리해 시스템 설계의 두 결정 축을 정형화

💭 의의 및 한계

**의의**: LLM 에이전트·자동 정리 증명기·연속 학습 등 점점 더 길어지는 추론 루프에서, 멈춤 결정이 휴리스틱에 의존하던 관행을 이론적 기준으로 전환할 수 있는 토대를 제공한다. **한계**: 결과는 지역 조건에 한정되어 전역 수렴 보장이 아니며, 실제 LLM 기반 시스템에서 epistemic state graph를 신뢰성 있게 추출·유지하는 엔지니어링 비용은 별개 과제로 남는다.

🚀 실용적 활용

LLM 에이전트의 자기 반성 종료 시점 자동 결정
연구 보조 에이전트의 "다음 라운드가 필요한가?" 판단 모듈
정리 증명·tree-of-thought 탐색에서 가지치기 기준