본 논문은 대규모 언어 모델(LLM)의 탐색 능력의 한계를 탐구한다. 기존 연구에서 LLM이 강건한 탐색을 수행하는 데 어려움을 겪는다는 점을 바탕으로, 이러한 어려움이 데이터 부족, 모델 파라미터 부족, 또는 트랜스포머 아키텍처의 근본적인 한계 때문인지 조사한다. 기본적인 그래프 연결 문제를 테스트베드로 사용하여 방대한 양의 데이터를 생성하고, 소규모 트랜스포머를 훈련하여 탐색 능력을 평가한다. 적절한 훈련 분포가 주어지면 트랜스포머가 탐색을 학습할 수 있음을 발견하고, 새로운 기계적 해석 가능성 기법을 통해 학습된 모델에서 계산 그래프를 추출하여 트랜스포머가 모든 정점에서 병렬적으로 탐색을 수행하는 알고리즘을 분석한다. 각 층에서 도달 가능한 정점 집합을 점진적으로 확장하여 지수적으로 많은 정점을 탐색한다는 것을 밝혔다. 그러나 입력 그래프 크기가 증가함에 따라 트랜스포머는 작업 학습에 더 큰 어려움을 겪으며, 파라미터 수를 늘려도 이러한 어려움이 해결되지 않아 모델 규모를 확장하는 것이 강건한 탐색 능력으로 이어지지 않음을 시사한다. 또한, 인컨텍스트(사고연쇄) 탐색으로도 더 큰 그래프에서 탐색 학습 능력이 향상되지 않음을 발견하였다.
