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

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 시뮬레이션과 극명한 대조를 이룹니다.