ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models

Authors: siwei  wang
yifei  shen
shi  feng
haoran  sun
shang-hua  teng
wei  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 09:30:01

Abstract: Planning is a crucial element of both human intelligence and contemporary large language models (LLMs). In this paper, we initiate a theoretical investigation into the emergence of planning capabilities in Transformer-based LLMs via their next-word prediction mechanisms. We model planning as a network path-finding task, where the objective is to generate a valid path from a specified source node to a designated target node. Our mathematical characterization  shows that Transformer architectures can execute path-finding by embedding the adjacency and reachability matrices within their weights. Furthermore, our theoretical analysis of gradient-based learning dynamics reveals that LLMs can learn both the adjacency  and a limited form of the reachability matrices. These theoretical insights are then validated through experiments, which demonstrate that Transformer architectures indeed learn the adjacency and an incomplete reachability matrices, consistent with our theoretical predictions. When applying our methodology to the real-world planning benchmark Blocksworld, our observations remain consistent. Additionally, our analyses uncover a fundamental limitation of current Transformer architectures in path-finding: these architectures cannot identify reachability relationships through transitivity, which leads to failures in generating paths when concatenation is required. These findings provide new insights into how the internal mechanisms of autoregressive learning facilitate intelligent planning and deepen our understanding of how future LLMs might achieve more advanced and general planning-and-reasoning capabilities across diverse applications.

Main paper: 
 introduction: 
 Large language models (LLMs) such as ChatGPT have impressed many with their powerful capabilities across a wide range of tasks, including language processing, knowledge extraction, reasoning, planning, coding, tool use, and more [1] . However, we continue to be intrigued by the underlying mechanisms that fuel the power of LLMs. While all current LLMs are built on the Transformer architecture, which uses autoregressive learning to predict the next word in a language sequence, the overarching question remains:There is no definite answer to this question yet, but researchers are approaching the problem from various angles, aiming to characterize the power and limitations of LLMs, as well as to capture their underlying acquisition, abstraction, generalization, adaptation, and reasoning mechanisms.Recently, the mechanisms of grammar learning, knowledge manipulation, scaling laws, and arithmetic operations have been empirically uncovered [4, 3, 5, 2, 31, 11] . Furthermore, theoretical analyses have been conducted on in-context learning, chain-of-thought, and other forms of reasoning [30, 8, 7, 27] . Beyond these, LLMs' capability for planning-a fundamental component of human intelligence-has also drawn considerable attention. Planning is involved in nearly every aspect of our daily life, such as organizing a task at work, planning a trip, or seeking a mathematical proof of a theorem. Additionally, task planning plays a pivotal role in state-of-the-art LLM-empowered autonomous agents, such as HuggingGPT [18] , Voyager [23] , and Reflection [19] . Understanding how LLMs complete a planning task can shed light on how the seemingly low-level statistical task of next-word prediction transforms into a high-level intelligent process. Several prior studies have empirically evaluated the planning capabilities of LLMs, yielding both positive and negative results [16, 22] . However, the current results are incomplete and do not fully explain why LLMs can or cannot successfully accomplish specific planning tasks (see Appendix A for a detailed discussion of related works).Given that planning often involves making sequential selections of next steps to achieve a desired goal, it naturally relates to the path-finding task in networks. For example, autonomous agents (e.g., HuggingGPT [18] ) for scheduling API calls can be likened to finding a call path in the API call graph; a mathematical proof can be seen as a proof path from the axioms to the final theorem [21] ; and a step-by-step solution to a grade-school math problem can be viewed as a path in the dependency graph among the variables [28, 29] . Many previous studies on LLM planning capabilities are related to path-finding. e.g., an LLM planning benchmark called Blocksworld [22] can be viewed as pathfinding from the initial state of the blocks to the final state in a state transition graph. Furthermore, in neuroscience, planning is often evaluated through path-finding in a maze [26] . Consequently, in this paper, we abstract planning in LLM learning as the following path-finding task: given an underlying directed graph, a Transformer architecture is provided with training data consisting of a collection of paths that specify the source node, the target node, and a path from the source to the target. The task of the language model is then to generate a path for a new source-target pair. In addition to measuring the performance of the trained model, we examine the internal weighting mechanism and the learning dynamics of the Transformer architecture during the learning and problem-solving process. This research is part of our broader project, ALPINE (Autoregressive Learning for Planning In NEtworks), which aims to answer the overarching question on the connection between the process of next-word prediction and the emergence of intelligence through the lens of planning.Our Contributions: Our project initiates a theoretical investigation into the development of planning capabilities in Transformer-based language models by focusing on characterizing their expressiveness and learning dynamics in the path-finding task. First, in Theorem 2, we present a mathematical construction of a Transformer that encodes both the adjacency and reachability matrices of the network, thereby establishing that Transformer architectures possess the expressive capacity to complete the path-finding task. Then, in Theorem 3, we prove that when applying gradient descent to minimize the cross-entropy loss on the training data, a model based on a simplified Transformer architecture can extract the adjacency matrix and a limited form of the reachability matrix, using them to mimic human-like intelligence in path-finding. Our theoretical analysis further reveals a fundamental limitation of current Transformer architectures: they do not learn certain types of reachability, particularly transitive reachability, resulting in an incomplete ability to reason about future steps when planning. To validate our theoretical findings, we conduct extensive experiments training Transformers on the path language using autoregressive learning. First, these experiments demonstrate that Transformers achieve high accuracy in the path-finding task (Figure 3 ). Second, we show that it is indeed possible to extract both the adjacency and a limited form of the reachability matrices from the Transformers' weights (Figures 1, 2, 5, 6(a) ). Third, we observe a significant drop in test accuracy when the source and target nodes are connected only through concatenated path segments in the training data (Figure 6 ). These findings align with our theoretical analysis, confirming that current Transformers have limitations in learning transitive reachability relationships, unlike human intelligence. Finally, we validate these results on a real-world task planning benchmark, Blocksworld [22] , which directly corresponds to the path-finding problem (see Appendix F). 
preliminaries: 
 Throughout this paper, we use the following notations for matrices and vectors: a and A stand for a column vector and a matrix, respectively. Notations a (i) and A (i,j) denote the i th entry of vector a and the (i, j) th entry in matrix A, respectively. We also denote the i th row of matrix A by A (i,:) .In this paper, we adopt the standard GPT architecture [17] . We use the following notation for the architecture and loss function in our analysis. Let N denote the sequence length, d the embedding size, H the number of heads, d k = d/H the embedding size per head, and M the vocabulary size. One key component of the architecture is the attention mechanism, which is formulated as:EQUATIONwhereQ ∈ R N ×d k , K ∈ R N ×d k , V ∈ R N ×d kare the query, key, and value matrices, respectively. Denoting X ∈ R N ×d as input, the multi-head attention is computed as MHA(X) = Concat i∈[H] (Attention(XW Q i , XW K i , XW V i )), where W Q i ∈ R d×d k , W K i ∈ R d×d k , W V i ∈ R d×d kare the learnable weight matrices for the query, key, and value matrices of the i-th head. The feed-forward layer is a two-layer multi-layer perceptron (MLP) defined as follows:FFN(X) = max(0, XW 1 + 1 N ×1 b ⊤ 1 )W 2 + 1 N ×1 b ⊤ 2 (2)whereW 1 ∈ R d×4d , W 2 ∈ R 4d×d , b 1 ∈ R 4d, and b 2 ∈ R d are the learnable weight matrices and 1 N ×x is the all-one matrix with dimension N × x. Finally, one Transformer layer is defined as:EQUATIONwhere LN 1 and LN 2 are two layer normalizations.With these essential components in place, we proceed to introduce the procedures of GPT. The training data consists of many sequences of tokens, where each sequence is expressed asu = (u 1 , • • • , u N ),in which u n denotes the token id for the n-th token in sequence u. We first represent the tokens in u by a one-hot embedding matrix U ∈ R N ×M , where U (n,un) = 1 and 0 elsewhere. Then there are learnable token embedding matrix W t ∈ R M ×d and positional embedding matrix W p ∈ R N ×d , and the inputH 0 = U W t + W p ∈ R N ×d . This input H 0 is fed into an L-layer Transformer, i.e., H l = Transformer(H l-1 ) ∈ R N ×d for l = 1, • • • , L.Finally, the output embedding goes through another layer normalization LN t , and then it is multiplied by a learnable output weight matrix W o ∈ R d×M to convert back to probability weights over all possible tokens. We calculate the output probability vector at position n, denoted by û(n+1) , using û(n+1) = softmax((LN t (H L )) (n,:) W o ), 1 ≤ n < N . This probability vector is used to predict the token for position n + 1, which reflects the autoregressive learning paradigm. The adopted loss function is the cross-entropy loss for the next token prediction, given by:EQUATIONThe dataset is designed to evaluate GPT's path-planning capability on simple graphs. It is generated from a directed graph G = (V, E), where V is the set of nodes, and E is the set of edges. For any two nodes u, v ∈ V, (u, v) ∈ E means that there is a directed edge from u to v in G. A pair of source node s and target node t is considered a valid pair if G contains at least one path from s to t.The training dataset D contains sequences in the format "s t s a b c t \n", where s represents the source node token, t the target node token, s a b c t are tokens for nodes in a valid path from s to t, and \n indicates the end of the sequence. During testing, we provide valid pairs of source and target nodes in the format "s t". The model is tasked with completing the remaining tokens in the sequence. The completion is considered correct if the model generates a valid path with the correct syntax.3 Expressiveness and Learning Dynamics of Transformer Models Obtain S = {k|A (i,k) = 1 and R (t,k) = 1} 5:Randomly sample next node k from S 6:Append k to path P , and set i = k 7: end while 8: output path P In our path-finding task, the essential step for completing a path is to predict the next node based on the current information. It is evident that to predict the subsequent node on the path, only information related to the current node and the target node is necessary. Algorithm 1 introduces a idealized method that utilizes both the adjacency and reachability matrices of the graph. The true adjacency matrix A true and the true reachability matrix R true are defined as:A true (i,k) = 1, if (i, k) ∈ E, 0, otherwise. R true (t,k) = 1, if k can reach t in G, 0, otherwise.Fact 1. Assuming that t is reachable from s, then Algorithm 1 is guaranteed to output a valid path with input A = A true and R = R true .To illustrate the expressive capacities of the Transformer model, we first demonstrate how to manually construct a Transformer that can perform the path-finding task by simulating Algorithm 1. Theorem 2. Given a graph G (with adjacency matrix A true and reachability matrix R true ), for every ε > 0, there exists a 1-layer, 1-head, and O(|V|)-embedding-size Transformer model that generates a valid path for every valid source-target pair (s, t) with probability at least 1 -ε.The proof involves encoding the adjacency and reachability matrices into the weights of the FFN and attention layers, respectively, while mimicking the computation of Algorithm 1 (see Appendix B). 
learning dynamics: 
 Having established the mathematical existence of a Transformer model capable of accomplishing path-finding in a given network, as demonstrated in Theorem 2, we now shift our focus to the following fundamental question: Can the Transformer architecture, trained on sufficient path data with an autoregressive loss as in Equation (4) and using the gradient descent (GD) method, learn the adjacency and reachability matrices and carry out path-finding similar to the idealized Algorithm 1?Theoretically, we notice that the Transformer may not be able to learn the true adjacency and reachability matrices for the underlying graph. Instead, it can only learn the relevant information that is directly encoded in the observed training data D. Therefore, we define the observed adjacency and reachability matrices based on the training data D as follows.A obs (i,k) (D) = 1, if ∃u ∈ D, n ∈ [3, N -1] s.t. u n = i, u n+1 = k 0, otherwise R obs (t,k) (D) = 1, if ∃u ∈ D, n ∈ [4, N ] s.t. u 2 = t, u n = k 0, otherwise.Naturally, the observed adjacency matrix A obs (D) only records the edges (i, k) that appear in some path within the training data D. On the other hand, the observed reachability matrix R obs (D) exhibits more nuanced distinctions from the true reachability matrix. It only records that node t is reachable from node k, if the training data D contains a path (sequence) whose target node is t and k appears as a non-source node on the path. We call such pairs (t, k) observed reachable pairs. Noticeably, reachability through transitivity, i.e., through concatenation of path segments in D, is not observed.Here we consider the following simplified 1-layer and 1-head Transformer structure: a) The attention weight is only on the target node (the second token), i.e., we manually set every row in softmax QK ⊤ √ d k in Eq. ( 1) to be a one-hot vector with the second coordinate being 1 (this is validated in our experiments shown in Figure 4 ), and set the positional embedding matrix W p = 0; b) We remove all the layer normalizations, and use FFN(X) = XW M instead of Eq. (2), Transformer(X) = FFN(X) + MHA(X) instead of Eq. (3); c) The token embedding matrix W t and the output weight matrix W o are set to be identity. The embedding size is the same as the vocabulary size (d = M ), and we only consider the cross-entropy loss of predicting the next node.Since there is only one layer and one head, we use W V to represent the weight of the value matrix in the attention layer. Under the above Transformer structure,(H L ) (n,:) W o = (U W t W M +αU W t W V ) (n,:) W o = (U W M +αU W V ) (n,:) = W M(un,:) +W V (u2,:) , where α is the manually set attention weight matrix (every row is a one-hot vector with the second coordinate being 1). Therefore, the probability vector when predicting the (n + 1)-th token is softmax(W M (un,:) + W V (u2,:) ), and the prediction probability ûn+1,k equalsEQUATIONLet N i,j,k be the number of times in D that: a) the current node is i; b) the target node is j; c) the next node is k, and let N i,j = k N i,j,k , then we have the following theorem.Theorem 3. Under the cross-entropy loss ℓ(D), for all(i, k) pairs, i) if j N i,j = 0, then ∂ℓ(D) ∂W M (i,k) is always 0; ii) if j N i,j > 0 but j N i,j,k = 0, then ∂ℓ(D) ∂W M (i,k) is always positive; iii) if j N i,j,k > 0, then ∂ℓ(D) ∂W M (i,k) is negative when W M (i,k) → -∞. Similarly, for all (j, k) pairs, i) if i N i,j = 0, then ∂ℓ(D) ∂W V (j,k) is always 0; ii) if i N i,j > 0 but i N i,j,k = 0, then ∂ℓ(D) ∂W V (j,k) is always positive; iii) if i N i,j,k > 0, then ∂ℓ(D) ∂W V (j,k) is negative when W V (j,k) → -∞.Proof Sketch. By the definition of the cross-entropy loss in Eq.( 4), and the prediction probability vector in Eq.( 5), the total cross-entropy loss of the model (with matricesW M , W V ) is ℓ(D) = - i,j,k N i,j,k (W M (i,k) + W V (j,k) ) + i,j N i,j log ℓ exp(W M (i,ℓ) + W V (j,ℓ) ) .Then we can get that: (the proof for the W V part is similar)EQUATIONIn case i), j N i,j = 0 implies that j N i,j,k = 0. Hence ∂ℓ(D)∂W M (i,k)is always 0.In case ii), j N i,j > 0 implies that the second term in Eq. ( 6) is positive, while j N i,j,k = 0 implies that the first term in Eq. ( 6) is 0. Hence ∂ℓ(D)∂W M (i,k)is always positive.In case iii), when j N i,j > 0 and W M (i,k) → -∞, the second term in Eq. ( 6) converges to 0, and it is smaller than j N i,j,k > 0. Hence, ∂ℓ(D)∂W M (i,k) is negative when W M (i,k) → -∞.The above technical theorem directly leads to a theoretical explanation on how the model learns the adjacency and reachability information, as explained below.Learning the adjacency matrix. Let E(D) denote the set of edges appearing in the training dataset D, which corresponds to the observed adjacency matrix A obs (D). For any (i, k) ∈ E(D), j N i,j,k > 0, and for any (i ′ , k ′ ) / ∈ E(D), j N i ′ ,j,k ′ = 0. Then from the above theorem, under the gradient descent learning paradigm, W M (i ′ ,k ′ ) will keep decreasing (since its gradient is always positive), while W M (i,k) will not (since its gradient becomes negative when its value is sufficiently negative). This tends to make W M (i,k) higher than W M (i ′ ,k ′ ) after training. In this way, the Transformer model learns the information about the observed adjacency matrix with matrix W M .To facilitate comprehension, we conducted a simple experiment on the simplified Transformer, and present the results in Figure 1 all the paths with length 1 and 20% of the paths with length higher than 1; and D 3 contains all the possible paths. Figure 1 (a) is the true adjacency matrix of the graph, which is also the observed adjacency matrix for the three datasets. Learning the reachability matrix. Similar to the process of learning the adjacency matrix, since only observed reachable pairs (j, k) have i N i,j,k > 0, the gradient descent learning paradigm tends to make the W V (j,k) terms corresponding to observed reachable pairs (j, k) higher than the W V (j ′ ,k ′ ) terms corresponding to non-observed reachable pairs (j ′ , k ′ ) (which is either not reachable or not observed) after the training. In this way, the Transformer model captures the structural information of observed reachability matrix with weight matrix W V .(D1) (c) R obs (D2) (d) R obs (D3) (e) W V under D1 (f) W V under D2 (g) W V under D3Figure 2 shows the correlation between W V and the observed reachabilities under different dataset D's in the above experiment. Predicting the next node on a path. From Eq.( 5), the probability vector for predicting the next node is softmax(W M (un,:) + W V (u2,:) ), where u n represents the current node, and u 2 represents the target node. This resembles the procedure in Algorithm 1: it predicts the next node k such that both In summary, our theoretical analysis demonstrates that a simplified one-layer, one-head autoregressive Transformer (with perfect attention) can effectively learn crucial adjacency and reachability information from the training data through gradient descent training. Moreover, it can utilize this learned information to predict the next node akin to the decision-making process of a human algorithm designer in similar scenarios. This suggests that, when confronted with the path-finding or more general planning task with a given goal, the Transformer learns the structural information to associate the next step with both the current step and the goal, enabling it to generate the subsequent task step. Nevertheless, the Transformer's limitation in learning only the observed reachability matrix-without deducing the complete reachability matrix-hints at potential constraints on the goal-oriented information it can acquire. This limitation may result in the Transformer failing to grasp novel reachability relationships derived from the transitivity of reachability relations, unlike human intelligence.W M (un,k) is high (corresponding to A (un,k) = 1) and W V (u2,k) is high (corresponding to R (u2,k) = 1). 
empirical evaluations: peeking into a trained transformer: 
 In this section, we conduct extensive experiments on the path-finding task using the general Transformer architecture as described in Section 2.1. The datasets are generated as described below.The DAG is generated randomly based on two parameters: the number of nodes n, and the probability of edge p = 0.1: For any 1 ≤ i < j ≤ n, there is an edge (i, j) ∈ E with probability p. Given the DAG, we first find all the possible reachable pairs (s, t). Then these reachable pairs are separated into the training set (w.p. 0.5) and the test set (w.p. 0.5), but if edge (s, t) ∈ E, we always put (s, t) in the training set. For a reachable pair (s, t) in the training set, we generate m = 20 random paths that start at s and end at t, and put these m paths into the training dataset. When generating the random path, at each current node i, we find all the possible k ∈ V such that A true (i,k) = 1 and R true (t,k) = 1 (i.e., there is an edge (i, k) ∈ E, and k could also reach the target node t), and uniformly choose a random one in them. Moreover, if (s, t) ∈ E, we always put the one-edge path "s t s t \n" in the training dataset to guarantee that all edges appear at least once in the training data.We train Transformer models on the aforementioned training dataset and subsequently evaluate the performance of these models using the pairs in the test dataset. The correctness of a model's output is determined based on its validity in terms of syntax and whether it corresponds to a valid path from s to t. In our experiments, we employ Transformer models with an embedding size of d = 120. We conduct tests using various configurations, ranging from 1-layer and 1-head to 6-layer and 6-head, while considering different graph sizes, with number of nodes n ranging from 100 to 500. The accuracy results take average over 10000 trials, and are presented in Figure 3 (due to space limits, some results are deferred to Appendix E, and all of them are consistent with our conclusions). From these results, we make the following observations: a) When comparing the figures, the accuracy tends to decrease as the number of nodes increases; b) When examining each row, the accuracy remains relatively stable even as the number of attention heads increases; c) When examining each column, the accuracy shows at most a slight improvement as the number of layers increases.The above observations suggest that the embedding size is the most important hyperparameter that affects the accuracy of the model. On the one hand, when the embedding size is sufficiently large compared to the graph size, even 1-layer and 1-head models perform well. This coincides with our theoretical analysis, which shows that when the embedding size equals to the graph size, the 1-layer and 1-head structure is enough to predict the next nodes accurately. On the other hand, when the embedding size is small compared to the graph size, even 6-layer and 6-head Transformers cannot achieve good performance. Because of this, in the following, we concentrate on the explainability of the 1-layer and 1-head Transformer models.Attention. In our analysis, we assume that the attention is fixed on the target node. Is this true for the Transformer models learned from real data? The corresponding results are shown in Figure 4 . These results are obtained by looking into the attention mechanism of the 1-layer and 1-head Transformer models, and showing the average (taking on the test dataset) matrix of softmaxQK ⊤ √ d k ,of which the n-th row represents the attention vector for predicting the (n + 1)-th token.Note that the second column in these figures represents the attention weights on the second token, which corresponds to the target node in our test data. We can see that, when predicting the next tokens, almost all the attention weights are concentrated on this column, especially for those models with higher accuracy (Figure 4 (a) for n = 100 and Figure 4 (b) for n = 200). This demonstrates that indeed the Transformer model learns the correct attention for the path-finding task, and our assumption on the attention weights for the theoretical analysis is reasonable.Adjacency Matrix. In the 1-layer and 1-head Transformers, let W M ′ (shown in Figure 5 ) be thematrix whose i-th row is FFN e ⊤ i W t W o + (e ⊤ i W t )W o, where e i is the one-hot column vector that represents the token for node i. Based on the Transformer computation, intuitively this matrix is one of the components in the output that contains information related to the current node. The detailed reason for choosing this matrix is explained in Appendix D.In Figure 5 (a), the W M ′ matrix and the adjacency matrix are highly aligned: all large entries in the W M ′ matrix correspond to real edges, and all real edges correspond to large entries in the W M ′ matrix. This high accuracy is because the embedding size d = 120 is higher than the number of nodes n = 100. If the embedding size is lower than the graph size (Figures 5(b ), 5(c)), we inevitably lose some accuracy when approximating the adjacency matrix by the product of matrices with rank smaller than the graph size. Even so, there is still high relevance between W M ′ and the adjacency matrix: almost all real edges correspond to large entries in the W M ′ matrix.In Figure 5 (d), we show the gap between the average weight corresponding to edges (i.e., the average of W M ′ (i,j) 's with i < j and (i, j) ∈ E) and the average weight corresponding to non-edges (i.e., the average of W M ′ (i,j) 's with i < j and (i, j) / ∈ E) during the training process. These gaps keep increasing until convergence, suggesting that weights between edges and non-edges are more easily separated as the learning process proceeds.Reachability Matrix. In the 1-layer and 1-head Transformers, let W V ′ be the matrix whose i-th row is (e⊤ i W t )W V W o + FFN (e ⊤ i W t )W V W o, where e i is the one-hot column vector that represents the token for node i. Intuitively, this matrix is the remaining component in the output that contains information related to the target node. The detailed reason is also explained in Appendix D.In Figure 6 (a), we show the average weights of three different sets in the graphs: "obs" corresponds to the W V ′ (t,k) 's with t ≥ k and R obs (t,k) = 1; "real\obs" corresponds to theW V ′ (t,k) 's with t ≥ k, R obs (t,k) = 0 but R real (t,k) = 1;and "non" corresponds to the W V ′ (t,k) 's with t ≥ k and R real (t,k) = 0. Here we only show the results of graphs with 100 nodes and 200 nodes, since their accuracy is high enough and their attention is quite close to being concentrated on the target node. When there are more nodes, the ability to approximate the reachability matrix is not enough for us to distinguish it. From these average weights, we can see that the Transformer learns R obs quite well, as for those terms in "real\obs", their weights are almost the same as those in "non". This echoes our analysis.To further demonstrate that R real is not learned as good as R obs , we divide the source-target node pairs (s, t) in the test dataset into four categories: a) degree 0: R obs (t,s) = 1; b) degree 1: (s, t) is not of degree 0, while s has at least one out-neighbor node u such that (u, t) is of degree 0, i.e. R obs (t,u) = 1; c) degree 2: (s, t) is not of degree 0 and 1, while s has at least one out-neighbor node u such that (u, t) is of degree 1; d) degree 3 or more: the remaining (s, t) pairs in the test dataset. Roughly speaking, in our analysis, for (s, t) pairs of degree 0 or 1, we know that there is a node u such that A obs (s,u) = 1 and R obs (t,u) = 1. Then node u will have a large weight, indicating a high accuracy. As for (s, t) pairs of degree 2 or more, there is no node u such that both A obs (s,u) = 1 and R obs (t,u) = 1. In this case, the high-weight entry when predicting the next node of s is either an adjacent node of s or a recorded node that can reach t. This should reduce the accuracy.To see this, we check the accuracy of the Transformers on the (s, t) pairs of the four different categories. The results are shown in Figure 6 (b)-(d) . In these figures, each row of the accuracy matrix is further divided into four sub-rows corresponding to the accuracy of degree-0 pairs, degree-1 pairs, degree-2 pairs, and degree-3 or more pairs respectively (in the graph with 100 nodes, there are no test (s, t) pairs in the degree-3 or more category). From these results, we can see that the accuracy for degree-2 pairs and degree-3 or more pairs is much lower than the two other categories in most cases. It indicates that, even with more parameters and a more complex structure (e.g. a 6-layer and 6-head Transformer), the Transformer model has a fundamental difficulty in generating paths for high-degree source-target pairs, namely those pairs that can only be connected by concatenating several path segments in the training dataset. This result demonstrates the validity of our theoretical analysis, i.e., after training with gradient descent on cross-entropy loss, the Transformer can only learn observed reachability, and will miss those unobserved reachability deduced from the transitivity of the reachability relation.In summary, our extensive empirical evaluation leads to the following conclusions about the Transformer model in achieving the path-finding task: (a) With large enough embedding size, the model can achieve high accuracy in general; (b) The model achieves its performance by concentrating attention on the target nodes as intended, and learning the information on adjacency and reachability matrices, just as what a human would do and as predicted by our theoretical analysis; and (c) The model may have limitations and fail to learn high-order reachability relations through transitivity, and thus fail to generate paths derived from high-order reachability. 
discussion and future work: 
 In summary, this paper and Project ALPINE more broadly conceptualize planning as path-finding in networks, and combine theoretical analysis of the Transformer architecture and autoregressive loss with empirical validation. Our aim is to uncover the mechanisms by which intelligence may emerge from autoregressive Transformer architectures. We analytically demonstrate that Transformers possess the expressiveness required to perform path-finding tasks and that gradient descent on crossentropy loss enables them to learn necessary-but incomplete-graph information for path-finding. Additionally, we reveal both analytically and empirically that autoregressive training of language models has inherent limitations in the path-finding task.Practical Implications: Our findings in LLMs for path planning may have practical implications for the training, testing, and enhancement of language models. In particular, the limitations we identified in current Transformer architectures for transitive reasoning suggest several directions for enhancing LLM frameworks to achieve more advanced and general planning-and-reasoning capabilities across diverse applications. For instance, in data generation for training, creating more diversified datasets that explicitly cover more reachability relationships may help the model achieve a higher accuracy.When evaluating a language model's planning capability, it may be beneficial to test for higher-order relationships not directly encoded in the training data but requiring chaining and concatenation to assess whether the model can perform transitive planning. Furthermore, by highlighting limitations in current language models, our study motivates future research into improved Transformer architectures, including incorporating transitivity directly into the model structure.Challenges in Reasoning about Unobserved Reachability: Technically, the challenge in learning unobserved reachability with current Transformer architectures stems from the nature of next-token prediction loss: learning unobserved reachability incurs a higher training loss. Specifically, when predicting the next token for a given current node i and target node j, the optimal distribution for minimizing training loss should align with the observed distribution in the training dataset, i.e., Pr[next node = k|current node = i and target node = j] =N i,j,kNi,j (as explained in Section 3.2). Learning unobserved reachabilities requires deviating from the distribution defined by the training data, which leads to a higher training loss. Consequently, with the current training loss and Transformer architecture, the model cannot learn unobserved reachabilities, such as transitive reachability. To enable the model to learn transitivity, we may need alternative training objectives, such as path accuracy, or structural improvements to the Transformer that allow it to 'deduce' unobserved reachabilities. Conceptually, the current training data and loss objective do not provide sufficient information to teach the model transitivity or other derived relationships. Therefore, enhancing transitivity and similar capabilities may require enriching the training data, modifying the objective function, or incorporating new components into the model architecture.Future Directions: Our investigation opens several promising directions for future research: (a) Extending our study to hyper-graphs and hyper-paths, where a hyper-edge represents scenarios requiring multiple preconditions to be met simultaneously in order to carry out the next step, as often seen in task planning and mathematical proofs. (b) Addressing the limitations of Transformers in path-finding and other planning tasks by exploring richer path-finding languages, fine-tuning, or architectural improvements to LLMs. (c) Examining connections between the abstract path-finding task and concrete planning tasks (e.g., block manipulation in Blocksworld) to understand whether, and how, Transformers abstract these tasks into path-finding frameworks. (d) Investigating in-context path-finding capabilities, where training data includes different graphs with corresponding paths, to see how Transformers learn to find new paths in new graphs. (e) Exploring the integration of chain-of-thought and backtracking capabilities into Transformers for path-finding, which may offer crucial insights into enabling these features for general search and planning tasks.In our ongoing project ALPINE, we plan to deepen our investigation into all the aforementioned fronts. We also hope that our work will inspire more researchers to study LLMs through combined theoretical and empirical analysis, with the ultimate goal of enhancing their capabilities and understanding how human-like intelligence can be achieved through statistical learning and AI mechanisms.Several recent studies have empirically evaluated the planning abilities of large language models. For instance, CogEval has introduced a variety of planning tasks set in mazes and graphs, ultimately finding no evidence to suggest LLMs grasp the intricacies of the maps or the planning tasks themselves [16] . Similarly, another study explored the Blocksworld game, a planning challenge where humans typically achieve success rates above 70%, in stark contrast to GPT-3's mere 5% success rate [22] . Our paper also proposes a novel approach by formulating a class of planning problems as path-finding on graphs, applying this model to the Blocksworld game and uncovering significant insights, as detailed in Appendix F. Despite these seemingly negative evaluations, LLMs have shown remarkable aptitude in executing real-world planning tasks, creating the field of autonomous agents [25] . Certain applications of autonomous agents feature explicit graphs. In the tool agent HuggingGPT [18] , LLMs are deployed to trigger a sequence of external APIs in response to user requests. Here, APIs are conceptualized as graph nodes, with their interrelations represented as edges, and the selection process akin to identifying a path or subgraph that aligns with user demands. This scenario is an extension of the settings discussed in this paper, where the graph is text-attributed and the objective function is evaluated through textual analysis. In addition, the application of graph search techniques has been shown to enhance the performance of tool agents significantly [13, 12] . This demonstrates that our approach of abstracting planning as path-finding in graphs is reasonable. The math agent AlphaGeometry utilizes LLMs to solve geometry problems [21] . By treating lemmas as nodes and their interdependencies as edges, the process of finding a proof of a theorem is analogous to finding a path to the theorem node in the above graph formed by possible lemma nodes and their interdependency edges. However, [21] only focuses on using LLMs to generate auxiliary constructions, and the reasoning tasks are done by a non-LLM engine. This is very different from our approach. There are no explicit graphs in other agents, such as game agents [23] , embodied agents [10] , and code agents [19] . The core strategy in these domains is to employ verbal reinforcement learning within LLMs. However, it is noteworthy that any dynamic programming problem characterized by deterministic state transitions can be reformulated as a shortest path problem on a graph, with states and transitions represented as nodes and edges, respectively. As a result, the area of autonomous agents is also closely related to the path-finding task investigated in this paper.GPT4Graph [9] and NLGraph [24] have developed extensive frameworks for assessing LLMs in the context of graph tasks. These frameworks encompass a broad spectrum of challenges, including classic graph problems (e.g., connectivity, cycle detection, and topological sorting), graph neural network (GNN) tasks (e.g., node and graph classification), and semantic graph question answering (e.g., knowledge graph inquiries). They also explore various input formats, such as adjacency lists, edge lists, GML, and GraphML, alongside innovative prompting techniques such as few-shot, role prompting, chain-of-thought, and algorithmic prompting (e.g., stating "we are using DFS"). These studies demonstrate that LLMs possess basic graph processing capabilities, and the choice of prompts and formats significantly influences the performance. Yet, they also reveal the models' susceptibility to spurious correlations within graphs. GPT-4, for instance, only achieves around 50% accuracy on shortest path tasks, even when utilizing complex prompts. To our knowledge, our paper presents the first theoretical analysis that identifies and explains the spurious correlations learned by transformers, partially supporting some of the negative outcomes reported in these studies.There has also been a surge in efforts aiming at bolstering LLMs' performance on graph tasks. Innovations such as GraphGPT [20] and GraphLLM [6] , which incorporate an additional GNN encoder, have shown notable improvements across the aforementioned graph tasks. GraphInstruct [14] seeks to enhance LLMs' capabilities using pure LLM approaches. This involves meticulously documenting the steps of classical algorithms (e.g., BFS and DFS) and fine-tuning LLMs to learn these graph algorithms. This method of procedural supervision has extended the capacity of LLMs in graph tasks from the complexity class TC 0 to P/poly [7] . However, while this approach has yielded performance improvements in simpler tasks such as topological sorting and connectivity, it has proven less effective for more complex challenges, e.g., finding Hamiltonian Paths.Recent theoretical investigations have shed light on the capability of the Transformer to simulate algorithms, a topic that has garnered considerable interest. From the view of discrete algorithms, Transformer models are likened to parallel circuits characterized by polynomial width and constant depth, which places them within the TC 0 complexity class (note that TC 0 ⊆ NC 1 ⊆ P ). On the other hand, despite their impressive expressiveness, the Transformer is theoretically incapable of addressing a range of P-complete problems, including the testing of Context-Free Grammar Membership [15] . However, the advent of chain-of-thought prompting has enabled the Transformer to sequentially simulate algorithms, thereby equipping them to tackle P-complete problems in domains such as arithmetic and decision-making [7] . The exploration then extends to continuous algorithms, where it has been demonstrated that the Transformer can approximate functions such as matrix inversion, Stochastic Gradient Descent (SGD), and power iterations [8] . Our study specifically applies Transformer models to simulate path-finding algorithms, presenting evidence that their expressiveness is sufficient for such tasks (Theorem 2). Nevertheless, the usage of autoregressive loss and gradient descent introduces certain limitations, which have not been studied in existing works.LLMs have demonstrated capabilities that exceed the theoretically predicted lower bounds of expressiveness. To demystify this paradox, numerous studies have employed experimental methodologies akin to those used in the physical and biological sciences. Their aim is to decode the mechanisms of LLMs. The foundational strategy is to generate controlled synthetic datasets to analyze how transformers (not necessarily LLMs) complete various tasks. Standard methods for this analysis include visualizing attention patterns to examine computational properties (such as locality and time invariance) and employing linear probing on the hidden states to determine the extent of learning. Given that the training data is synthetic and the ground-truth mappings are generally known, it becomes feasible to isolate the influence of various factors (e.g., prompting strategies, chain-of-thought reasoning, and data formatting). For example, a dataset designed for learning group operations, as detailed in [31] , facilitates the exploration of how pretraining, data composition, and neural architecture influence reasoning tasks within LLMs. Similarly, the generation of synthetic context-free grammar (CFG) data, as described in [2] , enables training GPT-2 models, uncovering their capacity to learn dynamic programming algorithms for parsing CFGs. Synthetic datasets focusing on biographical knowledge, presented in [3, 4, 5] , probe into the mechanisms of knowledge storage, retrieval, manipulation, and the implications of scaling laws. Moreover, the work in [11] introduces synthetic datasets that aim to understand how smaller LLMs tackle basic arithmetic operations, e.g., addition, and examines the effects of few-shot prompting, pretraining, and model scaling [11] . Our work builds upon these investigations by conducting controlled experiments with a path-finding dataset, thereby shedding light on the complexities and challenges of planning in language models.Theorem 2. Given a graph G (with adjacency matrix A true and reachability matrix R true ), for every ε > 0, there exists a 1-layer, 1-head, and O(|V|)-embedding-size Transformer model that generates a valid path for every valid source-target pair (s, t) with probability at least 1 -ε.Proof. For simplicity, we omit all layer normalizations in this construction. Suppose the input token sequence is "s t s u 1 u 2 . . . u k " with k ≥ 0, where s (= u 0 ) and t are the tokens of the source and target nodes, respectively, and nodes s, u 1 , • • • , u k form a path that can reach node t in graph G. Our objective is to construct a 1-layer and 1-head Transformer model that generates an out-neighbor u k+1 of u k such that there exists at least one path from u k+1 to t in G.In essence, we utilize the attention layer to attend the output solely to the target node t. This approach allows the distribution of next token u k+1 to become a function of both the current node u k and the target node t (as formulated in Section 2). Then, by integrating the adjacency matrix A true into the FFN layer and the reachability matrix R true into the matrix W V in the attention layer, we extract row vectors R true (t,:) and A true (u k ,:) from R true and A true , respectively, corresponding to the target node t and current node u k . By selecting proper coefficients, we can let the output be the sum of R true (t,:) and A true (u k ,:) . Following the softmax layer, the non-negligible entries in the final vector correspond to the feasible next nodes. With this encoding, the Transformer serves as a simulator of Algorithm 1 with input A = A true and R = R true .Following our notation in Section 2.1, we adopt d = |V| + 2, M = |V| + 1 and N = k + 3. In the Transformer, there are M = |V| + 1 tokens representing the |V| nodes and the end-of-line "\n". Hence, the input tokens can be represented by the one-hot embedding matrix U ∈ R N ×M . We letW t = (I M ×M | 0 M ×1 ) ∈ R M ×d and W p = 0 (k+3)×(|V|+1) | c 0 • e 2 ∈ R N ×d, here e 2 represents the second unit column vector of dimension k + 3, (A | B) is the notation for matrix concatenation by column, and c 0 is a positive parameter to be decided. According to the definition of the Transformer, we now have a matrix H 0 such that the first |V| + 1 columns are the tokens of nodes in the sequence and the last column indicates the positions of the target node t. More specifically, we haveH 0 =        e ⊤ s 0 e ⊤ t c 0 e ⊤ s 0 e ⊤ u1 0 • • • • • • e ⊤ u k 0        ∈ R N ×d ,here e u represents the one-hot token vector for node u (with dimension M = |V| + 1).Then we construct the attention layer of the Transformer. We only have one head and letW K = 0 (|V|+2)×(|V|+1) | 1 (|V|+2)×1 ⊤ ∈ R d×d and W Q = √ d • I d×d . Then we can compute H 0 W K = 0 (|V|+2)×1 | c 0 • 1 (|V|+2)×1 | 0 (|V|+2)×(k+1)⊤ , i.e., second rows are all c 0 's and other rows are all 0's, andH 0 W Q = √ d • H 0 .Therefore,(H0W Q )(H0W K ) ⊤ √ d =   0 c0 0 1×(k+1) 0 c 2 0 + c0 0 1×(k+1) 0 (k+1)×1 c0 • 1 (k+1)×1 0 (k+1)×(k+1)   ∈ R N ×N .And we can compute the first part of the attention layer assoftmax (H0W Q )(H0W K ) ⊤ √ d =     1 k+2+e c 0 e c 0 k+2+e c 0 1 k+2+e c 0 • 1 1×(k+1) 1 k+2+e c 2 0 +c 0 e c 2 0 +c 0 k+2+e c 2 0 +c 0 1 k+2+e c 2 0 +c 0 • 1 1×(k+1) 1 k+2+e c 0 • 1 (k+1)×1 e c 0 k+2+e c 0 • 1 (k+1)×1 1 k+2+e c 0 • 1 (k+1)×(k+1)     ∈ R N ×N .By setting c 0 → +∞, we obtain:softmax (H 0 W Q )(H 0 W K ) ⊤ √ d →   0 1 0 1×(k+1) • • • • • • • • • 0 1 0 1×(k+1)   .Furthermore, we setW V = c 1 • R true 0 |V|×2 0 2×|V| 0 2×2, where c 1 > 0 is also a parameter to be decided later. Then after the attention layer, we have a matrix aslim c0→+∞ MHA(H 0 ) = c 1 •   R true (t,:) 0 0 • • • • • • • • • R true (t,:) 0 0   ∈ R N ×d .Now we construct the feed-forward layer, which is a two-layer MLP.For the first layer, the weight matrix W 1 is set to be,W 1 = I (|V|+2)×(|V|+2) 0 (|V|+2)×3(|V|+2) ∈ R d×4d .and the bias b1 = -c 1 • 1 4d×1 , which implies that 1 N ×1 b ⊤ 1 = -c 1 • 1 N ×4d . When c 0 is large enough, the (k + 3) th row of the matrix max 0, (MHA(H 0 ) + H 0 )W 1 + 1 N ×1 b ⊤ 1 is max 0, c 1 • R (t,:) | 0 1×(3|V|+8) + e ⊤ u k | 0 1×(3|V|+7) -c 1 • 1 1×4(|V|+2) . Since u k can reach t, in c 1 • R (t,:) | 0 1×(3|V|+8) + e ⊤ u k | 0 1×(3|V|+7), only the entry for node u k is c 1 + 1 while all other entries are 0 or c 1 . Therefore, the (k + 3) th row of the matrix max 0, (MHA(H0 ) + H 0 )W 1 + 1 N ×1 b ⊤ 1 can be arbitrarily close to e ⊤ u k | 0 1×(3|V|+7). Here e u represents the one-hot token vector for node u (with dimension M = |V| + 1).For the second layer, we setW 2 = c 2 • A 0 |V|×2 0 (3|V|+8)×|V| 0 (3|V|+8)×2 ∈ R 4d×d ,where c 2 is a positive parameter to be decided, and b 2 = 0. By this way, we havelim c0→∞ (FFN(MHA(H 0 ) + H 0 )) (k+3,:) → c 2 • A (u k ,:) | 0 1×2 ∈ R |V|+2 .Therefore,lim c0→∞ (H 1 ) (k+3,:) → c 1 • R (t,:) + c 2 • A (uj ,:) | 0 1×2 + (e u k | 0) ∈ R |V|+2 ,where e u represents the one-hot token vector for node u (with dimension M = |V| + 1).Then we fix c 1 = c 2 and let them be large enough. In this case, the dominant entries in (H 1 ) (k+3,:) represent the nodes that are both the out-neighbor of u j and reachable to t, since those entries will have the value of 2c 1 while other entries are at most c 1 + 1. This means that (H 1 ) (k+3,:) can correctly indicates the next node u k+1 . Specifically, letW o = I (|V|+1)×(|V|+1) | 0 (|V|+1)×1 ⊤ ∈ R d×M .Then the final output approaches the following vectorlim c0,c1=c2→∞ ûk+1 = lim c0,c1=c2→∞ softmax((H 1 ) (k+3,:) W o ) = 1 C • I[A (u k ,1) = 1 ∧ R (t,1) = 1], • • • , I[A (u k ,|V|) = 1 ∧ R (t,|V|) = 1], 0 ,where C is the number of nodes that are both the out-neighbor of u k and reachable to t. Thus, this encoding guarantees that for any ε > 0 and Q > 0, we can always construct a 1-layer, 1-head, and (|V| + 2)-embedding-size Transformer that provides the correct next token with probability at least 1 -ε 2Q by selecting large enough parameters c 0 , c 1 , c 2 . Then we prove that there exists a Q such that this Transformer can output a correct path for every valid source and target node pair with probability at least 1 -ε. Suppose we can output all the nodes that are both the out-neighbor of the current node and reachable to the target node with the same probability in each round without any error. Then, whatever the current node is, there is a probability of at least ε 2Q • Q + ε 2 = ε.Finally, there are two different rules (other than output a correct next node): i) when the input sequence is only "s t", the prediction of the next token should be the source node s; ii) when the input sequence is "s t s a b c t", the prediction of the next token should be \n. Case i) can be solved using the Transformer architecture utilizing the position information and attention to the first position; and case ii) can be solved by using the Transformer architecture utilizing the position information and attention to the second position. To maintain focus on the main construction corresponding to Algorithm 1, we omit the detailed construction for these two boundary cases.Theorem 3. Under the cross-entropy loss ℓ(D), for all (i, k) pairs, i) if j N i,j = 0, then ∂ℓ(D)∂W M (i,k) is always 0; ii) if j N i,j > 0 but j N i,j,k = 0, then ∂ℓ(D) ∂W M (i,k) is always positive; iii) if j N i,j,k > 0, then ∂ℓ(D) ∂W M (i,k) is negative when W M (i,k) → -∞.Similarly, for all (j, k) pairs, i) if i N i,j = 0, then Then we know that û(n+1) ≈ FFN X 2 W V + X n + X 2 W V + X n W o . Table 1: Cosine Similarity of FFN X 2 W V + X n W o and FFN X 2 W V W o + FFN (X n ) W o Graph 1002 W V + X n W o ≈ FFN X 2 W V W o + FFN (X n ) W o .As shown in Table 1 (which takes average over all possible X 2 's and X n 's), this is a good approximation.Then we can treat FFN X 2 W V W o as the information of the target node, and FFN (X n ) W o as the information of the current node.Because of this, we let W M ′ be the matrix whose i-th row is FFN e⊤ i W t W o + (e ⊤ i W t )W o, where e i represents the one-hot column vector for node i (with dimension M = |V| + 1). Note that in the simplified Transformer model of Theorem 3, there is no X n W o term, andW M ′is the same as matrix W M . Similarly, we let W V ′ be the matrix whose i th row is(e ⊤ i W t )W V W o + FFN (e ⊤ i W t )W V W o, where e i represents the one-hot column vector for node i (with dimension M = |V| + 1). Note that in the simplified Transformer model of Theorem 3, there is no FFN X 2 W V W o term, and W V ′ is the same as matrix W V .In this section, we state the complete experimental results on the synthetic datasets. All these results are conducted on a single A100 GPU.• The accuracy results on all these tests are presented in Figure 7 .• The attention results on all the 1-layer and 1-head Transformers are presented in Figure 8 .• The results of W M ′ 's are shown in Figure 9 . • The accuracy of the Transformers on the (s, t) pairs of the four different categories are shown in Figure 10 .As we can see, all these results are consistent with our conclusions. To further validate the theoretical results in Section 3 and the practicability of the proposed pathfinding task, we consider Blocksworld benchmark [22] . Blocksworld is a scenario consisting of a set of blocks identified by different colors. The blocks are either placed on table or on top of another block and the task is to plan a block manipulation from the source state to the target state.We formulate Blocksworld as a path-finding task. Here we construct a graph G BW for the case with 4 blocks, where each node represents a state of the blocks. For example, node 0 refers to the state that "the red block is on top of the blue block, the blue block is on top of the orange block, the orange block is on top of the yellow block, and the yellow block is on the table". G BW is a directed graph with 73 nodes, and the adjacency matrix of G BW is presented in Figure 11 (a).In the original Blocksworld task, the answer is a sequence of actions, which is equivalent to the notion of edges in G BW . We reformulated it to let the model output a path from the given source state to the given target state, only consisting of the nodes. This can be seen as a simplified version and a pure planning task. We randomly select 80% of all node pairs for training and the rest 20% for testing, and generate 50000 training sequences in the same format as introduced in Section 2. We mainly use Transformers with 1 layer and 1 head for the convenience of visualization.We first present the accuracy results during training when using different embedding sizes d ∈ {30, 60, 120}. As shown in Figure 11(d) , although a smaller embedding size results in a longer time to converge, all models reach an accuracy near 100% at the end of the training.Then, we use the same method introduced in Section 4 to visualize the attention map and the W M ′ matrix for the model with d = 120 after the entire iterations. In Figure 11 (c), we can see that when predicting the tokens on the path, almost all the attention weights are on the second token which represents for the target node, demonstrating the capability of the model to learn a correct attention.For adjacency matrix, we find that the W M ′ matrix in Figure 11 (b) almost perfectly aligns to the real adjacency matrix of G BW . And the weight gap (average edge weight minus average non-edge weight) for all models keeps increasing in the training process until convergence, as shown in Figure 11(e) .In addition, we present the results related to observed reachability matrix in Figure 12 . Figure 12(a) shows the observed reachability in the training dataset. Although G BW is fully-connected, some reachability are not observed since we request that all training data has no cycle. Specifically, in this Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The code is uploaded in the supplementary material. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work mainly contributes to the theory of interpretability and explainability in Transformers. We believe the societal impacts are limited. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We believe this paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.For simplicity, though the layer normalizations LN1,LN2 and LNt are used in our experiments, we omit them in the equations in this section. 
 
 Appendix:  


Decision: Reviewers agreed the manuscript is interesting and sheds some light on the planning capabilities of Transformers. This is topical as Transformers have not taken over in planning in the way they have in NLP. Work that moves us in the direction of understanding what's different between the two settings and why Transformers are suitable for one case but not for the other is useful for the wider community.

Reviewers would have liked to see if the analysis carries over to some more realistic scenarios, but for an initial paper with this framework they found the setting sufficient. Reviewers also note that this is essentially a negative result but without theory to back it up and make it definitive. Scaling to more scenarios to back up the hypothesis and ultimately finding a theoretical justification for the work would make this much stronger. We can't get there without initial investigations, which is what this is and why it merits acceptance and exposure.

Reviews: review: paper_summary: paper_summary: This paper studies the planning capabilities of language models and provides a theoretical foundation for understanding it. The paper investigates the problem by abstracting it as a path-finding problem, showing both theoretically and empirically that transformers can embed adjacency and reachability matrices within their weights. It also highlights their limitations in handling complex planning scenarios.

Main contributions: 
- This paper initiates the theoretical study of planning in autoregressive language models by abstracting it as a path-finding problem. 
- This paper shows that the transformer has the expressiveness to perform path-finding tasks, and gradient descent on cross-entropy loss cause the Transformer to learn necessary but incomplete graph information for the path-finding task. 
- This paper unveils both analytically and empirically that autoregressive training of language models has limitations in the path-finding task.
- The paper analyzes the learning dynamics of a simplified Transformer architecture. It highlights the limitation of transformers to identify reachability relationships through transitivity. 
- The theoretical insights are supported by experiments on synthetic path-finding and a real-world planning task (Blocksworld).

The findings contribute to the broader effort of explaining the power and limitations of large language models.
strength_weakness: strength_weakness: - Although the experiments are thorough. They are limited to specific datasets (synthetic and Blocksworld). The paper can benefit from broader validation across diverse planning datasets.
- In my opinion, the practical implications of the theoretical findings are not fully explored. How to leverage the studies still requires further thinking for readers. Further elaboration could strengthen the paper.
questions: questions: - How do you envision the practical applications of your findings influencing the development of future LLMs, particularly in planning? 
- Very interesting results, do you have similar studies for the other benchmark logistics in Planbench, maybe it also worth conducting this study on neutral plan benchmark. https://arxiv.org/abs/2406.04520 (note: not required for this paper, just a suggestion)
limitations: limitations: The authors addressed the limitations in the paper.
paper_summary: paper_summary: The paper investigates planning capabilities in Transformer-based language models by framing planning as a network path-finding task. It reveals that while Transformers can successfully embed adjacency and reachability matrices to perform path-finding, they struggle with transitivity in reachability, limiting their effectiveness in more complex planning scenarios. These theoretical insights are substantiated with experimental validations using both synthetic and real-world datasets, including the Blocksworld benchmark.
strength_weakness: strength_weakness: - The paper suffers from a lack of logical connections among the introduction, theory, and experiments. For instance, the broad question posed, "Why does next-word prediction generate intelligence?" lacks a clear alignment with specific aspects of their work. It is unclear which parts of their work address this question and to what extent. 
- The clarity of writing needs improvement. For example, the mention of "Project ALPINE" in the introduction is vague, as it does not specify what the project encompasses.
questions: questions: - Could you clarify whether your project encompasses theory, algorithms, or insights? 
- Additionally, it would be beneficial to investigate whether the claims presented in your paper hold up under more realistic setup.
limitations: limitations: - The paper requires a rewrite to better articulate the contributions and clarify the core arguments.
- Further investigation is necessary to assess whether the claims presented hold up under more realistic conditions.
paper_summary: paper_summary: This paper addresses the question of whether or not a transformer-based language model can learn to plan based on next-token prediction. The authors analyse the ability of a transformer-based language model to learn in an abstracted path planning domain, and show that the model can some of the underlying structure of planning problems but has real difficulty in learning to generalise from the training data to be able to solve novel planning problems using relations such as transitivity.
strength_weakness: strength_weakness: There are unfortunately two fairly substantial weaknesses in this paper.

- Firstly, while the paper demonstrates that the specific network architecture chosen cannot deduce the existence of reachability relations that are not observed in the training data, the paper does not adequately describe why there might be any reason to think this. The result that reachability cannot be inferred without observing it is not really surprising, and the brief motivation in the third paragraph of the introduction (describing learned planning) is not really adequate. At the same time, it is a little surprising that the learner does not generalise at all to *similar* reachable concepts.

This weakness could perhaps be addressed in a revised version of the paper through a clearer introduction, and the introduction itself is a little hard to follow. I did not entirely understand where the paper was headed until I got to the end of the paper and read "the Transformer can only learn observed reachability, and will miss those unobserved reachability deduced from the transitivity of the reachability relation." (To be fair, this idea is also present in the abstract, but not strongly present in the introduction.) A clearer motivation for the investigation and why it is reasonable to be unsure about what the Transformer is learning would be extremely helpful.

- The second weakness is that it is not clear the extent to which the lack of inference of reachability is a problem with the specific network architecture. I was surprised that the feed forward layer is a multi-layer perceptron, rather than a graph neural network, as described by Khan et al (2020). Gama et al (2019) showed that GNNs are invariant to graph permutations which make them particularly useful in certain kinds of planning problems. The real problem is that the theoretical result is a positive result about what *is* learnable, and is supported by the experiments, but the primary conclusion of the paper is a negative result. The paper does not have a corresponding theoretical result to justify the negative result, and it is hard not to wonder if the experimental results are an accident of the specific network and training process.

The fact that the "Transformer model has a fundamental difficulty in generating paths for high-degree source-target pairs" may also be an accident of the network architecture, although a GNN formulation would (most likely) need to know ahead of time the degree of the node. 

- The experimental results are reasonable, but the specific planning domains are somewhat ad hoc and not very general. I am happy to see assessment across a range of domain sizes, but the domains are still quite limited. Future work (c) is crucial for these results to become more broadly relevant.
questions: questions: - Why exactly is it not clear whether or not a Transformer can learn
  unobserved reachability? Are there any computational structures that suggest
  that this might be possible, or any domains with a similar kind of inference
  process where transitivity *was* learned and used?

- What possibility is there for a negative theoretical result, that a
  Transformer of this kind could *never* learn to use transitivity and
  therefore infer reachability?

- In Figure 2, why is $R^{obs}(D_3)$ not identical to $R^{true}$, since $D_3$
  is all possible paths?
limitations: limitations: The authors did not provide a limitations section -- the technical limitations
of the work have been addressed in the weakness section.

Comments: comment: We would like to extend our heartfelt thanks for the valuable time and effort you have invested in reviewing our manuscript. Your insightful feedback has significantly contributed to enhancing the manuscript's clarity. We are dedicated to meticulously revising the manuscript in line with your comments.

Could you please provide additional details regarding your further concerns about the paper's writing style and experimental setup? We welcome any further comments or suggestions you may have that could help improve our paper.
Thanks for your comments. Some of my concerns have been addressed, but I still have some concerns about the paper's writing and the experimental setup, so I keep my score. However, I'm open to the opinions of the other reviewers and AC, and I will respect their final decision.
Thank you for your comments and this helped resolve my concerns.
We greatly appreciate your insightful suggestions and comments, which have significantly contributed to the refinement of our paper. We are also thankful for your acknowledgment of our rebuttal efforts. Due to rebuttal space limitations, we cannot explain the rationale for investigating unobserved reachabilities well, which may cause confusion. 

**Definition of Observed Reachability:**
We first revisit the concept of observed reachability, as defined between lines 140 and 154 in our paper. In the context of our experiments, the training dataset is denoted as $\mathcal{D}$. The format for input sequences is 's t s a b c t', where 's' represents the source node, 't' is the target node, and the sequence 's a b c t' constitutes a valid path from 's' to 't'. We define $R^{obs}(t,k)$ as the **observed reachability** from node 'k' to 't', which is determined by the following condition:
$R^{obs}(t,k) = 1,\text{if } \exists u \in \mathcal{D}, n \in [4,N] \text{ s.t. } u_2 = t, u_n = k$, otherwise $R^{obs}(t,k) = 0$. If node 't' can be reached from 's' while $R^{obs}(t,k)=0$, this is considered an **unobserved reachability**.

**Example:**
Consider a training dataset containing two sequences: 'a b a b' and 'b d b c d'. The observed reachabilities are (d,c), (b,b), and (d,d). Conversely, the unobserved reachabilities include reachability through transitivity (i.e., (c,a) and (d,a)) and other reachability that does not satisfy the definition (i.e., (b,a), (d,b), (c,c) and (c,b)). For humans, deducing unobserved reachabilities from the given paths is relatively straightforward.

**Rationale for Investigating Unobserved Reachabilities:**
The motivation for exploring unobserved reachabilities is twofold. Firstly, Algorithm 1 indicates that complete knowledge of all reachabilities is essential for flawlessly completing the path-finding task. Observing the high accuracy of Transformers in path finding, as depicted in Figure 3, leads us to hypothesize that they might infer the true reachabilities. Secondly, Theorem 2 presents a specific configuration of a Transformer's weights that encodes all reachabilities and is capable of finding a path with a high probability. This raises the question: can such weights be derived from the next token prediction loss, a common loss function used by current LLMs?

**Consequences of Inability to Learn Unobserved Reachabilities:**
The findings presented in Theorem 3 are negative, implying that Transformers with next token prediction loss are unable to infer unobserved reachability through transitivity. Besides the failure of finding a path via transitivity, it has practical implications for compositional reasoning in LLMs. Even if an LLM is aware of the reasoning chains $a\rightarrow b$ and $b\rightarrow c \rightarrow d$, it cannot deduce the extended chain $a \rightarrow b \rightarrow c\rightarrow d$ using transitivity. This limitation applies to current LLMs, including GPT-4, as referenced in [1,2].

[1] Wang B, Yue X, Su Y, et al. Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization[J]. arXiv preprint arXiv:2405.15071, 2024.

[2] Yang S, Gribovskaya E, Kassner N, et al. Do Large Language Models Latently Perform Multi-Hop Reasoning?[J]. arXiv preprint arXiv:2402.16837, 2024.
I thank the authors for their clear rebuttal. 
- Regarding the point about whether your understanding aligns with my review, I think we are on the same page about why generalisation might not happen. 
- Regarding the point about learning unobserved reachability, your answer on the difference between next-token-prediction and predicting the entire path is clear and helpful, but I still wish there had been some evidence included in the paper that unobserved reachability might be learnable at all in this way. It's very good to have a negative result, but what led you to asking the question in the first place?  

I am still moderately positively disposed towards this paper, and don't really have any further questions.