탐색을 외우는 법, 계획을 덜 저장하는 법

오늘 다룰 논문은 arXiv에 2610.10954번으로 공개된 Learning How to Search for Plans with Exponentially Less Space입니다. 제목 아래에 원문으로 이어지는 링크를 달아두었으니 직접 확인하실 수 있습니다. 이 논문이 내세우는 주장은 한 문장으로 정리되는데요, 과제마다 다시 탐색하는 대신 도메인마다 탐색을 제어하는 지식을 배우면 방문한 상태를 저장하지 않고도 다항식 공간 안에서 계획을 찾을 수 있다는 것입니다.

거의 완벽한 휴리스틱이 왜 메모리를 터뜨릴까

계획 문제를 풀어본 분이라면 휴리스틱이 좋으면 탐색이 쉬워진다고 기대하실 텐데요, 이 논문은 그 기대가 깨지는 지점부터 이야기를 시작합니다. 휴리스틱이 거의 완벽에 가까워도 탐색이 저장해야 하는 상태 수가 기하급수적으로 불어날 수 있다는 것입니다. 저는 이 대목에서 멈칫했습니다. 보통은 평가 함수가 정확하면 몇 단계만 둘러보고 답을 찾을 것 같기 때문입니다.

그런데 생각해보면 사람이 길을 찾을 때도 비슷합니다. 목적지까지 남은 거리를 거의 정확히 아는 내비게이션이 있어도, 갈림길마다 실제로 가보지 않으면 알 수 없는 막다른 골목이 계속 나오면 결국 지나온 길을 전부 메모해야 합니다. 거리 추정이 정확하다는 것과 어디로 꺾어야 하는지를 안다는 것은 다른 문제니까요. 논문이 지적하는 지점도 바로 여기입니다. 남은 비용을 잘 어림하는 것과 다음에 어떤 물건을 잡아야 하는지를 아는 것은 층위가 다릅니다.

그래서 저자는 질문을 바꿉니다. 매 과제마다 더 좋은 숫자를 구할 수는 없을까를 묻는 대신, 도메인 전체에 통하는 제어 지식을 따로 배울 수는 없을까를 묻는 것이죠. 이 전환은 생각보다 중요합니다. 전자는 매번 같은 미로를 처음부터 헤매는 방식이고, 후자는 미로의 종류마다 요령을 외워두는 방식이기 때문입니다. 그렇다면 그 요령은 어떤 모양이어야 할까요.

과제마다 찾지 말고 도메인마다 외우자는 발상

여기서 논문이 제안하는 단위가 바뀌는데요, 과제(task)가 아니라 도메인(domain)입니다. 과제는 초기 상태와 목표가 정해진 한 판이고, 도메인은 같은 규칙으로 돌아가는 여러 판을 묶은 세계입니다. 매 판마다 처음부터 탐색하는 대신, 그 세계에서 통하는 행동 방식을 하나로 적어두자는 것이 논문의 출발점입니다.

저는 이 발상이 마음에 들면서도 곧바로 다음 의문이 생겼습니다. 도메인마다 통하는 방식이라는 게 과연 몇 줄로 적힐 수 있을까 하는 점입니다. 물체의 개수가 늘어나고 상태 공간이 커지면 규칙도 함께 비대해지는 것 아닐까요. 논문은 이 의심을 피하지 않고, 오히려 제어 지식을 담는 그릇부터 새로 설계합니다. 그 그릇이 바로 indexical policy입니다.

이 이름이 낯설게 느껴지신다면 이렇게 읽으셔도 됩니다. 손가락으로 가리키는 말을 쓰는 정책이라는 뜻입니다. 여기 있는 블록, 지금 들고 있는 상자처럼 문맥에 따라 가리키는 대상이 바뀌는 표현을 정책 안에 넣자는 것이죠. 고정된 물체 이름을 나열하는 대신, 지금 주목하는 물건을 담아두는 자리를 만들고 규칙이 그 자리를 참조하게 합니다. 그렇다면 그 자리는 구체적으로 어떻게 생겼을까요.

물건을 담는 레지스터와 순서를 정하는 모드

논문이 쓰는 정책은 두 가지 장치를 함께 씁니다. 하나는 물체를 담는 레지스터이고, 다른 하나는 규칙의 순서를 정하는 모드입니다. 레지스터는 말 그대로 손에 쥐고 있는 물건을 기록하는 자리인데요, 특정 블록이나 특정 위치를 이름으로 못 박는 대신 지금 다루는 대상을 그릇에 담아둡니다. 모드는 지금 어떤 단계에 있는지를 알려주는 표지판입니다. 같은 상황이라도 모드가 다르면 적용되는 규칙이 달라집니다.

이 조합이 좋은 이유는 일반화 때문입니다. 물체가 열 개든 백 개든 정책 자체는 그대로인데, 레지스터에 담기는 내용만 바뀌면 되니까요. 마치 요리 레시피에서 양파 두 개, 당근 세 개라고 적지 않고 지금 손질 중인 채소라고 적어두는 것과 비슷합니다. 재료가 바뀌어도 조리 순서는 그대로 따라갈 수 있죠. 물론 이렇게만 쓰면 언제 무엇을 집어야 하는지가 여전히 남는데요, 그래서 다음 장치가 등장합니다.

다만 여기서 한 가지는 짚고 넘어가고 싶습니다. 레지스터와 모드라는 말이 멋있게 들리지만, 실제로는 제어가 어디까지 책임지는지를 분명히 하려는 설계에 가깝습니다. 무엇을 기억할지, 언제 다음 단계로 넘어갈지를 정책의 문법으로 못 박아두는 것이죠. 저는 이 숫자보다 그 뒤의 구조가 더 중요하다고 봅니다. 기억의 모양을 바꾸면 탐색의 모양도 바뀌기 때문입니다.

하나만 맞으면 되는 지점을 따로 두는 규칙

이제 논문에서 제가 가장 흥미롭게 본 부분인데요, 바로 choose라는 규칙입니다. choose는 물체를 레지스터에 올리면서 백트래킹 지점을 만드는 규칙입니다. 다시 말하면, 여기서만큼은 여러 후보 중에서 하나만 맞으면 된다고 선언하는 자리입니다. 탐색이 필요하다면 바로 이 지점에서만 일어난다는 뜻이기도 합니다.

반면 choose가 아닌 다른 규칙들은 훨씬 엄격합니다. 그 규칙들은 모든 경우에 통해야 하고, 탐색 없이 그대로 실행되어야 합니다. 하나만 맞으면 되는 지점과 무엇이 나와도 통해야 하는 지점을 문법으로 나눈 셈이죠. 이 구분은 실제 문제를 풀 때 제가 자주 느끼는 감각과 닮았습니다. 대부분의 단계는 정해진 순서대로 밀고 나가면 되는데, 가끔 어떤 물건을 먼저 잡을지 같은 갈림길에서만 고민하게 되니까요.

그렇다면 왜 이런 구분이 공간을 아낄까요. 답은 책임의 분리에 있습니다. 어디서든 헤맬 수 있는 정책이라면 매번 지나온 길을 저장해야 하지만, 헤맬 수 있는 자리가 미리 정해져 있으면 되돌아갈 지점도 정해져 있기 때문입니다. 물론 choose 지점이 너무 많아지면 다시 탐색이 커질 텐데요, 논문은 그 깊이를 작게 유지하는 쪽으로 학습을 이끕니다. 그 이야기는 학습 부분에서 다시 다루겠습니다.

무한 실행을 막았더니 실행 길이가 묶인 이유

논문의 중심에는 structural termination이라는 조건이 있습니다. 이름 그대로 구조적으로 무한 실행을 막는 조건인데요, 규칙들의 모양을 보고 영원히 돌 수 있는 실행이 없음을 보장합니다. 여기까지만 들으면 당연한 안전장치처럼 들릴 수 있습니다. 무한 루프를 막는다는 것은 바른 정책이라면 갖춰야 할 성질처럼 보이니까요.

그런데 논문이 보여주는 것은 한 걸음 더 나아갑니다. 이 종료 조건을 만족하면 모든 실행의 길이가 물체 개수에 대한 다항식으로 묶인다는 것입니다. 무한히 돌지 않는다는 정성적인 보장이, 길이가 길어봤자 어느 선을 넘지 않는다는 정량적인 보장으로 이어지는 셈입니다. 저는 이 연결이 이 논문에서 가장 단단한 대목이라고 봅니다. 보통은 끝나긴 끝난다는 것과 빨리 끝난다는 것 사이에 큰 간격이 있는데, 여기서는 문법이 그 간격을 메워주기 때문입니다.

왜 이런 일이 생길까요. 직관적으로 말하면, 모드와 레지스터의 움직임이 물체의 개수를 기준으로 층층이 정리되어 있기 때문입니다. 같은 상태를 빙빙 도는 실행이 구조적으로 불가능해지면, 서로 다른 실행 단계의 개수도 물체의 조합 수 안에서 묶이게 됩니다. 상태 공간 전체가 아무리 커도, 정책이 실제로 밟는 궤적의 길이는 그보다 훨씬 짧은 천장 아래에 들어가는 것이죠. 그렇다면 이 궤적을 따라가는 탐색 절차는 어떤 모양일까요.

방문 목록 없이 깊이 들어가는 탐색이 가능한 이유

논문이 제안하는 절차는 깊이 우선 탐색의 변형인데요, 특이한 점은 방문한 상태 목록을 두지 않는다는 것입니다. 보통 탐색이라고 하면 어디를 다녀왔는지 적어두는 것이 상식인데, 여기서는 그 목록이 없습니다. 상태 공간이 아무리 커도 필요한 공간은 물체 개수에 대한 다항식 수준으로 묶입니다.

어떻게 이런 일이 가능할까요. 이유는 정책이 이미 궤적의 길이를 묶어두었기 때문입니다. 되돌아갈 지점은 choose에서만 생기고, 그 외의 구간은 정해진 규칙대로 밀고 나가면 되니까 넓게 펼쳐진 상태들을 일일이 기억할 필요가 없습니다. 막다른 골목에 들어서면 마지막으로 갈라졌던 choose 지점으로 돌아가 다른 후보를 집으면 됩니다. 스택에 쌓이는 것도 지금 파고드는 경로뿐이죠.

실제 시스템 관점에서 보면 다음 질문이 바로 생깁니다. 시간이 아니라 공간을 아꼈다는 것은 정확히 무슨 이득일까요. 메모리 사용량이 작다는 것은 더 큰 문제를 같은 기계에 올릴 수 있다는 뜻이고, 동시에 캐시와 대역폭에 걸리는 부담도 줄일 수 있다는 뜻입니다. 논문이 보고하는 100MiB라는 숫자는 그래서 단순한 절약 이야기가 아니라, 계획 탐색을 가벼운 실행기로 바꾸는 이야기처럼 읽힙니다. 물론 시간은 여전히 남는데요, 그 대가는 choice depth라는 하나의 숫자에 모여 있습니다.

왜 NP 이야기와 P 이야기가 함께 나오는 걸까

여기서 논문은 복잡도 이야기로 시야를 넓힙니다. 이런 식으로 종료가 보장되는 정책으로 풀리는 문제 부류는 NP에 들어간다는 것입니다. 그리고 choice depth가 상수로 묶이면 P에 들어간다고 말합니다. 처음 들으면 추상적으로 느껴지실 수 있는데요, 저는 이 대목을 학습 가능성과 복잡도를 잇는 다리로 읽었습니다.

연결은 이렇게 따라갈 수 있습니다. 실행 길이가 다항식으로 묶여 있으면, 정답이 되는 실행 자체가 짧은 증명처럼 쓸 수 있습니다. choose 지점에서 어떤 후보를 골랐는지만 적어두면 검증은 다항 시간에 끝나니까요. 그래서 NP라는 말이 나옵니다. 여기서 한 걸음 더 나아가 choose 지점의 깊이까지 상수로 묶어두면, 후보를 전부 따져보는 데 드는 시간도 다항식으로 묶입니다. 그래서 P라는 말이 이어지는 것이죠.

이 구분은 학습을 설계할 때도 그대로 살아 있습니다. 정책을 배울 때 choice depth를 작게 유지하라는 것은 단순한 취향이 아니라, 찾아낸 지식이 실제로 다루기 쉬운 복잡도 안에 머물게 하려는 선택입니다. 깊이를 얼마나 허용할지가 곧 얼마나 헤맬지를 정하고, 얼마나 헤맬지가 곧 얼마나 기다려야 할지를 정하니까요.

언어 모델이 반례를 보며 정책을 고치는 과정

그렇다면 이런 정책은 어떻게 배울까요. 논문은 언어 모델을 쓰는 반례 기반 루프로 정책을 학습합니다. 처음에는 후보 정책을 하나 만들고, 종료 조건을 검사하고, 훈련 과제들에서 검증하면서 어긋난 지점을 찾습니다. 어긋난 지점이 나오면 그 반례를 모델에게 보여주고 정책을 고치게 하는데요, 말하자면 오답 노트처럼요. 틀린 문제를 모아두었다가 다음에는 같은 실수를 하지 않도록 규칙을 다듬는 방식입니다.

이 루프가 신경 쓰는 것은 세 가지입니다. 종료가 깨지지 않는지, 훈련 과제들을 실제로 푸는지, 그리고 choice depth가 작게 유지되는지입니다. 하나라도 어긋나면 다시 고칩니다. 제가 보기에 이 과정의 미덕은 욕심을 부리지 않는 데 있습니다. 처음부터 완벽한 정책을 뽑아내려 하지 않고, 틀린 자리를 정확히 짚어서 작은 수정으로 메워 나갑니다.

여기서는 조금 조심해서 읽을 필요가 있습니다. 언어 모델이 정책을 쓴다고 해서 모델이 계획을 직접 푸는 것은 아닙니다. 모델이 쓰는 것은 탐색을 제어하는 규칙이지, 매 과제의 답 자체가 아닙니다. 이 차이는 생각보다 중요합니다. 답을 외우는 기계는 과제가 바뀌면 다시 헤매지만, 요령을 적는 기계는 같은 도메인의 새 과제에도 같은 요령을 꺼내 쓸 수 있기 때문입니다. 그렇다면 그렇게 배운 요령은 실제로 얼마나 통했을까요.

1709개라는 숫자를 조심해서 읽는 법

논문이 보고하는 숫자는 분명합니다. IPC 2023 Learning Track과 Autoscale Agile 묶음에서 가져온 1,890개 과제 가운데 1,709개를 풀었고, LAMA와 BFWS와 Levitron보다 많이 풀었으며, 대부분을 1초 안과 100MiB 안에서 풀었다는 것입니다. 표면적으로 보면 단순합니다. 많이 풀었고, 빨리 풀었고, 가볍게 풀었다는 이야기니까요.

하지만 저는 이 숫자를 그대로 받아들이기 전에 조건을 함께 보고 싶었습니다. 이 결과는 특정 학습 트랙과 특정 과제 묶음에서 나온 것이고, 비교 대상도 명시된 세 가지 탐색 방식입니다. 다시 말하면, 모든 계획 문제에서 이 방식이 항상 앞선다는 뜻이 아니라, 배운 제어 지식이 통하는 도메인 안에서는 꽤 강하고 가볍다는 뜻에 가깝습니다. 실제로 시스템 관점에서 보면 이런 해석이 더 유용합니다. 저희가 새로운 AI 아키텍처를 볼 때도 benchmark 숫자만 보지는 않습니다. 실제로 무엇이 바뀌었고, 그 변화가 시스템에서 어떤 비용 구조를 만드는지를 함께 봅니다.

개인적으로 인상 깊었던 점은 속도와 메모리 조건입니다. 1초와 100MiB라는 수치는 연구실 점수라기보다 운영의 수치에 가깝기 때문입니다. 방문 목록을 두지 않는 설계가 이런 가벼움으로 이어졌다는 설명은 앞선 이론과도 맞물립니다. 물론 풀지 못한 과제들도 남는데요, 그 실패가 choice depth가 깊어지는 지점에서 생긴 것인지, 종료 조건 때문에 표현 자체가 막힌 것인지는 논문 밖에서 더 따져볼 여지가 있습니다. 그럼에도 이 정도 규모의 과제에서 세 가지 기준 탐색을 앞섰다는 점은 가볍게 넘기기 어렵습니다.

계획을 외우는 기계에게 앞으로 보고 싶은 것

마지막으로 시야를 넓혀보겠습니다. 이 논문이 바꾸는 것은 탐색의 크기가 아니라 탐색의 단위입니다. 과제마다 더 멀리 보는 대신, 도메인마다 더 정확히 외우는 쪽을 택한 것이죠. 휴리스틱 숫자를 다듬는 경쟁에서 한 발 물러나, 언제 무엇을 집을지를 문법으로 적는 경쟁을 시작한 셈입니다.

그렇다면 다음 질문은 자연스럽게 이어집니다. 이런 정책은 어디까지 일반화될까요. 훈련 과제에서 통했던 레지스터와 모드의 조합이 전혀 본 적 없는 크기의 과제에서도 그대로 통할까요. 종료 조건이 길이를 묶어준다는 보장은 든든하지만, 그 보장이 통하는 표현 안에 우리가 풀고 싶은 도메인이 얼마나 들어오는지도 함께 물어야 합니다. 학습 루프가 반례를 얼마나 적은 시도로 메우는지, choice depth를 작게 유지하는 압력이 어려운 도메인에서도 버티는지도 궁금합니다.

제가 앞으로 보고 싶은 것은 그래서 실패 목록입니다. 풀지 못한 과제들이 어떤 모양인지, 그 과제들에서 choose 지점이 어떻게 늘어나는지, 그리고 그 지점을 줄이기 위해 규칙을 어떻게 바꿀 수 있는지를 보고 싶습니다. 성공한 숫자도 좋지만, 다음 요령이 어디서 필요한지를 알려주는 것은 언제나 실패 쪽이었으니까요. 계획을 외우는 기계가 다음에는 어떤 도메인을 외울지, 그 장면을 지켜보는 일은 꽤 즐거울 것 같습니다.