Graph of Thoughts: Solving Elaborate Problems with Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/29720

---

Abstract:

• Graph of Thoughts(GoT)라는 새로운 프레임워크를 제안하는 논문임.
• 이 프레임워크는 기존의 Chain-of-Thought(CoT)나 Tree of Thoughts(ToT)와 같은 패러다임을 넘어 대형 언어 모델(LLM)의 프롬프트 능력을 향상시키는 것을 말함.
• GoT의 핵심 아이디어는 LLM이 생성하는 정보를 임의의 그래프로 모델링하는 것임. 여기서 “LLM의 생각” 은 그래프의 노드(정점) 가 되고, 이들 사이의 의존성은 엣지(간선) 로 표현됨. 이를 통해 다양한 생각들을 결합하여 시너지 효과를 내거나, 생각들의 네트워크에서 핵심을 추출하거나, 피드백 루프를 통해 생각을 강화하는 것이 가능해진다.
• GoT가 다양한 작업에서 기존 최첨단 기술보다 우수한 성능을 보여준다고 함.
• 예를 들어, 정렬(sorting) 작업에서 ToT보다 품질을 62% 향상시키면서도 31% 이상 비용 절감을 이뤄냈다고도 한다.

 

 

Introduction:

• Chain-of-Thought(CoT)와 그 한계:
  • CoT는 프롬프트에 중간 추론 단계(생각의 흐름)를 포함시켜 대형 언어 모델(LLM)의 문제 해결 능력을 향상시키는 프롬프트 엔지니어링 기법임.
  • 이는 모델이 단순히 입력에 대한 출력만 생성하는 것이 아니라, 문제 해결 과정을 단계별로 따라가며 논리적인 추론을 수행하도록 유도 하는 것.
  • CoT는 생각의 흐름을 선형적으로 연결된 일련의 단계로 표현하는데 복잡한 문제에서 필요한 다양한 경로의 탐색이나 대안의 고려가 어려움.
  • 여러 가능성을 동시에 고려하거나 중간에 새로운 아이디어를 통합하는 등의 복잡한 사고 과정을 표현하기에 한계가 있음.
  • 잘못된 추론 경로를 선택했을 때, 그 경로에서 벗어나 다른 경로를 탐색하는 기능이 부족하기도 함. (백트리깅 불가)
  • 여기서 말하는 복잡한 문제는 선형적인 구조로는 해결할 수 없는, 여러 생각을 결합해야하는 문제를 말함.
• Tree of Thoughts(ToT)와 그 한계:
  • ToT는 CoT를 확장하여 LLM의 추론 과정을 나무 구조로 모델링한 방법임.
  • 여러 개의 추론 경로를 동시에 탐색하고, 비효율적인 경로를 포기하거나 더 유망한 경로로 전환할 수 있다는 장점이 있다. (백트래킹이 가능함.)
  • ToT는 추론 과정을 트리 구조로 제한하므로, 사이클이나 복잡한 의존 관계를 표현하기 어렵다.
  • 인간의 사고는 네트워크처럼 복잡하게 연결되어 있지만, 트리 구조는 이러한 복잡성을 충분히 담아내지 못한다.
  • 서로 다른 경로에서 나온 아이디어를 결합하여 새로운 해결책을 도출하는 능력이 제한됨.
• Graph of Thoughts(GoT)의 제안:
  • GoT는 LLM의 추론 과정을 임의의 그래프 구조로 모델링하여 CoT와 ToT의 한계를 극복하기 위한 것.
  • 여기서 생각은 노드로, 생각 간의 의존성이나 관계는 엣지로 표현됨.
  • 트리나 연쇄 구조에 제한되지 않고, 사이클, 루프, 병합 등 복잡한 구조를 표현할 수 있다. 여러 경로에서 나온 아이디어를 하나로 결합하거나, 특정 생각을 반복적으로 재검토하는 피드백 루프를 구성할 수 있음.
• GoT 구현의 설계 과제:
  • 다양한 작업에 대해 어떤 그래프 구조가 가장 적합한지 결정해야 함. 즉 정확도를 최대화하고 비용을 최소화하기 위해 생각(LLM의 중간 추론 단계)을 어떻게 가장 잘 결합할 것인지 고민
• GOT 구현으로 모듈식 아키텍처 제안:
  • (1) 개별 생각에 대한 세밀한 제어:
    • 각 생각에 대해 상세하게 관리할 수 있어, LLM과의 대화를 완전히 통제할 수 있음.
  • (2) 확장 가능한 구조:
    • 새로운 생각 변환, 추론 패턴(즉, 다양한 그래프 구조), 그리고 LLM 모델(GPT-3.5, GPT-4, Llama 2 등)을 쉽게 통합할 수 있도록 설계되었음.
• 생각의 부피(V) 메트릭 제안:
  • Graph of Thoughts(GoT) 프레임워크에서 새로운 평가 지표로 제안된 개념.
  • 이 지표는 특정 생각(또는 노드)에 도달하는 데 기여한 다른 생각들(LLM의 추론 과정)과의 관계를 수량화하는 방식임.
  • 생각의 부피가 크다면 더 많은 생각들이 결합된 결과라는 뜻임. 이는 LLM이 복잡하고 다층적인 추론을 수행했음을 나타낸다.
  • 생각 v의 부피는 그래프 내에서 생각 v에 도달할 수 있는 모든 LLM 생각들의 수를 말함. 구체적으로, v로 도달할 수 있는 방향성 엣지(directed edges) 를 통해 연결된 모든 노드(LLM 생각들)를 포함한다.
  • 부피가 클수록 LLM이 여러 경로를 탐색하고, 다양한 생각을 결합하여 최종적인 결론에 도달한 것을 말함.
  • 기존의 CoT(Chain-of-Thought)나 ToT(Tree of Thoughts) 방식에서는 추론 과정이 선형적이거나 트리 구조로 제한되므로, 생각의 부피는 상대적으로 작고 제한적임.
  • 면, GoT는 임의의 그래프 구조를 활용하기 때문에 생각들 간의 상호 의존성을 더 풍부하게 표현할 수 있다. 이를 통해 GoT는 더 큰 부피를 가지는 생각을 생성할 수 있으며, 이는 더 복잡하고 정교한 추론을 가능하게 함.

 

 

Graph of Thought:

• GoT 는 LLM과의 상호작용에서 생각(추론 과정)을 그래프 구조로 모델링하는 방법을 말함.
• GoT 프레임워크 개요:
  • GoT 구성 요소:
    • G: LLM의 추론 과정(모든 생각과 그 관계를 나타냄)
    • T: 생각 변환(Thought Transformations)의 집합
    • E: 생각을 평가하는 평가 함수
    • R: 가장 관련성 높은 생각을 선택하는 순위 매기기 함수
  • 추론 과정(Reasoning Process):
    • LLM과의 대화는 사용자 프롬프트와 LLM의 응답(생각)으로 구성되며, 이 상호작용을 그래프로 표현됨.
    • 이 그래프 G는 노드(V) 와 엣지(E) 로 구성되며, 각 노드는 문제의 해결 과정(초기, 중간, 최종 결과)을 나타냄.
    • 엣지는 생각 간의 관계를 나타내며, 한 생각(t1)이 다른 생각(t2)을 생성하는 데 사용되었음을 의미한다.
  • 생각 변환(Thought Transformations):
    • GoT에서는 LLM이 생성한 생각들을 변화시키는 다양한 방식의 변환을 지원함.
    • 예를 들어, 여러 고득점 생각을 결합하여 새로운 생각을 만들거나, 하나의 생각을 반복하여 개선할 수 있음.
    • 이러한 변환들은 기존 CoT나 ToT에서는 불가능했던 방식으로, GoT의 그래프 기반 모델링에서만 가능하다.
    • 예시:
      • 글쓰기 예시: 여러 개의 입력 기사를 결합하여 하나의 일관된 요약을 만들 수 있음.
      • 정렬 예시: 여러 개의 정렬된 부분 배열을 결합하여 최종적으로 완전한 정렬 배열을 만들 수 있음.
    • 생각의 집합(aggregation):
      • 여러 생각을 결합하여 새로운 생각을 만드는 변환을 말함.
      • 예를 들어, k개의 생각(v1, v2, …, vk)을 결합하여 새로운 생각 v+ 를 생성할 수 있음.
      • 이때, 새로운 엣지 E+ 는 각 생각(v1, v2, …, vk)이 v+ 로 이어지는 방식으로 추가된다.
    • 생각의 정제(refinement):
      • 현재 생각 v를 반복적으로 개선하는 변환
      • 그래프에서는 v에서 다시 v로 연결되는 루프가 형성되며, 이는 동일한 연결을 가진 반복적인 생각을 나타냄
  • 생각의 평가(Scoring Thoughts):
    • 평가 함수 E(v, G, pθ):
      • v는 평가하려는 특정 생각이고, G는 전체 추론 과정을 나타내는 그래프, 또한 pθ는 LLM의 파라미터를 의미한다.
      • 이 함수는 생각 v가 얼마나 좋은지 점수로 평가함. 점수는 생각 v 자체뿐만 아니라 전체 추론 과정 G와의 관계를 기반으로 평가될 수 있습니다. 이는 특정 생각의 품질이 다른 생각들과 비교하여 상대적으로 평가될 수 있음을 의미한다.
  • 생각의 순위 매기기(Ranking Thoughts):
    • 순위 함수 R(G, pθ, h):
      • R은 전체 추론 과정 G에서 가장 높은 점수를 받은 상위 h개의 생각을 반환하는 함수.
      • h는 반환할 상위 생각의 개수를 나타낸다. 보통 상위 h개의 생각을 선택하여 이후 과정에서 사용하거나 결합함.
      • 이 과정은 여러 생각 중에서 가장 우수한 생각들을 선택하고, 이를 통해 최종 해결책에 기여할 수 있는 최적의 생각을 선택하는 데 사용됨.

 

 

System Architecture & Extensibility:

• GoT 프레임워크는 다양한 모듈이 상호작용하여 LLM의 추론 과정을 관리하고 확장할 수 있도록 설계되었음. 이게 목표.
• GoT 아키텍처는 서로 상호작용하는 여러 모듈로 구성되며, 각 모듈은 다음과 같은 역할을 함:
  • Prompter: LLM으로 보낼 메시지를 준비하는 모듈. 그래프 구조를 프롬프트에 인코딩하는 세부 사항을 처리한다.
  • Parser: LLM의 응답에서 정보를 추출하는 모듈. 각 생각에서 추출한 정보를 바탕으로 GRS를 업데이트하여, 현재까지의 추론 과정을 기록하고 관리한다.
  • Scoring 모듈: LLM의 생각을 검증하고 점수를 부여하는 모듈. 수는 다양한 방식으로 도출될 수 있으며, 경우에 따라 LLM의 도움을 받을 수도 있고, 특정 작업에서는 사람이 직접 점수를 매길 수도 있다고 함.
  • Controller: 전체 추론 과정을 조정하고 진행 방향을 결정하는 모듈.
    • GRS 구조에서 어떤 생각을 선택할지 결정하고, 해당 생각에 어떤 변환을 적용할지 선택한다.
    • 이러한 선택 정보를 Prompter에 전달하고, LLM과의 상호작용이 계속되어야 할지, 아니면 추론 과정을 종료할지 결정함.
    • Controller는 GoO에서 정의된 실행 계획에 따라 작동하며, 변환의 순서와 의존 관계를 관리한다.
• 이외에 GoO(Graph of Operations) 와 GRS(Graph Reasoning State) 라는 중요한 구조가 있다:
  • GoO는 주어진 작업의 그래프 분해를 명시하며, 생각에 적용할 변환과 그 순서, 의존 관계를 정한다. 사용자가 작업 실행 전에 정의하는 정적 구조임.
  • GRS는 현재 LLM의 추론 상태를 유지하고 추적하며, LLM이 생성한 생각과 그 상태를 기록한다.

 

 

정렬 작업 (Sorting Task) 처리 과정:

• 목표: 주어진 숫자 배열을 오름차순으로 정렬하는 작업을 GoT 프레임워크를 통해 수행하는 것.
• (1) GoO(Graph of Operations) 설정:
  • GoO는 작업의 계획을 정의한다.
  • 작업의 각 단계(분할, 부분 정렬, 병합)를 그래프의 노드와 엣지로 표현하여 전체 과정을 구조화한다.
  • 즉, 정렬 작업에서 각 부분 배열을 처리하고, 이 부분들을 결합하여 최종적으로 완전히 정렬된 배열을 얻기 위한 단계적인 변환을 미리 설정함.
  • GoO에서 각 단계는 다음과 같이 나뉨:
    • Step 1: 배열을 더 작은 부분 배열로 나누기 (예: 2개의 부분 배열로 나눔)
    • Step 2: 각 부분 배열을 독립적으로 정렬
    • Step 3: 정렬된 부분 배열을 결합하여 최종 배열을 완성
  • 이렇게 정렬 작업에 필요한 일련의 변환 단계와 그 의존성을 GoO에 정의
• (2) Prompter 모듈: LLM으로 프롬프트 보내기:
  • Prompter는 LLM에 보낼 프롬프트를 준비한다.
  • Step 1에서는, Prompter는 LLM에 숫자 배열을 두 개의 부분 배열로 나누라는 지시를 포함한 프롬프트를 만든다.
  • Step 2에서는 각 부분 배열을 정렬하라는 프롬프트를 작성한다.
  • Step 3에서는 정렬된 부분 배열을 결합하는 작업에 대한 프롬프트를 생성한다.
• (3) Parser 모듈: LLM의 응답에서 정보 추출:
  • Parser는 LLM이 응답으로 제공한 각 생각에서 정보를 추출함.
  • 각 생각의 상태를 업데이트하여 GRS에 기록합니다. 즉, 각 단계에서 추론된 상태(예: 현재 배열 상태)가 기록된다.
• (4) Scoring 모듈: 생각 검증 및 점수 부여:
  • Scoring 모듈은 LLM이 생성한 생각이 올바른지, 즉 조건을 만족하는지 검증한다.
  • Step 1에서 배열이 적절하게 두 부분으로 나뉘었는지 확인, Step 2에서 배열이 올바르게 정렬되었는지 점수로 평가, Step 3에서 최종 배열이 완전히 정렬되었는지 확인하고, 이에 따라 최종 점수를 부여함.
• (5) Controller 모듈: 과정 제어 및 추론 결정:
  • Controller는 전체 과정의 흐름을 관리.
  • GRS에 저장된 상태를 기반으로 다음에 어떤 변환을 수행할지, 어떤 생각을 선택할지 결정한다.
  • Controller는 GoO에서 미리 정의된 실행 계획에 따라 각 단계를 제어하며, 작업이 완료되었는지 여부를 판단함.
  • 정렬이 완료되면, Controller는 전체 과정을 종료함.

 

 

Graph of Thoughts(GoT) vs ToT, CoT :

• 총 생각의 수가 N, 체인의 길이는 K.
• CoT
  • Latency: N
  • Volume: N

• CoT-SC (Chain-of-Thought with Self-Consistency):
  • 단일 시작 생각에서 시작하는 k개의 독립적인 체인으로 구성
  • 각 체인은 독립적으로 추론을 진행하며, 최종 결과에서 가장 일관된 답을 선택함.
  • 부피가 N/k 인 이유는 여러개의 생각들 중에서 하나만 선택되기 때문.
  • Latency: N/k
  • Volume: N/k
• ToT (Tree of Thoughts):
  • 완전한 k진 트리(complete k-ary tree) 로 표현
  • 각 노드에서 k개의 분기를 생성하여 다양한 추론 경로를 탐색
  • Latency: logₖ N
  • Volume: O(logₖ N) (여러개의 생각 경로는 많지만 최종적인 응답에 포함되는 생각의 개수는 적을 것.)

• GoT (Graph of Thoughts):
  • 완전한 k진 트리의 리프(leaf) 노드들이 동일한 크기의 반전된(reverse) k진 트리와 연결되어 있다고 가정
  • 리프 노드에서 반전된 트리로의 연결을 통해 생각의 집합(aggregation)을 활용
  • 여기서 말하는 반전된 트리는 부모-자식 간의 방향이 뒤집힌 트리로, 리프 노드들이 역으로 부모 역할을 하고, 더 많은 노드들과 연결되면서 생각들을 통합하는 방식으로 활용되는 걸 말함. (리프 노드 → 중간 노드 → (새로운) 루트 노드)
  • Latency: logₖ N
  • Volume: N (N개의 생각(thought)이 합쳐져서 최종 생각을 구성하기 때문)

 

 

Conclusion:

• GoT 는 기존의 CoT 와 ToT 와 비교했을 떄 기존의 할 수 없었던 유연한 워크 플로우와 기능을 제공해준다: 생각의 집합(aggregation) 과 생각의 정제(refinement) (트리의 연쇄 구조와 CoT 의 선형성에 제한받지 않음.)
• 여기서 제안하는 이러한 워크플로우 적인 기능은 LangGraph 와 유사하다. LangChain 에서 이것들을 구현하기 위에서 개발한 기능으로 보임.
• LangGraph 에서는 이 논문에서 말하는 기능을 만들 수 있음: 평가 함수, 그래프 표현, 순위 매기기, 생각의 집합, 생각의 정제 등
• GoT 를 ToT, CoT 와 비교하기 위해서 Latency 와 Volume 측면에서 비교해볼 수 있음. 그런 측면에서 더 우수하다. 이렇게.