[논문 리뷰] Generative Recursive Reasoning (GRAM)

TL;DR

본 논문은 기존 결정론적 재귀 추론 모델의 한계를 극복하기 위해 **생성적 재귀 추론 모델(Generative Recursive Reasoning Model, GRAM)**을 제안합니다. GRAM은 재귀 과정을 확률적으로 모델링하여, 단일 경로가 아닌 다양한 추론 경로를 동시에 탐색합니다. 이를 통해 여러 정답이 존재하거나 불확실성이 높은 문제에서 기존 모델을 압도하는 성능을 보입니다. 특히, 복잡한 제약 만족 문제인 스도쿠-익스트림에서 97%의 정확도를 달성했으며, 추론의 깊이(재귀 횟수)와 너비(병렬 샘플 수)를 조절하는 스케일링을 통해 성능과 효율성을 유연하게 제어할 수 있음을 입증했습니다.

1. 연구 배경: 재귀 추론의 가능성과 한계

인공지능 분야에서 복잡한 문제를 해결하기 위한 추론 방식은 크게 두 가지로 나뉩니다.

자기회귀(Autoregressive) 모델: Transformer(LLM)처럼 순차적으로 토큰을 생성하여 해답을 구축합니다. 이는 점진적인 문제 해결에 강력하지만, 전체적인 구조를 한 번에 파악하고 수정하기 어렵고 계산 비용이 높습니다.
재귀 추론(Recursive Reasoning) 모델: 문제 전체에 대한 잠재적 해답(latent state)을 설정하고, 이를 반복적으로 정제(refine)하여 최종 해답을 도출합니다. 이는 전체적인 맥락을 유지하며 효율적인 계산이 가능하지만, 기존 모델들은 대부분 **결정론적(deterministic)**입니다.

결정론적 재귀 모델은 동일한 입력에 대해 항상 똑같은 단일 추론 경로를 따릅니다. 이는 정답이 하나로 정해진 문제에서는 효율적일 수 있지만, 다음과 같은 한계를 가집니다.

다중 해답 문제: N-Queens처럼 유효한 해답이 여러 개인 경우, 단 하나의 해답만 찾거나 아예 찾지 못할 수 있습니다.
불확실성: 추론 초기에 잘못된 경로를 선택하면 되돌리기 어려워 국소 최적해(local optima)에 빠지기 쉽습니다.

이러한 한계를 극복하기 위해, 본 연구는 재귀 추론 과정에 확률적 생성 모델의 개념을 도입한 GRAM을 제안합니다. GRAM은 마치 탐정이 여러 용의자를 동시에 수사선상에 올려놓고 가능성을 저울질하듯, 다양한 가설(추론 경로)을 병렬적으로 탐색하여 더 강건하고 유연한 문제 해결을 가능하게 합니다.

2. 관련 연구와의 차별점

GRAM은 여러 선행 연구의 아이디어를 융합하고 발전시켰습니다.

Transformer 기반 모델: 순차적 생성에 강점을 보이지만, GRAM은 전체 해답을 반복적으로 개선하는 병렬적 정제 방식에 집중하여 효율성을 높입니다.
변분 추론(Variational Inference): 불확실성을 모델링하는 VAE의 원리를 재귀 추론에 접목했습니다. GRAM은 잠재 상태의 전이 과정 자체를 확률적으로 모델링하여 동적인 추론 경로를 생성한다는 점에서 차별화됩니다.
Tree-of-Thoughts (ToT): LLM에서 다양한 사고 경로를 탐색하는 ToT와 철학적으로 유사합니다. 하지만 GRAM은 LLM에 의존하지 않는 독립적인 아키텍처로, 특정 구조를 가진 문제(예: 스도쿠, 그래프 문제)에 더 특화되고 효율적으로 설계되었습니다.

3. 핵심 기여

확률적 다중 경로 추론: 재귀 추론 과정을 확률적 잠재 변수 모델로 공식화하여, 단일 경로의 한계를 넘어 다양한 해답 공간을 효과적으로 탐색하는 새로운 패러다임을 제시했습니다.
효율적인 추론 스케일링: 추론의 **깊이(depth, 재귀 스텝 수)**와 **너비(width, 병렬 샘플 수)**를 조절하여 문제의 복잡도와 가용 자원에 맞춰 성능을 유연하게 확장할 수 있습니다. 너비를 늘리면 더 넓은 탐색이 가능해져 정확도가 향상됩니다.
다중 해답 문제 해결 능력: N-Queens와 같은 문제에서 거의 모든 유효한 해답을 찾아내는 높은 정확도(accuracy)와 커버리지(coverage)를 동시에 달성했습니다.
뛰어난 무조건부 생성 능력: 별도의 조건 입력 없이도 유효한 스도쿠 보드나 MNIST 숫자 이미지를 생성하는 능력을 보여주며, 모델이 데이터의 기저 분포를 성공적으로 학습했음을 입증했습니다.

4. 제안 방법론: GRAM의 작동 원리

GRAM은 재귀 추론을 확률적 잠재 변수 생성 모델로 재구성합니다. 핵심 아이디어는 결정론적 업데이트에 확률적 노이즈를 더해 다양한 추론 경로를 생성하는 것입니다.

모델 아키텍처

GRAM은 크게 세 부분으로 구성됩니다.

인코더(Encoder): 입력 문제(예: 미완성 스도쿠 보드)를 잠재 상태로 변환합니다.
재귀 코어(Recursive Core): 모델의 핵심으로, 잠재 상태를 $T$ $T$ 번 반복적으로 정제합니다. 이 코어는 두 종류의 잠재 상태를 유지합니다.
- 상위 상태 ( $h$ ): 문제에 대한 전역적, 추상적 정보를 담는 상태. 확률적 전이를 통해 다양한 가설을 탐색합니다.
- 하위 상태 ( $l$ ): 지역적, 구체적 정보를 담는 상태. 결정론적으로 업데이트되며 상위 상태의 가설을 구체화합니다.
디코더(Decoder): 최종적으로 정제된 잠재 상태를 인간이 이해할 수 있는 해답(예: 완성된 스도쿠 보드)으로 변환합니다.

핵심 메커니즘: 확률적 잠재 전이

GRAM의 추론 과정은 다음과 같은 확률적 상태 업데이트를 통해 이루어집니다. $t$ 번째 스텝에서 상위 상태 $h_t$ 는 이전 상태 $h_{t-1}$ 과 현재 하위 상태 $l_t$ 를 기반으로 업데이트됩니다.

h_t \sim p_\theta(h_t | h_{t-1}, l_t) = \mathcal{N}(f_H(h_{t-1}, l_t), \sigma^2 I)

$f_H(\cdot)$ : 결정론적 업데이트를 수행하는 신경망(재귀 코어의 일부)입니다.
$\mathcal{N}(\cdot, \sigma^2 I)$ : 평균이 $f_H$ 의 결과이고 분산이 $\sigma^2$ 인 정규분포입니다. 이 분포에서 $h_t$ 를 샘플링함으로써 확률적 탐색이 가능해집니다. 이 작은 '흔들림'이 모델이 다른 경로를 탐색하도록 유도하는 원동력입니다.

학습 목표: ELBO 최적화

GRAM은 변분 오토인코더(VAE)와 유사하게 **증거 하한(Evidence Lower Bound, ELBO)**을 최대화하도록 학습됩니다. 전체 잠재 경로를 $\tau = (h_1, ..., h_T)$ 라고 할 때, 목적 함수는 다음과 같습니다.

\log p_\theta(y | x) \geq \mathbb{E}_{q_\phi(\tau|x,y)}[\log p_\theta(y | \tau,x)] - \text{KL}(q_\phi(\tau | x,y) || p_\theta(\tau | x))

첫 번째 항 (재구성 손실): 주어진 잠재 경로 $\tau$ 를 통해 최종 정답 $y$ 를 얼마나 잘 복원하는지를 측정합니다. 모델이 정답을 생성하도록 유도합니다.
두 번째 항 (KL 발산): 근사 사후분포 $q_\phi$ 가 사전분포 $p_\theta$ 와 얼마나 유사한지를 측정하는 정규화 항입니다. 모델이 너무 복잡한 분포를 학습하지 않도록 제어하고, 탐색 공간을 부드럽게 만듭니다.

5. 실험 및 결과 분석

GRAM의 성능은 스도쿠-익스트림, 추상 추론(ARC-AGI), N-Queens, 그래프 색칠 등 다양한 구조적 추론 문제에서 검증되었습니다.

데이터셋: Sudoku-Extreme, ARC-AGI, N-Queens, Graph Coloring, MNIST
비교 모델: Transformer (TRM), Hierarchical Transformer (HRM) 등 기존 결정론적/자기회귀 모델

주요 실험 결과

모델	스도쿠-익스트림 정확도 (%)	N-Queens 정확도 (%)	MNIST 생성 유효성 (%)
GRAM	97.0	99.7	99.05
TRM (Transformer)	87.4	85.0	91.33
HRM	55.0	75.0	85.00

스도쿠-익스트림: 복잡한 제약 조건이 있는 이 문제에서 GRAM은 97.0%라는 압도적인 정확도를 기록하며, 결정론적 모델이 빠지기 쉬운 오류를 확률적 탐색으로 극복함을 보여주었습니다.
N-Queens: 수많은 정답이 존재하는 이 문제에서 99.7%의 정확도를 달성했습니다. 이는 GRAM이 다양한 유효 해답을 폭넓게 탐색하고 찾아내는 데 매우 효과적임을 시사합니다.
추론 스케일링: 추론 시 병렬 샘플 수(너비)를 늘릴수록 성능이 꾸준히 향상되는 것을 확인했습니다. 예를 들어, 스도쿠 문제에서 샘플 수를 1개에서 1024개로 늘렸을 때 정확도가 87%에서 97%로 상승했습니다. 이는 계산 자원을 추가하여 성능을 높일 수 있는 실용적인 확장성을 의미합니다.

6. 강점 및 한계점

강점

유연성: 다중 해답, 불확실성이 높은 문제에서 강건한 성능을 보입니다.
확장성: 추론의 깊이와 너비를 조절하여 성능과 비용의 트레이드오프를 제어할 수 있습니다.
효율성: 전체적인 해답을 한 번에 정제하므로, 긴 시퀀스를 생성해야 하는 자기회귀 모델보다 특정 유형의 문제에서 더 효율적일 수 있습니다.

한계점

튜닝의 복잡성: VAE 기반 모델의 특성상 KL 발산 가중치 등 추가적인 하이퍼파라미터 튜닝이 필요합니다.
계산 비용: 추론 시 너비(병렬 샘플 수)를 늘리면 정확도가 높아지지만, 그에 비례하여 계산 비용이 증가합니다.
보편성의 한계: 구조적 추론 문제에 특화되어 있어, 자유로운 형식의 텍스트 생성과 같은 일반적인 자연어 처리 태스크에서는 LLM이 더 적합할 수 있습니다.

7. 향후 연구 및 실무 적용 가이드

향후 연구 방향

LLM과의 결합: GRAM을 LLM의 추론 모듈로 활용하여, LLM이 복잡한 계획이나 수학 문제 풀이 시 여러 가능성을 체계적으로 탐색하도록 돕는 하이브리드 모델을 연구할 수 있습니다.
더 정교한 확률 모델: 단순한 가우시안 분포 외에 더 복잡한 사전분포를 도입하여, 특정 문제 도메인의 구조를 더 잘 반영하는 모델을 개발할 수 있습니다.
강화학습과의 연동: GRAM이 생성한 다양한 추론 경로를 강화학습 에이전트의 행동 정책으로 활용하여, 보상을 최대화하는 최적의 경로를 학습하는 연구도 가능합니다.

실무 적용 가이드

언제 사용해야 하는가?:
1. 유효한 해답이 여러 개인 문제 (e.g., 경로 계획, 스케줄링 최적화)
2. 초기 선택이 결과에 큰 영향을 미치는 복잡한 제약 만족 문제
3. 결정론적 탐색이 국소 최적해에 쉽게 빠지는 문제
어떻게 활용할 것인가?:
- 문제의 난이도와 요구되는 정확도에 따라 **추론 너비(width)**를 조절하세요. 간단한 문제는 작은 너비로 빠르게 해결하고, 어려운 문제는 너비를 늘려 탐색 공간을 넓히는 것이 효과적입니다.
- 초기 모델 학습 후, 추론 단계에서 너비 스케일링만으로 추가 학습 없이 성능을 향상시킬 수 있다는 점을 적극 활용할 수 있습니다.

8. 결론

GRAM은 기존 재귀 추론 모델의 결정론적 한계를 확률적 다중 경로 탐색이라는 새로운 접근법으로 극복했습니다. 이는 복잡하고 불확실성이 높은 문제 해결에 있어 AI의 추론 능력을 한 단계 끌어올린 중요한 기여입니다. GRAM은 단순히 하나의 정답을 찾는 것을 넘어, 가능한 해답의 공간을 탐색하고 이해하는 방향으로 나아가는 생성 모델의 미래를 보여줍니다.

9. 참고 자료

논문 원문: Generative Recursive Reasoning
공식 코드 저장소: https://github.com/ahn-lab/gram

[논문 리뷰] Generative Recursive Reasoning