CoAT: Chain-of-Associated-Thoughts 논문 리뷰

대규모 언어 모델(LLM)은 일반적으로 단일 질의(“빠른 사고”)만으로 추론 결과를 생성하므로 복합적이고 반복적인 추론에는 한계가 있다. 최근 OpenAI-o1 같은 프로젝트에서 인간의 “느린 사고” 과정처럼 단계적이고 반복적으로 사고를 보강하는 방법론이 주목받고 있다. CoAT(Chain-of-Associated-Thoughts) 프레임워크는 이에 착안하여, 몬테카를로 트리 탐색(MCTS)과 연상 메모리(Associative Memory)라는 동적 외부 지식 보강 메커니즘을 결합했다. CoAT는 MCTS의 체계적 탐색 구조와 연상 메모리의 적응적 학습 능력을 융합하여 LLM의 추론 탐색 공간을 크게 확장한다. 각 단계에서 새로 유도된 핵심 정보를 실시간으로 반영함으로써, 과거의 추론을 재검토·수정하고 점진적으로 지식을 보강함으로써 최종 답변의 정확도와 포괄성을 높인다.

그림 1. (좌) 전통적인 인간의 연쇄적 사고 과정, (우) CoAT의 연상-강화된 사고 과정. CoAT는 각 추론 단계에서 추가 정보(Extra Info)를 동적으로 보강하여 인간의 연상 메커니즘을 모방한다.

CoAT의 핵심 기여는 다음과 같다: (1) 연상 메모리 메커니즘 도입: 추론 과정 중에 관련 외부 지식을 동적으로 검색·통합하는 메커니즘을 도입하여 LLM이 지속적으로 새로운 정보를 보강하도록 함.. (2) MCTS 최적화: MCTS의 경로 탐색 중간에 연상 단계(Association)를 삽입하고 평가 기준을 보완하여, 각 노드에 연관된 정보를 평가 요소로 반영함... (3) 유연한 외부 지식 소싱: “외부 두뇌(External Brain)”를 통해 지식 그래프, 벡터 DB, 웹 검색 등에서 정보를 얻어 연상 메모리를 강화할 수 있어, 필요한 경우 더 풍부한 정보를 확보할 수 있다..

본 보고서에서는 CoAT 프레임워크의 개념적 배경과 기존 연구 대비 특징(Chain-of-Thought, RAG 등), 전체 시스템 아키텍처, 알고리즘 및 수식 해설, 실험 설정 및 결과 분석, 한계점과 향후 활용 가능성, 코드 구현 방향 등을 상세히 다룬다.

1. 관련 연구

기존 LLM 추론 전략으로는 Chain-of-Thought(CoT) 프롬프트 기법이 대표적이다. CoT는 복잡한 문제를 작은 단계로 분해하는 방식으로 추론 품질을 개선하지만, 일단 분해된 이후에는 모델이 이전 추론을 동적으로 재검토하거나 수정할 수 없다는 한계가 있다. 또한 RAG(Retrieval-Augmented Generation) 기법은 외부 지식을 초기 입력 단계에서 가져와 LLM에 보강하지만, 한번 가져온 지식은 추론 도중 동적으로 갱신되지는 않는다. 최근에는 CoT 변종으로 Self-Consistency CoT, Graph-of-Thought, Tree-of-Thought 등 다양한 방법이 제안되었으나, 기본적으로 고정된 추론 메커니즘을 크게 바꾸지는 않는다.

한편 몬테카를로 트리 탐색(MCTS)는 불확실성하 의사결정에서 균형 잡힌 탐색을 수행하는 기법으로, 최근 LLM 추론에 적용되려는 시도가 나오고 있다. 예를 들어 LLM-MCTS, LATS, RAP 등의 연구는 MCTS를 이용해 LLM의 탐색 공간을 확장하거나 계획적 추론을 수행하지만, CoAT는 여기에 연상 메모리 개념을 더해 각 탐색 노드에 새로운 정보를 삽입하도록 확장했다.

또한 외부 지식 활용 측면에서 외부 지식 증강 메커니즘 연구가 진행 중이다. 기존의 메모리-증강 신경망이나 힙포캄(RAG) 등은 외부 지식을 입력 단계에 고정적으로 통합하지만, CoAT는 이와 달리 실시간으로 연관 정보를 찾고 추론에 반영할 수 있다.

본 논문의 CoAT는 이러한 기존 전략들보다 동적이고 반복적인 추론을 중시한다. 특히 CoT와 달리 추론 도중 연상의 유연성을 도입하고, RAG처럼 외부 지식을 활용하되 추론 중 계속 갱신할 수 있는 메커니즘이 특징적이다. 이로써 전통적 CoT나 RAG의 제한을 넘어, 복잡한 문제에서 더욱 적응적이고 맥락에 맞는 답변을 생성할 수 있다..

2. CoAT 프레임워크 아키텍처

CoAT 시스템은 MCTS 탐색 트리를 중심으로 동작한다. MCTS의 각 노드는 LLM이 생성한 내용(Generated Content, $G$)과 해당 단계에서 검색된 연관 정보(Associative Memory, $AM$)를 포함한다. 트리 탐색 과정은 그림 2와 같다.

그림 2. CoAT 전체 구조: 질의(Query)에 대해 LLM(Target LLM)이 추론을 수행하며, 각 MCTS 노드에서 생성 내용($G$)과 연관 정보($AM$)가 누적된다. 필요한 경우 지식 그래프, 벡터 DB, 웹 검색 등의 외부 두뇌(External Brain)를 통해 추가 정보를 가져올 수 있다. 오른쪽의 평가기(Evaluator)는 각 노드의 품질(생성값 $V_G$ 및 연상값 $V_{AM}$)을 계산하여 MCTS의 UCT 값에 반영한다.

시스템 흐름을 요약하면 다음과 같다. 우선 초기 루트 노드에는 질의 $q$만이 들어간다. Expansion(확장) 단계에서 트리의 각 후보 경로에 대해 새로운 노드를 생성할 때, LLM은 현재 노드의 맥락(루트부터의 생성 내용과 연상 메모리 모두)을 입력으로 받아 다음 내용을 생성한다. 이 때 노드마다 연상 메모리 단계가 삽입되어, 생성된 내용으로부터 추가로 보강할 만한 핵심 정보를 찾아낸다. 구체적으로, 현재 노드의 생성 내용 $G_i$와 외부 두뇌(필요 시)를 통해 관련 정보를 얻어, 노드의 연상 메모리 $AM_i$를 생성한다. 이 $AM_i$는 기존에 생성된 내용과 중복을 최소화하며 중요 정보를 함축한다..

그 다음 Evaluation(평가) 단계에서, 각 노드에 대해 생성된 내용과 연상 메모리의 품질을 평가한다. 평가 함수 $F$는 두 가지 요소를 합산하여 노드의 가치(Value)를 계산한다. 즉, 노드 $i$의 최종 값은 생성 내용의 평가값과 연상 내용의 평가값을 결합하여 계산한다. 예를 들어 식(4)와 같이 연관 메모리에 가중치 $\alpha$를 적용해 노드 값을 구할 수 있다.. 이렇게 계산된 노드 값은 MCTS의 Selection(선택) 과정에서 사용되는 UCT 값에 반영된다.

마지막으로 Backpropagation 단계에서 시뮬레이션 결과에 따라 각 노드의 방문 횟수와 평가값을 부모 노드들로 전파한다.. 이 과정에서 각 부모 노드는 자식 노드들의 품질을 종합하여 업데이트되며, 이 값은 다음 탐색 라운드에서 UCT 계산에 활용된다.. 이러한 과정을 반복하며, 궁극적으로 보상 모델(Reward Model)을 통해 종료를 판단하거나 최대 깊이($d$)에 도달하면 가장 좋은 답변을 반환한다..

아키텍처 상으로 CoAT는 그림 2에서 보듯, 중앙의 MCTS 트리 구조를 LLM이 수행하고, 우측에는 각 노드를 평가하는 평가기가 위치한다. 각 노드에서는 생성 컨텐츠와 연상 메모리가 한 세트로 관리되며, 연관 정보가 없는 노드는 $AM$을 생략할 수도 있다. 외부 두뇌는 필요할 때 노드의 연상 메모리 생성을 도와주는 선택적 모듈로, 검색 과정에서 추가 정확도를 높이는 역할을 한다.. 이 구조를 통해 CoAT는 탐색의 깊이(사고 단계)와 폭(연관 정보 보강)을 모두 확장하여 더 다양하고 정교한 추론 경로를 탐색할 수 있다.

3. 핵심 알고리즘 및 수식

CoAT의 알고리즘적 핵심은 연상 메모리 생성과 MCTS 최적화에 있다. 각 단계의 수식은 다음과 같다.

• 연상 메모리(Associative Memory): 노드 $i$가 생성한 내용 $G_i$로부터, 연관된 추가 정보를 찾아 연상 메모리 $AM_i$를 생성한다. 기본적으로 연상 메모리는 이전에 생성된 내용과 중복을 최소화하며, 추론에 유용한 새로운 정보를 담아야 한다.. 외부 두뇌($\mathrm{EB}$)를 사용하는 경우, 노드 $i$의 연관 정보를 얻는 과정은 다음과 같이 요약된다:
  
  

  

  
  
  (식의 형태는 식(1)과 같다) 여기서 $G_i$는 노드 $i$의 생성 내용, $\mathrm{EB}$는 외부 두뇌이다.. 얻어진 $AM_i$는 이후 해당 노드의 컨텍스트에 추가된다. 이후 노드 $i$의 실제 생성은 질의 $q$와 모든 조상 노드의 연상 메모리 집합 ${AM_1,\dots,AM_{i-1}}$를 입력으로 수행된다. 즉 식(2)와 같이:
  
  

  

  
  여기서 $x_i$는 노드 $i$의 출력 컨텐츠를 의미하며, 질의와 조상들의 연상 메모리가 LLM의 추가 맥락으로 사용된다.. 이렇게 함으로써 각 노드는 현재까지의 추론 내용과 실시간으로 연관된 외부 정보를 함께 고려하여 새로운 콘텐츠를 생성한다.
• MCTS 선택 기준(Selection): 트리의 각 노드 $n$에 대해 UCT(Upper Confidence bound for Trees) 값을 계산하여 다음 탐색 노드를 선택한다. 노드 $n_i$의 UCT는 표준 식(3)처럼 정의된다:UCT(ni)=N(ni)Q(ni)+cN(ni)lnN(parent(ni)),여기서 $Q(n_i)$는 노드 $i$의 현재 스코어(품질 총합), $N(n_i)$는 방문 횟수, $c$는 탐색 가중치 상수이다.. 이 값을 최대로 하는 노드를 선택하여 탐색 경로에 추가한다.
  

  

• MCTS 확장 및 연상(Expansion & Association): 선택된 노드에서 자식 후보 노드를 생성할 때, LLM이 새 내용을 생성하고 동시에 연상 메모리를 산출한다. 이 과정에서 우선 노드의 기존 생성 내용과 조상들의 연상 메모리를 참고하여 내용을 생성한 후, 그 생성 내용 $G_j$를 바탕으로 식(1)과 같은 방식으로 $AM_j$를 얻는다.
  
  
• 노드 평가(Evaluation): 각 노드의 가치는 생성 내용의 품질과 연상 내용의 품질을 종합하여 계산한다. CoAT는 기존 MCTS에 더해 연상 단계(Association)를 도입하므로, 평가지표도 두 요소를 모두 고려한다.. 평가 함수 $F$를 사용하여 노드 $i$의 생성 컨텐츠 값 $V_G(i)=F(G_i)$와 연상 컨텐츠 값 $V_{AM}(i)=F(AM_i)$를 산출한 뒤, 최종 노드 값 $V(n_i)$를 다음과 같이 조합할 수 있다(식(4)):V(ni)=VG(i)+αVAM(i),여기서 $\alpha$는 연상 메모리에 부여하는 영향력 가중치다.. (실제 논문에서는 정규화된 결합 형태로 제안되었으나, 본 보고서에서는 이해를 돕기 위해 합산 형태로 표현하였다.) 이 값은 다음 탐색 단계의 UCT 계산에 반영되어, 생성 컨텐츠와 연관 정보의 균형을 맞춘 탐색을 유도한다
  

  

  
  
  
• 역전파(Backpropagation): 리프 노드에서 얻은 평가 결과를 바탕으로, 해당 경로의 모든 조상 노드의 방문 횟수 $N(\cdot)$와 값 $Q(\cdot)$를 갱신한다. 방문 횟수는 자식 노드들의 방문 수 합으로 업데이트되고, 노드의 품질 평가는 자식 노드들의 값에 기반하여 계산된다.. 예를 들어 식(5)처럼 각 부모 노드의 값은 자식들 간의 평균이나 합으로 설정된다. 이 업데이트된 노드 값이 다시 Selection 단계에서 UCT 계산에 사용된다.

그림 3. CoAT에서 제안된 MCTS 최적화된 탐색 과정. 기존 MCTS(Selection–Expansion–Simulation–Backpropagation)에 사이사이에 Association(연상) 단계와 Evaluation(평가) 단계를 추가하였다. 연상 단계에서 LLM이 해당 노드의 생성 내용으로부터 추가 정보를 유도하며, 평가 단계에서는 생성 내용과 연상 내용의 품질을 함께 평가한다..

• 종료 조건(Reward & Depth): CoAT는 리프 노드에서의 콘텐츠를 전문 평가 모델(Reward Model)을 통해 평가하여 종료 조건을 판단한다.. 또한, 무한히 깊이까지 탐색하지 않도록 탐색 깊이 상한값 $d$를 설정할 수 있다. 깊이가 $d$를 초과하면 현재까지 가장 좋은 결과를 반환한다. 이로써 탐색 비용과 효율성을 조절할 수 있으며, $d=\infty$로 설정하면 최적 결과를 찾을 때까지 탐색을 계속한다..

이상의 과정을 요약한 CoAT 알고리즘은 다음과 같다. 첫째, 루트 노드부터 시작하여 UCT에 따라 트리를 선택적으로 탐색한다. 둘째, 각 자식 후보 노드를 확장할 때 LLM을 호출하여 내용을 생성하고 연상 메모리를 얻는다. 셋째, 생성물과 연상정보를 평가하여 노드 값을 계산한다. 넷째, 평가된 값을 통해 부모 노드를 역전파로 업데이트한다. 이 과정을 정해진 깊이 또는 보상 기준을 만족할 때까지 반복한다.. CoAT는 이처럼 MCTS의 기본 순환(선택→확장→시뮬레이션→역전파)에 연상과 평가 단계를 추가함으로써 기존 MCTS 기반 추론보다 더 풍부하고 유연한 사고 경로 탐색이 가능하다..

4. 실험 설정 및 성능 평가

CoAT의 성능을 평가하기 위해 다양한 생성 및 추론 과제를 대상으로 실험을 수행하였다. 실험에는 HotpotQA와 2WikiMultiHopQA 같은 다중 홉 질의응답 데이터셋과 HumanEval, MBPP 등의 코드 생성 데이터셋이 사용되었다... 비교 대상은 NativeRAG, IRCoT, HippoRAG, LATS, KAG 등의 최신 기법들 및 동일 LLM의 기본 모델 및 튜닝 모델이다. 평가 지표로는 QA에서는 Exact Match(EM)와 F1 점수를, 코드 생성에서는 HumanEval 채점기준 등을 활용했다...

4.1 정성적 결과

복합적 지식 추론을 요구하는 몇 가지 사례에서 CoAT의 효과를 관찰했다. 예를 들어, “현대 국제 경쟁에서 인공지능의 역할을 어떻게 볼 수 있는가? 어떤 국가들이 선두권인가?”라는 복잡한 질의에 대해, Qwen2.5-32B-Instruct 모델에 CoAT를 적용하여 생성한 답변과 원 모델의 출력, 그리고 ChatGPT의 출력을 비교하였다(그림 5). 그 결과 CoAT 기반 모델의 답변이 가장 풍부했다. 특히 “윤리적·규제 프레임워크(Ethical and Regulatory Frameworks)”와 같은 중요한 분류 항목을 새로 제시했고, 각 카테고리당 상세 내용도 다른 모델들보다 훨씬 많았다.. 이는 CoAT가 추론 도중 관련 정보(예: 국제 AI 규제 현황, 국가별 전략 등)를 연상하여 답변에 동적으로 통합했기 때문이다. 반면 기본 모델들은 이와 같은 추가 카테고리를 놓쳤다.

이 사례에서 알 수 있듯이, CoAT는 단순 생성 외에도 LLM이 종종 간과하는 추가 정보를 자동으로 보강함으로써 정성적으로 더 완전한 답변을 제공한다..

4.2 정량적 성능 비교

다음으로 CoAT의 정량적 성능을 분석하였다. 지식 집약적 QA 과제에서 HotpotQA와 2WikiMultiHopQA에 대해 CoAT를 적용한 모델을 비교하였다. 실험 결과, CoAT 모델은 기존 RAG, CoT 기반 방법보다 높은 EM/F1 성능을 기록했다(예: 기존 NativeRAG나 KAG 대비 수%p 상승). 이는 CoAT의 연상 메모리로 생성된 풍부한 정보가 다중 홉 추론에 유리하게 작용했음을 시사한다.

또한 코드 생성 과제에서는, Qwen2.5-7B/14B 모델에 CoAT를 적용한 결과를 각 모델의 전용 코드 튜닝 버전(예: Qwen2.5-Coder-7B/14B)과 비교하였다. CoAT를 활용한 비튜닝 모델이 튜닝 모델과 유사한 성능을 내거나 소폭 앞서는 결과를 얻었다. 이는 비록 LLM에 코드 전용 튜닝을 하지 않았더라도 CoAT가 코드 생성에도 연상 메모리를 통해 성능 향상을 이끌어낼 수 있음을 보여준다.

정리하면, CoAT는 다양한 과제에서 전통적 기법 대비 정확도·일관성·다양성 측면에서 유의미한 이득을 보였다.. 특히 연관 정보를 동적으로 탐색하고 활용함으로써, 복합적이고 변화하는 문제에서도 성능 저하 없이 적응할 수 있음을 실험적으로 입증했다.

5. 한계점 및 향후 방향

CoAT는 반복적·동적 사고 과정을 통해 추론력을 크게 향상시키지만, 몇 가지 한계가 존재한다. 첫째, MCTS 탐색과 연상 메모리 생성 과정이 연산량을 크게 늘린다. 특히 외부 두뇌를 사용할 경우 지연이 발생할 수 있어 추론 효율이 떨어질 수 있다.. 둘째, 연상 메모리의 품질은 LLM 자체 역량과 외부 검색 결과에 크게 의존한다. 관련 정보가 없거나 부정확하면 오히려 추론 품질을 떨어뜨릴 수 있다. 따라서 적절한 정보 필터링과 평가 기준이 필요하다. 셋째, 탐색 깊이 제한($d$)과 탐색 폭(자식 수 $b$), 연관 가중치 $\alpha$ 등 하이퍼파라미터를 잘 조정해야 안정적인 결과를 얻을 수 있다.

향후 연구에서는, CoAT의 연산 비용을 줄이기 위한 효율적인 탐색 스킴 개발과, 검색된 연상 정보를 정제하는 학습 기반 필터링, 또 강화학습(Reinforcement Learning) 기반 Reward 모델 고도화 등을 고려할 수 있다. 또한 시각·음성 등 비정형 데이터로의 확장, 멀티태스크 협업 추론 등에 CoAT를 적용해 보는 것도 흥미로운 방향이다. CoAT가 강조하는 구조적 탐색과 연상 기억의 결합은, LLM이 외부 지식을 실시간으로 융합하여 더욱 인간과 유사한 방식으로 사고하도록 하는 새로운 연구 경로를 제시한다..

6. 구현 방향 및 코드 힌트

실제 시스템 구현 시, CoAT는 MCTS 루프 안에서 LLM API 호출과 지식 검색을 조합하여 구현할 수 있다. 예를 들어 Python으로는 while 루프로 MCTS를 수행하면서 다음과 같은 단계를 수행한다:

1. 선택(Selection): 각 노드에 저장된 방문 횟수와 값으로 UCT 값을 계산하여 다음 노드를 선택한다.
2. 확장(Expansion): 선택된 노드의 후보 자식 노드들에 대해, LLM에 프롬프트를 보내 다음 내용을 생성한다. 이때 프롬프트에는 질문과 해당 노드까지의 생성 내용, 조상 노드들의 연상 메모리를 포함시킨다.
3. 연상(Association): 새로 생성된 내용에 대해 연상 질문을 LLM에 던져 보강 정보를 얻거나, 키워드를 추출하여 지식 그래프/벡터 DB에서 검색해 연관 문장을 가져온다. 이를 노드의 $AM$에 저장한다.
4. 평가(Evaluation): 생성내용과 연상내용을 평가하기 위해 또다른 LLM이나 사전학습된 평가지표(예: 문장 유사도, AI 평가모델)를 사용할 수 있다. 생성과 연상의 평가 결과를 가중합하여 노드 값을 계산한다.
5. 역전파(Backpropagation): 계산된 노드 값을 경로에 있는 부모 노드들에 전파하여 방문 횟수와 값을 업데이트한다.
6. 종료 판단: 리프 노드의 내용 평가가 충분히 높거나, 설정한 최대 탐색 깊이에 도달하면 최종 답변을 선택한다.

이 과정을 반복적으로 구현하면 CoAT를 구성할 수 있다. 실제 코드는 MCTS 템플릿 라이브러리(예: OpenAI의 OpenAI-Treebeard 참고)와 LLM API 클라이언트(OpenAI, vLLM 등)를 결합하여 작성할 수 있다. 연상 단계에서는 간단한 프롬프트 설계 외에도 외부 API(위키피디아 검색 등)를 활용할 수 있으며, 평가 단계에는 transformers 라이브러리의 평가모델(예: GPT-4o 평가자)을 적용할 수 있다.

python

# (예시) 간단한 의사 코드 예시
while not 종료:
    node = select_node(root)              # UCT 기준 선택
    for _ in range(자식수):
        generated = LLM.generate(node.context)     # 확장: LLM에 질의+맥락 입력
        associated = LLM.associate(generated)      # 연상: 생성 내용으로 추가 정보 생성
        value = evaluate(generated, associated)    # 평가: 생성+연상 정보 품질 계산
        child = Node(context=node.context+generated, AM=associated, value=value)
        node.add_child(child)
        backpropagate(child)                      # 역전파: 값 갱신
        if reward_model(child) or depth_limit:    # 종료 조건
            return child.context  # 최적 답변

이처럼 CoAT는 MCTS 루프와 LLM 호출을 적절히 결합하는 방식으로 구현할 수 있으며, 주요 기술 포인트는 UCT 계산, 프롬프트 디자인(생성과 연상), 평가 함수 설계 등에 있다. 적절한 멀티스레딩과 캐싱을 도입하여 추론 속도를 개선하는 것도 고려해야 한다.

CoAT 프레임워크는 LLM의 추론력을 체계적으로 확장하는 강력한 방법론으로, 여러 영역에서 응용이 가능하다. 다만 구현 복잡도가 있으므로 프로토타입 개발 시에는 위 가이드라인을 참고하여 단계별로 기능을 검증해 나가는 것이 바람직하다.

CoAT_ Chain-of-Associated-Thoughts 프레임워크 개요.pdf

1.23MB

CoAT_Chain-of-Associated-Thoughts.pdf

3.94MB