Graph of Thoughts (KO)

Graph-of-Thoughts (GoT) — 대형 언어 모델(LLM, Large Language Models) 연구 분야의 개념으로, 모델의 추론 과정을 상호 연결된 «사고»(풀이의 중간 단계)들로 이루어진 임의의 그래프 형태로 표현하는 방식입니다. 이 접근법은 ETH Zurich의 마체이 베스타(Maciej Besta)가 이끄는 연구팀에 의해 제안되었으며, 2024년 AAAI 학회에서 발표되었습니다. Graph-of-Thoughts의 목표는 Chain-of-Thought(사고의 사슬)나 Tree-of-Thoughts(사고의 나무)와 같은 기존 방식을 넘어 prompt engineering(프롬프트 설계)의 가능성을 확장하는 것입니다. 이들과 달리, GoT 방식은 모델이 생성한 어떤 추론 단위(사고)든 다른 어떤 단위에도 참조할 수 있게 하여, 엄격한 선형 구조나 트리 구조가 아닌 아이디어의 네트워크를 형성합니다. 저자들은 이것이 복잡하고 비선형적인 인간 사고의 특성을 더 정확히 반영하며, LLM의 추론 메커니즘을 인간 뇌(재귀적 신경 연결을 지닌)의 작동 방식에 잠재적으로 더 가깝게 만든다고 주장합니다.

Graph-of-Thoughts는 프롬프트 형성 방법(prompting framework)으로, 모델 자체의 추가 학습이나 fine-tuning을 필요로 하지 않습니다. 대신 LLM과의 대화를 특별한 방식으로 구성하여, 그래프 구조로 연결된 일련의 «사고» 단계를 통해 모델을 안내합니다. 이러한 구조 덕분에 서로 다른 추론 분기를 조합하고 재활용할 수 있습니다. 예를 들어 모델이 여러 가설이나 문제의 부분들을 병렬로 검토한 뒤, 그중 가장 유망한 것들을 하나의 해답으로 통합할 수 있습니다. 백과사전적 정의로는, Graph-of-Thoughts를 LLM을 활용한 구조적 추론 전략의 이전 방식들을 일반화한 것으로, 하나의 복합 프롬프트 안에서 사고 과정을 구성하는 데 최대한의 유연성을 제공하는 것으로 정의할 수 있습니다.

전제 조건: Chain-of-Thought와 Tree-of-Thoughts

Graph-of-Thoughts 방법은 언어 모델 활용 시 명시적인 추론 구조를 사용하는 초기 접근법에서 발전했습니다. 기본적인 접근법은 Chain-of-Thought (CoT) — «사고의 사슬»입니다. CoT 방법에서는 사용자가 문제 조건뿐만 아니라 답으로 이어지는 중간 추론 단계도 모델 쿼리에 포함하도록 권장됩니다. 연구 결과, 이러한 방식이 모델 파라미터 변경 없이도 LLM이 수학적 또는 논리적 퍼즐과 같은 복잡한 문제를 해결하는 능력을 크게 향상시키는 것으로 나타났습니다. 사실상 CoT는 모델이 복잡한 문제를 단계별로 더 간단한 단계들로 분해하도록 유도하여 순차적인 사고 흐름을 모방합니다.

이 아이디어를 발전시킨 것이 Self-Consistency 기술입니다. 하나의 사고 사슬 대신 여러 개의 독립적인 사슬을 생성한 뒤, 그중 가장 설득력 있는 것을 선택합니다. 이를 통해 모델이 다양한 해결 접근법을 검토할 수 있으며, 단 하나의 잘못된 추론 흐름을 따라가다 오답을 얻을 위험이 줄어듭니다. 그러나 여러 개의 CoT 사슬조차도 «아이디어를 결합»하는 것은 불가능합니다. 각 사슬은 독립적으로 처리되며 모델은 내용을 조합하지 않고 단지 최선의 것을 선택할 뿐입니다.

이 한계를 극복하기 위해 Tree-of-Thoughts (ToT) — «사고의 나무» 방식이 제안되었습니다. ToT에서 추론 과정은 트리 구조로 구성됩니다. 각 지점에서 모델은 여러 사고 전개 방향(분기)을 생성할 수 있으며, 이후 이 중간 상태들을 평가하여 더 깊이 탐색할 가장 유망한 것을 선별합니다. 트리 탐색(예: 너비 우선 탐색 BFS, 또는 깊이 우선 탐색 DFS)과 노드로 되돌아가 다른 분기를 전개하는 기능을 활용함으로써, Tree-of-Thoughts는 선형 CoT보다 언어 모델에 더 강력한 복잡한 문제 해결 메커니즘을 제공합니다. 역추적 및 재검토와 같은 새로운 가능성이 생겨납니다. 한 분기가 막다른 곳에 이르면 이전 노드로 돌아가 다른 경로를 시도할 수 있습니다. 이 방법론은 다양한 경우의 수를 따져보고 계획하는 것이 중요한 논리 문제와 탐색 문제 해결에 효과적임을 입증했습니다.

그러나 Tree-of-Thoughts는 엄격한 제약도 부과합니다. 각 사고(트리의 노드)는 하나의 분기에만 속하며, 상호작용은 부모 노드와 자식 노드 사이에서만 이루어지고, 서로 다른 분기들은 합쳐지거나 정보를 교환할 수 없습니다. 다시 말해, 하나의 풀이 과정에서 서로 다른 가설 간의 교차 아이디어 교환(cross-pollination)이 어렵습니다. 트리의 분기들은 독립적으로 발전하며, 최선의 추론 사슬이 선택될 때 루트에서만 합쳐집니다. 그러나 실제 창의적 또는 분석적 사고에서 인간은 종종 이전에 검토한 아이디어로 돌아가 다른 추론 분기와 결합합니다. 이러한 사고의 얽힘은 트리 구조의 범위를 벗어납니다.

이러한 관찰들이 연구자들을 더 유연한 구조, 즉 사고 간 연결이 제한되지 않고 복잡한 네트워크를 형성할 수 있는 그래프라는 아이디어로 이끌었습니다. 2024년 분석 리뷰에서 지적된 바와 같이, 사고의 사슬, 나무, 그래프의 등장은 명시적인 추론 과정 구조화를 통해 LLM의 능력을 크게 강화할 수 있는 새로운 방법 클래스의 탄생을 반영합니다. 특히 구조화된 프롬프트는 수학 문제 풀이와 논리 퍼즐에서 계획 수립, 심지어 창작에 이르기까지 다양한 분야에서 LLM의 성과를 눈에 띄게 향상시켰습니다. 이러한 전반적인 배경 속에서 Graph-of-Thoughts 방식이 구조적 prompting 방법 발전의 다음 단계로 등장했습니다.

개념: 사고의 그래프 구조

Graph-of-Thoughts는 언어 모델이 과제를 수행하는 흐름을 임의의 방향 그래프 형태로 표현할 것을 제안합니다. 형식적으로, GoT에서 사고 그래프는 정점(사고)의 집합과 간선(사고 간 의존 관계)의 집합입니다. 그래프의 정점은 모델의 개별 사고를 나타냅니다. 이 용어는 과제 맥락에 따라 달라지는 모든 의미 있는 단위를 의미하며, 모델이 쿼리에 응답하여 생성한 개별 명제, 풀이 단계, 텍스트 단편, 단락, 코드 블록 등이 될 수 있습니다. 정점 사이의 간선은 한 사고가 다른 사고를 생성하는 데 사용되었음을 의미합니다. 즉, 프롬프트에 모델이 특정 이전 결과에 기반하여 새로운 결과를 도출해야 한다고 명시되어 있는 것입니다. 이처럼 간선은 의존 관계를 고정합니다. 현재 추론 단계가 어떤 이전에 얻어진 데이터에 의존하는지를 나타냅니다.

GoT가 단순한 구조와 구별되는 가장 중요한 차이점은 사고의 집계 및 병합 가능성입니다. 그래프에서는 하나의 정점(새로운 사고)이 여러 개의 선행 정점을 가질 수 있습니다. 이는 두 개 이상의 독립적인 추론 사슬이 합쳐지는 상황에 해당합니다. 모델이 이전에 생성된 여러 단편을 입력으로 받아 이를 바탕으로 종합적인 결론을 형성하는 것입니다. 예를 들어 문제를 풀 때 모델이 두 가설을 병렬로 검토한 뒤, 두 가설의 장점을 통합하고 단점을 제거한 새로운 사고를 생성할 수 있습니다. 이러한 집계 연산은 트리 구조(각 노드에 부모가 하나뿐인)에서는 불가능했지만, 그래프 구조에서는 자연스럽게 구현됩니다. 아이디어의 병합 외에도 그래프는 피드백 루프의 도입도 허용합니다. 원칙적으로 GoT 구조는 순환을 금지하지 않으므로, 모델이 어떤 결과를 이전 추론 단계로 되돌려 재처리하거나 정제할 수 있습니다. 저자들은 이를 뇌의 신경망에서 재귀적 연결에 대한 유추와 연결합니다. 뇌에서는 한 뉴런 그룹의 출력이 이전 층에 역으로 작용하여 닫힌 사고 루프를 형성할 수 있습니다.

Graph-of-Thoughts를 실제로 구현하려면 모델과의 대화를 특별히 구성해야 합니다. 연구자들은 GoT를 위한 모듈식 아키텍처 프레임워크를 개발했습니다. 이 프레임워크에는 다음 구성 요소들이 포함됩니다. (1) 개별 단계(사고)에 대한 세밀한 제어 — «컨트롤러»가 사고 생성의 순서와 논리를 관리합니다. (2) 동적 프롬프트 구성 — 각 단계에 대해 전용 모듈이 현재 맥락과 선택된 그래프 정점(선행 정점)을 기반으로 prompt를 구성합니다. (3) 모델 응답의 파싱 및 평가 — LLM으로부터 얻은 단편들을 품질, 유용성, 또는 과제 기준 적합성 면에서 분석하고 평가합니다. GoT 아키텍처는 이를 통해 추론 그래프를 인터랙티브하게 구축할 수 있게 합니다. 각 단계 후 어떤 새로운 정점을 추가할지, 이전 정점들과 어떻게 연결할지, 어떤 분기를 계속하거나 합칠지 결정합니다. 모듈식 구조 덕분에 이러한 프레임워크는 새로운 유형의 «사고 변환»(예: 그래프에 대한 특수 연산)으로 확장될 수 있으며, 다양한 모델에 맞게 조정될 수 있습니다(저자들은 GPT-3.5, GPT-4, LLAMA 2 등 여러 LLM 계열로 GoT를 성공적으로 테스트했습니다). 중요한 특성은 GoT가 언어 모델 자체의 파라미터 변경을 요구하지 않는다는 점입니다 — 모든 개선은 더 현명한 쿼리 구성과 응답 처리를 통해 달성됩니다. 이는 기존의 강력한 LLM을 «있는 그대로» 사용할 수 있으며, Graph-of-Thoughts가 그 작동을 관리하는 상위 레이어 역할을 한다는 것을 의미합니다.

주목할 점은, Graph-of-Thought라는 용어가 베스타와 동료들의 접근법과는 다른, 독립적인 다른 연구에서도 등장했다는 것입니다. 2023년 야오 야오(Yao Yao)와 공저자들은 사고 그래프의 추가 인코더 모듈을 통해 LLM의 reasoning을 향상시키는 방법론을 제안했으며, 이는 모델의 추가 학습을 필요로 했습니다. «Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models»라는 제목의 그들의 연구는 2단계 아키텍처를 설명합니다. 먼저 상호 연결된 중간 명제들의 그래프를 생성하고, 이어서 특수 인코더로 변환하여 gated fusion 메커니즘을 통해 모델에 통합합니다. 이러한 학습이 포함된 하이브리드 접근법은 일부 과제에서 정확도 향상을 보였습니다. 예를 들어 멀티모달 질문 세트 ScienceQA에서 T5-base 모델 사용 시 정확도가 85.2%에서 87.6%로 향상되었습니다. 그러나 이 접근법은 이름은 비슷하지만 근본적으로 다릅니다. 모델 변경(fine-tuning)을 필요로 하며 prompt engineering 방식이 아닙니다. 원래 GoT 접근법(AAAI 2024)의 저자들은 자신들의 연구가 LLM 파라미터 업데이트 없는 방법에만 초점을 맞추기 때문에 야오 등의 모델을 다루지 않는다고 명시적으로 밝혔습니다. 따라서 이 개요의 맥락에서 Graph-of-Thoughts는 어디까지나 프롬프트 수준의 프레임워크이며, 신경망 아키텍처의 수정이 아닙니다.

응용 및 결과

GoT 저자들은 하나의 직접 프롬프트(input-output prompting)나 사고 사슬로도 해결하기 어려운 여러 과제에서 그 장점을 입증했습니다. 이런 과제들의 특징적인 특성은 여러 부분(하위 과제)으로 분해하고, 이 부분들을 따로 풀어, 부분 결과에서 완전한 답을 합성할 수 있다는 것입니다. 다룬 예시에는 무작위 목록의 정렬, 텍스트에서 키워드 계산(예: 문서 요약을 위한), 집합 연산 수행(목록의 합집합, 교집합 등), 그리고 텍스트 문서 병합(여러 출처의 정보 통합) 등이 포함됩니다. 이 모든 경우에서 Graph-of-Thoughts는 자연스러운 과제 분해를 가능하게 합니다. 예를 들어 정렬의 경우 목록을 부분들로 나누고, 각 부분을 독립적인 사고 분기로 따로 정렬한 뒤, 결과를 합칩니다(merge sort와 유사한 알고리즘을 모방). 또는 텍스트 분석 시 모델이 서로 다른 문서에서 병렬로 정보를 추출한 뒤 하나로 통합할 수 있습니다.

실험 결과는 GoT 방식의 효과를 확인해 줍니다. 베스타와 동료들의 보고에 따르면, 정렬 과제에서 사고 그래프는 이전 접근법들에 비해 풀이 품질을 크게 향상시켰습니다. 구체적으로, GoT 사용 시 정렬 정확도는 단순 사고 사슬 CoT보다 70% 높고, 사고 나무 ToT보다 62% 높았습니다. 동시에 이 방법은 계산 자원 소비를 줄였습니다. 동일 과제에서 모델 호출 횟수(및 그에 따른 토큰화된 쿼리 양)가 Tree-of-Thoughts 대비 31% 감소했습니다. 이는 그래프식 추론 구성이 최종 결과를 개선했을 뿐만 아니라, 중간 결론을 현명하게 조합함으로써 불필요한 계산을 피하고 풀이를 더 경제적으로 만들었음을 의미합니다. 이러한 이득은 다른 테스트 과제들, 특히 이질적인 정보를 집계해야 하는 경우에서도 얻어졌습니다. 연구자들은 GoT가 여러 요소로 구성된 복합 과제에 특히 효과적임을 지적합니다. «Graph-of-Thoughts는 더 작은 하위 과제들로 자연스럽게 분해되어 별도로 해결된 후 결과가 합쳐지는 과제들에 특히 잘 맞습니다». 이러한 경우에 사고 그래프는 문제의 모든 측면을 포괄하고, 하나의 추론 흐름을 따를 때보다 더 완전한 성격의 풀이를 합성할 수 있습니다.

왜 한 방식의 프롬프트 구성이 다른 것보다 나은지 더 깊이 이해하기 위해, 2024년 연구에서는 특수 지표인 «사고의 부피»(volume of a thought)를 제안했습니다. 부피는 그래프의 각 개별 사고(정점)에 대해, 방향 간선을 따라 해당 정점에 도달할 수 있는 다른 사고들의 수로 정의됩니다(간단히 말해, 이 정점이 얼마나 많은 중간 단계의 정보에 의존하는지). Chain-of-Thought에서 모든 사고는 선행자 하나에만 의존하므로 그 부피는 1입니다(선형 사슬). 사고 나무에서는 부피가 더 클 수 있지만 여전히 단일 분기의 구조로 제한됩니다. 그래프에서는 집계 덕분에 단일 정점이 여러 다른 정점들의 기여를 축적할 수 있어 그 «부피»가 현저히 높습니다. GoT는 최종 결론이 훨씬 더 많은 수의 선행 사고들에 기반하도록 하여 그 내용을 통합할 수 있음이 입증되었습니다. 이 사실은 풀이 공간을 더 깊이 포괄함을 반영하며, 그래프식 추론이 더 단순한 방식보다 우월한 이유에 대한 정량적 설명이 됩니다.

비교 및 의의

Graph-of-Thoughts는 현재 LLM을 위한 구조화된 prompting의 가장 일반화된 형태를 대표합니다. 다양한 방식(CoT, 자기 일관성 CoT, ToT, GoT)의 비교표에서는 오직 GoT만이 사고 과정의 임의적 토폴로지를 지원한다는 점이 강조됩니다. GoT는 이전 모든 접근법의 가능성을 포함합니다. 과제 해결에 적합하다면 단일 사슬로도, 분기가 있는 나무로도, 여러 사슬의 조합으로도 작동할 수 있습니다. 핵심은 단계 간 연결에 엄격한 제한이 없다는 것으로, 이론적으로 가능한 추론 전략의 공간을 최대한 넓게 만듭니다.

GoT의 유연성은 더 높은 제어 복잡도를 대가로 한다는 점을 이해하는 것이 중요합니다. 사고 그래프를 구현하려면 언제 어떤 사고를 생성할지, 어떤 것을 선별하거나 조합할지, 언제 과정을 멈추고 답을 출력할지를 결정하는 외부 오케스트레이터 알고리즘이 필요합니다. 단순한 CoT에서는 그러한 결정이 필요 없습니다 — 모델이 끝까지 선형 추론을 스스로 생성합니다. ToT에서는 제어의 일부가 트리 탐색 알고리즘(예: 전개할 노드 선택)에 맡겨집니다. GoT에서는 자유도가 더 높아서 방법의 효율성이 중간 결과를 평가하는 휴리스틱의 품질과 각 단계에서 프롬프트를 올바르게 구성하는 것에 달려 있습니다. 따라서 Graph-of-Thoughts는 단순한 쿼리 형식이 아닌, LLM과의 상호작용 과정에 부과되는 추론 구조로 볼 수 있습니다. 모델이 과제를 해결하고 사용자(또는 컨트롤러 프로그램)가 이 과정을 안내하는 일종의 동적 계획입니다.

Graph-of-Thoughts의 등장은 대형 언어 모델의 작동을 더 해석 가능하고 관리 가능하게 만들려는 노력을 반영합니다. 풀이 구조를 명시적으로 설정함으로써 연구자들은 더 나은 품질을 달성할 뿐만 아니라, 모델이 어떻게 특정 결론에 도달했는지 분석할 수 있게 됩니다. 이는 NLP 접근법을 고전적인 알고리즘적 탐색 및 계획 방법에 가깝게 하지만, 이제 단계 실행은 신경망 모델에 맡겨집니다. 일부 전문가들은 구조화된 프롬프트(사고의 사슬, 나무, 그래프)를 심층 모델의 «블랙박스» 한계를 극복하고 복잡한 과제에서의 신뢰성을 높일 수 있는 유망한 방향으로 바라봅니다.

Graph-of-Thoughts 방법론은 계속 활발히 발전하고 있습니다. 저자들은 GoT 구현을 위한 코드와 예제를 공개적으로 공개했으며, 이를 통해 커뮤니티가 새로운 접근법을 실험할 수 있게 되었습니다. 텍스트와 이미지 및 기타 데이터 유형을 결합하는 멀티모달 버전의 사고 그래프, 그리고 GoT 아이디어를 모델 아키텍처에 직접 통합하려는 시도(앞서 언급한 Yao et al., 2023 연구처럼)와 같은 확장들도 등장하고 있습니다. 2025년에는 Chain-of-Thought, Tree-of-Thoughts, Graph-of-Thoughts 방법들의 상세한 분류 리뷰가 출판되어, 축적된 지식을 체계화하고 이러한 접근법들의 이론적 기초를 설명합니다. 이 모든 것은 LLM의 사고를 구조적으로 제어하는 것에 대한 과학 커뮤니티의 큰 관심을 반영합니다. Graph-of-Thoughts는 이미 복잡한 과제 해결을 위한 효과적인 도구로 자리 잡았으며, 대형 언어 모델의 강력함과 고전적 알고리즘의 투명성 및 논리를 결합하는 AI 솔루션 분야의 추가 혁신을 위한 기반이 될 것입니다.

참고 링크

• arXiv에 게재된 원문 «Graph of Thoughts: Solving Elaborate Problems with Large Language Models»
• 원문의 HTML 버전
• arXiv에 게재된 리뷰 «Demystifying Chains, Trees, and Graphs of Thoughts»
• arXiv에 게재된 논문 «Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Models»
• Multimodal Graph-of-Thoughts — Deepgram 논문
• LLMs Graph of Thoughts Framework — Medium 게재 논문

문헌

• Besta, M. et al. (2024). Graph of Thoughts: Solving Elaborate Problems with Large Language Models. arXiv:2308.09687.
• Yao, S. et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. arXiv:2305.10601.
• Yao, Y. et al. (2023). Beyond Chain-of-Thought: Effective Graph-of-Thought Reasoning in Language Models. arXiv:2305.16582.
• Wei, J. et al. (2022). Chain of Thought Prompting Elicits Reasoning in Large Language Models. arXiv:2201.11903.
• Wang, X. et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv:2203.11171.
• Wei, J. et al. (2024). Demystifying Chains, Trees, and Graphs of Thoughts. arXiv:2401.14295.
• Huang, S. et al. (2023). Language Is Not All You Need: Aligning Perception with Language Models (Kosmos-1). arXiv:2302.14045.
• Mitra, C. et al. (2024). Compositional Chain-of-Thought Prompting for Large Multimodal Models. In CVPR 2024. PDF.
• Zheng, G. et al. (2023). DDCoT: Duty-Distinct Chain-of-Thought Prompting for Multimodal Reasoning in Language Models. arXiv:2310.16436.
• Mu, J. et al. (2023). Learning to Compress Prompts with Gist Tokens. arXiv:2304.08467.