대규모 언어 모델 (LLMs)은 부분적인 해결책을 탐색하고 수정하는 중간 추적 (intermediate traces)을 생성함으로써 추론 문제를 해결하곤 합니다. 탐색 (search) 관점에서 볼 때, 이러한 추적은 모델이 부분적인 해결책을 확장하고, 실패하면 이를 포기하며, 대안을 시도하기 위해 백트래킹 (backtrack)하는 선형화된 탐색 트리 (linearized search trees)로 간주될 수 있습니다. 전통적인 휴리스틱 가이드 탐색 (heuristic-guided search)과 비교했을 때, 이러한 정책은 잠재적인 장점을 가집니다. 즉, 현재의 지역 상태 (local state)에만 의존하는 것이 아니라 전체 탐색 추적 (search trace)을 조건으로 삼는다는 점입니다.

우리는 먼저 현재의 지역 상태만을 관찰하는 LLM 휴리스틱 (LLM heuristic)을 갖춘 최선 우선 탐색 (best-first search)과 추적 조건부 추론 정책 (trace-conditioned reasoning policies)을 비교하여, LLM이 이러한 장점을 활용하는지 테스트합니다. Blocks World, grid Navigation, Sokoban이라는 세 가지 통제된 추론 환경을 통해 실험한 결과, 탐색 이력 (search history)에 대한 원시적인 접근만으로는 휴리스틱 탐색 (heuristic search)을 안정적으로 능가하기에 충분하지 않다는 것을 발견했습니다.

그 후 우리는 한 가지 가능한 원인을 연구했습니다. LLM 추론 추적에서 기저에 깔린 탐색 트리는 암시적으로만 표현되며, 모델이 백트래킹하거나 분기를 전환할 때 추적은 어떤 이전 탐색 상태가 재방문되고 있는지를 명시적으로 식별하지 못한다는 점입니다. 우리는 선형화된 트리 (linearized tree) 구조를 명시적으로 표현하기 위해 단순한 부모 포인터 (parent pointers)를 추가하는 것 (LinTree)이 암시적 추론 모델 (implicit reasoning models) 및 LLM 휴리스틱 가이드 탐색 (LLM-heuristic-guided search)에 비해 작업 성능과 탐색 효율성을 모두 향상시킨다는 것을 보여줍니다. 이러한 결과는 탐색 이력의 트리 구조가 명시적으로 만들어질 때 가장 유용해진다는 것을 시사하며, LLM 추론을 위한 더 구조 인식적인 표현 (structure-aware representations)의 필요성을 뒷받침합니다.