Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity

당신이 초지능 로봇에게 생각하는 법을 가르치려 한다고 상상해 보세요. 당신은 로봇에게 미로 그림을 보여주며 출구를 찾으라고 요청합니다. 과거에 이 로봇들은 전체 그림을 한 번 쓱 훑어보고 답을 추측하기만 하는 빠른 독자 같았습니다. 그들은 패턴을 찾아내는 데는 뛰어났지만, 만약 문제가 미로를 통과하며 어디서 회전했는지 기억하고 막다른 길에 부딪혔을 때 되돌아오는 것과 같은 긴 단계별 여정을 요구한다면 길을 잃곤 했습니다. 그들은 "생각을 소리 내어 말하거나" 메모를 할 수 없었습니다.

그러다 과학자들이 "생의 사고 사슬(Chain of Thought, CoT)"이라는 기술을 발견했습니다. 단순히 최종 답을 추측하는 대신, 로봇이 마치 사람이 수학 문제를 풀 때 연습장에 풀이 과정을 적는 것처럼 일련의 중간 단계들을 적을 수 있게 된 것입니다. 이것은 로봇을 단순한 추측가에서, 한 걸음씩 실제로 미로를 걸어 다닐 수 있는 여행자로 변화시켰습니다. 하지만 여기서 중요한 질문이 생깁니다. 이 로봇이 실제로 트리 구조를 탐색하거나 최단 경로를 찾는 것과 같은 복잡한 현실 세계의 과업을 수행할 수 있을까요, 아니면 그저 단순한 잔재주에 능숙한 것뿐일까요? 이 논문은 로봇의 "사고 과정"을 데이터의 숲을 가로지르는 실제적인 여정으로 취급하며, 적절한 지침이 있다면 이 로봇이 놀라울 정도로 깊이 있는 수학과 논리를 수행할 수 있음을 증명합니다.

---

논문의 위대한 모험: 로봇에게 나무 속을 걷는 법 가르치기

이 논문은 로봇에게 숲을 탐험하고 그 복잡성을 측정하는 법을 가르치기 위한 설계도와 같습니다. 저자인 데반잔 두타(Debanjan Dutta), 아니쉬 차크라바티(Anish Chakrabarty), 스와가탐 다스(Swagatam Das)는 특정 유형의 AI 모델(트랜스포머)이 나침반을 든 등산객처럼 행동하도록 프로그래밍될 수 있으며, 컴퓨터 과학의 두 가지 고전적 과업인 **깊이 우선 탐색(DFS)**과 **다익스트라 알고리즘(Dijkstra's Algorithm)**을 수행할 수 있음을 보여줍니다.

여기서 트리를 식물로서의 나무가 아니라 가계도나 분기 지도라고 생각하세요.

• DFS는 경로를 하나 정해 최대한 멀리 가보고, 막다른 길에 부딪히면 마지막 갈림길로 되돌아와 다음 경로를 시도하는 등산객과 같습니다. 이는 "깊게 들어갔다가 다시 돌아오는" 전략입니다.
• 다익스트라 알고리즘은 숲속의 모든 캠핑장까지의 거리를 꼼꼼히 확인하고 지도를 업데이트하며, 모든 캠핑장까지 가는 최단 경로를 찾는 등산객과 같습니다.

저자들은 "하드 어텐션(hard-attention)" 로봇(매우 구체적이고 엄격한 유형의 AI)이 이러한 탐색을 수행할 수 있음을 증명했습니다. 그들은 단순히 "가능하다"라고 말하는 데 그치지 않고, 실제 기계를 구축했습니다.

• DFS 탐색을 위해, 그들은 단 **두 개의 사고 계층(layers)**과 두 개의 어텐션 헤드(서로 다른 것을 바라보는 두 쌍의 눈과 같은 역할)를 가진 로봇을 사용했습니다.
• 다익스트라 탐색을 위해, 그들은 두 개의 계층과 한 개의 어텐션 헤드를 가진 로봇을 사용했습니다.

이것이 왜 중요할까요? 일단 로봇이 이러한 경로를 걸을 수 있게 되면, 훨씬 더 어려운 문제들을 해결할 수 있기 때문입니다. 저자들은 "DFS 로봇"을 재사용하여, n개의 정점을 가진 트리에서 2n - 1번의 단계만에 스트라흘러 수(Strahler number)(트리가 얼마나 '가지가 많은지' 또는 복잡한지를 나타내는 척도)를 계산할 수 있음을 보여주었습니다. 또한 "다익스트라 로봇"을 재사용하여 트리의 너비(숲의 가장 넓은 부분)를 n - 1번의 단계만에 계산할 수 있음을 보여주었습니다.

"트리-투-패스(Tree-to-Path)" 기술의 마법

여기서 이야기는 매우 흥有趣로워집니다. 3D 트리 구조를 1D 선으로 바꾸는 유명한 수학적 기법이 있는데, 이는 지도를 평평하게 접는 것과 같습니다. 이를 **딕 경로(Dyck path)**라고 합니다. 가지를 내려갈 때마다 언덕을 올라가고, 가지를 다시 올라올 때마다 언파를 내려가는 과정을 상상해 보세요. 이 걷기를 그리면 땅 아래로 내려가지 않고 시작점에서 끝나는 물결 모양의 선이 그려집니다.

저자들은 로봇에게 트리를 걷게 하거나, 혹은 그 선을 걷도록 가르칠 수 있다는 사실을 발견했습니다.

• 그들은 트리를 걸으며 스트라흘러 수를 계산하는 로봇을 만들었습니다.
• 그들은 선(딕 경로)을 걸으며 동일한 스트라흘러 수를 계산하는 다른 로봇을 만들었습니다.

하지만 반전이 있습니다. 트리를 걷는 로봇은 일을 수행하기 위해 네 개의 계층이 필요했던 반면, 선을 걷는 로봇 역시 네 개의 계층이 필요했습니다(다만 내부 설정은 달랐습니다). 저자들은 "트리 로봇"을 가져다가 내부 기어를 바꾸지 않고는 마법처럼 "선"에서 작동하게 만들 수 없다는 것을 발견했습니다. 트리에 대해 생각하는 방식과 선에 대해 생각하는 방식은 근본적으로 다르며, 비록 그것들이 동일한 것을 나타낼지라도 말입니다. 이는 트리의 "언어"와 선의 "언어"가 로봇들에게 쉽게 호환되지 않는다는 점을 시사합니다.

이것이 증명하는 것 (그리고 증명하지 못하는 것)

저자들은 자신들의 주장에 대해 매우 신중합니다. 그들은 단순히 시뮬레이션을 돌려보고 "어, 잘 되네!"라고 말한 것이 아닙니다. 그들은 특정 계층과 어텐션 헤드를 가진 이 특정 로봇들이 이러한 과업을 정확하게 수행할 수 있음을 수학적으로 증명했습니다.

• 그들이 증명한 것: 그들은 2n - 1 단계(트리의 경우) 또는 n - 1 단계(너비의 경우)를 통해, 로봇이 매우 어렵다고 알려진 문제들(구체적으로 NC1이라 불리는 클래스의 문제들)을 해결할 수 있음을 보여주었습니다. 이는 "생의 사고 사슬"이 단순한 질문을 위한 마법의 속임수가 아니라, 로봇이 복잡하고 재귀적인 논리를 다룰 수 있게 해주는 강력한 도구임을 보여준다는 점에서 큰 의미가 있습니다.
• 그들이 배제한 것: 그들은 이 작업을 수행하기 위해 "레이어 정규화(layer normalization)"(숫자를 안정적으로 유지하기 위한 흔한 AI 기법)와 같은 화려한 추가 도구가 필요하지 않다는 것을 보여주었습니다. 로봇은 어텐션과 수학이라는 기본 구성 요소만으로도 이를 수행할 수 있습니다.
• "아니오"의 부분: 또한, 로봇이 트리에서 문제를 해결할 수 있다고 해서, 그 트리의 선 버전에서도 자동으로 해결할 수 있다고 가정해서는 안 된다는 점도 보여주었습니다. 새로운 형태에 맞춰 메커니즘을 처음부터 다시 구축해야 합니다.

호기심 많은 십 대를 위한 요약

당신에게 한 번에 한 가지만 볼 수 있는 로봇이 있다고 상상해 보세요. 만약 미로의 출구를 찾으라고 하면, 로봇은 혼란에 빠질 수 있습니다. 하지만 만로에게 "한 걸음 내딛고, 네가 어디 있는지 적고, 그다음 또 한 걸음을 내디뎌라"라고 말한다면, 로봇은 숙련된 탐험가가 됩니다.

이 논문은 이러한 "단계별 사고"를 하는 로봇들이 진지한 수학을 수행할 수 있을 만큼 강력하다는 것에 대한 증거입니다. 그들은 트리의 가지를 세고, 숲을 통과하는 최단 경로를 찾으며, 심지어 동일한 지도를 그리는 서로 다른 방식 사이를 번역할 수도 있습니다. 저자들은 단순히 추측한 것이 아니라, 이 로봇들을 위한 정확한 지침(설계도)을 구축했고 그것이 완벽하게 작동함을 보여주었습니다.

가장 흥미로운 점은 그들이 어떤 추가적인 지름길이나 별도의 하드웨어 없이 이 일을 해냈다는 것입니다. 그들은 단지 로봇이 적절한 시간에 적절한 것에 주의를 기울이는 능력만을 사용했습니다. 이는 마치 연필과 종이를 가진 인간이, 종이조차 없는 컴퓨터는 시작조차 할 수 없는 퍼즐을 풀 수 있음을 보여주는 것과 같습니다. 그리고 로봇이 나무를 걸을 수도, 선을 걸 수도 있지만, 각 경로에 맞는 서로 다른 신발이 필요하다는 점—그냥 신발을 갈아 신는다고 해서 걷는 방식이 바뀌지 않는다는 점—을 보여줍니다.

요컨대, 이 논문은 적절한 "생의 사고 사슬"이 있다면 AI가 단순히 추측하는 것을 넘어 진정으로 탐험하기 시작할 수 있다는 것을 보여주는 로드맵입니다.