Hanyong Lee

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

8 minute read

요약: 생각의 체인(Chain-of-Thought, CoT) 프롬프트가 대규모 언어 모델(LLM)의 수학 및 추론 과제 성능을 크게 향상시키는 방법과 이론적 기초를 탐구한 연구로, CoT를 사용하여 결정 문제와 기초 수학 문제 해결 능력을 분석하였다.

1 Introduction

  • 트랜스포머 기반의 대형 언어 모델(LLMs)이 자연어 처리의 기초 모델로 출현
  • 자가 회귀(paradigm) 접근법이 특히 인기를 끌고 있음
    • 모든 작업을 시퀀스 생성 문제로 통일적으로 처리 가능
    • 입력과 작업 설명이 함께 시퀀스 토큰으로 인코딩됨 (prompt)
  • 적절하게 설계된 prompt가 LLM의 성능에 큰 영향을 미침
    • Chain-of-Thought prompting (CoT)이 특히 중요:
      • 산술적 문제나 추론 관련 작업에서 답변의 정확성을 크게 향상시킴
      • “단계별로 생각해 보자”와 같은 특수 구문 추가 또는 few-shot CoT의 예시로 이루어짐
  • CoT의 성과 뒤에 있는 기본 메커니즘은 여전히 불명확함
    • LLM이 직접적으로 수학/추론 질문에 답하는 데 한계가 있는가?
    • CoT가 LLM의 성능 향상에 기여하는 본질적인 이유는 무엇인가?
  • 본 논문은 이러한 질문을 이론적으로 답하기 위한 첫걸음을 내딛음
    • LLM의 수학적 작업 능력을 평가하는 두 가지 기본 과제 연구
      • 산술 표현 평가 및 선형 방정식 해결
    • 기본적인 불가능성 결과 제시
      • 제한 깊이의 트랜스포머 모델이 CoT 없이 이러한 작업을 해결할 수 없음을 증명 (정리 3.1 및 3.2)
      • 문제의 계산 비용이 아닌 병렬 복잡성에 기인
  • 자가 회귀 생성의 강점을 간과하고 있다는 주장
    • 고정 크기의 자가 회귀 트랜스포머가 단계별로 중간 유도 결과를 생성하여 두 작업을 완전히 해결할 수 있음을 증명 (정리 3.3 및 3.4)
  • CoT는 수학 작업뿐만 아니라 다양한 추론 작업에서도 뛰어난 성능 보임
    • 동적 프로그래밍(Dynamic Programming, DP) 문제로의 확장
      • DP는 복잡한 문제를 하위 문제의 시퀀스로 분해하여 해결하는 프레임워크
      • LLM과 CoT의 조합이 올바른 답변을 출력할 수 있음을 증명 (정리 4.7)
    • 그러나 일반적으로 직접 답변을 생성할 수는 없음
      • 상반된 예시로 다항 크기의 제한 깊이 트랜스포머가 Context-Free Grammar Membership Testing 문제를 해결할 수 없음을 증명 (정리 4.8)
  • 이론적 발견을 보완하기 위한 폭넓은 실험 세트 진행
    • 산술 작업 두 가지 및 “알고리즘 소개” 책에 수록된 DP 문제 두 가지 고려
    • CoT 없이 답변을 직접 예측하는 경우 항상 실패 (정확도 60% 미만)
    • CoT가 장착된 자가 회귀 트랜스포머는 충분한 훈련 시연을 통해 전체 솔루션을 학습
    • 모델이 입력-출력의 분포를 통계적으로 기억하기보다는 기본적인 추론 과정을 학습했다는 결과 도출
  • 이 결과는 이론을 검증하고 자가 회귀 LLM의 강점과 CoT의 중요성을 실질적인 상황에서 드러냄

2 Preliminary

  • Transformer 설명

    image

    • 오토회귀(autoregressive) Transformer는 순차적 입력 토큰을 처리하고 후속 위치의 토큰을 생성하기 위해 설계된 신경망 아키텍처.
    • 입력 시퀀스 s의 길이 n에 대해 Transformer는 다음과 같은 방식으로 작동.
  • 입력 변환 과정
    • 각 입력 토큰 si는 임베딩 레이어를 통해 d 차원 벡터 vi = Embed(si)로 변환.
    • 순서 정보를 식별하는 위치 임베딩 pi도 존재.
    • 임베디드 입력은 행렬 형태로 표현: \(X(0) = [v1 + p1, ··· , vn + pn]^{⊤} ∈ Rn×d\).
  • Transformer 블록
    • L개의 Transformer 블록이 순차적으로 입력을 변환.
    • 각 블록의 변환 과정은 다음의 수식으로 표현:
      • \[X(l) = X(l−1) + Attn(l)(X(l−1)) + FFN(l)(X(l−1) + Attn(l)(X(l−1)))\]
    • 여기서 Attn(l)은 다중 헤드 자기 주의 (multi-head self-attention) 레이어, FFN(l)은 피드포워드 네트워크를 의미.
  • 모델 파라미터
    • Transformer의 크기는 깊이 L, 너비 d, 헤드 수 H로 결정됨.
    • 파라미터들:
      • W(l,h)Q, W(l,h)K, W(l,h)V, W(l,h)O는 각각 쿼리, 키, 값, 출력 행렬.
      • M은 인과 마스크(causal mask)로, 시퀀스의 각 위치가 이전 위치만 주의할 수 있도록 보장.
  • 토큰 예측 과정
    • 최종 출력 X(L)의 마지막 항목 X(L)n,:는 다음 토큰 sn+1 예측에 사용.
    • sn+1을 입력 시퀀스에 결합하여 다음 토큰 sn+2 생성을 위한 과정 반복.
  • Chain-of-Thought(CoT) 프롬프팅
    • 오토회귀 Transformer는 작업 설명을 부분 문장으로 인코딩하여 다양한 작업을 처리할 수 있음.
    • 복잡한 수학 문제나 일반적 추론이 필요한 작업에서는 직접 생성이 올바른 답을 도출하는 데 어려움.
    • CoT 프롬프팅은 LLM이 답에 도달하기 전 중간 추론 단계를 생성하도록 유도.
    • 본 논문에서는 CoT의 메커니즘을 이해하는 데 중점, 프롬프팅이 이를 유도하는 점은 제외.
    • 수학 문제와 일반적 의사결정 작업의 표현 능력을 조사: (i) 답을 직접 생성, (ii) CoT 해결안을 생성할 수 있는지.

3 CoT is the Key to Solving Mathematical Problems

  • LLM의 수학 능력: Transformer 기반의 큰 언어 모델(LLM)은 여러 수학적 작업에서 놀라운 능력을 보여주고 있음.

  • 문제 정의:

    image

    • 산술 표현: 입력으로 주어진 산술 표현을 평가하고 결과를 생성. CoT를 사용한 자연스러운 해결 방법이 존재.
    • 선형 방정식: 선형 방정식의 집합에서 변수의 값을 출력. Gaussian 소거법을 통해 각 단계에서 특정 변수를 제거하는 방식으로 해결 가능.

  • 수체계 전환: 입력 시퀀스에서 일반적인 부동 소수점 숫자 대신 소수 정수 모듈로 p의 유한 필드를 사용하여 문제를 정리.

  • 이론적 결과:
    • Transformer의 직접 답변 생성: LLM이 직접적으로 정답을 생성하도록 하는 것은 표현의 한계로 인해 어렵고, 이를 해결하기 위해 많은 네트워크 크기가 필요하다고 언급.
    • CoT 솔루션 생성: 고정된 크기의 Transformer만으로도 CoT 솔루션을 생성할 수 있으며, 이로 인해 복잡한 수학 문제를 해결 가능하다는 결과 도출.
  • 정리:
    • 정리 3.1 & 3.2: 조밀한 네트워크를 통해 수학 문제를 해결하는 것이 불가능하다는 결과.
    • 정리 3.3 & 3.4: 고정 크기의 Transformer가 CoT 솔루션을 생성할 수 있음을 증명.

  • 증명 개요: Transformer 레이어에서 실행할 수 있는 기본 연산을 구축하고 병렬 알고리즘을 통해 CoT 시퀀스를 생성.

  • 핵심 논의:
    • Transformer의 설계에서 주의 메커니즘, 다중 헤드, 전방위 신경망의 중요성 강조.
    • CoT의 내적 구조와 효과적인 깊이의 필요성 설명: CoT를 활용함으로써 출력 토큰 간의 종속성이 복잡성을 증가시킴.
    • LLM이 CoT를 통해 P-complete 문제를 해결할 수 있다는 가능성도 제시.

4 CoT is the Key to Solving General Decision-Making Problems

  • 이전 섹션에서는 CoT의 수학 문제 해결에서의 중요성을 설명.
  • 이 섹션에서는 CoT의 일반적인 의사결정 문제 해결 능력에 주목.
  • CoT를 사용하는 대형 언어 모델(LLM)은 동적 프로그래밍(Dynamic Programming, DP)이라는 강력한 의사결정 프레임워크를 모방할 수 있다.

4.1 동적 프로그래밍(DP)

  • DP는 의사결정 문제를 해결하는 핵심 기술로 알려져 있음.
  • 복잡한 문제를 일련의 작은 하위 문제로 분해하고 순차적으로 해결.
  • 하위 문제 간의 상호 연결성을 통해 이전 문제의 답변을 활용하여 효율적으로 해결.

DP 알고리즘의 구성 요소

  1. 상태 공간 I: 각 하위 문제를 나타내는 지표.

  2. 변환 함수 T: 하위 문제의 연관성을 정의하고 어떻게 해결되는지를 나타냄.

    image

    image

  3. 집계 함수 A: 모든 결과를 결합하여 최종 답을 얻는 함수.

    image

DP의 예시 문제

image

  • 가장 긴 증가 부분 수열(LIS)과 편집 거리(ED)는 DP 문제로 유명.
  • 각 문제에 대해 상태 공간, 변환 함수, 집계 함수 설명.

4.2 이론적 결과

  • LLM이 DP 문제를 해결할 수 있는지 조사.
  • 자연스러운 CoT 생성 과정 설명: 각 하위 문제의 결과가 포함된 최종 답안 도출.

가정

  • 함수가 다항식 효율로 근사 가능해야 하며, DP 문제의 상태 공간 크기 등 여러 조건들이 충족되어야 함.
  • 모든 가정은 온건하며, 다양한 문제에 대해 만족됨을 증명.

주요 결과

  • CoT를 가진 LLM은 모든 DP 문제를 해결할 수 있으며, 이를 위한 특수한 Transformer의 존재를 보임.

불가능성 결과

  • Transformers가 CoT 없이 DP 문제를 직접 예측할 수 없다는 결론.
  • 특히 문맥 자유 문법(CFG) 포함 여부 테스트 문제는 고유하게 어렵다는 명제.

결론

  • CoT는 본질적으로 해결하기 어려운 작업 수행에 있어 중요한 역할을 한다는 결론.

5 Experiments

  • 목적: LLM이 수학적 및 의사결정 작업을 해결할 수 있는 능력을 학습할 수 있는지 실험을 통해 검증.

5.1 실험 디자인

  • 작업 및 데이터셋:
    • 평가할 네 가지 작업:
      1. 산술 (Arithmetic)
      2. 방정식 (Equation)
      3. 최장 증가 부분수열 (LIS)
      4. 편집 거리 (ED)
    • 산술과 방정식 작업의 입력/CoT 형식 제공.
    • LIS의 목표: 주어진 정수 수열의 최장 증가 부분수열 길이 찾기.
    • ED의 목표: 한 수열을 다른 수열로 변환하는 최소 비용 계산.
    • 두 가지 데이터셋 구성:
      • CoT 데이터셋: <문제, CoT 단계, 답> 샘플로 구성.
      • 직접 데이터셋: CoT 단계를 제거한 모델 학습용.
    • 각 작업에 대해 난이도 증가에 따른 세 가지 데이터셋 구성.
    • 샘플 수: 각 학습 데이터셋에 대해 1M, 테스트에 대해 0.1M.
  • 모델 훈련 및 추론:
    • 표준 Transformer 모델 사용 (d=256, H=4, 서로 다른 깊이 L).
    • AdamW 옵티마이저 사용.
    • 모델 훈련: 100 에폭 동안 4개의 V100 GPU에서 실행.
    • CoT 데이터셋은 CoT 단계와 답에 대한 음의 로그 가능성 최적화.
    • 직접 데이터셋은 답 토큰에 대한 음의 로그 가능성 최적화.
    • 평가 지표로 정확도 사용.

5.2 실험 결과

  • 주요 결과:

    image

    • CoT로 훈련된 3층 Transformers는 모든 작업에서 거의 완벽한 성능을 발휘.
    • 직접 데이터셋으로 훈련된 모델은 성능 저조, 특히 방정식 작업에서.
    • 깊이를 증가시키면 직접 예측 성능이 개선되지만 입력 길이가 증가할수록 성능이 급격히 떨어짐.
  • 데이터 품질에 대한 견고성:
    • 저품질 데이터셋(예: 중간 CoT 단계 소실)의 경우에도 3층 Transformer는 95% 이상의 정확도를 달성.
  • 길이 외삽 실험:
    • 훈련 데이터셋을 1~15개의 연산자로 구성하고, 16~18개의 연산자에 대해 테스트.
    • 결과: 3층 Transformer가 긴 수열에서도 좋은 성능을 유지, 문제 해결 능력 학습 가능성을 암시.

6 Related Work

  • Transformers와 대형 언어 모델의 성공: 다양한 분야에서의 높은 성공률로 인해 그들의능력과 한계를 이해하려는 연구들이 활발함.

  • 함수 근사에 대한 초점: 초기 연구자들은 주로 Transformer의 표현력을 함수 근사의 관점에서 탐구.
    • Yun et al.에 의하면, 충분한 크기의 Transformers는 컴팩트 도메인에서 임의의 연속 순서 대 순서 함수에 대해 보편적으로 근사할 수 있음.
    • 최근에는 Sparse Transformers와 상대적 위치 부호화(RPE)가 이러한 보편성 결과에 포함됨.
  • 계산적 관점에서의 Transformer 연구:
    • 초기 결과들이 표준 인코더-디코더 Transformers와 반복된 Transformer 인코더가 튜링 완전하다는 것을 보여줌.
    • 그러나 이는 무한 정밀도의 비현실적인 가정에 의존하여 실제 시나리오와는 맞지 않음.
    • Giannou는 상수 깊이의 반복형 Transformer 인코더가 실제 컴퓨터 프로그램을 시뮬레이션할 수 있음을 입증.
    • Wei et al.은 유한 정밀도의 인코더-디코더 Transformers가 제한된 계산 시간을 가진 튜링 기계를 근사적으로 시뮬레이션할 수 있음을 보여줌.
    • Liu et al.은 제한된 설정의 학습 오토마타를 고려하여, 얕은 비재귀형 Transformer가 충분함을 증명.
    • Yao et al.은 Transformers가 유한 깊이 Dyck 언어 같은 특정 형태의 문맥 자유 언어를 인식하거나 생성할 수 있음을 입증.
  • 표현력의 한계에 대한 연구:
    • 일부 연구들은 Transformers의 표현력 한계를 공식 언어 모델링이나 회로 시뮬레이션의 관점에서 평가.
    • 하지만 이러한 연구들은 주로 일반적인 설정을 다루었으며, LLM에 일반적으로 적용되는 자기 회귀 Transformer 환경을 탐구하지 않음 (예: [66] 제외).
  • LLM의 맥락 학습 가능성: 최근 LLM의 맥락 학습 능력이 주목받음.
    • Garg et al.은 자기 회귀 Transformers가 기본 함수 클래스(선형 함수, MLP, 결정 트리 등)를 맥락 학습할 수 있음을 입증.
    • 후속 연구들은 Transformers가 선형 회귀, 경량 하강법, 베이지안 추론 등과 같은 학습 알고리즘을 구현할 수 있다고 밝혀냄.
    • “유도 헤드” 개념을 통한 맥락 학습 연구도 있음.
  • 논문의 초점: 본 연구는 (자기 회귀) Transformer 모델의 표현력 관점에서 논의되지만, 특히 Transformer의 추론 능력에 중점을 두고 CoT의 중요성을 강조함.

7 Limitations and Future Directions

  • Chain-of-Thought (CoT) 시퀀스의 필요성: 본 연구는 CoT 프롬프트가 수학적 및 의사결정 문제 해결에서 왜 중요한지를 이론적으로 분석함.

  • 모델 용량 한계: CoT 없이 제한 깊이의 Transformer는 문제 해결에 어려움을 겪으며, 크기가 지나치게 커져야 가능하다는 부정적인 결과를 도출.

  • 모델 크기와 CoT의 관계: CoT를 장착한 일정 크기의 Transformer는 중간 유도 과정을 순차적으로 생성하여 이러한 작업을 충분히 해결할 수 있음.

  • 실험 결과: CoT 데이터셋으로 훈련된 모델이 거의 완벽하게 솔루션을 학습할 수 있음을 확인했으며, 직접 예측은 항상 실패함.

  • 미래 연구 방향:
    • CoT 생성 과정이 특정 프롬프트에 의해 어떻게 촉발되는지 명확히 할 필요성. 프롬프트와 출력 간의 관계 규명은 LLM을 보다 효과적으로 활용하는 데 기여.
    • 모델 크기를 확장하는 것이 CoT 능력을 개선함을 경험적으로 관찰. 이론적으로 모델 크기가 CoT에서 어떤 역할을 하는지 이해하는 것이 흥미로운 연구 주제가 될 수 있음.
    • LLM이 CoT 시연에서 어떻게 일반화할 수 있는지에 대한 이론적 연구 필요. 분포 외 설정에서의 일반화 가능성을 탐구하는 것도 중요함.
    • 제한된 CoT 시연만으로 모델이 CoT 솔루션을 학습하는 방식에 대한 실용적인 연구 필요.
  • 미래 연구의 의미: 이러한 질문들은 LLM의 강점과 한계를 더욱 잘 드러내는 데 기여할 것으로 기대됨.

독자 의견

  • 우리가 이제는 자연스럽게 사용하는 CoT 방법론을 수학적으로 설명하는 것은 더 좋은 추론 방법론을 발견하는 데에 큰 인사이트를 제공할 것임.
  • 이론적인 결과와 실험 결과가 일치하는 것을 보면, CoT가 LLM의 성능을 향상시키는 데에 중요한 역할을 한다는 것을 알 수 있음.
  • 앞으로 이러한 연구들이 더욱 발전하여, LLM이 다양한 추론 문제를 해결하는 데에 더욱 효과적으로 활용될 수 있기를 기대함.

Comments

You May Also Enjoy