💬 NLP

TSLM: Tree-Structured Language Modeling for Divergent Thinking

이 논문은 특수 토큰을 사용하여 분기되는 탐색 경로를 단일 생성 과정으로 인코딩하고, 완전한 탐색 트리를 학습함으로써 외부 탐색 방식의 중복된 계산 없이 효율적이고 체계적인 발산적 사고를 가능하게 하는 새로운 접근 방식인 트리 구조 언어 모델링(Tree-Structured Language Modeling, TSLM)을 소개한다.

원저자: Doyoung Kim, Jaehyeok Doo, Minjoon Seo

게시일 2026-02-02

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Doyoung Kim, Jaehyeok Doo, Minjoon Seo

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

매우 까다로운 미로를 풀려고 노력하고 있다고 상상해 보세요.

과거의 방식 (순차적 사고)
현재 대부분의 AI 모델은 눈을 감고 미로를 헤매는 사람과 같습니다. 한 번에 한 걸음씩 나아갑니다. 하나의 경로를 선택해 앞으로 나아가다가 벽에 부딪히면, 다시 처음부터 시작하여 다른 경로를 시도해야 합니다. 만약 초기에 실수를 하면, 그것이 막다른 길이라는 것을 깨닫기 전까지 아주 오랫동안 잘못된 길을 계속 걸어갈 수도 있습니다. 이들은 한 번에 하나의 경로만을 생각할 수 있습니다.

새로운 방식 (TSLM: 트리 구조 언어 모델링)
이 논문은 TSLM이라는 새로운 방법을 소개합니다. 대신 혼자 미로를 걷는 것이 아니라, 당신이 마법의 탐험가가 되어 현재 서 있는 곳에서 뻗어 나오는 모든 가능한 경로를 즉시 볼 수 있다고 상상해 보세요.

TSLM은 텍스트 속의 특별한 "마법 표식"(토큰)을 사용하여 AI가 이를 수행하도록 가르칩니다. 단순히 문장 하나를 쓰는 대신, AI는 한 번에 전체 지도를 작성합니다:

경로 A를 작성하고, "이 경로는 좋아 보이니 계속 가세요!"라는 의미의 초록색 깃발([SEP])을 답니다.
경로 B를 작성하고, "이 경로는 막다른 길로 이어지니 여기서 멈추세요."라는 의미의 빨간색 깃flag([FAIL])를 답니다.
경로 C를 작성하고, "보물을 찾았습니다!"라는 의미의 황금 별([GOAL])을 답니다.

작동 원리

학습 (Training): AI는 이러한 완성된 지도(막다른 길과 승리하는 경로를 모두 포함한)를 보여주며 학습됩니다. 이를 통해 AI는 나무 한 그루가 아닌 숲 전체를 보는 법을 배웁니다. 때로는 어떤 경로를 시도했다가 그것이 막다른 길임을 깨닫는 과정이 필요하며, 그것이 괜찮다는 사실도 배웁니다.
사고 (Thinking): 나중에 문제를 해결할 때, AI는 단순히 하나의 답을 추측하지 않습니다. 한 번에 전체 "트리(tree)" 형태의 가능성들을 생성합니다. 가지들을 살펴보고, 어떤 것이 막다른 길인지 확인하며, 유망해 보이는 경로를 따라갑니다.

이것이 왜 중요한가
논문은 재미있는 비유를 사용하여 TSLM을 다른 방법들과 비교합니다:

"24 게임" (수학 퍼즐): 네 개의 숫자를 사용하여 수학적으로 24를 만드는 게임을 상상해 보세요.
- 기존 AI: 하나의 조합을 시도하고, 실패하면, 또 다른 조합을 시도합니다. 쉽게 막혀버립니다.
- TSLM: 모든 수학적 조합을 한꺼번에 펼쳐 놓습니다. 테스트에서 기존 방식이 17%의 성공률을 보인 반면, TSLM은 **100%**의 확률로 해답을 찾아냈습니다.
"그리드월드" (내비게이션 퍼즐): 로봇이 벽과 구덩이가 있는 격자 위를 항해하는 상황입니다.
- 기존 AI: 격자가 커질 때(10x10에서 20x20으로), 기존 AI는 완전히 길을 잃고 혼란에 빠집니다. 마치 작은 방은 잘 알지만 거대한 창고에서는 길을 잃는 사람과 같습니다.
- TSLM: 격자가 두 배로 커졌음에도 불구하고, TSLM 로봇은 여전히 **91.5%**의 확률로 길을 찾아냈습니다. 이 로봇은 특정 지도를 외운 것이 아니라, 항해하는 '전략'을 배운 것입니다.
"환각(Hallucination)" 문제: 때때로 문제에 해결책이 없을 수도 있습니다 (예: 숫자 1, 1, 2, 3으로 24를 만들려는 경우).
- 기존 AI: 답을 내놓으려는 욕심 때문에, 작동하지 않는 가짜 수학적 기교를 만들어낼 수 있습니다.
- TSLM: 전체 가능성의 트리를 보기 때문에, 지도를 살펴보고 모든 경로가 막다른 길임을 확인한 뒤, 자신 있게 "이것은 불가능합니다"라고 말할 수 있습니다. 이 방식은 불가능한 문제를 **97%**의 정확도로 식별해 냈습니다.

핵심 요점
이 논문은 AI를 여러 번 병렬로 실행하여 더 "깊게 생각"하게 만드는 것(느리고 비용이 많이 드는 방식)이 아니라, 학습 과정에서 AI에게 트리 구조로 생각하도록 가르칠 수 있다고 주장합니다. 잘못된 길을 포함하여 전체 지도를 보는 법을 배움으로써, AI는 훨씬 더 뛰어나고, 빠르며, 신뢰할 수 있는 문제 해결사가 됩니다. 이것은 단순히 직선으로 걷는 법만 아는 사람과, 지도를 보고 모든 도로를 파악하여 최선의 길을 선택할 줄 아는 사람의 차이와 같습니다.

기술 요약: TSLM: 발산적 사고를 위한 트리 구조 언어 모델링

문제 정의

현재의 대규모 언어 모델(LLM)은 근본적으로 순차적 생성기로 작동하며, 선형적 이력에 기반하여 다음 토큰의 확률을 모델링한다( $p(y|x) = \prod p(y_t | x, y_{<t})$ ). 최근의 추론 모델들(예: o1, DeepSeek-R1)은 확장된 추론 흔적(reasoning traces)을 통해 인상적인 능력을 보여주었으나, 여전히 이러한 순차적 본질에 의해 제약을 받는다. 이러한 아키텍처는 단일 경로에 대한 "선형적 전념(linear commitment)"을 강요하며, 이로 인해 여러 대안을 체계적으로 탐색하거나, 초기의 실수를 복구하거나, 무관한 탐색 경로를 분리하는 것을 어렵게 만든다.

이 문제에 대한 기존의 해결책들은 두 가지 범주로 나뉘며, 둘 다 상당한 한계를 지닌다:

순차적 모델링(Sequential Modeling): 모델은 단일 결정론적 경로를 생성하며, 이는 대안의 탐색을 제한한다.
외부 탐색(예: Tree-of-Thoughts): 이러한 방법들은 여러 독립적인 궤적을 샘플링하기 위해 외부 오케스트레이션을 사용한다. 그러나 이 접근 방식은 파편화된 분포, 공유 접두사(prefix)의 중복 계산, 그리고 브랜치 간의 조율 부족 문제를 겪는다. 또한, 외부 탐색 방법은 문제의 복잡성이 증가할 때(예: 더 큰 Gridworld 환경에서 성능이 크게 하락함) 견고하게 확장되는 데 실패하는 경우가 많다.

식별된 핵심 과제는 모델이 단일 생성 과정 내에서 일관되게 다양한 탐색 브랜치를 구축할 수 없다는 점이며, 이는 조기 전념 혹은 비효율적이고 파편화된 병렬 샘플링으로 이어진다.

방법론: 트리 구조 언어 모델링 (TSLM)

저자들은 모델이 지도 학습을 통해 트리 구조의 추론을 네이티브하게 생성하고 관리할 수 있게 하는 프레임워크인 **트리 구조 언어 모델링(TSLM)**을 소개한다.

핵심 메커니즘

TSLM은 표준 언어 모델링 목적 함수를 수정하여, 독립적인 궤적이 아닌 완전한 탐색 트리를 단일 포워드 패스(또는 일관된 일련의 패스) 내에서 생성하도록 한다.

토큰 기반 직렬화(Token-Based Serialization): 모델은 특수 토큰을 사용하여 표준 트랜스포머 아키텍처와 호환되는 선형 시퀀스로 트리 구조를 인코딩한다:
- [SEP]: 추가로 확장 가능한 유효한 행동을 나타낸다.
- [FAIL]: 유효하지 않은 행동(막다른 길)을 나타낸다.
- [GO_AL]: 원하는 목표 상태를 표시한다.
- [BOS]/[EOS]: 자식 확장을 위한 시퀀스 경계를 표시한다.
조건부 의존성(Conditional Dependencies): 모든 토큰이 전체 접두사에 의존하는 표준 순차 모델과 달리, TSLM은 **선택적 문맥 디커플링(selective context decoupling)**을 채택한다. 노드의 생성은 전체 접두사가 아닌, 해당 노드의 조상 경로와 동일한 노드 내에서 이전에 생성된 형제 노드들에만 조건화된다. 이를 통해 모델은 중복 재계산 없이 체계적으로 브랜칭 구조를 학습할 수 있다.
학습 목적 함수(Training Objective): 모델은 성공적인 경로와 실패한 시도를 모두 포함하는 완전한 탐색 트리에 대해 학습된다. 손실 함수는 직렬화된 시퀀스에 적용되는 표준 교차 엔트로피 손실이며, 이를 통해 모델은 다음을 학습한다:
1. 각 결정 지점에서 여러 행동을 생성한다.
2. 적절한 유효성 마커([SEP], [FAIL], [GOAL])를 할당한다.
3. 탐색을 체계적으로 구조화한다.

데이터 구축

구조화된 작업: 사전 정의된 탐색 트리가 있는 작업(예: 보드 게임)의 경우, 모델은 트리 구조를 직접 재현하도록 학습된다.
개방형 작업: 명시적인 트리가 없는 작업(예: GSM8K, ProntoQA)의 경우, 저자들은 부트스트래핑 방법을 사용한다. 감독 모델(예: Tree-of-Thoughts 샘플링)을 사용하여 의사(pseudo) 탐색 트리를 생성하며, 이때 알려진 골드 궤적을 고순위 브랜치로 포함하고 나머지 브랜치는 보상 함수를 사용하여 정렬한다.

추론 절차

추론 단계에서 TSLM은 일관된 트리 구조를 생성한다. 그 후 구조적 토큰을 파싱하여 유효한 브랜치([SEP])를 식별하고, 이 브랜치들을 병렬 확장을 위한 독립적인 시퀀스로 포크(fork)한다. 이를 통해 전체 탐색 토폴로지를 내부적으로 유지하면서도 체계적인 탐색(예: 너비 우선 탐색)이 가능하며, 외부 탐색 방법에서 발생하는 중복 샘플링을 피할 수 있다.

주요 기여

새로운 프레임워크: 일관된 탐색 흔적에 대한 지도 학습을 통해 순차적 LM이 트리 구조 추론을 학습할 수 있게 하는 토큰 기반 직렬화 프레임워크인 TSLM을 도입하였다.
성능 향상: 다양한 작업에서 일관된 성능 향상을 입증하였다:
- Game of 24: 100% 정확도 (순차적 베이스라인의 17% 대비).
- Gridworld (외삽): 미학습 20×20 그리드에서 91.5% 정확도 (Tree-of-Thoughts의 42.7% 대비), 학습 복잡도를 넘어선 견고한 외삽 능력을 보여주었다.
- 개방형 추론: ProntoQA 및 GSM8K에서 성능을 향상시켰다.
창발적 능력: 완전한 탐색 패턴을 학습함으로써 발생하는 새로운 능력을 발견하였다:
- 해결 불가능한 문제 탐지: TSLM은 환각(hallucination) 없이 해결 불가능한 인스턴스를 식별하고 종료할 수 있다 (예: Game of 24의 해결 불가능한 사례 100개 중 97개). 이는 순차적 베이스라인에는 없는 능력이다.
- 견고한 외삽: 재학습 없이도 더 큰 환경과 더 높은 브랜칭 팩터로 일반화할 수 있는 능력.
새로운 스케일링 패러다임: "k개의 독립적인 궤적을 병렬 샘플링하는 것"에서 "단일한 일관된 트리 내에서 k개의 브랜치를 탐색하는 것"으로의 전환. 이 접근 방식은 더 우수한 추론 효율성과 높은 수렴 정확도를 제공한다.

실험 결과

저자들은 TSLM을 Sequence Cloning (SC), Procedure Cloning (PC), GRPO (강화 학습), 그리고 Tree-of-Thoughts (ToT)와 같은 여러 베이스라인과 비교 평가하였다.

구조적 계획 (Game of 24): TSLM은 100% pass@1 정확도를 달성하여 SC (17%), PC (47%), GR포 GRPO (15%)를 크게 앞질렀다. ToT@100 (pass@100 메트릭)과 비교해도 TSLM (pass@1)이 더 우수한 결과를 보였다.
Gridworld 스케일링: 인도메인(10×10) 테스트에서 TSLM은 100%에 도달했다. 결정적으로, 아웃도메인(20×20) 테스트에서 TSLM은 **91.5%**의 정확도를 유지한 반면, ToT는 **42.7%**로 급락했다. 이는 TSLM이 외부 탐색 알고리즘보다 더 잘 일반화되는 탐색 절차를 내재화했음을 강조한다.
개방형 추론: GSM8K에서 TSLM (61.6% pass@1)은 ToT (62.3% pass@100) 및 PC (55.9%)와 대등하거나 이를 약간 상회하면서도 훨씬 더 효율적이었다.
효율성: TSLM은 중복 샘플링과 계산 공유 부족으로 인해 "시간 폭발"을 겪는 ToT에 비해 현저히 빠른 추론 시간을 보여주었다. TSLM은 단일 생성 트리 내에서 공통 접두사에 대한 계산을 공유한다.

의의 및 주장

본 논문은 강력한 추론 능력을 갖추기 위해 강화 학습(RL)이나 복잡한 추론 시점 탐색 오케스트레이션이 반드시 필요하다는 통념에 도전한다. 대신, 저자들은 트리 형식의 추론 흔적을 적절히 구조화된 방식으로 지도 학습하는 것이 향상된 추론과 계획을 위한 더 직접적이고 효율적인 경로를 제공한다고 주장한다.

저자들이 주장하는 주요 시사점은 다음과 같다:

탐색의 내재화: 완전한 트리에 대해 학습함으로써, 모델은 체계적인 탐색 전략을 내재화하여 외부 탐색 방법보다 더 나은 일반화 성능을 보인다.
효율성: TSLM은 단일한 일관된 구조 내에서 더 많은 브랜치를 탐색함으로써 새로운 테스트 타임 스케일링 패러다임을 제공하며, 독립적인 병렬 샘플링의 계산적 중복을 피한다.
견고성: 이 접근 방식은 모델이 해결 불가능한 문제를 처리할 수 있게 하며, 외부 탐색 방법에서 나타나는 파괴적인 성능 저하 없이 증가된 복잡도로 확장할 수 있게 한다.

저자들은 TSLM을 단순한 성능 개선을 넘어, 언어 모델이 추론하는 방식을 학습시키는 근본적인 변화로 위치시키며, "병목"은 추론 계산량이 아니라 학습 과정에서의 체계적인 탐색 공간 구축에 있음을 시사한다.