확률로 문턱을 밀어 올리는 탐색, Probabilistic Focal Search를 읽다

이번에 다룰 논문은 Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement이며, arXiv에 2609.10584로 공개된 연구입니다. 제목 아래에 걸어둔 원문 링크에서 전체 논문을 바로 확인할 수 있습니다. 이 논문이 내세우는 주장은 한 문장으로 정리됩니다. FOCAL 안에서 휴리스틱이 고른 노드를 확률 p로 확장하고 나머지 확률로는 f값이 가장 작은 OPEN 노드를 확장하면, 오랫동안 멈춰 있던 하한 f_min이 다시 움직이면서 제한을 만족하는 해에 더 빨리 닿을 수 있다는 것입니다.

왜 저는 이 탐색 논문을 오래 붙잡고 있었을까

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

저는 경로 찾기나 일정 짜기처럼 답을 하나씩 꺼내야 하는 문제를 보면 늘 같은 장면을 떠올립니다. 마트에서 계산대가 여러 개 열려 있는데, 모두가 한 줄이 빨리 줄어들기를 바라면서도 정작 그 줄이 왜 안 줄어드는지는 아무도 모르는 풍경이죠. 탐색 알고리즘도 비슷합니다. 머릿속으로는 좋은 순서대로 노드를 꺼내고 있다고 믿는데, 막상 로그를 열어보면 같은 구간을 몇만 번이나 맴돌고 있거든요.

제가 이 논문에서 가장 흥미롭게 본 부분은 그 맴돔을 탓하지 않고 구조에서 풀었다는 점입니다. 탐색이 느려진 이유를 휴리스틱이 나빠서라고 말하는 대신, 하한이 올라가지 못하는 구간에 주목했기 때문입니다. 여러분도 A스타로 큰 퍼즐을 풀어본 적이 있다면 아실 겁니다. f값이 같은 노드가 끝없이 이어지면, 아무리 좋은 평가 함수를 써도 체감 속도는 그대로인데요. 이 논문은 바로 그 답답한 구간을 정면으로 다룹니다.

그렇다면 하한이 멈추면 왜 전체 탐색까지 느려질까요? 그 질문을 따라가면 FOCAL이라는 독특한 대기열이 나옵니다.

제한 안에 들어오면 충분한 탐색이 따로 있습니다

탐색 이야기를 할 때 우리는 흔히 최적해를 찾는 장면부터 떠올립니다. 그런데 현장에서는 최적이라는 말이 늘 정답이 아닌데요. 물류 창고에서 로봇이 다음 통로로 접어들어야 하는 시각이 정해져 있다면, 완벽한 경로를 한 시간 뒤에 받는 것보다 10퍼센트쯤 돌아가더라도 지금 바로 받을 수 있는 경로가 낫습니다. 이럴 때 쓰는 생각이 bounded-suboptimal search입니다. 최적 비용을 C라고 할 때, w배 이내의 비용이면 받아들이겠다는 약속인데요. 예를 들어 w가 1.5라면 최적보다 50퍼센트까지 비싸도 괜찮다는 뜻입니다.

이 약속이 있으면 탐색은 여유가 생깁니다. 최적을 증명하려고 모든 가능성을 뒤질 필요가 없기 때문입니다. 대신 탐색은 두 개의 목록을 들고 다닙니다. 하나는 아직 열어보지 않은 모든 후보를 담은 OPEN이고, 다른 하나는 그중에서 f값이 w 곱하기 f_min 이하인 후보만 따로 모은 FOCAL입니다. 여기서 f_min은 OPEN에서 가장 작은 f값을 가리키는데, 이 값이 사실상 현재 증명된 하한 역할을 합니다. FOCAL 안에 들어온 노드는 제한을 어기지 않는다는 보증이 있으니까, 그 안에서는 휴리스틱이 마음껏 취향을 드러낼 수 있죠. 빨리 목표에 닿을 것 같은 노드를 골라도 안전망이 유지되는 구조입니다.

제가 이 구조를 좋아하는 이유는 역할 분담이 분명하기 때문입니다. 하한은 안전을 맡고, 휴리스틱은 속도를 맡습니다. 그런데 이 분업이 깨지는 순간이 있습니다. 하한이 오랫동안 같은 자리에 붙어 있으면, FOCAL의 입장권 기준도 함께 굳어버리기 때문입니다.

FOCAL 앞에 놓인 낮은 문턱이 잘 움직이지 않을 때

FOCAL의 입장 기준은 w 곱하기 f_min입니다. 그래서 f_min이 오르지 않으면 FOCAL의 크기도 늘지 않는데요. 새로운 노드가 들어오려면 기존 문턱을 넘어야 하는데, 그 문턱 자체가 꿈쩍하지 않는 셈입니다. 결정적 focal search는 FOCAL 안에서 휴리스틱이 가리키는 노드만 계속 확장합니다. 이 선택은 당장 목표에 가까워 보이는 길을 파고들기에는 좋은데, OPEN 깊숙이 잠든 작은 f값들을 깨우지는 못합니다. 그래서 f_min이 그대로 남고, FOCAL도 그대로 남고, 다음 확장에서도 같은 풍경이 반복됩니다.

생각해보면 사람도 비슷하게 일합니다. 마감 기한이 넉넉하다고 해서 당장 손에 잡히는 급한 일만 계속 처리하면, 진짜 중요한 일정은 캘린더 맨 아래에 그대로 남죠. 급한 일을 치울수록 마음은 바빠지는데, 전체 일정표는 한 칸도 앞으로 나아가지 않습니다. 탐색에서도 같은 일이 벌어집니다. 눈앞의 유망한 노드를 수만 번 확장하는 동안, 하한을 밀어 올릴 열쇠는 OPEN 한쪽 구석에서 조용히 대기하고 있습니다.

문제는 그다음입니다. FOCAL이 갇히면 탐색은 제한을 만족하는 해로 이어질 수 있는 노드를 아예 구경하지 못합니다. 그 노드는 f값이 조금 커서 입장권을 받지 못했는데, 사실 그 노드 뒤쪽에 길이 뚫려 있었던 것이죠. 논문은 이 지점을 탐색의 병목으로 지목합니다. 휴리스틱이 나빠서가 아니라, 입장 자체가 막혀서 생기는 병목이라는 해석인데요. 저는 이 진단을 읽고 고개를 끄덕였습니다. 많은 탐색 실패담이 평가 함수의 탓으로 돌려지지만, 실제로는 목록 관리의 문제인 경우가 적지 않기 때문입니다.

그렇다면 문턱을 억지로 끌어올릴 수는 없을까요? 다음 장면에서 논문이 꺼내는 카드는 의외로 단순합니다.

동전 하나로 문턱을 밀어 올리는 발상

논문이 제안하는 Probabilistic Focal Search, 줄여서 PFS는 동작을 거의 바꾸지 않습니다. 매번 확장할 노드를 고를 때 동전을 한 번 던지는데, 확률 p로는 기존처럼 FOCAL 안에서 휴리스틱이 고른 노드를 가져오고, 나머지 확률 1 빼기 p로는 OPEN에서 f값이 가장 작은 노드를 가져옵니다. 이게 전부입니다. 새로운 평가 함수도 없고, 복잡한 학습도 없으며, 자료구조를 뜯어고칠 필요도 없습니다.

그런데 이 단순한 섞음이 하한을 움직입니다. f값이 가장 작은 노드를 확장하면 그 노드는 OPEN을 떠나고, 다음으로 작은 f값이 새로운 f_min이 되기 때문입니다. f_min이 한 칸 오르면 FOCAL의 입장 기준인 w 곱하기 f_min도 함께 오릅니다. 그러면 지금까지 문 앞에서 기다리던 노드 몇 개가 안으로 들어옵니다. 그중에 목표 쪽으로 이어지는 길이 있으면 탐색은 단숨에 속도가 붙습니다.

저는 이 숫자보다 그 뒤의 구조가 더 중요하다고 봅니다. 확률을 섞는다는 말은 얼핏 대충 고른다는 뜻으로 들리지만, 여기서는 역할을 나누는 것에 가깝기 때문입니다. p만큼은 목표를 향해 달리고, 1 빼기 p만큼은 하한을 밀어 올리는 일을 맡습니다. 마트 비유로 돌아가면, 계산원 대부분은 손님을 계속 받으면서 한 명만 주기적으로 줄의 맨 앞을 정리해 전체 흐름을 빠르게 만드는 셈이죠. (참고로 이 p는 논문에서 고정된 값으로 실험하는데, 상황에 따라 바꾸는 이야기는 뒤에서 다시 꺼내겠습니다.)

여기서 재미있는 질문이 생깁니다. 왜 하필 f값이 가장 작은 노드일까요? 답은 하한의 정의에 있습니다. f_min을 올리는 가장 직접적인 방법은 그 값을 가진 노드를 치우는 것이기 때문입니다.

이 방법은 무작정 헤매는 것과 다릅니다

확률이라는 말을 들으면 무작위 탐색을 떠올리기 쉽습니다. 그래서 여기서 오해를 하나 바로잡아야 합니다. PFS는 FOCAL 밖에서 아무 노드나 집는 것이 아니라, f값이 가장 작은 노드를 정확히 집습니다. 무작위로 고르면 하한이 오를 수도 있고 그대로일 수도 있지만, 최소 f 노드를 고르면 하한은 정의상 그대로이거나 오릅니다. 즉, 운에 맡기는 선택이 아니라 하한을 겨냥한 선택이라는 것이죠.

또 하나 헷갈리는 지점은 탐험과 활용의 구분입니다. 강화학습에서 말하는 탐험은 종종 모르는 곳을 찔러보는 뜻인데, 여기서 최소 f 노드를 확장하는 일은 모험이 아니라 정리입니다. OPEN에서 가장 작은 숫자를 처리하는 것은 교과서에 나오는 A스타의 기본 동작이거든요. PFS는 그 기본 동작을 일정 비율로 끼워 넣은 셈이라서, 전체 보증도 그대로 유지됩니다. w배 이내의 해를 내준다는 약속이 깨지지 않는다는 점은 실제 시스템을 만드는 사람에게는 상당히 반가운 소식입니다.

저는 여기서 조금 의심했습니다. 이렇게 쉬운 섞음이 정말 큰 차이를 만들까 싶었기 때문입니다. 그런데 논문이 보여주는 로그를 따라가면 생각이 바뀝니다. 하한이 평평한 구간, 즉 plateau가 길게 이어지는 문제에서는 f_min이 몇만 확장 동안 한 칸도 안 움직이는데요. 그 구간에서 최소 f 노드를 가끔씩 건드리는 것만으로도 정체가 풀립니다. 마치 꽉 막힌 도로에서 견인차 한 대가 길 어깨로 차 몇 대를 옮기자 전체 차선이 다시 흐르기 시작하는 장면과 비슷합니다.

그렇다면 이 효과는 모든 문제에서 똑같이 나타날까요? 이제 숫자를 들여다볼 차례입니다.

같은 처방이 어떤 미로에서는 통하고 어떤 미로에서는 덜 통할까

논문은 N-Puzzle과 TSP에서 눈에 띄는 변화를 보고합니다. 하한이 오랫동안 멈추는 구간이 생기는 문제에서는 노드 확장 횟수가 90퍼센트 이상 줄기도 했는데요. 10만 개를 펼치던 탐색이 1만 개 이하로 줄어든다는 뜻이라서, 체감상으로는 완전히 다른 알고리즘처럼 느껴집니다. 퍼즐 조각이 뒤엉킨 N-Puzzle에서는 f값이 같은 국면이 넓게 깔리고, 외판원 문제인 TSP에서는 아직 가보지 않은 도시들의 하한이 한동안 같은 숫자에 머뭅니다. 그런 지형에서는 FOCAL이 갇히기 쉽고, 그래서 문턱을 밀어 올리는 개입이 크게 먹힙니다.

반면 팬케이크 정렬 문제에서는 차이가 작았습니다. 팬케이크 정렬은 뒤집기 동작으로 팬케이크 탑을 정리하는 문제인데, 결정적 탐색만으로도 하한이 비교적 잘 올라가는 편입니다. 이미 문이 잘 열리고 있는데 문을 더 밀어봐야 크게 달라지지 않는 것과 같죠. 저는 이 대조를 논문의 가장 정직한 대목으로 읽었습니다. 만능 처방이라고 우기지 않고, FOCAL 입장이 병목일 때 가장 유용하다는 조건을 분명히 밝혔기 때문입니다.

이 차이는 현장에서 바로 체감되는 차이입니다. 탐색 알고리즘을 고를 때 우리는 숫자만 보고 줄을 세우기 쉬운데, 그 숫자가 어떤 지형에서 나왔는지를 함께 봐야 한다는 뜻이니까요. 저희가 새로운 AI 아키텍처를 볼 때도 benchmark 숫자만 보지는 않습니다. 실제로 무엇이 바뀌었고, 그 변화가 시스템에서 어떤 비용 구조를 만드는지를 함께 봅니다. PFS도 마찬가지입니다. 확률 p가 마법의 숫자가 아니라, 정체 구간이 긴 문제에서 문을 여는 용도로 먹힌다는 이해가 먼저입니다.

여기서는 조금 조심해서 읽을 필요가 있습니다. 90퍼센트라는 감소폭은 특정 문제와 특정 제한 w에서 나온 결과라서, 모든 설정에 그대로 붙일 수는 없습니다. 제한이 빡빡하면 FOCAL 자체가 작아져서 섞음의 여지가 줄고, 반대로 제한이 넉넉하면 원래도 쉽게 풀려서 차이가 가려질 수 있습니다. 논문이 여러 도메인과 제한을 함께 보여준 이유도 그 때문으로 보입니다.

그렇다면 한 번 찾은 해를 계속 다듬는 anytime 탐색에서는 이 섞음이 어떻게 작동할까요?

시간을 나눠 쓰면 답이 먼저 보이고 나서 좋아집니다

Anytime 탐색은 시간이 넉넉하지 않은 현장에서 자주 씁니다. 일단 제한을 만족하는 해를 빨리 하나 내놓고, 시간이 남으면 그 해를 계속 고치는 방식이죠. 배달 경로를 짜는 장면을 떠올려보시면 됩니다. 출발 시각까지는 일단 달릴 수 있는 경로를 주고, 트럭이 움직이는 동안 더 짧은 경로가 나오면 갈아태우는 식입니다. 이때 처음 해가 늦어지면 뒤쪽의 개선 기회도 함께 사라집니다.

논문은 PFS를 anytime으로 넓힌 APFS가 GCTSP라는 일반화된 외판원 변형 문제에서 비교한 anytime 방법들 가운데 가장 좋은 흐름을 보였다고 전합니다. GCTSP는 도시를 하나씩 찍는 대신 군집별로 대표를 고르면서 돌아야 해서, 하한이 들쭉날쭉하기 쉬운 문제입니다. 이런 문제에서는 초반에 FOCAL이 갇히면 첫 해 자체가 늦어지는데, 확률적 섞음이 그 문을 일찍 열어줍니다. 첫 해가 일찍 나오면 남은 시간은 고스란히 개선에 쓸 수 있으니, 최종 해의 질도 함께 올라갑니다.

저는 이 대목을 읽으면서 앞선 마트 비유가 다시 떠올랐습니다. 계산대를 빨리 여는 것과 손님을 빨리 받는 것은 다른 일인데, anytime에서는 두 가지가 맞물립니다. 문을 일찍 열수록 첫 손님이 일찍 나가고, 그 뒤로는 여유 인력을 개선에 붙일 수 있기 때문입니다. APFS의 결과는 그 맞물림이 실제로 돌아간다는 이야기로 읽힙니다.

물론 여기서도 조건을 봐야 합니다. Anytime 비교는 시간 예산과 초기 제한, 그리고 개선 단계의 설계에 따라 결과가 달라질 수 있습니다. 논문이 말하는 우위는 같은 평가 틀 안에서의 우위라서, 예산을 아주 짧게 잡거나 아주 길게 잡으면 그림이 달라질 수 있죠. 그럼에도 첫 해를 앞당기는 장치가 anytime 전체를 끌어올린다는 방향은 분명해 보입니다.

그렇다면 같은 장치를 전혀 다른 엔진에 달아도 작동할까요? 논문은 그 질문까지 따라갑니다.

다른 엔진에 같은 장치를 달면 어떻게 될까

논문은 Dynamic Potential Search라는 또 다른 탐색에 같은 스케줄러를 붙여 Probabilistic Dynamic Potential Search, 약자로 PDPS를 만들었다고 설명합니다. Dynamic Potential Search는 FOCAL 대신 potential이라는 기준으로 후보를 고르는 방법인데요. 쉽게 말하면 휴리스틱의 눈높이를 상황에 따라 바꾸는 탐색입니다. PFS의 섞음은 FOCAL 전용 장치가 아니라, 하한을 밀어 올리는 일반적인 처치라는 것이 논문의 주장입니다.

실험에서는 도메인과 제한에 따라 효과가 갈렸다고 합니다. 어떤 설정에서는 통하고, 어떤 설정에서는 덜 통했다는 것이죠. 저는 이 결과가 오히려 설득력 있다고 봅니다. 어떤 엔진이든 무조건 빨라진다고 했다면 의심했을 텐데, 조건에 따라 갈린다고 말하니까 장치의 역할이 더 또렷해지기 때문입니다. Potential을 쓰는 탐색에서도 하한 정체가 병목일 때 섞음이 먹히고, 그렇지 않을 때는 조용해지는 패턴입니다.

여기서 잠깐 구조를 정리하면, PFS와 PDPS는 서로 다른 평가 함수를 쓰는 사촌처럼 보입니다. 한쪽은 FOCAL의 입장권을 기준으로 삼고, 다른 쪽은 potential의 높낮이를 기준으로 삼습니다. 그런데 두 방법 모두 하한이 멈추면 선택지가 굳는다는 같은 약점을 안고 있습니다. 확률적으로 최소 f 노드를 건드리는 일은 그 굳은 곳을 푸는 공통 처방인 셈이죠. 처방이 통하는 조건까지 닮았다는 점은, 이 문제가 특정 알고리즘이 아니라 탐색 구조 전반에 깔린 문제라는 방증으로 읽힙니다.

그렇다면 이 처방을 쓸 때 p는 어떻게 골라야 할까요? 논문은 고정된 p로 효과를 보여주는데, 실제 시스템 관점에서 보면 다음 질문이 바로 생깁니다. 정체가 심할 때는 섞음을 늘리고, 잘 풀릴 때는 줄이는 식의 조절이 가능하지 않을까 하는 것이죠. 그 이야기는 뒤에서 다시 이어가겠습니다.

창고 로봇을 떠올리면 계산이 달리 보입니다

연구실 숫자를 현장 숫자로 바꾸면 계산이 조금 달라집니다. 노드 확장 횟수가 90퍼센트 줄었다는 말은 연산량이 줄었다는 뜻이지만, wall-clock 시간과 비용은 다른 문제이기 때문입니다. 휴리스틱 계산이 무겁거나, 노드 하나를 펼치는 데 메모리 접근이 많이 든다면 확장 횟수의 감소가 시간 감소로 곧장 이어지지 않을 수 있습니다. 반대로 휴리스틱이 가볍고 OPEN 관리가 병목이라면 효과가 더 크게 체감될 수도 있죠. 저는 그래서 확장 횟수 그래프를 볼 때마다 그 옆에 시간 그래프가 있으면 좋겠다고 생각합니다.

실제 시스템 관점에서 보면 다음 질문이 바로 생깁니다. 이 섞음을 넣으면 메모리와 동시성은 어떻게 될까요. 최소 f 노드를 건드리면 FOCAL이 커지는데, FOCAL이 커지면 그 안에서 고를 후보를 평가하는 비용도 함께 늘어납니다. 단일 스레드에서는 대개 감당할 수준이지만, 여러 탐색 스레드가 OPEN을 공유하면 동기화 비용이 생길 수 있습니다. 또한 휴리스틱이 배치 추론을 쓰는 신경망이라면, FOCAL이 커졌을 때 배치를 어떻게 채울지도 설계 문제로 돌아옵니다. 좋은 건 알겠는데, 이걸 실제로 어떻게 서빙할까요. 이 질문에 답하려면 도메인별 프로파일링이 필요합니다.

저희 팀에서 경로 계획을 다룰 때도 비슷한 경험을 했습니다. 지도 크기가 커지면 최적 경로 증명에 드는 비용이 폭증해서, 제한을 두고 빨리 타협하는 쪽으로 기울게 되는데요. 그때 가장 아까운 시간이 바로 하한이 멈춘 채 휴리스틱만 바쁘게 움직이는 구간이었습니다. PFS의 관점을 빌리면, 그 구간에서는 휴리스틱을 더 좋게 만드는 대신 하한을 밀어 올리는 쪽에 예산을 써야 합니다. 같은 예산을 어디에 쓸지 고르는 일이 탐색 튜닝의 한가운데에 있다는 점이 현장에서는 더 크게 와닿습니다.

물론 모든 현장에 이 처방이 맞는 것은 아닙니다. 팬케이크 정렬처럼 원래 하한이 잘 오르는 문제에서는 섞음을 넣어도 체감이 작을 수 있습니다. 그래서 도입 순서는 이렇게 잡는 편이 낫습니다. 먼저 로그에서 f_min의 궤적을 그리고, 평평한 구간이 긴지 확인한 뒤, 그 구간이 전체 시간의 어느 정도를 차지하는지 재는 것이죠. 정체가 길고 FOCAL 크기가 함께 굳어 있다면 PFS는 시도해볼 만한 선택지입니다.

그래서 저는 다음 실험을 기다리고 있습니다

앞에서 미뤄뒀던 질문으로 돌아올 차례입니다. p를 고정이 아니라 상황에 따라 바꾸면 어떻게 될까요. 저는 이 지점이 남은 이야기 가운데 가장 궁금합니다. 하한이 멈춰 있을 때는 최소 f 확률을 높이고, FOCAL이 잘 돌 때는 휴리스틱 확률을 높이는 식의 적응형 스케줄이 자연스러워 보이기 때문입니다. 다만 적응형으로 가면 또 다른 질문이 따라붙습니다. 정체를 어떻게 감지할 것인지, 감지에 든 비용이 이득보다 크지 않은지, 그리고 w가 바뀌면 스케줄도 함께 바꿔야 하는지 같은 것들이죠.

제가 앞으로 보고 싶은 것은 그다음 장면입니다. 서로 다른 w에서의 p 민감도 곡선, 도메인별 plateau 길이 분포, 그리고 anytime 예산에 따른 초기해 도달 시각 분포 같은 것들이죠. 이런 숫자가 쌓이면 PFS는 요령에서 원칙으로 넘어갈 수 있습니다. 언제 섞고 언제 달리는지에 대한 판단이 감이 아니라 로그에서 나오게 되는 셈입니다.

이 논문이 남기는 더 넓은 질문도 있습니다. 탐색 평가에서 우리는 휴리스틱의 똑똑함ばかり 주목해왔는데, 목록이 열리는 속도를 함께 봐야 하지 않을까요. FOCAL 입장이라는 관문을 보면 탐색은 두 개의 속도로 움직입니다. 하나는 좋은 노드를 고르는 속도이고, 다른 하나는 고를 수 있는 집합 자체를 넓히는 속도입니다. PFS는 두 번째 속도를 올리는 장치로 읽힙니다.

다 읽고 나면 처음의 마트 풍경이 조금 다르게 보입니다. 줄이 안 줄어든다고 계산원을 탓하기 전에, 막힌 줄을 풀어줄 정리 담당이 있는지 먼저 묻게 되는데요. 탐색에서도 마찬가지입니다. 휴리스틱이 게으른 걸까 묻기 전에, 하한이 멈춰 있지는 않은지, FOCAL의 문은 열려 있는지 먼저 확인하게 됩니다. 그렇다면 탐색에서 사람의 직관은 어디에 남을까요. 저는 좋은 휴리스틱을 만드는 손맛보다, 언제 문을 열지 판단하는 운영 감각에 더 남지 않을까 싶습니다. 그 감각을 수치로 옮기는 작업이 다음 연구의 몫으로 보입니다.

(End of file)