LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories | AI Paper Digest

TL;DR Highlight

LLM의 추론 트레이스에 부모 포인터(parent pointer)만 추가해도 탐색 성능과 효율이 크게 올라간다.

Who Should Read

LLM을 이용한 계획(planning)이나 추론 에이전트를 만드는 개발자. 특히 Chain-of-Thought나 Tree-of-Thoughts 방식으로 복잡한 문제를 풀게 하려는 ML 엔지니어.

Core Mechanics

LLM이 전체 탐색 기록(search trace)을 볼 수 있어도, 트리 구조가 암묵적으로만 표현되면 로컬 상태만 보는 휴리스틱 기반 탐색보다 딱히 낫지 않다.
핵심 아이디어: 각 탐색 스텝에 'sid=0', 'sid=1' 같은 parent pointer(어떤 상태에서 파생됐는지 알려주는 ID)를 붙이면, 같은 데이터로 학습해도 성능이 확 올라간다.
학습 파이프라인은 SFT(예제 트레이스로 모방 학습) → GRPO(정확도+효율 보상으로 강화학습) 2단계로 구성되며, 백본 모델로 Qwen3-0.6B를 사용했다.
명시적 트리 구조 덕분에 모델이 자신의 탐색 트레이스에서 최종 플랜을 추출하는 실패율이 낮아진다. 예컨대 Sokoban SFT 단계에서 추출 실패 비율이 80.78% → 54.17%로 감소.
명시적 구조를 가진 모델은 탐색 중 방문 상태의 다양성(평균 pairwise distance)도 더 높다. Navigation 도메인에서 GRPO-implicit 4.11 vs GRPO-explicit 4.19로, 더 넓은 상태 공간을 탐색.
보상 함수 설계 시 상수 페널티나 단순 geometric decay는 학습 불안정을 유발했고, 유한 geometric sum으로 페널티를 주는 방식이 안정적으로 작동했다.

Evidence

GRPO-explicit은 Blocks World 100.0%, Navigation 100.0%, Sokoban 89.6% 성공률을 달성. GRPO-implicit은 각각 97.3%, 94.9%, 85.9%에 그쳤다.
탐색 효율(expansions 수)도 explicit이 우세: Sokoban에서 63.54 → 52.82로 약 17% 감소, Blocks World에서 8.25 → 7.31로 약 11% 감소.
Sokoban에서 generation constraint(잘못된 액션 차단) 적용 시 explicit 모델이 98.9% 성공률로 BFS(RL) 99.1%에 근접하면서 expansions는 54.70 vs 64.08로 더 효율적.
SFT 단계만 봐도 explicit 표현이 평균 solve rate를 5.0포인트 향상시킨다. Navigation 90.6% → 95.2%, Sokoban 74.8% → 85.6%.

How to Apply

LLM에게 탐색/계획 문제를 풀게 할 때, 각 스텝에 'sid=N' 같은 상태 ID를 붙여서 어떤 상태에서 파생됐는지 명시하면 된다. 예: 'EXPAND sid=2 ACT R -> sid=5 ...' 형식으로 SFT 데이터를 만들면 같은 양의 데이터로도 더 잘 학습된다.
ReAct나 Tree-of-Thoughts 스타일 에이전트 트레이스를 학습 데이터로 쓸 때, 'let me try another approach' 같은 자연어 백트래킹 표현 대신 parent pointer로 명시적 트리 구조를 노출하도록 데이터 포맷을 바꿔보면 된다.
강화학습 보상 설계 시, 단순히 정답 여부만 주면 효율이 개선되지 않는다. 논문처럼 R(τ) = correctness × (1 - λ × Σγ^t) 형태로 탐색 스텝 수에 페널티를 주되, 모든 정답 트레이스는 여전히 양수 보상을 받도록 λ < 1-γ 조건을 지켜라.

Code Example

snippet

# LinTree 스타일 search trace 포맷 예시
# 기존 implicit 방식
implicit_trace = """
EXPAND S{ 0:B<A<C ; 1:D }
EXPAND ACT C:A->D -> S{ 0:B<A ; 1:D<C }
GOAL_REACHED
"""

# LinTree explicit 방식 (parent pointer 추가)
explicit_trace = """
EXPAND sid=0 S{ 0:B<A<C ; 1:D }
EXPAND sid=0 ACT C:A->D -> sid=1 S{ 0:B<A ; 1:D<C }
GOAL_REACHED
"""

# Navigation 예시 - 백트래킹 시 어떤 노드로 돌아가는지 명확히 표현
nav_explicit = """
EXPAND sid=0 A=(7,6)
EXPAND sid=0 ACT U -> sid=1 A=(6,6)
EXPAND sid=1 ACT U -> sid=2 A=(5,6)
BLOCKED ACT L -> (5,5) WALL
EXPAND sid=1 ACT L -> sid=3 A=(6,5)  # sid=2가 아닌 sid=1로 백트래킹
EXPAND sid=3 ACT L -> sid=4 A=(6,4)
"""

# GRPO 보상 함수 (Python 구현)
def compute_reward(trace, lam=0.005, gamma=0.99):
    is_valid = validate_trace(trace)  # 트레이스 유효성 검사
    is_correct = check_goal_reached(trace)  # 목표 도달 여부
    
    if not (is_valid and is_correct):
        return 0.0
    
    n_exp = count_expansions(trace)
    # 유한 geometric sum 페널티: 모든 정답 트레이스는 양수 보상 보장
    penalty = sum(gamma**t for t in range(n_exp))
    reward = 1.0 - lam * penalty
    return max(reward, 0.0)  # lam < 1-gamma 조건 지키면 항상 양수

Terminology

SFT모범 답안(데모 트레이스)을 보여주고 따라하게 하는 지도 학습. 학교에서 예제 풀이 보고 따라 푸는 것과 같다.

GRPO그룹 상대 정책 최적화(Group Relative Policy Optimization). 여러 번 시도한 결과를 서로 비교해서 좋은 행동을 강화하는 RL 기법. DeepSeekMath에서 제안됐다.

best-first search현재까지 가장 좋아 보이는 후보를 우선 탐색하는 알고리즘. 휴리스틱(어림 추정값)을 기준으로 탐색 순서를 정한다.

parent pointer트리에서 각 노드가 자신의 부모 노드를 가리키는 포인터. 이 논문에서는 'sid=2에서 파생됐다'처럼 탐색 상태의 계보를 명시하는 ID.

Chain-of-ThoughtLLM이 최종 답 전에 중간 추론 단계를 쭉 써내려가도록 유도하는 프롬프트 기법. 복잡한 문제를 단계별로 풀게 만든다.

Tree-of-ThoughtsLLM이 여러 추론 경로를 트리 형태로 탐색하도록 외부 컨트롤러가 관리하는 기법. 가지를 뻗고 가지치기하면서 최적 경로를 찾는다.

heuristic최적 해를 보장하진 않지만 탐색 방향을 잡아주는 어림 추정 함수. 예: 목표까지의 맨해튼 거리.

Sokoban플레이어가 상자를 밀어 목표 지점에 놓는 퍼즐 게임. 되돌릴 수 없는 실수가 생겨 복잡한 탐색이 필요한 벤치마크로 자주 쓰인다.

Related Papers

Related Resources

Boxoban Levels (DeepMind Sokoban dataset)

Original Abstract (Expand)

Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions. From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution, abandons it when it fails, and backtracks to try alternatives. Compared with traditional heuristic-guided search, such a policy has a potential advantage: it conditions on the whole search trace rather than only on the current local state. We first test whether LLMs utilize this advantage by comparing trace-conditioned reasoning policies against best-first search equipped with an LLM heuristic that only observes the current local state. Across three controlled reasoning environments, Blocks World, grid Navigation, and Sokoban, we find that raw access to search history alone is not enough to reliably outperform heuristic search. We then study one possible reason: in LLM reasoning traces, the underlying search tree is only implicitly represented, and when the model backtracks or switches branches, the trace does not explicitly identify which earlier search state is being revisited. We show that adding simple parent pointers to explicitly represent the linearized tree (LinTree) structure improves both task performance and search efficiency relative to implicit reasoning models and LLM-heuristic-guided search. These results suggest that search history becomes most useful when its tree structure is made explicit, motivating more structure-aware representations for LLM reasoning.