A*를 넘어서: 트랜스포머를 활용한 더 나은 계획 수립

• Transformer와 LLM은 대화·이미지 이해·코드 완성에서는 강하지만, 다단계 계획과 고차 추론에서는 안정적인 성능을 내기 어려움
• 이 논문은 계획 과제와 최적 해법을 토큰 시퀀스로 만들고, A*가 문제를 푸는 실행 추적까지 학습 데이터에 넣음
• Searchformer는 A*의 탐색 과정을 먼저 모방한 뒤, 최적 계획을 유지하면서 더 짧은 탐색 시퀀스를 만들도록 미세조정됨
• Sokoban 실험에서 Searchformer 계열 모델은 테스트 과제의 93.7% 를 해결했고, A* 기준 구현보다 평균 26.8% 적은 탐색 단계를 사용함
• 실행 추적은 생성 시퀀스를 10×~100× 늘리는 부담이 있지만, 더 큰 solution-only 모델보다 적은 학습 시퀀스로도 미지 과제에서 최적 계획을 더 자주 생성함

---

Transformer가 잘하는 일과 약한 계획 과제

• Transformer 기반 아키텍처는 여러 작업에서 높은 성능을 보임
  • 사람 수준 대화
  • 고품질 이미지 이해
  • 비디오 생성
  • 멀티모달 생성
  • 코드 완성
• 인터넷 규모 데이터로 학습된 LLM 같은 모델은 실제 사용 사례에서 잘 일반화할 수 있음
• 하지만 계획 및 추론 과제에서는 여전히 한계가 남아 있음
  • LLM은 다단계 계획 과제에서 부족한 모습을 보임
  • 고차 추론 수행에서도 어려움이 나타남

단계적 사고 프롬프트의 한계

• 최근 접근들은 Transformer가 중간 “생각”을 생성한 뒤 답하도록 유도해 성능을 높이려 함
• Chain-of-Thought(CoT) 프롬프팅과 Tree-of-thoughts(ToT) 는 모델이 단계적으로 “생각”하도록 장려함
• 이런 기법은 자주 효과적이지만, self-enforcing 같은 이유로 오히려 성능을 낮출 수도 있음
• 한 데이터셋에서 잘 통하던 방식이 다른 데이터셋에서는 실패할 수 있음
  • 공간 추론과 수학 추론처럼 필요한 추론 유형이 달라지는 경우가 예시임
• Transformer와 LLM이 계획, 다단계 의사결정, 추론을 안정적으로 수행하게 하는 방법은 여전히 활발한 연구 주제임

A* 탐색 동역학을 학습 데이터로 넣는 방식

• 이 접근은 Transformer가 복잡한 계획 과제를 더 강건하게 풀도록 학습시키는 데 초점을 둠
• 모델은 LLM처럼 단어 시퀀스가 주어졌을 때 다음 단어를 예측하도록 학습됨
• 실험은 합성 언어와 합성 어휘를 사용하는 합성 생성 데이터셋에서 수행됨
• 계획 과제와 최적 해법 계획은 토큰이라고 부르는 단어 시퀀스로 표현됨
• A*가 수행한 계산 과정은 실행 추적 토큰 시퀀스로 기록됨
  • 실행 추적은 A*의 탐색 동역학을 담은 시퀀스 데이터셋을 구성함
  • Transformer는 탐색이 보강된 시퀀스를 통해 A*의 탐색 동역학과 최적 계획을 함께 인코딩한 토큰 시퀀스를 생성하도록 학습됨

Searchformer의 학습 절차

• 최종 모델인 Searchformer는 두 단계로 만들어짐
  • 먼저 Transformer가 A*의 탐색 과정을 모방하도록 학습됨
  • 이후 최적 계획을 출력하면서도 더 적은 탐색 단계 안에서 계획을 찾도록 미세조정됨
• 이 과정을 search dynamics bootstrapping이라고 부름
• 목표는 A* 기준 구현보다 더 적은 탐색 단계로 복잡한 계획 과제를 해결하는 Transformer를 얻는 것임

Sokoban 실험과 일반화 성능

• Sokoban 퍼즐에서 Searchformer 계열 모델은 전체 테스트 과제의 93.7% 를 해결함
• 평균 탐색 단계는 A* 기준 구현보다 26.8% 더 적음
• 과제 복잡도, 데이터셋 크기, 모델 크기를 통제한 실험에서 실행 추적 포함의 효과가 확인됨
• 실행 추적을 학습 데이터에 넣으면 생성 시퀀스 길이가 10×~100× 늘어남
• 그럼에도 독립 테스트 과제 세트에서는 성능이 증가함
• search-augmented 모델은 더 큰 solution-only 모델보다 학습 시퀀스가 10배 적어도 미지 과제에서 최적 계획을 더 자주 생성함
  • search-augmented 모델은 과제 설명, 해법, 실행 추적을 포함한 데이터로 학습됨
  • solution-only 모델은 과제 설명과 과제 해법만 포함한 시퀀스로 학습됨
• 이 결과는 A*의 탐색 동역학을 Transformer 학습 과정에 포함하면 계획 과제 성능을 높일 수 있음을 보여줌

[GN⁺]

Hacker News 의견들

• 로봇 모션 플래닝에 트랜스포머를 쓰는 더 흥미로운 연구도 있었음 0
  로봇 팔을 A 지점에서 B 지점으로 옮기면서 충돌을 피하는 문제는 고차원이고 연속적이라 매우 어렵고, 기존 플래닝 방법은 계산량이 크면서도 성능이 좋지 않은 편임
  그래서 로봇 움직임이 “부자연스럽게” 보이고 로봇이 우리가 원하는 여러 작업을 잘 못하는 이유 중 하나가 되는데, 이 접근은 거의 최적인 경로를 더 빠르게 계획해 다른 방법들과 꽤 경쟁력 있어 보임

• 연구 방향으로 가기 전에 게임 그래프/경로 탐색용 A* 최적화인 수정 J 알고리즘*을 시도해 봤는지 궁금함
  궁금한 사람은 Game AI Pro 2에 있음 0

  • 관련해서 https://github.com/anvaka/ngraph.path도 있음
  • 공정하게 보면 논문 끝부분에서 자기들의 경로 탐색기가 아직 최신 기법과 경쟁할 수준은 아니라고 했음
    이 논문은 트랜스포머가 실행 추적을 얼마나 잘 예측하는지, 예를 들면 JIT 컴파일러 같은 경우처럼, 그리고 그게 경로 탐색 같은 곳의 휴리스틱 개선에 도움이 되는지를 테스트함
    다만 트랜스포머는 느려서 조심스럽게 보게 됨
  • 이 책들을 좋아하고 Steve Rabin이 계속 작업하는 것도 반갑지만, 전자책이 120달러라는 건 예상 밖임

• 계획 문제는 이미 그래프 탐색, SAT 해결기, 운영 연구, Prolog 같은 확립된 기법들이 잘 다루고 있음
  보통 핵심은 여러 가능한 대안 사이의 최적화인데, 트랜스포머가 거기에 적합한지는 잘 모르겠음
  LLM 계열 기법의 역할은 자연어 설명을 실행 가능한 프로그램으로 번역하는 쪽에 더 있어 보이지만, Prolog도 애초에 고전 자연어 처리를 위해 설계된 만큼 이미 꽤 가까움

  • 비슷한 목적에서 Prolog와 LLM을 비교해 보면 흥미로울 것 같음

• 기계 번역은 예전에는 탐색을 쓰는 복잡한 문법 디코딩이 필요했지만, 지금은 훨씬 단순하고 사실상 탐색이 필요 없는 디코딩으로 트랜스포머를 씀
  이제 완전한 재귀 구조까지 가볼 수도 있음
  현재 최고 수준의 예측 모델로 신경망 구조 탐색(NAS)의 휴리스틱을 학습하고, transformer나 mamba보다 나은 새 신경망 블록을 찾아보자는 것임

  • “언어학자를 해고할 때마다 음성 인식기의 성능이 올라간다.” — Frederick Jelinek
  • 결국 기술을 개발하는 사람들조차 더 이상 작동 원리를 이해하지 못하는 세계로 들어가게 될 수도 있음
    특이점이 온다…

• Sokoban류 게임에 관심 있으면 https://thinky.gg를 봐도 좋음
  Sokopath라는 재미있는 Sokoban 변형과, A 지점에서 B 지점까지 최단 걸음 수로 가는 것이 목표인 Pathology라는 또 다른 NP-난해 변형이 있음
  커뮤니티에서 여러 해결기를 만들려고 했지만 격자가 5x5를 넘으면 매우 어려워지고, thinky 커뮤니티가 simulated annealing으로 최대 걸음 수가 매우 큰 흥미로운 레벨들도 찾아냈음

• “표준 A* 탐색보다 탐색 단계 26.8% 감소”
  그러니까 Sokoban에서는 최신 수준과 거리가 먼 A*보다 약간 나은 정도임 (https://festival-solver.site/)
  이 논문에서 인상적인 게 뭔지, 왜 Hacker News에 올라왔는지 모르겠음

  • A는 자신이 명시한 특정 제약 아래에서는 가장 최적인 탐색 알고리즘이라 더 잘할 수 없음
    하지만 탐색 대상 도메인에 활용 가능한 다른 제약이 있으면 A보다 나아질 수 있음
    예를 들어 Jump Point Search는 특정 방식으로만 이동할 수 있는 격자 탐색의 성질을 활용함
    기반 도메인의 특수한 성질을 사람이 직접 분석하지 않아도 “자동으로” 효과적으로 활용하는 일반 탐색 알고리즘을 만들 수 있다면 유용하지 않겠나 싶음
  • 트랜스포머로 표준적인 A* 탐색보다 나은 괜찮은 해법에 도달했기 때문임
    A*는 “순진한” 기본 해법에 가깝고, 이들은 알고리즘 설계를 직접 고민하지 않았음
    단순한 인코더-디코더 트랜스포머가 이 정도를 해낼 수 있다는 점이 꽤 인상적임
  • 초록 첫 줄에 바로 나옴
    “Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
    이 논문은 의사결정에 트랜스포머를 쓰는 예시라서 흥미롭고, 지금 당장 A 수준*인지에는 별로 관심이 없음
  • HN에 올라온 건 커뮤니티가 좋아했기 때문임
  • 트랜스포머가 다음 토큰 예측뿐 아니라 온갖 학습 과제에 적용 가능한 완전 범용 접근이라는 트랜스포머의 불합리한 효과성을 뒷받침하는 증거가 하나 더 나온 셈임
    물론 그 가설에는 강한 버전과 약한 버전이 있고 강한 버전은 아마 사실이 아니겠지만, 자연이 일을 배우는 “하나의 참된 방식”에 가까워지고 있는 것처럼 보이는 한 중요한 소식으로 보임

• 트랜스포머가 계획할 수 있다면, 범용 인공지능에는 더 나은 교육만 필요하다는 뜻일 수도 있음

  • 완전 탐색을 근사하는 것은 논리나 인과성이 아님
  • 필요한 조각은 훨씬 많고, 행위성이 큰 부분을 차지함
    온라인 학습도 필요하고 그 밖에도 여러 계층이 더 있어야 함
  • 예측 가능한 미래는 점점 더 많은 데이터를 먹여서 환각을 막아보려는 방향일 가능성이 큼

• 청각형 학습자를 위해 이 논문을 요약 오디오북 형식으로 만든 것이 있음
  https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f

• A*나 Focal search, 여러 정수 선형 계획법 계열 같은 이산 알고리즘에 학습된 휴리스틱을 쓰는 데에는 매우 낙관적임
  CPLEX 같은 현대 이산 최적화 라이브러리 대부분에서 성능 차이는 휴리스틱과 튜닝이 설명함
  잘 이해된 최적 탐색 루틴을 끝단 간 학습 접근으로 대체하는 건 덜 납득되지만, 그건 괜한 걱정일 수도 있음
  다만 저자들이 그 기회를 놓친 것처럼 보임

  • 그냥 트랜스포머와 AI 주변의 거품/과장 효과 같음
    나도 트랜스포머로 틱택토를 풀어보고 VC 돈을 신청해 볼까 싶음
    몇 년 뒤에는 실제 코드가 AI보다 얼마나 더 효율적인지 모두 글을 쓰고 있을지도 모름 ;)
  • 동의함
    허용 가능한 휴리스틱을 학습하면 최악의 경우 성능을 유지할 수 있고, 이것이 늘 이런 알고리즘들의 기준이었음
    평균이나 p99 사례에서는 더 빠르지만 최악의 경우 보장을 제공하지 못하는 해법을 찾는 일은 전혀 드물지 않음

• 딥러닝으로 더 잘 수행하게 된 고전 알고리즘이나 NP-완전 문제 목록을 누가 정리하고 있는지 궁금함

  • 편의를 위해 “AI”가 최악의 경우에서 최신 기법보다 더 잘하는 NP-완전 문제 목록을 적어보면:
  • 이해하기로는 아직 매우 활발한 연구 단계이고, 프로덕션 환경에 배포된 명확한 승리는 아직 없음