Hanyong Lee

Ph.D. student in artificial intelligence at CAU AutoML Lab.

8 minute read

요약: 대형 언어 모델(LLM)의 프롬프트 능력을 향상시키는 “Graph of Thoughts (GoT)” 프레임워크를 소개하며, 이는 LLM의 정보를 그래프 형태로 모델링하여 시너지 효과를 창출하고 다양한 작업에서 성능을 개선한다. GoT는 새로운 사고 변환을 확장할 수 있어 새로운 프롬프트 방식에 기여할 수 있다.

1 Introduction

대형 언어 모델(LLMs)은 AI 분야에서 중요한 역할을 차지하고 있다. 최근 몇 년간 GPT, PaLM, LLaMA 등 디코더 전용 트랜스포머 모델들이 빠르게 발전하였다. 프롬프트 엔지니어링은 LLM 작업을 해결하는 효율적인 방법으로, 작업 설명을 LLM에 입력하는 방식이다. 올바르게 작성된 설명은 LLM이 자가 회귀 토큰 기반 메커니즘으로 텍스트를 생성하여 문제를 해결하게 한다. 이러한 프롬프트는 예제 작업과 솔루션을 포함할 수도 있으며(퓨샷 프롬프팅), 전혀 포함하지 않을 수도 있다(제로샷 프롬프팅).

image

image

Chain-of-Thought (CoT) 접근 방식은 문제를 해결하는 과정에서 중간 단계의 사고 과정을 포함하여 성능을 향상시킨다. CoT의 발전된 형태인 Self-Consistency with CoT (CoT-SC)는 여러 CoT를 생성하고 최상의 결과를 선택하는 방법이다. 최근에는 CoT 및 CoT-SC를 확장한 Tree of Thoughts (ToT) 접근이 제안되어 다양한 사고 경로를 모델링할 수 있게 되었다. 하지만 ToT는 사고 과정을 단단한 트리 구조에 제한하여 근본적으로 사고 능력을 제한한다.

이 연구에서는 LLM의 사고 과정을 임의의 그래프 구조로 구성하여 더 강력한 프롬팅이 가능하다고 주장한다. 인간의 사고 방식은 단순한 사고의 연쇄를 넘어서 복잡한 네트워크 형성의 예를 보여준다. 우리는 Graph of Thoughts (GoT)를 제안하여, LLM의 사고를 정점으로, 사고 간의 의존성을 엣지로 모델링한다. GoT는 CoT와 ToT를 통합하여 더 복잡한 사고 패턴을 지원하며, 여러 가지 설계 과제를 해결해야 한다.

GoT는 독립적인 사고에 대한 세밀한 제어를 가능하게 하며, 새로운 사고 변환과 추론 패턴을 통합할 수 있다. 우리는 GoT의 몇 가지 활용 사례(정렬, 키워드 계산, 집합 연산 등)를 제시하고, 그래프 기반 패러다임을 활용한 구현 방법을 상세히 설명한다. GoT는 이전 방식들보다 성능을 70% 이상 개선하면서도 비용을 31% 이상 절감할 수 있다.

마지막으로, 우리는 프롬팅 전략을 평가하기 위한 새로운 메트릭인 ‘사고의 볼륨’을 제안하여 GoT가 다른 방식보다 본질적으로 더 큰 사고 볼륨을 가질 수 있음을 보여준다.

2 The GoT Framework

image

GoT(Thought의 그래프)는 사용자 메시지(프롬프트)와 LLM의 응답(생각)으로 구성된 대화를 바탕으로 형성된다. GoT는 (G; T; E; R)라는 튜플로 모델링되며, 여기서 G는 LLM의 추론 과정, T는 잠재적 사고 변환, E는 사고의 점수를 얻기 위한 평가 함수, R은 관련 있는 사고를 선택하는 랭킹 함수다.

2.1 추론 과정

추론 과정은 유향 그래프 G = (V; E)로 모델링되며, 여기서 V는 정점 집합, E는 엣지 집합이다. 각 정점은 문제에 대한 솔루션을 포함하며, 유향 엣지(t1; t2)는 t2가 t1을 기반으로 생성된 것을 나타낸다. 사고 변환을 통해 G를 발전시킬 수 있으며, 예를 들어 현재까지 가장 점수가 높은 사고들을 새 사고로 병합하는 것이 있다.

2.2 사고의 변환

GoT는 그래프 기반 모델 덕분에 새로운 사고 변환을 가능하게 한다. 예를 들어, 여러 입력 기사를 하나의 일관된 요약으로 결합하거나, 여러 정렬된 부분 배열을 하나의 최종 정렬된 배열로 병합할 수 있다. 각 변환은 T(G; pθ)로 모델링되며, G는 현재 추론 상태를 반영하는 그래프이다. 사용자는 필요에 따라 사고를 명시적으로 제거할 수도 있다.

2.3 사고의 점수 매기기 및 순위 정하기

사고는 현재 솔루션이 충분히 좋은지를 이해하기 위해 점수를 매겨지며, 점수는 E(v; G; pθ)라는 일반 함수로 모델링된다. GoT는 사고를 랭킹할 수 있으며, R(G; pθ; h) 함수를 통해 최상위 점수를 가진 사고를 반환하는 방법으로 순위를 매긴다. 이러한 기능은 사용 사례에 따라 달라질 수 있으며, 예를 들어 정렬의 경우 점수는 올바르게 정렬된 요소의 수에 해당한다.

3 System Architecture & Extensibility

GoT 아키텍처는 상호 작용하는 모듈들로 구성되어 있으며, 이들 모듈은 다음과 같다: Prompter (LLM에 대한 메시지를 준비), Parser (LLM의 생각에서 정보 추출), Scoring 모듈 (LLM의 생각을 검증하고 평가), Controller (전체 추론 과정을 조정하고 진행 방법 결정). Controller에는 두 가지 중요한 요소가 포함되어 있다: 작업의 그래프 분해를 명시하는 정적 구조인 Graph of Operations (GoO)와 LLM의 추론 과정 상태를 유지하는 동적 구조인 Graph Reasoning State (GRS)이다.

  • Prompter: LLM에 전송할 프롬프트를 준비하며, 그래프 구조의 인코딩 세부 사항을 담당한다. 사용자가 특정 용도에 맞는 그래프 인코딩을 구현할 수 있다.

  • Parser: LLM의 생각에서 정보를 추출하여 생각 상태를 구성하고, 이를 GRS에 업데이트한다.

  • Scoring & Validation: LLM의 생각이 정확성 조건을 충족하는지 검증하고 점수를 부여한다. 점수는 경우에 따라 LLM 또는 인간이 부여할 수 있다.

  • Controller: GRS 구조에서 생각을 선택하고, 어떤 변환을 적용할지 결정하여 Prompter에 전달한다. 실행 계획에 따라 전체 과정을 마무리할지 추가 상호작용을 시작할지 결정한다.

GoO는 작업 실행 계획을 규정하는 정적 구조로, GRS는 LLM의 추론 과정에 대한 정보(현재 실행된 작업, 생성된 LLM 생각의 상태, 점수 등)를 유지한다. 이 요소들은 다양한 프롬프트 형식을 쉽게 구현할 수 있는 확장 가능한 API를 제공한다. API는 Figure 2의 녹색 부분에 나열되어 있으며, 문서에서는 자세히 설명되어 있다.

4 Example Use Cases

image

이 섹션에서는 두 가지 예제 사용 사례를 다룹니다: 정렬과 집합 교집합.

첫 번째 사용 사례는 정렬이다. 숫자 0에서 9까지의 시퀀스를 정렬하는 데 있어 LLM(대규모 언어 모델)이 길이에 따라 중복 개수를 일관되게 맞추지 못하므로, 정렬 알고리즘이 정확하지 않다. GoT에서는 머지 기반 정렬을 사용하여 입력 시퀀스를 서브 배열로 분해하고, 각 서브 배열을 개별적으로 정렬한 후 최종 솔루션으로 머지하여 결과를 도출한다.

두 번째 사용 사례는 집합 교집합이다. 두 집합의 교집합을 구하는 과정은 정렬과 유사하며, 두 번째 입력 집합을 서브셋으로 분할한 후 LLM의 도움으로 첫 번째 입력 집합과의 교집합을 결정하여 최종적으로 교집합 집합을 집계한다.

추가적으로, 키워드 카운팅도 다루어집니다. 이 경우 GoT는 입력 텍스트를 여러 구절로 나눈 후 각 구절에서 키워드의 빈도를 세고 이 결과를 집계한다. 최종 점수는 키워드의 개수와 정확한 개수 간의 절대 차이를 합산하여 계산된다.

마지막으로, 문서 병합 사례에서는 여러 개의 입력 문서를 바탕으로 중복 최소화 및 정보 최대화를 목표로 하는 새로운 비밀유지계약(NDA) 문서를 생성한다. 이 과정에서 LLM에게 두 가지 값을 요청하여 결과의 중복성과 정보 보유율을 평가하고, 이 값을 바탕으로 조화 평균을 계산한다.

5 The Latency-Volume Tradeoff

GoT(Generative of Thoughts)는 이전의 프롬프트 방식들보다 지연(latency)과 부피(volume) 간의 균형에서 개선된 점을 보여준다. 여기서 볼륨은 주어진 생각 t에 영향을 줄 수 있는 이전의 LLM(대규모 언어 모델) 생각의 수로 정의된다. 공식적으로 볼륨은 t로 가는 경로가 있는 생각의 수로 정의된다.

모든 프롬프트 방식의 총 비용은 \(O(n)\)으로 고정되어 있으며, 단일 생각을 출력하는 데 드는 시간은 \(O(1)\)로 가정한다. 다양한 프롬프트 방식의 구조는 다음과 같다:

  • CoT: 독립적인 체인의 집합으로, 하나의 시작 생각에서 출발.
  • CoT-SC: 기존 CoT와 유사하지만, 지연을 줄이기 위해 k개의 경로로 나뉘어짐.
  • ToT: 완전 k-ary 트리 구조.
  • GoT: 각 리프에서 동일한 크기의 “거울” k-ary 트리와 결합된 완전 k-ary 트리.

다양한 프롬프트 방식의 성능을 비교한 표는 다음과 같다:

프롬프트 방식 지연 (Latency) 부피 (Volume)
CoT N N
CoT-SC N/k N/k
ToT logkN O(logkN)
GoT logkN N

GoT는 낮은 지연과 높은 부피를 동시에 제공하는 유일한 방식으로, 이는 GoT가 생각의 집합을 활용하여 그래프 분해에서 어떤 중간 생각에서든 최종 생각에 도달할 수 있게 한다는 점에서 가능하다.

6 Evaluation

GoT의 장점을 기존 최첨단 기법과 비교하여 보여준다. GoT는 특히 ToT에 비해 일관되게 성능이 우수하며, IO, CoT, CoT-SC와도 비교 실험을 진행하였다. 평가 방법론으로는 각 작업 및 비교 기준에 대해 100개의 입력 샘플을 사용하고, 온도를 1.0으로 설정하여 4k의 컨텍스트 크기를 적용했다. 각 실험에서 비슷한 비용을 유지하기 위해 각 기법의 사고 수를 고정했다.

GoT는 ToT와 ToT2에 비해 모든 문제 인스턴스에서 높은 성능을 보이고, ToT에 비해 비용을 줄이는 효과가 있음을 보여준다. 예를 들어, GoT는 P = 128에서 ToT에 비해 중앙 오류를 62% 줄이면서 31% 이상의 비용 절감을 달성했다. 이는 복잡한 작업을 단순한 하위 작업으로 분해하고 독립적으로 해결하여 최종 결과로 점진적으로 합치는 GoT의 특성에서 기인한다.

GoT는 IO 및 CoT와 비교에 있어서도 일관되게 더 높은 품질의 결과를 제공한다. 예를 들어, P = 64의 정렬 문제에서 GoT의 중앙 오류는 각각 CoT 및 IO보다 65% 및 83% 낮다. GoT는 복잡한 문제의 크기(P)가 커질수록 이러한 장점이 더욱 두드러지며, 문제 크기가 증가할수록 GoT의 중앙 오류 수치는 감소한다.

작업을 하위 작업으로 분해할 때, 응답의 크기 및 입력(토큰 수)은 분해의 정도에 비례하여 감소한다. 그러나 프롬프트의 “정적” 부분(예: 몇 가지 예시)은 상당한 오버헤드가 될 수 있다. 궁극적으로 그래프 분해의 목표는 LLM이 단일 프롬프트로 대다수의 경우에 정확하게 작업을 해결할 수 있도록 작업을 분해하는 것이다. 이 과정은 후속 수정 단계의 수를 크게 줄여준다.

7 Related Work

GoT와 관련된 연구들을 요약하자면 다음과 같다.

프롬프트 패러다임과 접근법 프롬프트와 관련된 다양한 연구들이 존재하며, 이는 Section 1과 Table 1에 자세히 설명되어 있다. 예를 들어, Plan-and-Solve (Wang et al. 2023a), Fu et al. (2022)의 방식, self-taught reasoner (Zelikman et al. 2022), Shum et al. (2023)의 방식, 자동 프롬프트 생성 (Shin et al. 2020; Li and Liang 2021; Lester et al. 2021), 간결한 답변의 불릿 포인트 형태로의 동시 확장 (Ning et al. 2023), 후보 집합에서 최적의 프롬프트 선택 (Zhou et al. 2022) 등이 있다. 이들 대부분은 GoT 추상화를 통해 표현될 수 있다.

프롬프트 체이닝 프롬프트 체이닝에서는 서로 다른 LLM들을 연결하여 사용한다 (Creswell et al. 2022; Nye et al. 2021; Wu et al. 2022; Dohan et al. 2022; Qiao et al. 2023; Wu et al. 2022). GoT를 확장하여 이러한 방식을 위한 실행 엔진으로 활용할 수 있다.

자기 반성 및 자기 평가 최근에 자기 반성과 자기 평가와 관련된 연구들이 소개되었다 (Shinn et al. 2023; Paul et al. 2023; Madaan et al. 2023; Xie et al. 2023; Zhu et al. 2023). GoT에서는 프롬프트 내에서 생각의 그래프를 확장할 때 자기 평가에 부분적으로 의존한다.

LLMs 및 계획 복잡한 작업을 LLM으로 계획하는 방법에 관한 많은 연구가 있다 (Huang et al. 2022a,b; Zhang et al. 2023; Yao et al. 2023b; Yang et al. 2023; Wang et al. 2023c). GoT는 복잡한 그래프 기반 계획 생성을 위한 패러다임을 제공하여 이러한 방식들을 강화할 수 있는 일반적인 프레임워크로 볼 수 있다.

그래프 및 그래프 컴퓨팅 그래프는 일반 컴퓨팅 환경에서 중요하고 인기 있는 요소가 되었다 (Lumsdaine et al. 2007; Malewicz et al. 2010; Gregor and Lumsdaine 2005a,b; Sakr et al. 2021). 최근에는 그래프 데이터베이스 (Robinson et al. 2015; Besta et al. 2022b, 2023b,d,c), 그래프 패턴 매칭 (Fan et al. 2010; Cheng et al. 2008; Teixeira et al. 2015; Besta et al. 2021a,b, 2022d), 그래프 스트리밍 (Feng et al. 2015; Dhulipala et al. 2019; Besta et al. 2023a), 그래프 머신 러닝 및 그래프 신경망 (Hamilton et al. 2017; Wu et al. 2021; Zhou et al. 2020; Zhang et al. 2022; Chami et al. 2020; Bronstein et al. 2017; Besta et al. 2022a,c; Gianinazzi et al. 2021; Scarselli et al. 2008)에 대한 관심이 증가하고 있다. 본 연구에서는 그래프 추상화를 LLM의 프롬프트 능력을 향상시키는 주요 메커니즘으로 활용하고 있다.

8 Conclusion

프롬프트 엔지니어링은 대규모 언어 모델(LLM) 연구의 중심 분야 중 하나로, 모델 업데이트 없이도 LLM을 효율적으로 사용할 수 있게 한다. 그러나 효과적인 프롬프트를 설계하는 것은 도전적인 작업이다. 본 연구에서는 다양한 작업을 효과적으로 해결할 수 있는 새로운 패러다임인 Graph of Thoughts (GoT)를 제안한다. GoT는 LLM의 추론을 그래프로 모델링하여, 생각을 정점으로, 생각 간의 의존성을 엣지로 표현한다. 이러한 구조는 생각의 집합이나 중간 해결책을 결합하는 비선형적 문제 해결 과정을 반영한다.

GoT는 다양한 프롬프트 사용 방식과 비교해 성능이 우수하며, 예를 들어 ToT 대비 정렬 품질이 62% 향상되고 비용이 31% 이상 절감된다. 또한, GoT의 출력 정보 범위를 나타내는 새로운 메트릭인 ‘사고의 볼륨’을 제안하였으며, 이 또한 GoT의 우수성을 보여준다. 그래프 추상화는 과거 몇십 년 동안 컴퓨터와 AI 디자인의 기초가 되어왔으며, 본 연구는 이러한 개념을 프롬프트 엔지니어링 분야에 접목시켰다.

독자의견

  • ToT를 확장하여 그래프 형태의 reasoning 탐색을 수행하는 방법론은 LLM이 더 복잡한 “생각”을 할 수 있게 한다.
  • 하지만 그 사용예시로 보여준 정렬 테스크나 키워드 카운팅, 집합 연산 등의 수학적인 작업을 굳이 LLM으로 해결해야하는가에 대한 필요성이 크게 느껴지지 않는다.
  • 위와 같은 수학 계산이 필요하면 Tool을 사용한 LLM agent 방식이 더 효과적, 효율적일 것이라고 생각된다.

Comments

You May Also Enjoy