Graph of Thoughts 논문 정리

한 줄 요약

Graph of Thoughts(GoT) 는 LLM의 중간 추론 단위(thought)를 체인(chain) 이나 트리(tree) 가 아니라 그래프(graph) 로 다루는 프레임워크다.
핵심은 여러 thought를 생성(generate) 하고, 평가(score) 하고, 합성(aggregate) 하고, 수정(refine) 하면서 더 좋은 답으로 수렴시키는 데 있다.

---

이 논문을 한눈에 보면

• CoT는 한 줄, ToT는 나무, GoT는 그래프다.
• GoT의 차별점은 여러 thought를 합쳐 새로운 thought를 만드는 aggregation 이 자연스럽다는 점이다.
• 그래서 쪼개서 풀고, 다시 합쳐야 하는 문제에 특히 강하다.
• 대표 결과로, 논문은 sorting 작업에서 ToT 대비 품질을 약 62% 높이고 비용을 31% 이상 줄였다고 보고한다.
• 이 논문은 모델을 다시 학습시키는 방식이 아니라, prompting 설계만으로 reasoning을 확장한다는 점에서 의미가 크다.

---

1. 왜 이 논문이 나왔나

기존 prompting 흐름은 대체로 이렇게 발전해 왔다.

• IO(Input-Output): 입력을 바로 출력으로 변환
• CoT(Chain-of-Thought): 중간 추론 단계를 한 줄로 전개
• CoT-SC(Self-Consistency): 여러 CoT를 뽑아 가장 좋은 결과 선택
• ToT(Tree of Thoughts): 트리 탐색처럼 여러 경로를 확장하고, 점수가 낮은 가지는 버림

문제는 여기서도 구조적 제약이 남는다는 점이다.

• CoT는 한 방향 직선형 추론
• ToT는 부모-자식 관계만 있는 트리형 추론
• 하지만 실제 문제 해결은 종종
  이전 경로를 다시 가져오고,
  서로 다른 경로를 합치고,
  중간 결과를 반복 수정하는 식으로 더 복잡하게 진행된다.

이 논문은 바로 그 지점을 찌른다.
“LLM 추론을 tree가 아니라 graph로 보면 어떨까?”

 

 

Figure 1. CoT/CoT-SC/ToT/GoT 비교. GoT의 핵심은 tree 제약을 풀고, aggregation·refinement·backtracking을 하나의 그래프 안에서 다룬다는 점이다.

이 그림에서 읽어야 할 포인트는 단순하다.

1. CoT는 생각을 길게 늘린다.
2. ToT는 생각을 여러 갈래로 뻗는다.
3. GoT는 생각을 다시 합치고, 되돌아가고, 다듬는다.

즉, GoT는 ToT의 “더 큰 버전”이 아니라, 추론 구조 자체를 일반화한 프레임워크에 가깝다.

---

2. Graph of Thoughts의 핵심 아이디어

논문에서 thought는 매우 넓게 정의된다.
문단일 수도 있고, 정렬된 숫자 리스트일 수도 있고, 코드 조각일 수도 있다.

GoT의 기본 표현은 다음과 같다.

• 정점(vertex): 하나의 thought
• 간선(edge): 어떤 thought가 다른 thought를 직접 입력으로 사용했다는 의존 관계

이 구조를 쓰면 기존 체계로는 어색했던 연산들이 자연스럽게 표현된다.

2-1. 세 가지 핵심 연산

• Generation: 하나의 thought에서 여러 새 thought를 생성
• Aggregation: 여러 thought를 합쳐 더 좋은 새 thought를 생성
• Refinement: 기존 thought를 반복적으로 다듬음

 

 

Figure 2. Aggregation과 Generation 예시. 정렬 문제에서는 부분 정렬 결과를 합치고, 문서/요약 문제에서는 여러 결과를 결합하는 방식으로 적용된다.

여기서 가장 중요한 건 aggregation 이다.
이게 바로 GoT가 ToT와 갈리는 지점이다.

• ToT는 잘 뻗어 나가지만, 기본적으로 가지를 합치는 데 약하다
• GoT는 여러 경로의 장점을 명시적으로 합성할 수 있다

논문의 관점에서 보면, GoT는 “더 많은 생각”이 아니라 더 나은 생각 조합 방식을 제안하는 셈이다.

---

3. 프레임워크 관점에서 본 GoT

논문은 GoT를 단순 아이디어가 아니라 구현 가능한 시스템 구조로 제시한다.
핵심 구성 요소는 다음과 같다.

• Prompter: LLM에 보낼 프롬프트 생성
• Parser: LLM 응답을 구조화된 thought 상태로 파싱
• Scoring & Validation: 결과의 품질을 평가하고 유효성 검사
• Controller: 어떤 thought에 어떤 연산을 적용할지 결정
• GoO(Graph of Operations): 미리 정의한 정적 실행 계획
• GRS(Graph Reasoning State): 실행 중 계속 갱신되는 동적 상태

 

 

Figure 3. GoT 시스템 구조. GoO는 “무슨 연산을 어떤 순서로 할 것인가”를 정의한 정적 계획이고, GRS는 실제 실행 중 thought들의 상태를 저장하는 동적 그래프다.

여기서 특히 중요한 구분은 GoO와 GRS다.

• GoO는 설계도다.
  예: “먼저 쪼개고 → 각각 풀고 → 점수 매기고 → 좋은 것만 남기고 → 합치고 → 다시 고친다.”
• GRS는 실행 로그이자 상태 저장소다.
  어떤 thought가 생성됐는지, 점수는 얼마인지, 어떤 thought가 살아남았는지 기록한다.

이 구조 덕분에 GoT는 “좋은 비유” 수준이 아니라,
실제로 새로운 prompting 전략을 실험할 수 있는 프레임워크가 된다.

---

4. 대표 예제: sorting을 어떻게 푸나

논문이 가장 자세히 보여주는 예제는 숫자 정렬(sorting) 이다.
이 예제가 중요한 이유는 GoT의 강점이 아주 직관적으로 드러나기 때문이다.

핵심 흐름은 이렇다.

1. 긴 숫자 리스트를 작은 조각으로 분할
2. 각 조각을 여러 번 독립적으로 정렬
3. 점수가 좋은 결과만 선택
4. 부분 결과들을 merge
5. 필요하면 다시 improve/refine

 

 

Figure 4. Sorting 작업의 GoO 예시. 문제를 16개 단위의 작은 정렬 문제로 쪼개고, 부분 결과를 평가·선택·병합하면서 전체 정답으로 간다.

이 방식이 강한 이유는 명확하다.

• LLM은 짧은 리스트 정렬은 비교적 잘한다.
• 하지만 긴 리스트를 한 번에 정렬하면 중복 개수나 순서가 틀어지기 쉽다.
• GoT는 큰 문제를 작은 문제로 나눈 뒤, 부분 정답을 조합하는 방향으로 난도를 낮춘다.

즉, 이 논문은 “LLM이 논리를 더 잘 하게 만드는 법”보다는
LLM이 잘할 수 있는 문제 크기로 재구성하는 법에 가깝다.

---

5. 실험 결과에서 봐야 할 핵심

논문은 네 가지 대표 과제에서 GoT를 평가한다.

• sorting
• set intersection
• keyword counting
• document merging

실험은 주로 GPT-3.5 기반으로 수행됐고, 각 설정마다 100개 입력 샘플을 사용한다(문서 병합은 50개).
저자들은 예산 제약 때문에 GPT-3.5 중심으로 분석했고, Llama-2는 더 느리고 대체로 성능이 떨어졌다고 적고 있다.

5-1. Sorting: GoT의 대표 승리 장면

 

 

Figure 5. Sorting 결과. 문제 크기(32/64/128)가 커질수록 GoT의 장점이 더 뚜렷해진다.

이 결과에서 읽어야 할 포인트는 세 가지다.

• 오류 수가 낮다
• ToT보다 비용도 낮다
• 문제가 커질수록 격차가 커진다

논문이 특히 강조하는 메시지는 다음이다.

• GoT는 sorting 품질에서 ToT 대비 약 62% 개선
• 동시에 비용은 31% 이상 절감
• CoT/IO와 비교하면 품질 차이는 더 크게 벌어진다

즉, GoT의 강점은 “조금 더 잘 푼다”가 아니라
복잡도가 커질수록 더 유리해진다는 점이다.

5-2. Set Intersection: 분할-계산-병합 구조의 재현

 

 

Figure 6. Set intersection 결과. sorting과 마찬가지로, 집합을 나눈 뒤 부분 교집합을 구해 병합하는 구조가 효과적이다.

set intersection은 sorting과 구조가 비슷하다.

• 한쪽 집합을 쪼개고
• 다른 집합과의 교집합을 구한 뒤
• 부분 교집합들을 병합한다

이 과제에서도 GoT는 대체로 오류를 가장 낮게 유지한다.
즉, GoT는 특정 예제 하나에만 맞춘 트릭이 아니라,
decomposition + aggregation 패턴이 먹히는 문제군에서 재현성 있는 이득을 보인다.

5-3. Keyword Counting: 너무 크게 쪼개도, 너무 덜 쪼개도 문제

 

 

Figure 7. Keyword counting 결과. 분할 granularity가 성능과 비용에 직접 영향을 준다.

이 그림은 블로그에서 꼭 짚을 만하다.
왜냐하면 GoT의 현실적인 trade-off 가 잘 드러나기 때문이다.

• 텍스트를 더 잘게 쪼개면 각 하위 문제는 쉬워진다
• 하지만 프롬프트의 정적 부분(few-shot 예시 등)이 많으면 오버헤드 가 커진다
• 따라서 “얼마나 잘게 쪼갤지”가 성능과 비용을 함께 결정한다

논문은 여기서 중요한 실무 감각을 준다.

GoT의 성능은 그래프 구조 그 자체만이 아니라,
어떻게 분해하고 어떤 크기로 합칠지 에 크게 좌우된다.

즉, GoT는 자동 마법이 아니라 설계 문제다.

5-4. Document Merging: 생성 결과를 다시 합치는 실험

 

 

Figure 8. Document merging 결과. 여러 NDA 문서를 합칠 때도 GoT 계열이 높은 품질을 유지한다.

문서 병합은 숫자 문제보다 더 “생성형”에 가까운 과제다.
여기서는 중복을 줄이면서 정보 보존을 높여야 한다.

이 과제가 보여주는 핵심은 다음이다.

• GoT는 숫자/기호 문제만 잘하는 것이 아니다
• 여러 생성 결과를 다시 모아 더 나은 문서로 합치는 작업에도 적용된다
• 즉, GoT는 reasoning뿐 아니라 structured generation workflow 로도 읽을 수 있다

---

6. 이 논문의 진짜 포인트: “graph”가 왜 중요한가

이 논문이 단순히 “ToT의 확장판”으로 읽히면 아쉬운 이유가 있다.
진짜 포인트는 추론의 구조를 그래프로 본다는 시각 전환에 있다.

저자들은 이를 더 분명히 보여주기 위해 volume of a thought 라는 지표도 제안한다.

volume이란?

어떤 thought에 도달할 수 있는 이전 thought들의 수를 뜻한다.
직관적으로는, 현재 답이 얼마나 많은 중간 추론의 영향을 품고 있느냐를 나타낸다.

논문의 메시지는 이렇다.

• CoT: volume은 클 수 있지만 latency가 길다
• ToT: latency는 짧아지지만 volume이 작다
• GoT: aggregation 덕분에 낮은 latency와 큰 volume 을 동시에 노릴 수 있다

이 부분이 중요한 이유는, GoT가 단순히 “잘 되는 프롬프트 모음”이 아니라
reasoning 구조를 분석하는 이론적 프레임까지 제시하기 때문이다.

---

7. 이 논문이 주는 실무적 시사점

이 논문은 연구적으로도 재미있지만, 실제 LLM 시스템 설계에도 힌트를 준다.

7-1. 체인보다 그래프로 설계하라

복잡한 업무를 프롬프트 한 번으로 해결하려 하지 말고,
다음처럼 생각하는 편이 낫다.

• 어떤 단계에서 분기할지
• 어떤 단계에서 검증할지
• 어떤 단계에서 좋은 결과만 남길지
• 어떤 단계에서 합성할지

즉, agentic workflow나 multi-step prompting을 짤 때
“단계들의 그래프”로 사고하라는 메시지로 읽을 수 있다.

7-2. GoT는 특히 이런 문제에 강하다

• 큰 문제를 작은 하위 문제로 나눌 수 있는 경우
• 하위 결과를 다시 합치는 것이 원 문제보다 쉬운 경우
• 중간 결과에 대한 점수 함수나 검증 기준이 비교적 분명한 경우

예를 들면

• 긴 문서 요약/병합
• structured extraction
• counting/consistency check
• set/array 연산
• 다단계 코드 수정 워크플로

같은 문제들이다.

7-3. 하지만 자동 설계는 아니다

이 논문의 한계도 분명하다.

• 어떤 그래프 구조가 좋은지는 사람이 설계해야 한다
• scoring 함수가 부실하면 좋은 thought를 고르기 어렵다
• 자연스럽게 분해되지 않는 문제에서는 이득이 줄 수 있다
• 실험은 주로 GPT-3.5 중심이라 최신 대형 모델에서의 일반화는 별도 검증이 필요하다

즉, GoT는 범용 만능키라기보다
잘 설계된 분해-병합형 프롬프트 프레임워크에 가깝다.

---

8. 개인적으로 이 논문이 흥미로운 이유

이 논문의 묘미는 “LLM reasoning을 더 길게 만들자”가 아니라,
“LLM reasoning을 더 구조적으로 만들자” 로 방향을 튼 데 있다.

많은 사람들이 CoT 이후 reasoning을 생각할 때
자연스럽게 더 긴 chain 이나 더 넓은 tree 를 떠올린다.
그런데 이 논문은 한 단계 더 나아가서,

• 합치고
• 되돌아가고
• 정제하고
• 다시 평가하는

보다 현실적인 문제 해결 패턴을 프롬프트 수준에서 구현하려 한다.

그래서 GoT는 단지 한 편의 prompting 논문이라기보다,
이후의 agent 설계, workflow orchestration, reasoning graph 아이디어와도 연결해서 읽을 수 있다.

---

9. 짧은 요약

Graph of Thoughts는 Chain-of-Thought와 Tree-of-Thought를 일반화한 prompting 프레임워크로, LLM의 중간 추론을 그래프 형태로 다룬다. 이를 통해 여러 thought를 생성하고, 평가하고, 합치고, 다시 다듬는 흐름을 자연스럽게 설계할 수 있다. 특히 큰 문제를 작은 하위 문제로 분해한 뒤 다시 합치는 작업에서 강점을 보이며, 논문은 sorting에서 ToT 대비 약 62%의 품질 향상과 31% 이상의 비용 절감을 보고한다. 이 논문의 진짜 의미는 LLM 추론을 더 길게 만드는 것이 아니라, 더 구조적으로 설계하는 데 있다.

---

10. 마무리

이 논문을 가장 짧게 정리하면 다음 한 문장으로 요약할 수 있다.

GoT는 “생각을 많이 하게 하는 방법”이 아니라, “생각을 어떻게 연결할지 설계하는 방법”이다.

 

LLM reasoning 연구를 볼 때 CoT → ToT까지는 익숙해졌다면,
이 논문은 그 다음 질문을 던진다.

“왜 꼭 tree여야 하지? graph면 안 되나?”

그 질문이 이 논문의 가장 좋은 출발점이다.