체인 오브 소트 트랜스포머를 활용한 알고리즘 효율적인 표현

Efficiently Representing Algorithms With Chain-of-Thought Transformers

추론 모델(사고 또는 추론 토큰 시퀀스를 출력하여 답을 생성하는 언어 모델)의 인기가 높아지는 이유는 이론적으로 체인 오브 소트 (CoT) 트랜스포머가 튜링 기계를 모방하여 임의의 계산을 수행할 수 있기 때문입니다. 그러나 튜링 기계는 복잡도 이론 분석에는 적합하지만, 알고리즘에 대한 논의를 위해 편리하거나 직관적이지 않으며 효율적이지 않습니다. 일반적으로 알고리즘은 랜덤 액세스 메모리와 O(log n) 비트 단어에 대한 단위 비용 연산을 갖는 Word RAM 모델과 같은 더 높은 수준의 추상화에서 설계되고 분석됩니다. 그 결과, Word RAM 알고리즘은 튜링 기계 기반 알고리즘보다 훨씬 효율적일 수 있으며, 다음과 같은 질문이 제기됩니다: 'CoT 트랜스포머는 Word RAM 알고리즘을 효율적으로 모방할 수 있는가?' 예를 들어, n개의 항목을 O(n log n) 단계로 정렬하거나 다익스트라 알고리즘을 O(E + V log V) 단계로 실행할 수 있는가? 우리는 다항 로그 오버헤드 내에서 긍정적인 답변을 제시합니다. 먼저 다항 로그 폭과 오른쪽 고유 하드 어텐션을 갖는 유한 정밀도 트랜스포머에 대해 이를 입증하고, 그런 다음 유한 폭 및 로그 정밀도를 가진 두 가지 더 실용적인 설정으로 결과를 확장합니다: 토큰 대신 벡터로 표현되는 '연속' CoT 모델과, 트랜스포머 레이어가 순환(선형 RNN) 레이어 위에 배치된 '하이브리드' 아키텍처입니다. 세 가지 경우 모두에서 CoT는 n에 대한 다항 로그 오버헤드만으로 모든 Word RAM 알고리즘을 효율적으로 모방할 수 있음을 확인했습니다. Word RAM이 '평탄한' 명령어 집합을 갖는 경우 이 오버헤드는 로그 제곱으로 줄어들며, 곱셈 없는 평탄한 명령어의 경우에는 로그 수준으로 감소합니다. 이는 튜링 기계에 대한 알려진 CoT 시뮬레이션과 대조적인 것으로, Word RAM에 대해 이차 오버헤드가 필요합니다.

The increasing popularity of \emph{reasoning} models -- language models that output a series of reasoning or thought tokens before producing an answer -- is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbitrary computation. However, the Turing machine, while suitable for complexity-theoretic analysis, is not convenient, intuitive, or efficient for discussing algorithms. Algorithms are typically designed and analyzed at a higher level of abstraction, captured by the \emph{Word RAM} model with random-access memory and unit-cost operations on $\bigO(\log n)$-bit words. As a result, Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: \emph{Can CoT transformers efficiently simulate Word RAM algorithms?} For instance, can they sort $n$ items in $\bigO(n \log n)$ steps or run Dijkstra's algorithm in $\bigO(E + V \log V)$ steps? We answer affirmatively, up to poly-logarithmic overhead. We first establish this for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention, then strengthen the result to two more practical settings with finite width and log-precision: \emph{continuous} CoT, where reasoning takes the form of vectors rather than tokens, and a \emph{hybrid} architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, we find that CoT \emph{can} efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$. This overhead reduces to log-square when the Word RAM has a ``flat'' instruction set, and only logarithmic for multiplication-free flat instructions -- in stark contrast to known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.