목차

• 탑 위에서 자꾸 무너지는 것들
• 컨텍스트 윈도우를 테이프처럼 다루기

이 글은 ICML 2026 워크숍에서 Nathan Sturtevant의 강연 “LLM Planning Success”를 발표자 1인칭 시점으로 재구성한 것입니다.

2012년, 브라이트니스에서 로드니 브룩스가 이런 말을 한 적이 있다. 우리가 지금 AI에서 진보를 이루고 있다고 믿을 이유는 없다고. 언덕을 오른다고 해서 그게 하늘에 닿는 길이라는 보장은 없다는 뜻이었다. 최근에는 교황도 비슷한 취지의 말을 했다. 인간의 지능과 우리가 데이터 분야에서 보는 지능을 동일시하는 오해를 피해야 한다고. 이런 말들은 LLM의 추론을 논할 때면 늘 배경에 깔려 있다. 나는 이런 거대 담론보다는 훨씬 실용적인 쪽에 서 있는 사람이다. 결국 내가 AI에서 하는 일도, 인간으로서 컴퓨테이션을 이용해 세상의 어떤 목표를 달성하려는 시도일 뿐이다. 그리고 이번 작업에서 내가 마주한 목표는 이랬다. LLM이, 혹은 LRM이 planning을 할 수 없다는 논문들, 중간 추론 토큰이 사실은 진짜 추론이 아니라는 주장들 앞에서 — 그렇다면 무엇이 필요한지를 실제로 만들어보자는 것.

동료 아산이 특히 이 질문에 관심이 많았다. LLM 기반 아키텍처로 100%에 가까운 정확도의 planning을 얻으려면 무엇이 필요한가. 게리 마커스는 올해 초, 이걸 하려면 논리적 오라클이 반드시 필요하다고 못 박았다. 이번 세션에서 나보다 뒤에 발표하는 랄프는 중간 추론 토큰을 계산의 흔적으로 봐서는 안 된다고 주장해왔다. 나는 오늘, 그 중간 토큰들을 진짜 계산의 흔적처럼 보이게 만들고, 그걸 기반으로 학습시켜서, 지금까지 논의된 벤치마크들에서 아주 높은 성공률을 얻는 방법을 보여주고 싶었다.

탑 위에서 자꾸 무너지는 것들

본론에 들어가기 전에, 우리가 왜 이 문제에 부딪혔는지부터 짚고 싶다. 하노이의 탑 문제를 애니메이션으로 만들어본 적이 있다. 원반 8개짜리, 240프레임으로 돌려도 풀리는 데 시간이 꽤 걸린다. 여기서 흥미로운 점은 이 문제를 풀 알고리즘이 없어서가 아니라는 것이다. 문제는 아주 긴 추론 흐름이 필요하고, 그 중 어느 한 지점에서라도 사소한 실수를 하면 전체가 무너진다는 데 있다. 텍스트 프롬프트로 이 문제를 준 실험에서, 성공률은 원반 수가 늘어날수록 사실상 0으로 수렴했다.

라오 교수 그룹은 블록스월드로 비슷한 걸 보여줬다. 테이블 위에 블록들이 쌓여 있고, 목표는 그걸 다시 정렬된 순서로 쌓는 것이다. 텍스트로 도메인을 설명하고 목표를 준 상태에서, 대칭 플래너인 Fast Downward는 이 모든 문제를 100% 정확도로 풀어냈다. 반면 통제군으로 넣은 추론 모델들은 전부 그 근처에도 가지 못했다. 서치포머 같은 연구도 있었다. 트랜스포머가 A* 탐색을 흉내 내도록 수백만 개의 탐색 흔적을 학습시키는 방식인데, 64번 시도 중 한 번만 성공하면 된다는 조건이라면 그럭저럭 높은 성공률이 나온다. 하지만 그건 우리가 원하는 신뢰도와는 거리가 멀었다.

이론 쪽에서는 또 다른 흐름이 있었다. 앨버타 대학의 데일 슈어만스, 마를로스 마차도, 그리고 박사과정생 알렉스가 최근 arXiv에 올린 논문에서, 자기회귀 방식으로 출력을 계속 이어붙이는 것만으로도 튜링머신, 즉 일반적인 계산이 가능하다는 걸 보여줬다. 심지어 아무런 사전학습도 되지 않은 언어모델조차 이 능력이 내재해 있다는 것도 확인했다. 다만 이걸 실제로 컴파일러처럼 가중치에 심어 넣는 작업까지는 하지 않았다. 하드코딩된 가중치를 가진 루프 트랜스포머로 튜링 완전성을 아키텍처 자체에 새겨 넣을 수 있다는 연구도 있었다. 뺄셈을 하고, 결과가 0 이하면 점프하거나 계속 진행하는 식의 프로그래밍 가능한 명령어를 트랜스포머 안에 구현하는 것이다. 하지만 이것 역시 실제로 계산을 수행하는 시스템으로 이어지지는 않았다. 우리는 바로 이 이론적 가능성과 실제로 벌어지는 일 사이의 긴장 지점에, 그 중간 어딘가에 자리 잡을 무언가를 만들어보고 싶었다.

컨텍스트 윈도우를 테이프처럼 다루기

여기서 시작한 아이디어는 단순하다. 튜링머신과 대형 언어모델을 나란히 놓고 보면 닮은 구석이 많다. 테이프가 있고, 거기에 토큰을 써 넣는다. 그렇다면 아예 언어모델에 튜링머신에 가까운 기능을 명시적으로 주면 어떨까. 우리는 append-only 튜링머신, 즉 끝에만 덧붙일 수 있는 변형된 튜링머신에서 시작했다. 이걸 위해 세 가지 조각을 준비했다. 첫째는 구조화된 컨텍스트 윈도우다. 컨텍스트를 고정된 크기의 블록으로 주소를 매겨 다룰 수 있게 만든 것으로, 튜링머신의 테이프처럼 작동한다. 둘째는 체인 오브 컴퓨테이션이다. 체인 오브 소트와 비슷하지만 더 구조화된 방식으로, 작은 창을 요청하고 읽고 계산한 다음 또 다른 창을 요청하는 식으로 반복한다. 셋째는 정책 학습이다. 일반적인 정책 샘플들로 학습해서, 세계 모델과 정책을 동시에 배우게 한다.

컨텍스트 윈도우는 여섯 개의 슬롯 블록으로 구성했다. 모델은 그 안에서 다음 블록을 가리킬 포인터를 지정하거나, 끝에만 쓸 수 있는 규칙 아래 새로운 내용을 덧붙일 수 있다. 잘못된 주소를 주면 그건 실패로 간주된다. 매 반복마다 이 작고 고정된 크기의 창만 보여주고 생성을 시키는데, 이때 특정 키워드가 나오면 추가 계산이 촉발된다. append는 결과를 내 구조화된 컨텍스트에 덧붙이라는 뜻이고, 포인터가 -1이 되면 계산이 끝났다는 신호다. 하노이의 탑으로 예를 들면, k개의 원반을 첫 번째 기둥에서 세 번째 기둥으로 옮기는 문제를 만나면, 모델은 컨텍스트 윈도우에 세 가지를 새로 적는다. k-1개를 1에서 2로, 1개를 1에서 3으로, 그리고 다시 k-1개를 2에서 3으로. 재귀가 그대로 컨텍스트에 펼쳐지는 셈이다. 팬케이크 퍼즐에서는 정렬되지 않은 것 중 가장 큰 팬케이크를 찾아 맨 위로 뒤집고, 그걸 다시 제자리로 뒤집어 넣는 정책을 썼다. 블록스월드는 더 단순해서, 일단 모든 블록을 테이블에 내려놓고 다시 순서대로 쌓아 올리는 두 단계 정책이면 충분했다. 이 모든 걸 디코더 온리 모델, 그것도 상당히 작은 어휘와 적은 파라미터로 학습시켰다. 대형 프레임워크를 빌려 쓰지 않은 이유는 간단하다. 우리가 알고 싶었던 건 아주 높은 성공률을 얻으려면 정확히 무엇이 필요한가였기 때문이다.

결과는 기대 이상이었다. 하노이의 탑은 원반 1개부터 15개까지, 즉 32,767 스텝짜리 계획까지 전부 100% 성공했다. 블록스월드에서는 6개부터 40개 블록까지 50개 테스트 문제를 전부 풀었다. 확장 블록스월드에서는 크기 35와 36에서만 두 문제를 놓쳤고, 40까지는 다시 다 풀어서 99.89%의 성공률을 기록했다. 팬케이크 퍼즐도 100%였는데, 딱 하나 흥미로운 예외가 있었다. 목표 상태를 보고 모델이 맨 위 팬케이크를 뒤집었다가 다시 뒤집는, 실제로는 아무 의미 없는 행동을 한 뒤 종료를 선언한 경우였다. 결과적으로는 맞는 답을 냈지만, 세상에 존재하지 않는 행동으로 도달한 것이다. 여기서 만족하지 않고, 크기 8짜리 블록스월드의 가능한 초기 배치 4만 개를 전부 시도해봤다. 겨우 500개 예제로 학습시켰을 뿐인데, 이 4만 개의 문제 전체에서도 거의 100%의 성공률이 나왔다. 트랜스포머가 정책을 진짜로 일반화하고 있다는 뜻이었다. 학습 데이터를 500개에서 5개까지 줄여봐도 블록스월드는 크게 흔들리지 않았고, 팬케이크 퍼즐은 데이터가 훨씬 적어도 잘 일반화됐다. 확장 블록스월드만 조금 더 많은 데이터를 필요로 했다.

하노이의 탑만은 조금 다른 이야기를 들려줬다. 처음 돌렸을 때는 100%가 나와서 흥분했는데, 홀드아웃을 무작위로 바꿔서 다시 돌리자 성공률이 떨어졌다. 왜 그런지 들여다보니, append-only 구조에서는 끝에 계속 큰 숫자를 써 넣어야 하는데, 그 숫자가 지수적으로 커지기 때문에 일반화된 덧셈을 배워야 했던 것이다. 그래서 덧셈을 아예 별도의 모듈로 빼주고 다시 돌려봤다. 그러자 반복되는 스텝 몇 가지만 학습해도 되는 구조가 드러났다. 160개의 스텝만 학습시켜도 길이 181까지 일반화가 됐다. 전체 데이터의 1%도 안 되는 양이었다. 결국 하노이의 탑이 어려웠던 진짜 이유는 플래닝 자체가 아니라, 지수적으로 커지는 숫자에 대한 덧셈의 일반화였다는 게 드러난 셈이다. 여기서 한 걸음 더 나아가, 하노이의 탑에는 임의 주소에 쓰는 범용 메모리가 굳이 필요 없다는 걸 깨달았다. 대신 스택처럼 밀어넣고 꺼내는 구조, 즉 푸시다운 오토마타를 써봤다. 이걸로는 push, push, push와 출력, 그리고 단순한 이동 연산만으로 하노이의 탑을 표현할 수 있었다. 이 구조로는 원반 20개까지 완전히 풀렸다. 100만 토큰짜리 시퀀스이고, 필요한 명령어의 80%만 학습시켰는데도 100% 성공률이 나왔다.

이 모든 결과가 말해주는 건 결국 하나다. 외부의 심볼릭 시스템에 기대지 않고도, 트랜스포머 스스로 아주 길고 신뢰할 수 있는 플래닝을 해낼 수 있다는 것. 구조화된 컨텍스트에서 나온 체인 오브 컴퓨테이션, 그리고 일반 정책의 학습이 그 방법이었다. 그리고 그 과정에서 숫자의 일반화라는, 얼핏 사소해 보이지만 실은 발목을 잡는 지점도 하나 찾아냈다. 물론 누군가는 물을 것이다. 그래서 어쩌라는 거냐고. 이건 특정한 플래닝일 뿐, 모든 걸 아우르는 일반적인 추론은 아니지 않냐고. 맞는 말이다. 이 논문의 목표는 애초에 일반 추론을 증명하는 게 아니었다. 우리가 가진 아키텍처만으로도 아주 높은 성공률을 달성할 수 있다는 걸 보여주는 것, 그게 전부였다. 이걸 더 큰 LLM이나 LRM 인프라에 어떻게 연결할지, 임의 크기의 상태를 다루려면 구조화된 컨텍스트를 얼마나 키워야 할지, 아니면 하나의 상태를 여러 컨텍스트에 쪼개어 담는 알고리즘을 새로 짜야 할지는 아직 열린 질문이다. 깊이 우선 탐색 같은 다른 알고리즘을 시뮬레이션하려 한다면 푸시다운 오토마타 구조로 충분할 수도 있고, 어쩌면 훨씬 풍부한 계산과 훨씬 단순한 학습을 동시에 허락하는 다른 아키텍처가 필요할 수도 있다.

이 작업을 몇 번이고 다듬는 동안 옆에서 함께 고민해준 우리 랩 사람들에게, 그리고 CIFAR AI Chairs 프로그램에서 만난 좋은 사람들과 나눈 대화들에 고맙다는 말을 남기고 싶다. 브룩스의 말로 돌아가 보면, 언덕을 오른다고 그게 하늘에 닿는 길이라는 보장은 여전히 없다. 하지만 이번에 우리는 적어도 하나의 언덕만큼은, 정상까지 가는 길을 한 걸음 한 걸음 지도로 그려냈다. 그 지도가 다음 언덕에서도 쓸모가 있을지는, 이제 이 방에 있는 사람들의 몫으로 남겨두려 한다.

---