Chain-of-Thought Transformer을 이용한 알고리즘의 효율적 표현

원문 발행 2026. 06. 18. 10:49원문 언어 영어AI 한국어 번역arXiv cs.CL (NLP) 원문 보기

요약

Chain-of-Thought(CoT) Transformer가 Word RAM 모델의 알고리즘을 효율적으로 시뮬레이션할 수 있음을 이론적으로 입증했습니다. 기존 Turing machine 시뮬레이션보다 훨씬 낮은 다항 로그 오버헤드로 알고리즘을 수행할 수 있음을 보여줍니다.

핵심 포인트

CoT Transformer가 Word RAM 알고리즘을 효율적으로 시뮬레이션 가능함을 증명
Turing machine 대비 획기적으로 낮은 다항 로그(poly-logarithmic) 오버헤드 달성
연속적(continuous) CoT 및 하이브리드 아키텍처에서도 결과 유효성 확인
명령어 세트 특성에 따라 오버헤드가 log-square 또는 log 수준으로 감소

reasoning (추론) 모델 — 정답을 내놓기 전에 일련의 추론 또는 사고 토큰을 출력하는 언어 모델 — 의 인기가 높아지는 이유는, Chain-of-Thought (CoT) Transformer가 Turing machine (튜링 기계)을 시뮬레이션할 수 있으며, 따라서 임의의 계산을 수행할 수 있음을 보여주는 이론적 결과에 부분적으로 근거합니다. 그러나 Turing machine은 복잡도 이론적 분석에는 적합하지만, 알고리즘을 논의하기에는 편리하거나 직관적이지 않으며 효율적이지도 않습니다. 알고리즘은 일반적으로 무작위 접근 메모리(random-access memory)와 $\bigO(\log n)$-bit 단어에 대한 단위 비용 연산을 갖춘 Word RAM 모델로 포착되는 더 높은 수준의 추상화 단계에서 설계되고 분석됩니다. 결과적으로 Word RAM 알고리즘은 Turing machine 대응 방식보다 실질적으로 더 효율적일 수 있으며, 이는 다음과 같은 질문을 제기합니다: CoT Transformer는 Word RAM 알고리즘을 효율적으로 시뮬레이션할 수 있는가? 예를 들어, $n$개의 항목을 $\bigO(n \log n)$ 단계 내에 정렬하거나 Dijkstra 알고리즘을 $\bigO(E + V \log V)$ 단계 내에 실행할 수 있을까요? 우리는 다항 로그(poly-logarithmic) 오버헤드 범위 내에서 이에 대해 긍정적인 답변을 내놓습니다. 우리는 먼저 다항 로그 너비(width)와 가장 오른쪽의 유일한 하드 어텐션(rightmost unique hard attention)을 가진 유한 정밀도(finite-precision) Transformer에 대해 이를 입증한 후, 유한한 너비와 로그 정밀도를 가진 두 가지 더 실용적인 설정으로 결과를 강화합니다: 추론이 토큰 대신 벡터의 형태를 취하는 연속적 (continuous) CoT, 그리고 Transformer 레이어가 순환(linear RNN) 레이어 위에 놓이는 하이브리드 (hybrid) 아키텍처입니다. 이 세 가지 경우 모두에서, 우리는 CoT가 $n$에 대한 다항 로그 오버헤드만을 사용하여 모든 Word RAM 알고리즘을 효율적으로 시뮬레이션할 수 있음을 발견했습니다. 이 오버헤드는 Word RAM이 "평탄한 (flat)" 명령어 세트를 가질 때 log-square로 감소하며, 곱셈이 없는 평탄한 명령어의 경우 로그 수준으로만 감소합니다. 이는 Word RAM 대비 이차(quadratic) 오버헤드를 요구하는 기존의 Turing machine에 대한 CoT 시뮬레이션과 극명한 대조를 이룹니다.

AI 자동 생성 콘텐츠

원문 바로가기

Chain-of-Thought Transformer을 이용한 알고리즘의 효율적 표현

요약

핵심 포인트

댓글