같은 예산으로 붙으면 무너지는 탐색의 환상

오늘 살펴볼 연구는 Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows라는 제목으로 arXiv에 공개된 논문 arXiv 2610.12542입니다. 이 연구가 내세우는 주장은 한 문장으로 정리할 수 있는데, 동일한 개수의 후보 스케줄을 만들고 평가하는 동등한 예산 아래에서는 정교한 몬테카를로 트리 탐색이 단순한 랜덤 재시작 리스트 스케줄링을 이기지 못했다는 것입니다. 원문 논문으로 이어지는 연결은 제목 아래에 걸려 있으니, 읽다가 원문이 궁금해지면 그곳에서 확인할 수 있습니다.

제가 이 논문에서 가장 흥미롭게 본 부분은 승패 자체가 아니라 승패를 가린 방식이었습니다. 보통은 새로운 탐색 기법이 나오면 더 좋은 점수를 보여주는 데 집중하는데, 여기서는 반대로 단순한 쪽에게 똑같은 기회를 주는 데 공을 들였기 때문입니다. 그래서 숫자를 보기 전에 먼저 어떤 문제를 다루는지부터 차근차근 따라가 보려 합니다.

똑똑해 보이는 방법이 항상 이기는 것은 아닙니다

안녕하세요, 패트릭입니다.

같이 일하는 팀에 마감 기한이 촉박한 프로젝트가 들어왔다고 상상해 보시죠. 일의 순서를 정하는 데만 하루를 쓰는 동료가 있는 반면, 다른 동료는 대충 순서를 정하고 바로 실행한 뒤 마음에 안 들면 처음부터 다시 짜는 식으로 일합니다. 전자 쪽이 훨씬 체계적으로 보이는데요. 그렇다면 실제로 결과물의 완성도도 전자 쪽이 더 좋을까요?

저는 이 질문을 읽으면서 스케줄링 연구에서 자주 보던 장면이 떠올랐습니다. 트리를 키우고 통계를 쌓고 선택 규칙을 다듬는 방법은 분명 지적으로 매력적입니다. 반면 무작위로 순서를 뽑아 탐욕적으로 배치하고 마음에 안 들면 다시 뽑는 방법은 너무 단순해서 논문으로 쓰기 민망하게 느껴질 정도죠. 그런데 이번 연구는 그 민망한 방법이 체계적인 방법을 이기는 장면을 보여줍니다. 그것도 운이 아니라 통제된 조건에서 반복적으로 말이죠.

여기서는 조금 조심해서 읽을 필요가 있습니다. 단순한 방법이 이겼다는 이야기가 정교한 탐색이 쓸모없다는 뜻은 아니기 때문입니다. 제가 앞으로 보고 싶은 것은 왜 같은 예산 아래에서 이런 역전이 일어나는지, 그리고 그 이유가 우리가 탐색을 평가하는 습관에 무엇을 말해주는지입니다.

워크플로 스케줄링은 결국 순서와 배치를 고르는 일입니다

DAG 워크플로 스케줄링이라는 말은 어렵게 들리지만, 실제로 하는 일은 꽤 직관적입니다. 서로 의존하는 일들의 묶음이 있고, 이를 여러 대의 프로세서에 나눠서 최대한 빨리 끝내는 순서를 찾는 것이죠. 선행 작업이 끝나야 다음 작업을 시작할 수 있고, 어떤 프로세서에 올리느냐에 따라 전체 종료 시각이 달라집니다.

이 문제를 어렵게 만드는 것은 경우의 수가 폭발적으로 늘어난다는 점입니다. 작업이 8개일 때는 눈으로 그려볼 만하지만, 16개, 32개로 늘어나면 가능한 순서와 배치를 다 세는 것은 현실적으로 불가능해집니다. 그래서 연구자들은 좋은 스케줄을 빨리 찾는 휴리스틱에 의존하는데요. 이번 논문이 고른 무대는 바로 그 지점입니다. 작업 수 8개, 16개, 32개와 프로세서 2대부터 8대까지를 조합한 합성 도메인을 쓰고, 최대 2048개의 후보 스케줄까지 예산을 늘려가며 두 방법을 비교합니다.

그렇다면 왜 합성 도메인일까요? 현실 워크플로는 조건이 제각각이라 무엇 때문에 이겼는지 알기 어렵기 때문입니다. 변수를 통제한 작은 방에서 먼저 승부를 가려보겠다는 선택인데, 저는 이 판단이 꽤 정직하다고 봅니다. 큰 문제로 가기 전에 작은 문제에서 공정한 비교를 통과하지 못하면, 큰 문제에서의 승리는 예산 차이 때문일 수 있으니까요.

같은 예산을 어디에 쓸지 고르는 일이었습니다

저희가 새로운 AI 아키텍처를 볼 때도 benchmark 숫자만 보지는 않습니다. 실제로 무엇이 바뀌었고, 그 변화가 시스템에서 어떤 비용 구조를 만드는지를 함께 봅니다. 이번 논문이 던지는 질문도 같은 결에 있는데, 좋은 점수를 내는 방법이 아니라 같은 노력을 들였을 때 누가 더 좋은 점수를 내는지를 묻습니다.

여기서 예산의 정의가 독특합니다. 벽시계 시간도 아니고 FLOPs도 아닙니다. 후보 스케줄을 만들고 평가한 횟수, 다시 말해 스케줄을 몇 번 짜보고 점수를 매겼는지를 기준으로 삼습니다. 모든 경쟁 방법은 정확히 같은 횟수만큼 스케줄을 만들고 평가받는데요. 이 차이는 생각보다 중요합니다. 정교한 방법은 한 번의 시도에 더 많은 계산을 숨길 수 있어서, wall-clock이나 구현 최적화로 비교하면 유리해 보이기가 쉽기 때문입니다. 시도 횟수로 묶어두면 그런 숨은 비용이 드러납니다.

표면적으로 보면 단순합니다. 실제로는 그렇지 않습니다. 같은 횟수라는 말은 같은 정보를 본다는 뜻이 아니라, 같은 횟수의 완성된 답안을 냈다는 뜻이기 때문입니다. 트리 탐색은 답 하나를 내기 위해 내부적으로 많은 시뮬레이션을 돌릴 수 있고, 재시작 기법은 매번 새로운 순서를 뽑아 탐욕적으로 배치합니다. 그래서 이 비교는 누가 더 많이 생각했는지가 아니라, 완성된 답안지 장수가 같을 때 누가 더 좋은 답을 내는지를 묻는 셈입니다. 저는 이 숫자보다 그 뒤의 구조가 더 중요하다고 봅니다. 예산을 무엇으로 정의하느냐가 곧 무엇을 공평하다고 믿는지를 보여주기 때문입니다.

이 논문이 트리 탐색을 부정하는 것은 아닙니다

오해하기 쉬운 지점을 먼저 정리하고 싶습니다. 이 논문은 몬테카를로 트리 탐색이라는 아이디어 자체가 틀렸다고 말하지 않습니다. 특정한 구현, 특정한 선택 규칙, 특정한 예산 범위에서 단순한 재시작보다 뒤졌다는 것을 보여줄 뿐인데요. 실제로 선택 규칙을 교과서적인 UCT로 바꾸면 격차의 대부분이 사라집니다.

그렇다면 왜 이런 구분이 중요할까요? 트리 탐색이라는 이름 아래에는 전혀 다른 동작이 들어갈 수 있기 때문입니다. 어떻게 자식을 펼치고, 어떤 통계를 유지하고, 언제 탐험을 멈추고 활용으로 넘어가는지에 따라 같은 이름의 방법이 정반대로 움직일 수 있습니다. 그래서 논문을 읽을 때는 트리 탐색이 졌다는 문장보다, 어떤 선택 규칙을 쓴 트리 탐색이 어떤 예산에서 졌다는 문장으로 읽어야 합니다.

또 하나 짚을 점은 예산의 상한입니다. 이번 실험은 최대 2048회 평가까지만 다루고, 그보다 큰 예산에 대해서는 아무 주장도 하지 않습니다. 2048번이면 적지 않아 보이지만, 일정 규모에서는 탐색이 뒤늦게 빛을 볼 수도 있죠. 연구진도 그 가능성을 열어두고 더 큰 예산으로 일반화하지 않습니다. 저는 이런 태도가 마음에 들었습니다. 이 결과는 마음에 들지만, 여기까지 일반화하기에는 데이터가 부족하다는 식의 솔직함이 논문 전체에 깔려 있기 때문입니다.

두 방법은 같은 출발선에서 어떻게 움직일까요

이제 두 선수가 같은 출발선에서 어떻게 뛰는지 따라가 보겠습니다. 먼저 리스트 스케줄링 쪽은 규칙이 단순합니다. 작업들의 우선순위 순서를 하나 정한 뒤, 순서대로 각 작업을 가장 빨리 끝낼 수 있는 프로세서에 올립니다. 탐욕적이라서 한 번의 시도는 금방 끝나는데요. 비결은 재시작에 있습니다. 순서를 무작위로 다시 뽑고 다시 배치하는 과정을 예산이 다할 때까지 반복한 뒤, 그중 가장 좋은 스케줄을 고릅니다.

반면 이번에 연구된 MCTS 쪽은 나무를 키우면서 배웁니다. 부분 스케줄을 노드로 보고, 어떤 작업을 다음에 둘지를 자식으로 펼치고, 시뮬레이션으로 끝까지 가본 뒤 돌아와 통계를 갱신합니다. 다음에는 좋아 보였던 가지를 더 파고들면서도 가끔은 안 가본 가지를 열어보는 식이죠. 듣기에는 훨씬 현명해 보입니다. 과거의 경험을 축적해서 다음 선택을 더 좋게 만드니까요.

문제는 그다음입니다. 현명해 보이는 축적이 실제로는 같은 답을 반복해서 내는 축적일 수 있다는 점입니다. 리스트 스케줄링의 재시작은 매번 서로 다른 순서를 뽑으니 답들이 흩어지는데, 트리 탐색은 초반에 좋았던 가지 주변을 계속 맴돌 수 있습니다. 같은 예산을 쓴다는 말이 같은 다양성을 본다는 뜻은 아니라는 것이죠. 일종의 오답 노트처럼요. 오답 노트가 두꺼워지는 것이 실력 향상을 뜻하지는 않듯이, 트리가 커지는 것이 곧 더 넓게 본다는 뜻은 아닙니다.

처음 펼친 자식을 계속 고르게 되는 탐색 규칙

제가 이 논문에서 멈칫했던 대목은 바로 여기입니다. 이번에 연구된 선택 규칙이 사실상 처음 펼친 자식에 결정적으로 달라붙는다는 분석인데요. 처음에 문을 연 가지가 좋든 나쁘든 계속 그 가지를 고르게 되니, 트리가 커져도 시야는 넓어지지 않는다는 것입니다.

생각해보면 사람도 비슷하게 배우는데, 처음에 운 좋게 푼 문제 유형만 계속 푸는 학생이 있습니다. 점수는 조금 오르지만, 새로운 유형이 나오면 손도 못 대죠. 이번 MCTS의 움직임이 이와 닮았습니다. 예산을 2048까지 써도 스스로 개선한 폭이 0.24퍼센트에 그쳤던 반면, 재시작 쪽은 같은 예산 안에서 스스로 1.85퍼센트를 개선했습니다. 예산이 모자라서 진 것이 아니라, 예산을 쓰는 방식이 다양성을 만들지 못해서 진 것에 가깝습니다.

더 직접적인 증거도 있습니다. MCTS가 낸 첫 결과 720개 가운데 700개가 그저 시작할 때 건네받은 warm start와 같은 답이었다고 합니다. 720번 중 700번이 사실상 같은 답을 낸 셈인데, 이는 매 시도가 독립적인 뽑기가 아니라 같은 답의 복사본에 가까웠다는 뜻입니다. 반면 재시작 쪽의 개선은 분포의 꼬리에서 왔습니다. 여러 번 뽑다 보면 가끔 아주 좋은 순서가 걸리는데, 그 드문 좋은 뽑기가 전체 최고점을 끌어올린 것이죠. 같은 횟수를 시도해도 한쪽은 같은 장면을 반복해서 보고, 다른 한쪽은 가끔 전혀 다른 장면을 본다는 차이가 승부를 갈랐습니다.

실험 설계가 먼저 잠기고 검증이 뒤를 받쳤습니다

이제 숫자 이야기로 들어가기 전에 실험이 어떻게 짜였는지 봐야 합니다. 저는 이 숫자보다 그 뒤의 구조가 더 중요하다고 봅니다. 점수 자체보다 점수를 믿게 만드는 장치가 더 오래 남기 때문입니다.

연구진은 데이터를 모으기 전에 분석 계획을 고정했습니다. 나중에 유리한 것만 골라 보여주는 일을 막기 위한 장치인데요. 실제 시스템 관점에서 보면 다음 질문이 바로 생깁니다. 그래도 구현 실수로 스케줄이 잘못 계산된 것은 아닐까? 여기서 독립적인 검사기가 등장합니다. 확인 단계의 스케줄 768개 전부에 대해 유효성과 종료 시각 계산이 맞는지 별도로 확인했고, 전부 정확했다고 합니다. 768개 전부라는 말이 주는 안도감은 꽤 큽니다. 한두 개를 표본으로 본 것이 아니라 확인 단계 전체를 본 것이니까요.

비교의 초점을 맞춘 방식도 눈여겨볼 만합니다. held-out 인스턴스 96개 가운데 기준선 대비 개선 여지가 양수인 72개에 주된 비교를 맞췄습니다. 이미 기준선이 최적에 가까워 더 좋아질 여지가 없는 문제는 빼고, 실제로 차이가 날 수 있는 문제에서 붙었다는 뜻인데요. 얼핏 보면 유리한 것만 골랐다고 오해할 수 있지만, 방향은 반대입니다. 천장이 낮아 변별이 안 되는 문제를 빼야 방법 사이의 차이가 제대로 드러나기 때문입니다. 물론 이 선택이 결과의 해석 범위를 정한다는 점은 기억해야 합니다. 72개에서의 패배가 모든 일정 문제에서의 패배는 아니라는 것이죠.

2048번의 평가 끝에 남는 2.88퍼센트의 간격

그렇다면 점수 차이는 얼마나 났을까요? 2048개의 스케줄을 평가하는 예산에서, 연구된 MCTS는 랜덤 재시작 리스트 스케줄링보다 2.88퍼센트 뒤졌습니다. 95퍼센트 신뢰구간은 마이너스 3.62퍼센트에서 마이너스 2.15퍼센트 사이였는데요. 일반 파일에만 남겼을 때와 SOUL.md에 옮겨 적었을 때처럼 조건에 따라 갈리는 수치가 아니라, 같은 조건에서 반복해도 구간 전체가 0보다 아래에 머무는 명확한 열세였습니다.

이 숫자는 어떻게 읽어야 할까요? 2.88퍼센트라고 하면 작아 보일 수 있습니다. 하지만 스케줄링에서 몇 퍼센트의 종료 시각 단축은 프로세서 대여 시간과 대기열 전체에 그대로 곱해지는 절감이기 때문에 운영에서는 작지 않습니다. 밤새 돌아가는 배치 워크플로에서 매일 3퍼센트 가까이 늦어진다면, 한 달이면 하루 가까운 계산 시간이 더 드는 셈이니까요. 저는 그래서 이 차이를 연구실 점수 이상으로 평가했습니다. 운영의 아침을 지켜주는 장치와 같은 문제이기 때문입니다.

여기서는 조금 조심해서 읽을 필요가 있습니다. 2.88퍼센트는 평균적인 격차이지 모든 문제에서 같은 격차가 났다는 뜻은 아닙니다. 어떤 인스턴스에서는 거의 차이가 안 났고, 어떤 인스턴스에서는 더 벌어졌을 수 있습니다. 신뢰구간이 말해주는 것은 방향의 일관성이지 크기의 균일함이 아닙니다. 다시 말해 운이 나빠서 진 것이 아니라 구조적으로 밀렸다는 신호로 읽는 것이 맞고, 그 구조가 바로 앞에서 본 선택 규칙과 다양성의 문제로 이어집니다.

예산이 모자라서가 아니라는 것을 어떻게 알 수 있을까요

여기까지 읽으면 이런 반문이 생깁니다. 트리 탐색이 더 많은 예산을 받았으면 역전했을 것 아니냐는 것이죠. 연구진은 이 질문을 피하지 않고 정면으로 다룹니다. 탐색용 풀에서 각 방법이 스스로 얼마나 개선됐는지를 재는 방식인데요. 재시작 쪽은 예산 안에서 1.85퍼센트 스스로 좋아진 반면, MCTS 쪽은 0.24퍼센트만 좋아졌습니다. 같은 양의 기회를 줬는데 한쪽은 계속 전진하고 다른 한쪽은 제자리걸음을 했다는 뜻입니다.

이 차이는 생각보다 중요합니다. 만약 예산 부족이 패인이라면 예산을 늘릴수록 MCTS의 개선 폭도 커져야 하는데, 실제로는 개선 폭 자체가 작았기 때문입니다. 앞서 본 720개 중 700개가 warm start와 같았다는 사실과 함께 읽으면 그림이 더 선명해집니다. 새로운 시도가 새로운 정보를 가져오지 못하는데 예산을 더 준다고 달라질까요? 같은 영화를 700번 다시 보는 데 시간을 더 쓴다고 새로운 장면이 생기지 않는 것과 비슷합니다.

그렇다면 선택 규칙만 바꾸면 어떻게 될까요? 연구진은 교과서적인 UCT로 교체하는 추가 실험을 했습니다. 결과는 격차가 마이너스 0.26퍼센트로 줄고, 95퍼센트 신뢰구간이 마이너스 0.71퍼센트에서 플러스 0.23퍼센트가 되었다는 것입니다. 구간이 0을 포함하게 됐으니 통계적으로는 비겼다고 말할 수 있는 수준인데요. 하지만 부호 자체가 뒤집히지는 않았습니다. 규칙을 고치면 치명상은 피할 수 있지만, 단순한 재시작을 앞지르기에는 여전히 부족했다는 뜻입니다. 저는 이 대목에서 고개를 끄덕였습니다. 규칙 하나가 병목이었다는 진단과, 그 병목을 풀어도 낙승은 없다는 현실이 함께 드러나기 때문입니다.

다음에 더 큰 문제를 만나면 질문은 달라집니다

마지막으로 범위를 정리해야 합니다. 이 결과는 작업 수 8개, 16개, 32개와 프로세서 2대부터 8대까지의 통제된 합성 도메인에 갇혀 있습니다. 더 큰 예산, 더 큰 문제, 현실의 잡음이 섞인 워크플로에서는 이야기가 달라질 수 있는데요. 연구진도 그 너머에 대해서는 주장하지 않습니다.

그렇다면 이 흐름은 어디에서 다시 살펴봐야 할까요? 저는 세 가지 장면이 궁금합니다. 먼저 예산을 훨씬 크게 줬을 때 UCT 쪽이 재시작을 추월하는 지점이 오는지입니다. 다음으로는 현실 워크플로처럼 의존 구조가 불규칙하고 실행 시간이 들쭉날쭉할 때, 꼬리에서 먹는 재시작의 이점이 그대로 유지되는지입니다. 마지막으로는 트리 탐색의 상관된 시도 문제를 풀어주는 다른 선택 규칙이나 다양성 장치가 단순 재시작을 이기는 조합을 만들 수 있는지입니다.

이 논문이 흥미로운 이유는 단순히 단순한 방법이 이겼다는 데 있지 않습니다. 평가의 기준을 시도 횟수로 묶는 순간, 정교해 보이는 축적이 반복에 불과했다는 사실이 드러난다는 데 있습니다. 그 통로가 구현의 버그가 아니라 평범한 선택 규칙이었다는 점도 눈에 띕니다. 앞으로 스케줄러를 고를 때는 어떤 방법이 더 똑똑해 보이는지가 아니라, 같은 개수의 답안지를 낼 때 누가 더 다른 답을 내는지를 함께 물어야 할 것 같습니다. 제가 앞으로 보고 싶은 것은 바로 그 질문을 통과한 다음 세대의 탐색입니다.