기술 요약: 강화된 사고 그래프 (RGoT)

문제 제기

대규모 언어 모델 (LLM) 은 Chain of Thought(CoT), Tree of Thoughts(ToT), Graph of Thoughts(GoT) 와 같은 프롬프팅 패러다임을 통해 의도적인 문제 해결에서 상당한 능력을 입증해 왔습니다. GoT 는 사고를 임의의 그래프로 구조화하여 집계와 복잡한 추론을 가능하게 하는 일반화된 프레임워크를 제공하지만, 기존 구현은 정적이며 수동으로 정의된 연산 그래프에 의존합니다.

이 수동 정의는 두 가지 주요 한계를 제시합니다:

1. 접근성: GoT 그래프를 구성하려면 문제 해결에 대한 심층적인 지식과 연산의 특정 순서 이해가 필요하여 사용자의 진입 장벽이 높습니다.
2. 적응성: 정적 그래프는 경직되어 있습니다. 입력 인스턴스의 다양한 복잡도나 LLM 출력의 비결정론적이고 엔트로피적인 특성에 적응할 수 없습니다. 결과적으로 특정 복잡도 수준을 위해 설계된 그래프는 다른 특성을 가진 입력에 적용될 때 실패할 수 있습니다.

Ha et al.(2024) 의 선행 연구는 GoT 를 자동화하려는 시도를 했으나, 이는 그래프를 구성하는 데 있어 기반 LLM 의 논리적 능력에 의존합니다. 본 논문은 추론 토폴로지 자체를 생성하는 데 LLM 의 계획 능력을 의존하지 않는 접근법의 필요성을 다룹니다.

방법론

저자들은 **강화된 사고 그래프 (Reinforced Graph of Thoughts, RGoT)**를 제안합니다. 이는 인간이 정의한 사용 가능한 연산 집합으로부터 강화 학습 (RL) 을 활용하여 연산 그래프를 적응적으로 생성하는 자동화 접근법입니다.

핵심 프레임워크 구성 요소

시스템은 **연산 그래프 (Graph of Operations, GoO)**와 **사고 그래프 (Graph of Thoughts, GoT)**를 분리합니다:

• 연산 그래프 (GoO): 연산의 순서와 구조를 정의하는 방향성 비순환 그래프 (DAG) 입니다. 최대 깊이 ($d_{max}$) 와 최대 너비 ($b_{max}$) 로 제약받습니다. 수렴을 보장하기 위해 발산 차단 깊이 ($d_{\neg div}$) 가 강제되며, 이를 지나면 그래프는 단일 싱크 (sink) 로 수렴해야 합니다.
• 사고 그래프 (GoT): LLM 사고가 생성되는 실제 실행 추적입니다. 각 사고는 이를 생성한 연산을 참조합니다.
• 연산: 프롬프트 연산(LLM 호출) 또는 실행 연산(프로그래밍 함수) 으로 정의됩니다. **점수 연산 (Score Operation)**은 사고의 품질을 평가하여 수치 점수를 반환합니다.

강화 학습 공식화

RGoT 에이전트는 GoO 를 층별로 구성하기 위해 맞춤형 RL 환경 내에서 작동합니다.

• 상태 공간 ($S$): 현재 그래프 깊이, 너비, 작업 복잡도, 지역 복잡도, 현재 그래프의 연산 시퀀스, 이전 행동, 이전 점수를 포함하는 이산 공간들의 조합입니다.
• 행동 공간 ($A$): stop(그래프 구성 종료), backtrack(싱크 층 제거), append(o)(연산 $o$ 를 가진 새 층 추가) 를 포함하는 이산 행동들입니다.
• 보상 함수: 과도한 깊이를 패널티로 부과하고 유효한 연산을 보상하며, 작업 성공 (최종 상태) 에 대해 상당한 긍정적 보상을 제공하도록 보상 설계 (reward shaping) 를 통해 설계되었습니다.
• 시뮬레이션: 실제 LLM 호출로 인한 높은 훈련 비용을 완화하기 위해 LLM 의 행동을 시뮬레이션합니다. 주어진 복잡도 $c$에서 연산의 성공 확률은 확률 $P(c)$를 가진 베르누이 실험으로 모델링되며, 이는 각 복잡도 수준마다 대상 LLM(예: gpt-3.5-turbo-0125) 을 100 회 프롬프팅하여 경험적으로 추정됩니다.

실험 설정

저자들은 RGoT 를 다섯 가지 작업에서 평가했습니다:

1. 리스트 합계 (Sum List): 정수 리스트의 합계 계산 (주요 예시).
2. 리스트 정렬 (Sort List): 정수 정렬.
3. 집합 교집합 (Intersect Set): 집합 교집합 찾기.
4. 키워드 카운트 (Count Keywords): 텍스트 내 키워드 발생 횟수 계산.
5. 문서 병합 (Merge Documents): 유지율을 최대화하고 중복을 최소화하면서 문서 병합.

실험에는 2 층 네트워크 아키텍처 (64 유닛) 를 사용한 근접 정책 최적화 (Proximal Policy Optimization, PPO) 알고리즘이 활용되었습니다. 에이전트는 특정 복잡도 범위에서 훈련된 후, 분포 내 (in-distribution) 및 분포 외 (out-of-distribution, 더 높은 복잡도) 인스턴스 모두에서 평가되었습니다.

주요 결과

• 적응적 구성: RL 에이전트는 작업 복잡도에 적응하는 연산 그래프를 구성하는 방법을 성공적으로 학습했습니다. 복잡도가 증가함에 따라 에이전트는 문제를 분해하기 위해 그래프의 분기 (발산) 와 깊이를 자동으로 증가시켰으며, 이는 명시적으로 프로그래밍된 것이 아니라 보상 신호를 통해 학습된 행동입니다.
• 기선 대비 성능: RGoT 에이전트는 표준 입력 - 출력 (IO) 프롬프팅 기선보다 현저히 우수한 성과를 보였습니다. IO 전략은 복잡도가 LLM 의 직접적 능력을 초과하면 실패하는 반면, RGoT 에이전트는 작업을 분해함으로써 높은 성공률을 유지했습니다.
• 일반화: 에이전트는 훈련 중에 본 것보다 높은 복잡도의 분포 외 복잡도를 해결할 수 있는 능력을 입증했으며, 총 평균 해결률은 $0.7512 \pm 0.1089$였습니다.
• 분산: 저자들은 특히 분포 외 영역에서 다양한 무작위 시드 간 에이전트 성능에 분산이 있음을 관찰했습니다. 이는 고복잡도에서의 희소 보상 신호와 PPO 의 온-정책 (on-policy) 특성으로 인해 에이전트가 초기 비최적 궤적 약속에서 회복하는 능력이 제한되기 때문으로 귀결됩니다.

중요성과 주장

본 논문은 언어 모델의 계획 능력이나 작업 속성을 이해하는 능력에 의존하지 않고 연산 그래프를 생성하고 탐색함으로써 사고 그래프를 구성하는 자동화 접근법을 제시한 최초의 연구라고 주장합니다.

주요 기여점은 다음과 같습니다:

1. GoT 자동화: 수동 그래프 정의의 필요성을 제거하여 사용 가능한 연산 집합만 정의하면 되는 사용자에게 GoT 패러다임을 더 접근 가능하게 만듭니다.
2. 적응성: 자동화된 에이전트가 입력 복잡도에 기반하여 동적으로 추론 토폴로지를 조정하여 정적 그래프의 경직성을 극복함을 입증했습니다.
3. 모델 중립성: 프레임워크는 특정 LLM 에 중립적입니다. LLM 의 성공 확률을 시뮬레이션함으로써 시스템은 비용 효율적으로 훈련될 수 있으며, 다양한 능력 범위를 가진 모델을 포함한 다양한 모델에 적용될 수 있습니다.
4. 상호 보완성: 저자들은 RGoT(추론 토폴로지 구조화) 가 외부에서 검색된 지식을 구조화하는 지식 사고 그래프 (KGoT) 와 상호 보완적이라고 지적하며, 향후 결합된 응용 가능성에 대해 언급했습니다.

저자들은 겸손한 어조를 유지하며, 이 접근법이 특정 제약 조건 하에서 정의된 작업에 대해 유망한 결과를 보이지만, 성능의 분산과 훈련을 위한 시뮬레이션 의존성은 고려해야 할 영역임을 인정합니다. 그들은 모든 프롬프팅 방법보다 보편적으로 우월하다고 주장하지는 않지만, 복잡하고 분해 가능한 작업을 위한 적응형 자동화 그래프 구성의 구체적인 유용성을 강조합니다.