Graph of Thoughts: 그래프 구조로 LLM의 정교한 문제 해결
Digest: Tree of Thoughts(ToT)는 추론을 트리로 확장했지만, 분리된 추론 경로를 다시 합치는(merge) 것은 불가능하다. Graph of Thoughts(GoT)는 이 한계를 극복하여 LLM의 사고를 **임의의 방향 그래프(DAG)**로 모델링한다. 핵심 혁신은 Aggregation(합류) 연산: 여러 사고 노드를 하나로 결합하여 분할정복(divide-and-conquer) 패턴을 LLM 추론에 최초로 도입한 것이다. 또한 **Refinement(자기 루프)**로 사고의 반복 개선이 가능하다. 정렬 과제에서 ToT 대비 62% 품질 향상 + 31% 비용 절감을 동시에 달성했으며, 이론적으로도 GoT가 ToT와 동일한 낮은 지연 시간(latency)에서 **N배 더 큰 정보량(volume)**을 활용할 수 있음을 증명했다.
메타데이터
| 항목 | 내용 |
|---|---|
| 제목 | Graph of Thoughts: Solving Elaborate Problems with Large Language Models |
| 저자 | Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger 외 7명 |
| 소속 | ETH Zurich |
| 연도 | 2023 |
| 발표 | AAAI 2024 |
| 링크 | arXiv |
| 키워드 | Graph of Thoughts, Aggregation, Refinement, Divide-and-Conquer, Prompting |
왜 이 연구를 하는가?
핵심 질문
LLM 추론 구조를 트리 너머 임의의 그래프로 확장하면, 분할정복·합류·반복 개선 같은 고급 추론 패턴을 구현할 수 있는가?
기존 접근법의 한계
| 한계 | 설명 |
|---|---|
| CoT의 단선성 | 하나의 추론 체인만 생성, 탐색 불가 |
| CoT-SC의 독립성 | 여러 체인을 생성하지만 체인 간 정보 교환 없음 |
| ToT의 트리 제약 | 분기(branch)와 가지치기는 가능하나, **합류(merge)**가 불가능 |
| 분할정복 불가 | 문제를 부분으로 나눠 풀고 결과를 합치는 패턴을 표현할 수 없음 |
핵심 통찰
- 추론 토폴로지를 임의 그래프로 확장하면 분할정복, 합류, 자기 개선 루프를 자연스럽게 표현 가능
- “부분 결과를 합치는 것은 대규모 문제를 처음부터 푸는 것보다 훨씬 쉽다” — Aggregation의 근거
- Latency-Volume 트레이드오프: GoT는 ToT와 동일한 지연 시간(log_k N)에서 Volume(선행 사고 접근 가능량) N을 달성
방법 (Method)
프레임워크 개요
graph TB subgraph "GoT Architecture" A["Controller<br/>(전체 오케스트레이션)"] A --> B["GoO: Graph of Operations<br/>(정적 실행 청사진)"] A --> C["GRS: Graph Reasoning State<br/>(동적 추론 상태 추적)"] A --> D["Prompter<br/>(그래프→프롬프트 변환)"] A --> E["Parser<br/>(LLM 출력→그래프 갱신)"] A --> F["Scoring/Validation<br/>(사고 점수 매김)"] end subgraph "Thought Transformations" G["Generation<br/>1개 사고 → k개 자식"] H["Aggregation<br/>k개 사고 → 1개 합류"] I["Refinement<br/>자기 루프로 반복 개선"] end B --> G B --> H B --> I
형식적 정의
GoT = (G, 𝒯, ℰ, ℛ)
| 구성요소 | 정의 |
|---|---|
| G | 방향 그래프: 정점 = LLM 사고, 간선 = 의존 관계 |
| 𝒯 | 사고 변환: Generation, Aggregation, Refinement |
| ℰ | 평가 함수: 사고에 점수 부여 |
| ℛ | 순위 함수: 관련 사고 선별 |
핵심 연산 (Thought Transformations)
1. Generation (생성): 하나의 부모 사고에서 k개의 새로운 자식 사고를 생성한다. ToT의 분기(branching)와 동일한 연산이다.
2. Aggregation (합류) — GoT의 핵심 혁신: k개의 서로 다른 사고를 하나의 새로운 사고로 결합한다. 이를 통해 분할정복이 가능해진다. 예: 128개 숫자 정렬 → 4개 부분 배열로 분할 → 각각 정렬 → Aggregation으로 병합 정렬.
3. Refinement (개선): 자기 루프(self-loop)를 통해 기존 사고를 반복적으로 개선한다. 예: 정렬 결과의 오류를 발견하고 수정.
시스템 아키텍처
Graph of Operations (GoO): 과제별로 정의된 정적 실행 청사진. 어떤 변환을 어떤 순서로 적용할지 미리 설계한다. 예: 정렬 과제의 GoO = “분할 → 각 부분 정렬(Generation) → 병합(Aggregation) → 검증·개선(Refinement)“.
Graph Reasoning State (GRS): 실행 중 동적으로 갱신되는 추론 상태 그래프. 각 사고 노드의 내용, 점수, 의존 관계를 실시간 추적한다.
Latency-Volume 트레이드오프
quadrantChart title Latency vs Volume 트레이드오프 x-axis "낮은 Latency" --> "높은 Latency" y-axis "낮은 Volume" --> "높은 Volume" CoT-SC: [0.25, 0.25] ToT: [0.35, 0.35] CoT: [0.75, 0.75] GoT: [0.35, 0.75]
| 방식 | Latency | Volume | 특징 |
|---|---|---|---|
| CoT | N | N | 높은 volume, 높은 latency |
| CoT-SC | N/k | N/k | 둘 다 감소 |
| ToT | log_k N | O(log_k N) | 둘 다 낮음 |
| GoT | log_k N | N | 낮은 latency + 높은 volume |
- Volume: 하나의 사고가 접근 가능한 선행 사고의 수 (정보 활용량)
- Latency: 입력에서 최종 사고까지의 최장 경로 길이
- GoT의 Aggregation이 낮은 latency를 유지하면서 volume을 N으로 끌어올리는 핵심 메커니즘
발견 (Findings)
실험 설계
GPT-3.5 turbo 사용, 과제당 100개 샘플. 네 가지 과제로 평가:
| 과제 | 측정 지표 | GoT 전략 |
|---|---|---|
| Sorting | 오류 범위 (위치 오류 + 빈도 불일치) | 분할 → 부분 정렬 → 병합 |
| Set Intersection | 누락 + 오포함 + 중복 | 부분 집합별 교집합 → 합류 |
| Keyword Counting | 절대 빈도 차이 합 | 하위 범주별 카운트 → 합산 |
| Document Merging | 중복제거(0-10) × 보존(0-10) 조화 평균 | 문단별 요약 → 합류 |
주요 결과
Sorting (정렬)
| 문제 크기 | GoT vs ToT 개선 | GoT vs CoT 개선 | GoT vs IO 개선 |
|---|---|---|---|
| P=32 | 미미 | ≈60% | ≈80% |
| P=64 | ≈61% | ≈65% | ≈83% |
| P=128 | ≈62% | ≈69% | ≈85% |
- 문제 크기가 커질수록 GoT의 이점이 증가 — 분할정복의 특성
- ToT 대비 31% 이상 비용 절감: 분할정복은 각 부분 문제가 작으므로 LLM 호출 효율이 높음
능력 비교 매트릭스
| 능력 | CoT | CoT-SC | ToT | GoT |
|---|---|---|---|---|
| 단일 체인 | ✓ | ✓ | ✓ | ✓ |
| 다중 체인 | ✗ | ✓ | ✓ | ✓ |
| 트리 구조 | ✗ | ✗ | ✓ | ✓ |
| 임의 그래프 | ✗ | ✗ | ✗ | ✓ |
| 합류 (Aggregation) | ✗ | ✗ | ✗ | ✓ |
| 자기 개선 (Refinement) | ✗ | ✗ | ✗ | ✓ |
| 분할정복 | ✗ | ✗ | ✗ | ✓ |
핵심 발견
- 분할정복의 효과: “큰 문제를 한 번에 풀기보다, 부분 문제로 나누고 결과를 합치는 것이 LLM에 훨씬 쉽다”
- 비용-품질 동시 개선: GoT는 품질을 높이면서 비용을 낮춤 (분할정복의 구조적 이점)
- 스케일링 특성: 문제 크기가 커질수록 GoT의 이점이 더 커짐 (P=32에서는 미미 → P=128에서는 62%)
Reasoning Topology 진화 계보
graph LR subgraph "추론 토폴로지 발전사" A["IO<br/>단일 입출력"] -->|"중간 단계 추가"| B["CoT (2022)<br/>선형 체인"] B -->|"다중 샘플링"| C["CoT-SC (2022)<br/>독립 병렬 체인"] B -->|"탐색 도입"| D["ToT (2023)<br/>트리 탐색"] D -->|"합류·루프 추가"| E["GoT (2023)<br/>임의 그래프"] end
| 발전 단계 | 추가된 능력 | 핵심 연산 |
|---|---|---|
| IO → CoT | 중간 추론 단계 | 순차 생성 |
| CoT → CoT-SC | 다양성 + 투표 | 독립 샘플링 |
| CoT-SC → ToT | 탐색 + 백트래킹 + 가지치기 | BFS/DFS |
| ToT → GoT | 합류 + 자기 개선 + 분할정복 | Aggregation + Refinement |
한계 및 논의
| 한계 | 설명 |
|---|---|
| 과제 특화 GoO 설계 | Graph of Operations를 과제별로 수동 설계해야 함 (자동화 미흡) |
| GPT-3.5 기반 평가 | GPT-4 등 더 강한 모델에서의 효과 검증 제한적 |
| 제한된 과제 다양성 | 정렬·집합·카운팅·병합 등 구조적 분할이 자연스러운 과제에 편중 |
| Aggregation 설계의 어려움 | 부분 결과를 어떻게 합칠지는 과제 의존적이며, 잘못된 합류는 오류 누적 |
| 동적 그래프 구조 결정 | 현재는 GoO가 정적 — 추론 중 그래프 구조를 동적 변경하는 메커니즘 부재 |
의의 및 후속 연구
학술적 기여
- Aggregation 연산 도입: LLM 추론에서 최초로 “합류” 개념을 정의하고 분할정복 가능성을 입증
- Latency-Volume 이론: 추론 토폴로지의 정보 이론적 분석 프레임워크 제시
- 모듈형 아키텍처: Prompter/Parser/Controller 분리로 새로운 추론 패턴의 쉬운 구현
후속 연구 방향
- 동적 GoO: 추론 중 그래프 구조를 적응적으로 변경
- 학습 기반 분할 전략: 어떻게 분할하고 합류할지를 LLM이 자체 결정
- GoT + MCTS: 몬테카를로 트리 탐색과 그래프 추론의 결합
- 다중 모델 GoT: 각 노드에 다른 전문 모델을 배치
BibTeX
@inproceedings{besta2024graph,
title={Graph of Thoughts: Solving Elaborate Problems with Large Language Models},
author={Besta, Maciej and Blach, Nils and Kubicek, Ales and Gerstenberger, Robert and Podstawski, Michal and Gianinazzi, Lukas and Gajda, Joanna and Lehmann, Tomasz and Niewiadomski, Hubert and Nyczyk, Piotr and Hoefler, Torsten},
booktitle={Proceedings of the AAAI Conference on Artificial Intelligence},
year={2024}
}