Image DeepLearning Engineer입니다. AI 모든 분야에 관심이 많습니다. NLP 연구개발 공부하고 관심갖는 사람으로서 논문과 정리된 내용을 좀 더 쉽게 이해하는데 집중하여 작성하였습니다.

논문명

Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures

1. 논문 개요

이 논문은 LLM의 추론 성능을 개선하기 위해 Adaptive Graph of Thoughts(AGoT)라는 새로운 접근 방식을 제안한다. AGoT는 CoT, ToT, GoT의 장점을 통합하여, 테스트 시점(test-time)에서 모델의 성능을 향상시키는 프레임워크입니다. AGoT는 문제를 작은 단위로 분해하고, 필요한 부분만 연산을 확장하여 좀 더 효율적으로 최적의 답을 찾게 됩니다. 추가적인 RLHF나 Fine-tuning없이 최대 46.2%의 성능 개선을 이루어 RL 기반 기법과 유사한 효과를 기대하게 됩니다.

Definition

  • CoT(Chain of Thoughts):
    • 복잡한 작업을 최종 해결을 향한 일련의 논리적 단계로 세분화하여 인간과 유사한 추론 과정을 시뮬레이션하는 인공 지능의 접근 방식입니다.
    • 인간 지능의 근본적인 측면을 반영하여 문제 해결을 위한 구조화된 메커니즘을 제공하는 방법론을 뜻합니다.
  • ToT(Tree-of-Thought):
    • 복잡한 개념이나 문제를 계층적 구조로 분해하여 이해하고 해결하는 프롬프트 엔지니어링 기법을 말합니다. ToT는 개념 간의 상하위 관계를 활용하여 사고의 흐름을 체계화하고, 이를 통해 AI시스템이 보다 논리적이고 일관된 응답을 생성할 수 있도록 돕습니다. ToT 프롬프트 설계에서는 주어진 주제를 상위 개념부터 하위 개념까지 단계적으로 세분화하는 것이 핵심입니다.
  • GoT(Graph-of-Thoght):
    • 그래프를 활용하여 개념 간의 관계와 맥락을 포현함으로써 프롬프트를 설계하는 방법입니다. GoT는 개념들을 노드로, 개념 간의 관계를 엣지(edge)로 표현하는 그래프 구조를 기반을 말합니다.

Prompt Chaining과 생각의 연결고리(CoT)의 차이점

프롬프트 체이닝에 대해 살펴보면, 프롬프트 체이닝은 AI가 주어진 상황이나 질문에 따라 응답을 생성하도록 유도하는 보다 기초적인 형태의 CoT 프롬프트입니다. 이와 달리, CoT 프롬프트는 단순히 일관되고 관련성 있는 응답을 생성하는 것을 넘어 AI가 전제와 결론을 포함한 전체 논리적 논증을 처음부터 구성하도록 요구합니다. 프롬프트 체이닝은 개별 응답을 다듬는 데 중점을 두는 반면, CoT 프롬프트는 포괄적이고 논리적으로 일관된 논증을 생성하여 AI의 문제 해결 능력의 한계를 뛰어넘는 것을 목표로 합니다.

Image

2. 기존 방법론과 AGoT의 차이점

기존 LLM 추론 기법으로는

  • CoT
  • ToT
  • GoT
  • AIoT

가 있으며, 각 기법은 특정한 한계를 가지고 있습니다.

Image2

CoT는 순차적 사고 과정을 통해 논리적인 답을 유도하지만, 직렬적 구조로 인해 복잡한 문제에서 한계를 나타냅니다.

ToT는 여러 경로를 동시에 탐색하여 정답 가능성을 확장하지만, 트리연산이다보니 불필요한 분기가 많아 연산량이 증가할 수 있습니다.

GoT는 임의의 노드 간 연결을 허용해 복잡한 문제 해결이 가능하지만, 효과적으로 탐색되지 않으면 성능이 저하될 수 있어 탐색적인 부분을 신경써야 합니다.

AIoT는 반복적 사고 구조를 도입해 문제 해결력을 높이지만, 구조가 고정적이어서 유연성이 부족할 수 있습니다.

AGoT는 동적 그래프(directed acyclic graph, DAG) 기반 추론을 활용해 앞서의 한계를 극복합니다. 기존 기법들이 정해진 방식으로 사고 단계를 확장하는 반면, AGoT는 문제를 분석하여 필요한 부분만 확장하여 연산량을 최소화하면서도 정교한 추론이 가능하도록 합니다.

3. AGoT의 작동 원리

AGoT는 DAG 형태의 동적 구조를 사용하여 복잡한 문제를 해결합니다.

Image3

기본적인 동작 과정은 다음과 같습니다.

  1. 초기 문제를 그래프의 최상위 노드로 설정
  • 입력 질문을 분석하여 초기 사고(thought) 노드를 생성합니다.
  1. 각 노드에 대해 복잡도 평가 수행
  • 특정 사고가 충분히 단순하면 즉시 평가(evaluate)하고, 복잡하면 서브 그래프를 확장합니다.
  1. 서브 그래프 확장을 통한 정교한 추론
  • 필요할 때만 특정 노드를 확장하여 추가 분석을 수행하며, 전체적인 연산량을 제어합니다.
  1. 최종적인 결과 도출
  • 그래프의 최상위 노드에서 최종 답을 종합하여 출력합니다.
  • 이 과정에서 AGoT는 기존 CoT, ToT, GoT의 장점을 유지하면서도, 필요 없는 연산을 줄이는 최적화된 방식으로 추론을 수행합니다.

4. AGoT의 수학적 정의 및 알고리즘 개요

  • AGoT의 주요 연산은 아래와 같이 정의할 수 있습니다.
    • Q: 모든 가능한 질문(query) 집합
    • T: 사고(thought) 집합
    • G: DAG(그래프) 자체
    • C(T, G): 특정 사고가 복잡한지 평가하는 함수
    • Eval(T, G): 사고를 평가하고 결과를 도출하는 함수

이러한 정의를 기반으로 Algorithm 1: Adaptive Graph of Thought(AGoT)가 동작합니다.

입력 질문 Q에 대해 DAG를 구성하고, 복잡도를 평가한 후 최적의 답을 찾는 방식입니다.

DAG에서 특정 노드가 “복잡한” 것으로 판단되면 서브 그래프를 확장하고, 그렇지 않으면 바로 답을 평가합니다. 이 과정을 반복적으로 수행하면서 전체적인 연산 효율성을 유지합니다.

5. 실험 및 성능 평가

AGoT는 다양한 데이터셋에서 성능을 평가하며, 기존 추론 기법들과 비교하여 더 나은 결과를 보입니다.

추론(Reasoning) 성능 평가:

GPQA

  • GPQA 데이터셋에서 GPT-4o-mini 모델을 사용했을 때, 기존 CoT, AIoT 대비 최대 32.4% 성능 향상했고 GPT-4o 모델에서는 최대 46.2%의 개선 효과를 보여주었고

정보 검색(Retrieval) 성능 평가:

  • HotpotQA, MoreHopQA, HybridQA와 같은 데이터셋에서 최대 30.9% 성능 향상을 보여주었고 LLM 기반 정확도 평가(LLM-Assisted Accuracy Score, LAAS)에서도 가장 높은 성능을 보여주었습니다.

탐색 기반 문제 해결(Explorative Tasks):

  • Game of 24 (수학적 연산 문제): 기존 입출력(IO) 방식 대비 +400% 성능 개선보여주었습니다.

Mini-Crossword 문제:

  • AIoT와 유사한 성능을 보이며, 조합 탐색 문제에서도 효과적입니다.

6. 논의 및 향후 연구 방향

AGoT의 장점과 한계를 분석하면 다음과 같습니다.

장점

  1. 모델 자체를 변경하지 않고 성능 향상 가능
  • 사전 학습된 LLM을 그대로 활용하면서도 성능을 높일 수 있어 실용적입니다
  1. 연산 자원을 효율적으로 사용하여 불필요한 계산 최소화
  • DAG 기반 동적 구조로 필요할 때만 사고 과정을 확장하여 최적화된 연산을 수행할 수 있습니다.
  1. 다양한 유형의 문제에서 고른 성능 개선
  • 추론, 검색, 탐색 기반 문제 등 다양한 분야에서 효과적입니다.

한계점

  1. 최적의 하이퍼파라미터 탐색이 필요합니다.

DAG의 깊이, 노드 개수 등의 하이퍼파라미터를 조정하는 과정이 필요합니다.

  1. AIoT와 유사한 성능을 보이는 경우가 있습니다.

특히 Mini-Crossword 같은 특정 도메인에서는 AIoT와 차별성이 적은 편입니다.

  1. 반복 구조에서 오류 증폭 가능성

LLM의 특성상 오류가 누적될 가능성이 있으며, 이를 방지하기 위한 추가적인 안정화 기법을 고안할 필요성이 있습니다.

7. 결론

본 논문에서 제안된 Adaptive Graph of Thoughts(AGoT)는 기존 LLM 추론 기법(CoT, ToT, GoT, AIoT)의 한계를 극복하면서, 동적 그래프 구조를 통해 테스트 시점에서 효율적으로 추론 성능을 향상시키는 방법론입니다

미세 조정 없이도 LLM의 성능을 향상할 수 있으며, 최대 46.2%의 개선 보여주는 효과가 있습니다.

게임 이론, 탐색 기반 문제 해결, 정보 검색 등 다양한 문제에서 효과적으로 동작합니다.

연산 효율성과 성능을 모두 고려한 기법으로, 향후 LLM 추론 프레임워크의 중요한 대안이 될 가능성이 높습니다.

AGoT는 향후 더 정교한 최적화 기법과 결합하여 보다 강력한 LLM 추론 기법으로 발전할 가능성이 큽니다.

Reference:

  • https://www.linkedin.com/posts/ugcPost-7301852092229394433-nrcx?utm_source=share&utm_medium=member_desktop&rcm=ACoAACIf4j4BaHFSrXBvSgbiZqSg4GG5YwZPE1U
  • https://www.ibm.com/kr-ko/think/topics/chain-of-thoughts
  • https://aiheroes.ai/community/153