Transformers Struggle to Learn to Search

Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, He He · 2024

Read Transformers Struggle to Learn to Search by Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, He He (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04703.txt.

Introduction

Abulhair Saparov and co-authors ask whether transformers can truly learn to search, in a 2024 paper. Language models fumble tasks like finding a path through a graph, and it was unclear whether data, size, or the architecture itself was at fault. Training small transformers on graph connectivity with rich, well-shaped data, the team found the models could learn the skill.

A new lens on the trained weights revealed the trick: each layer lets every point gather the set of points it can reach, doubling the horizon as layers stack. Yet bigger graphs grew harder to learn even as models grew, hinting that scale alone will not cure the weakness.

Catalog record

CREATORAbulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, He He
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04703

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Transformers Struggle to Learn to Search Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, He He Abstract Search is an ability foundational in many important tasks, and recent studies have shown that large language models (LLMs) struggle to perform search robustly. It is unknown whether this inability is due to a lack of data, insufficient model parameters, or fundamental limitations of the transformer architecture. In this work, we use the foundational graph connectivity problem as a testbed to generate effectively limitless high-coverage data to train small transformers and test whether they can learn to perform search. We find that, when given the right training distribution, the transformer is able to learn to search. We analyze the algorithm that the transformer has learned through a novel mechanistic interpretability technique that enables us to extract the computation graph from the trained model. We find that transformers perform search at every vertex in parallel : For each vertex in the input graph, transformers compute the set of vertices reachable from that vertex. Each layer then progressively expands these sets, allowing the model to search over a number of vertices exponential in n layers n_{\text{layers}} . However, we find that as the input graph size increases, the transformer has greater difficulty in learning the task. This difficulty is not resolved even as the number of parameters is increased, suggesting that increasing model scale will not lead to robust search abilities. We also find that performing search in-context (i.e., chain-of-thought) does not resolve this inability to learn to search on larger graphs. † † footnotetext: ∗ Equal contribution. × Much of the work was completed while author was at New York University. 1 Introduction The ability to search is fundamental in many important tasks, such as reasoning ( Yao et al., 2024 ; Kazemi et al., 2023 ; Hao et al., 2023 ) , planning ( Stein & Koller, 2023 ; Valmeekam et al., 2022 ) , and navigation ( Ding et al., 2024 ) . Recent work has demonstrated that transformer-based large language models (LLMs) struggle with proof search ( Saparov & He, 2022 ; Valmeekam et al., 2022 ; Kambhampati et al., 2024 ) . It is unknown whether this shortcoming is due to a lack of data, insufficient model parameters, or a fundamental limitation of the transformer architecture. In any case, as the scale of LLMs continues to increase, it is yet unclear whether future LLMs, equipped with more data, parameters, and compute, will be able to perform search and planning. Chain-of-thought and similar prompting techniques ( Wei et al., 2022b ; Nye et al., 2021 ) have enabled LLMs to decompose the search task into the repeated task of predicting the next step along the path to the goal. However, even in this setting, in the worst case, in order to avoid making a “wrong turn,” the model must perform the search within its forward pass to determine the correct next step. And LLMs have been observed producing errors or hallucinations after taking such a wrong turn ( Saparov & He, 2022 ) . We aim to shed light on this question by training small transformer models on a simple yet foundational search task: Given a directed acyclic graph (DAG), a start vertex, and a goal vertex, find the next vertex along a path from the start to the goal vertex. This task is the backbone of many reasoning problems as it is equivalent to proof search in a simplified logic which is a subset of almost any logic: The model must solve this task if there is any chance to generalize to more complex search and reasoning tasks. We demonstrate experimentally that transformers can indeed be taught to search, when given the right training distribution. The training distribution must be carefully constructed so as to preclude the usefulness of shortcuts or heuristics that would otherwise prevent the transformer from learning a robust and generalizable search algorithm. By automatically generating such examples, we provide the transformer with effectively limitless and idealized training data, with which we can estimate an “upper bound” on the transformer’s ability to learn to search. When the model does learn the constructed training distribution (i.e., reaches 100% training accuracy), it is able to correctly perform search in almost any graph. We aim to determine the algorithm that the model has learned to solve the search task, and to measure the extent to which the model uses such an algorithm or relies on heuristics. We develop a mechanistic interpretability analysis to study the learned algorithm. We find that transformers perform search simultaneously on all vertices of the input graph, where for each vertex, the transformer stores the set of vertices reachable within a certain number of steps. Each layer successively extends the sets of reachable vertices, thereby allowing the model to search over a number of vertices exponential in the number of layers. However, we find that as the input graph size increases, the transformer has increasing difficulty in learning the training distribution. We find that increasing model scale does not alleviate this difficulty, suggesting that simply increasing the size of the transformer will not lead to the robust acquisition of searching and planning abilities. We also consider modified versions of the search task where the model is permitted to output intermediate tokens ( Kojima et al., 2022 ; Wei et al., 2022b , akin to chain-of-thought prompting;) . More specifically, we test depth-first search and (zero-shot) selection-inference prompting ( Creswell et al., 2023 ) . We find that while it is easier to teach the model to solve this task, requiring a constant number of layers, the model still struggles on larger input graphs. Thus, our results suggest that future transformer-based models will not solve the search task with standard training, and alternative training approaches may be necessary. 1 1 1 All code for generating data, training and evaluation is open-source and freely available at github.com/asaparov/learning_to_search . 2 Related work Search abilities of transformers. A number of studies have explored the search capabilities of transformers and LLMs. Benchmarks have shown that LLMs can perform some graph reasoning tasks and related tasks such as repeated function composition and the k -hop induction head task ( Fan et al., 2024 ; Fu et al., 2024 ; Sanford et al., 2024a ; Sanford et al., 2024b ) , but they are limited to small graphs, relative to graphs we consider. Ruoss et al. (2024) ; Gandhi et al. (2024) ; Shah et al. (2024) find that a transformer can learn to approximate or simulate a search algorithm, but with a performance gap, and they do not test whether this gap is lessened by increasing model scale or training. Wang et al. (2023) ; Bachmann & Nagarajan (2024) show that LLMs can do some graph reasoning but are fooled by spurious correlations. Similarly Zhang et al. (2023) find that transformers are unable to learn to perform proof search since they strongly prefer heuristics. In this work, we also show that transformers are highly sensitive to the training distribution, but if extra care is taken to remove heuristics, they are able to

Read the complete text