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 2024 poster (2024)
Keywords: Planning
Path finding
Transformer
Autoregressive Learning
Language models
Primary area: interpretability_and_explainability

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.

ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models
Siwei Wang!" Yifei Shen Shi Feng" Haoran Sun Shang-Hua Teng" Wei Chen
*Microsoft Research Asia (fsiweiwang, yifeishen, weic)$microsoff com)
haa.eenndaaahhaaaaadddd Speking University (sunhaoran0301@stt pku. edu.puu.ue..eeee. edu. cn)
Harvard University (shifeng@fas. harvard. edu)
Univerrsiyy of Southern California (shanghua@usc. edu)
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-bant next-word prediction mechanisms. We model planning as a network path-finding task, where the objective is to generate valid path from specified source node to a designated target node. Our mathematical characterization shows that Trans- former architectures can execute path-finding by embedding the adjacency and reachability matrices within their weights. Furthermore, our theoretical analysis of gradient-basee based learning dynamics reveals that LLMs learn both the adja- cency and a limited form of the reachability matrices. These theoretical insights are then validated through experiments, which demonstrate that Transformer chitectures 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 current Transformer architectures in aath-finding: these architectures cannot identify reachability re- lationships through transitivity, which leads to failures in generating paths when concatenation is required. These findings provide new insights into how the in- ternal mechanisms of autoregressive learning facilitate intelligent planning and deepen our understanding of how future LLMs might achieve more advanced and general reasonngg capabilities across diverse applications.
LLMs via their
Introduction
Large language models (LLMs) such ChatGPT have impressed many with their powerful capabili- ties across wide range of tasks, including language processing, knowledge extraction, reasoning, planning, coding, tool use, and more [1]. However, we continue 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 predict the next word language sequence, the overarching question remains:
Why does the process of next-word prediction give rise to intelligence?
There is definite answer to this question yet, but researchers are approaching the problem from various angles, aiming to characterize the power and limitations LLMs, as well as to capture their underlying acquisition, abstraction, generalization, adaptation, and reasoning mechanisms.
denotes equal contributions. Corresponding author: Wei Chen treicffmccoooftccom i Supported by Simons Foundation Investigator Award.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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, L.LMs' capability for planning- 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 pivotal role in state-of-the-an 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 L.LMs can or cannot successfully accomplish specific planning tasks (see Appendix A for 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: mathematical proof can be seen proof path from the axioms to the final theorem [21]; and step-by-ster solution to a 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 wath-finding. e.g., an LLM planning benchmark called Blocksworld [22] can be viewed as path- finding from the initial state of the blocks to the final state in 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 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 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 problem-solving 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 project initiates a theoretical investigation into the development of planning capabilities in transformer-based language models by focusing characterizing their expressiveness and learning dynamics in the path-finding task. First, in Theorem 2, we present a mathematical construction of Transformer that encodes both the adjacency and reachability matrices of the network, thereby establishing that Transformer architectures possess the expressive capacity to complete the to minimize the cross-entropy loss on the training data, 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 bath-finding task (Figure 3). Second, we show that it is indeed possible to extract both the adjacency and limited form of the reachability matrices from the Transformers' weights (Figures (22,),(())). Third, we observe a significant drop in test accuracy when the source and target nodes 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 aath-finding problem (see Appendix F).
Our Contributions:
task. Then, in Theorem 3, we prove that when applying gradient descent
2 Preliminaries
Throughout this paper, we use the following notations for matrices and vectors: a and A stand for column vector and a matrix, respectively. Notations a() and A(. denote the 2th entry of vector a and the ji. entry in matrix A, respectively. We also denote the 7th row of matrix A by A(i.)-

---

2.1 Autoregressive Transformer Architecture and Loss Function
In this paper, we adopt the standard GPT architecture [17]. We use the following notation for the architecture and loss function in analysis. Let N denote the sequence length, the embedding size, H the number of heads, dy = 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:
QQK' vdz
Attention Q, K, V) ssotmmax
V
(1)
where Q E Nxd. K R V -Nxx are the query, key, and value matrices, respec- tively. Denoting X E Rxxd as input, the multi-head attention is computed as MHA(X) = Concatsginn(Attennio X XWO, XW; XW.)), where W.O Rdxd, W E Rdx4, W.y E Rdxds are the learnable weight matrices for the query, key, and value matrices of the i-th head.
The feed-forward layer is two-layer multi-layer perceptron (MLP) defined as follows:
( = max(0, 0, X + INNIb W2 + 1Nxib]
(2)
where W1 E ddd W2 14dxd b1 E R24, and by Rd are the learnable weight matrices and 1xx is the all-one matrix with dimension N x z. Finally, one Transformer layer is defined as:
Transformer( X) = FFN(LN,
+ X)) + MHA(LN, - X
where LN, and 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 as u = (#1,'.. u ) in which th, denotes the token id for the n-th token in sequence We first represent the tokens in u by a one-hot embedding matrix E N M. where U(n...)) = 1 and O elsewhere. Then there are learnable token embedding matrix W, E IR xd and positional embedding matrix W, E Nxx and the input H, UW, + W, E R xd This input H, is fed into an L-layer Transformer, i.e., H; = Transformer HH-1) E IR Nxd for / = 1. L.
Finally, the output embedding goes through another layer normalization LN,, and then it is multiplied by a learnable output weight matrix W. E RdxM to convert back to probability weights over all possible tokens. We calculate the output probability vector position n, denoted by (n++1); using ((++1)= softmax((LN)) H (m..) W.), 1 S < 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:
N-1
((u)
Σ
Σ U(+11A) log ((+1),
2.2 PlatnPllannn Dataset: Syntax and Data Sources
The dataset is designed to evaluate GPT's wath-planning capability simple graphs. It is generated from a directed graph G = (V,E), where is the set of nodes, and È is the set of edges. For any two nodes u, U E V. (u, v) & means that there is directed edge from node 8 and target node t is considered a valid pair if 9 contains at least one path from 8 to t.
in G. A pair of source
The training dataset D contains sequences in the format "s ts a b ct \n", where represents the source node token, the target node token, a b c are tokens for nodes in a valid path from s to f, 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 Dynamies of Transformer Models
3.1 Expressiveness
3

---

In our find-finding task, the essential step for completing a path is to predict the next
Algorithm 1 A handerafted path-finding algorithm
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 neces- sary. Algorithm I introduces a idealized method that utilizes both the adjacency and reachability matrices of the graph. The true adjacency matrix A tme and the true reach- ability matrix Rimee are defined as:
1: Input: Adjacency matrix A, reachability matrix
R. source node target node t
2: Set path P = [s s] and set current node =
3: while i + do
4: Obtain 5 = [A.]A(La) = 1 and (t,,)) = 1}
5: Randomly sample next node & from S
6: Append is to path P, and set i = h
7:
end while
8:
output path P
1, if (i, 0. otherwise.
[1, if k can reach t in G,
true A
Riree ((,k)
(1,k)
[o, otherwise.
Fact 1. Assuming that is reachable from s, then Algorithm 1 is guaranteed to output valid path with input A = tr and R = Rmme.
To illustrate the expressive capacities of the Transformer model, we first demonstrate how to manually construct a Transformer that can perform the aath-finding task by simulating Algorithm 1.
Theorem 2. Given a graph 9 (with adjacency matrix A and reachability matrix R! for every e > O, there exists a 1-layer, 1-head, and ((V)))-mbeddiig--te Transformer model that generates a valid path for every valid source source-target pair (s, t) with probability at least 1 E.
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 (see Appendix B).
3.2 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 I?
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 DD Therefore, we define the observed adjacency and reachability matrices based on the training data 'D as follows.
1,
if Bu E D, E [3,N- - 1.t.t. un = i, 2n++1 k
phs (1,)) (D)
0,
otherwise
1,
if E D, E N] s.t. U2 = Un =
R (D)
0, otherwise.
Naturally, the observed adjacency matrix A 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 (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 path (sequence) whose target node t and A 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 at- tention weight is only the target node (the second token), i.e., manually set every row in softmax QKK in Eq. (1) to be a one-hot vector with the second coordinate being 1 (this is vdz
validated in our experiments shown in Figure 4), and set the positional embedding matrix W, = O; b) We remove all the layer normalizations, and use FFN(X) = XWM instead of Eq. (2), Transformer( X) = FFN(X) (X) + MHA(X) instead of Eq. (3); c) The token embedding matrix W. and the output weight matrix W. are set to identity. The embedding size the same as the vocabulary size (d = MM), 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 to represent the weight of the value matrix in the attention layer. Under the above Transformer structure,
(n.) W. (UW, +OUW, W (m..) W. (UW +aU (m..) W (M...)) W
(wais))
where a 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 WWM
(kmss) + (W..))) and the prediction probability 1 equals
exp( WW + W. (aa.k)
(M2.K)
un++1 1.k
E, C WW
WV
(a2.0))
(5)
(u..e)
Let Nij.k be the number of times in DD that: a) the current node is i; b) the target node is j; c) the next node is k, and let No,- = Ex j. then we have the following theorem.
Theorem Under the cruss-entropy loss E(D), all (i, k) pairs, i) E, No. = then
(E is
SW (i.))
always 0; ii) i, No.- > but Σ, NN.j, = O, then DE(D) is always positive; iii) if i3 Nig, > O,
awar (i.M)
then (I(D) is negative when W.M. (1.k) - -o0. Similarly, for all (j, k) pairs, i) if E, Ni. = 0, then aw
BE(D) is always O; ii) if E N15 > 0 but E, Na,. = 0, then aE(D) is always positive; iii) if awY
BWY
Σ, Nij,k > 0, then aE(D) is negative when (.)) - -O0.
BwV (5.03
Proof Sketch. By the definition of the cross-entropy loss in (4),4), and the prediction probability vector in E5), the total cross-entropy loss of the model (with matrices W... W is
((D) = Σ
Ne (i.k) (GA) EN,, log
No.
Σ Eexp(W (i.e) + ((o)
i.
Then we can get that: (the proof for the WV part is similar)
dE(D)
- ENss Nisu + EN
N Σ, exp W M
exp W.
(e.
(ix))
(6)
dW M (1.k)
+ WV
(.0)
In case i), Eg No.- = 0 implies that E, NaJ.K O. Hence
aE(D) awil (i.k)
is always
In case ii). Σ3 No. implies that the second term in Eq. (6) is positive, while E, No. implies that the first term in Eq. (6) is O. Hence
(((D) is always positive. BW
(1.A)
In case iii), when E, No. > 0 and W.M. M (1.) -0, the second term in Eq. (6) converges to 0, and it
is smaller than E, Ni.. O. Hence, aW or
aE(D) is negative when W.M (t,k)
-00.
(c.k)
The above technical theorem directly leads theoretical explanation 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 (D)). For any k) E &D)), No,. 0, and for any (i', k') & E()), E, Ne = 0. Then from the above theorem, under the gradient descent learning paradigm, W. (F.N") will keep decreasing (since its gradient is always positive), while W.M. will not (since its gradient becomes negative when its value is sufficiently (i.k)
negative). This tends to make W.M.
(i.k) higher than W (P) after training. In this way, the Transformer model learns the information about the observed adjacency matrix with matrix M
To facilitate comprehension, we conducted simple experiment on the simplified Transformer, and present the results in Figure 1, In this experiment, we generate 10-node graph, and use different training datasets D1, D2, D3 based on this graph. Dj contains all the paths with length 1; D2 contains
5

---

(a) True adjacency A tuue
(b) W under
(c) W under D2
(d) W under D3
Figure 1: Empirical verification regarding the learning of the adjacency matrix.
(b) R (D,)
(c) R RD((D)
(d) (Ds)
(a) True reachability Tu
(c) WV under D,
(f) W under D2
(g) W under D3
Figure Empirical verification regarding the learning of the observed reachability matrix.
all the paths with length and 20% of the paths with length higher than 1; and D3 contains all the possible paths. Figure ((a) is the true adjacency matrix the graph, which is also the observed adjacency matrix for the three datasets. Figure ((b), (c)) I(d) are the WM M matrices with training datasets D,, D2, D3, respectively. Upon observation, becomes evident that these WM matrices all successfully capture the structural information from the adjacency matrix.
Learning the reachability matrix. Similar to the process of learning the adjacency matrix, since only observed reachable pairs (j, k) have E, Ni > 0, the gradient descent learning paradigm tends to make the WV (j.)) terms corresponding to observed reachable pairs (j. k) higher than the W.V. (F terms corresponding non-observed reachable pairs (j', k²) (which is either not reachable or observed) after the training. In this way, the Transformer model captures the structural information of observed reachability matrix with weight matrix W
Figure shows the correlation between WV and the observed reachabilities under different dataset D's in the above experiment. Figure 2(a) is the real reachability matrix the graph; Figure 2(b), 2(c), 2(d) are the observed reachability matrices in datasets D1, Dr, D3, respectively; and Figure 2(e), 2(f),
2(g) are the WV matrices with training datasets D,, D2. D3, respectively. These illustrations show that all the weight matrices W can satisfactorily learn the information of the observed reachabilities present in the training datasets, but cannot deduce any non-observed reachabilities.
Predicting the next node on path. From Eq.(5), the probability vector for predicting the next node softmax ( (M WY (V...))) where u, represents the current node, and u2 represents the target node. This resembles the procedure in Algorithm 1: it predicts the next node such that both W.M (k,. Je)
is high (corresponding A ((, 1) and W is high (corresponding to R( 1).
Ru2.R)

---

01:01
(a) 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
(d) 400 Nodes
Figure 3: Accuracy on the test datasets with embedding size d 120.
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 informa- tion from the training data through gradient descent training. Moreover, it can utilize this learned information to predict the next node akin to the decision decision-making process of a human algorithm designer in similar scenarios. This suggests that, when confronted with the path-finding 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 's limitation in learning only the observed reachability matrix -without deducing the complete reachability matrix-hints at potential constraints mation 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.
more
the goal-oriented infor-
4 Empirical Evaluations: Peeking into a Trained Transformer
In this section, we conduct extensive experiments on the path-finding task using the general Trans- former architecture as described in Section 2. The datasets are generated as described below.
The DAG is generated randomly based on two parameters: the number of nodes and the probability of edge p = 0.1: For any 1 < i < S n, there is an edge (i,j) E 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 edge (s, t) E E, we always put (s, t) in the training set. For a reachable pair (s, in the training set, we generate m 20 random paths that start at s and end at f, and put these m paths into the training dataset. When generating the random path, at each current node i, we find all the possible & E V such that A (i.k) 1 and ((.))
(i.e.,
there is an edge (i,A) k) E E, and & could also reach the target node t), and uniformly choose a random one in them. Moreover, if ts e E, we always put the one-edge path "s t t {n" in the training dataset to guarantee that all edges appear at least once in the training data.
4.1 Accuracy on Test Dataset
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 model's ss 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 I-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 I-layer and 1 -hhad structure is enough to predict the next nodes accurately. On the other hand, when the
7

---

a 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
(d) 400 Nodes
Figure The average attention in the I-layer and 1-head Transformers.
(a) 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
(d) Average Weight Gap
Figure 5: The first 20 rows and columns of W M' (the red boxes correspond to I's in the adjacency matrix), and the average weight gap between edge terms and non-edge terms in WAr Ad"
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 -llayer and 1-head Transformer models.
4.2 Peeking into a Trained Transformer
Attention. In our analysis, we assume that the attention is fixed on the target node. this true for the Transformer models learned from real data? The corresponding results are shown in Figure These results are obtained by looking into the attention mechanism of the 1-layer and 1-head Transformer models, and showing the average (taking the test dataset) matrix of softmax
[QK" Vdl
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 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 with higher accuracy (Figure 4(a) for = 100 and Figure 4(b) for = 200). This demonstrates that indeed the Transformer model learns the correct attention for the path-finding task, and our assumption the attention weights for the theoretical analysis is reasonable.
this column, especially for those models
Adjacency Matrix. In the 1-layer and 1 -hhea Transformers, let W' (shown in Figure 5) be the matrix whose i-th row FFN (e, W.) W. + (e, W., where e, is the one-hot column vector that represents the token for node i. Based on the Transformer computation, intuitively this matrix one 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 WM matrix and the adjacency matrix are highly aligned: all large entries in the WM matrix correspond to real edges, and all real edges correspond to large entries in the WM matrix. This high accuracy because the embedding size d 120 is higher than the number of nodes 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 product matrices with rank smaller than the graph size. Even so, there still high relevance between WMM M and the adjacency matrix: almost all real edges correspond to large entries in the M' M' matrix.
In Figure 5(d), we show the gap between the average weight corresponding edges (i.e., the average of W M' 's with j and (i.j) E) and the average weight corresponding to non-edges (i.c., (R))

---

the average of W 's with < and (i.5) & 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 I-layer and 1-head Transformers, let W be the matrix whose i-th row is (e, W W. + FFN ((e, W)) W.. where e; 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 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(..)) 's with & 2 k and (t.k) = 1; "real", robs" corresponds to the W(E..) 's with 2 k, R 0 but ( = 1; and "non" corresponds to the W with 2 k and R = O. Here (t.A)
(t.k)
(t.Ai
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 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 quite well, as for those terms in "real') oreal" their weights are almost the same as those in "non". This echoes our analysis.
To further demonstrate that R is not learned good Rots
divide the source-target node pairs (s, t) in the test dataset into four categories: a) degree 0: Riee, = 1; b) degree 1: (s, t) is not of degree O, while has at least one out-neighbor node such that (u, t) is of degree 0, i.e. R = 1; <) degree 2: (s, 1) is not of degree O and 1, while s has at least one out-neighbor node u such that (u, () is of degree I; d) degree or more: the remaining (s,() pairs in the test dataset. Roughly speaking, in our analysis, for (8, 1) pairs of degree 0 or 1, we know that there is a node u such that 1. Then node u will have a large weight, indicating high accuracy. As for A (s.u) 1 and (t.a))
(s, t) pairs of degree 2 or more, there is no node such that both A = 1 and R = 1. In this case, the high- high-weight entry when predicting the next node of is either an adjacent node of or recorded node that can reach t. This should reduce the accuracy.
To see this, we check the accuracy of the Transformers on the (s. 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- I pairs, d pairs, and degree-3 or more pairs respectively (in the graph with 100 nodes, there are no test (x, l) pairs in the d or more category). From these results, we can see that the accuracy for 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 more complex structure (e.g. 6-yayer 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 Trans- former 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.
5 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 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 cross- entropy loss enables them to learn necessary- but incoplete-grape information for path-finding finding.

---

(a) Average Weights
(b) 100 Nodes
(c) 200 Nodes
(d) 300 Nodes
Figure 6: The average weights in WV and the accuracy for (s, with different degrees.
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 capabilities across
LLM frameworks to achieve more advanced and general diverse applications. For instance, in data generation for training, creating more diversified datasets that explicitly cover more reachability relationships may help the model achieve 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 higher training loss. Specifically, when predicting the next token for 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 = and target node = j] Ni.i (as explained in Section 3.2). Learning unobserved reachabilities requires deviating from the distribution defined by the train- ing data, which leads to higher training loss. Consequently, with the current training loss and Transformer architecture, the model cannot learn unobserved reachabilities, such as transitive reacha- bility. 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
Nr.
Our investigation opens several promising directions for future research: (a) Extending our study to hyper- graphs and hyper-pathe where a hyper-edge represents scenarios requiring multiple preconditions to be met simultancously in order to carry out the next step, often seen in task planning and mathematical proofs. (b) Addressing the limitations of Transformers in math-finding and other planning tasks by exploring richer path-finding languages, fine-tuning, or architectural improvements to L.LMs. (c) Examining connections hetween the abstract aath-findin task and conerete planning tasks (e.g., block manipulation in Blocksworid) understand whether, and how, Transformers abstract these tasks into path- frameworks.
Future Directions:
(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 of-thhuthttttttthhh and backtracking capabilities into Transformers for aath-findin,, 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 Al mechanisms.
10

---

References
[1] O. J. Achiam, S. Adler, and et al. GPT-4 technical report. 2023.
[2] Z. Allen--ZZih and Y. Li. Physics of language models: Part 1, context-free grammar. arXiv preprint 230.::::300..3673... 2023.
[3] Z. Allen-Zhu and Y. Li. Physics of language models: Part 3.1, knowledge storage and extraction. arXiv preprini xrXiv22309.133111 2023.
[4] Z. Allen-Zhu and Y. Li. Physics of language models: Part 3.2, knowledge manipulation. arXiv preprint arXiv:2309. 230901402, 2023.
[5] Z. Allen-Zhu and Li. Physics of language models: Part 3.3, knowledge capacity scaling laws. arXiv preprint arX1v:2404.05405, 2024.
[6] Z. Chai, T. Zhang, L. Wu, K. Han, X. Hu, X. Huang, and Y. Yang. GraphLLM: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845, 2023.
[7] G. Feng, B. Zhang, Gu, H. Ye, D. He, and Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances in Neural Information Processing Systems, 36, 2023.
[8] A. Giannou, S. Rajput, Sohn, K. Lee, J. D. Lee, and D. Papailiopoulos. Looped transformers programmable computers. In International Conference Machine Learning, pages I 11398- 11442. PMLR, 2023.
[9] J. Guo, L. Du, and H. Liu. Gpt4graph: Can large language models understand graph structured data? empirical evaluation and benchmarking. arXiv preprint arXiv:2305. /5066, 2023.
[10] W. Huang, Abbeel, D. Pathak, and Mordatch. Language models zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning, pages 91 18-9147. PMLR, 2022.
[1]] N. Lee, K. Sreenivasan, D. Lee, K. Lee, and D. Papailiopoulos. Teaching arithmetic small transformers. arXiv preprint arXiv:2307.0338/1 2023.
[12] X. Liu, Z. Peng, X. Yi, X. Xie, L. Xiang. Y. Liu, and D. Xu. ToolNet: Connecting large language models with massive tools via tool graph. arXiv preprint SiVi:22030008833 2024.
[13] Liu, Z. Lai, Z. Gao, Cui, 7. Li, X. Zhu, Lu, Q. Chen, Y. Qiao, Dai, et al. ControlLI.M: Augment language models with tools by searching graphs. arXiv preprint arXiv:2310.17796 2023.
[14] Z. Luo, X. Song, H. Huang, J. Lian, C. Zhang. J. Jiang, X. Xie, and H. Jin. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.0444 04483, 2024.
[15] W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of precisson transformers. Transactions of the Association for Computational Linguistics, 11:531-555 1-531-545,40 2023.
[16] I. Momennejad, H. Hasanbeig, F. Vieira Frujeri, H. Sharma, N. Jojic, H. Palangi, R. Ness, and J. Larson. Evaluating cognitive maps and planning in large language models with CogEval. Advances in Neural Information Processing Systems, 36, 2023.
[17] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding by generative pre-training, 2018.
[18] Y. Shen, K. Song, X. Tan, D. Li, W. Lu, and Y. Zhuang, HuggingGPT: Solving AI tasks with ChatGPT and its friends in Huggingface. Advances in Neural Information Processing Systems, 36, 2023.
[19] N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
11

---

[20] J. Tang, Y. Yang, W. Wei, L. Shi, L. Su, S. Cheng, D. Yin, and C. Huang. GraphGPT: Graph instruction tuning for large language models. arXiv preprint arXiv:2310.13023, 2023.
[21] H. Trinh, Wu, Q Le, H. He, and T. Luong. Solving Olympiad geometry without human demonstrations. Nature, 625(7995):476-882, 2024.
[22] K. Valmeekam, M. Marquez, S. Sreedharan, and S. Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Information Processing Systems, 36, 2023.
[23] G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar. Voyager: An open-ended embodied agent with large language models, arXiv preprint arXiv:2305.16291 2023.
[24] H. Wang, S. Feng, T. He, Z. Tan, Han, and Y. Tsvetkov. Can language models solve graph problems in natural language? Advances in Neural Information Processing Systems, 36, 2023.
[25] L. Wang. C. Ma, X. Feng, Z. Zhang, H. Yang. J. Zhang. Z. Chen, J. Tang, X. Chen, Y. Lin, et al. survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):1-26, 2024.
[26] C. Whittington, D. McCaffary, J. Bakermans, and T. E. Behrens. How to build cognitive map: insights from models of the hippocampal formation. arXiv preprint urXiv:2202.01633 2022.
[27] K. Yang. J. Ackermann, Z. He, G. Feng. Zhang, Y. Feng, Q. Ye, He, and Wang. Do efficient transformers really save computation? arXiv preprint 24X. 2024.
[28] T. Ye, Z. Xu, Y. Li, and Z. Allen-Zhu. Physics of language models: Part 2.1, grade-school math and the hidden reasoning process. arXiv preprint arXiv:2407.20311, 2024.
[29] Ye, Z. Xu, Y. Li, and Z. Allen-Zhu. Physics of language models: Part 2.2. how to learn from mistakes on grade-school math problems. arXiv preprint arXiv:2408.1629) 2024.
[30] R. Zhang, S. Frei, and P. L. Bartlett. Trained transformers learn linear models in-context. arXiv preprint arXiv:2306.0999 2023.
[31] Y. Zhang, A. Backurs, S. Bubeck, R. Eldan, S. Gunasekar, and T. Wagner. Unveiling Trans- formers with LEGO: synthetic reasoning task. arXiv preprint arXiv:2206.0455 2022.
12

---

A Related Works
A.1 LLMs for Planning
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%, stark contrast to GPT-3's mere 5% success rate [22]. Our paper also proposes 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 identify- ing 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 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 path to the theorem node in the above graph formed by possible lemma nodes and their interdependency edges. However, [21] only focuses using LLMs to generate auxiliary constructions, and the reasoning tasks done by a 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 L.MMs. 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 result, the area of autonomous agents also closely related the path-finding task investigated in this paper.
A.2 LLMs for Graphs
GPT4Graph [9] and NLGraph [24] have developed extensive frameworks for assessing LLMs in the context of graph tasks. These frameworks encompass 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, -hain-of-thought, and algorithmic prompting (c.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 L.MM' performance on graph tasks. Innovations such GraphGPT [20] and GraphLLM [6]. which incorporate 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. 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, c.g., finding Hamiltonian Paths.
13

---

A.3 Algorithm Simulation with Transformers
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 complexity class (note that TC S NC C 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-thoughe prompting has enabled the Transformer to sequentially simulate algorithms, thereby equipping them to tackle P-complete problems in domains such as arithmetic and rrcision-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.
A.4 Mechansims of LLMs
LLMs have demonstrated capabilitiess that exceed the theoretically predicted lower bounds of expres- siveness. 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 trans- formers (not necessarily LLMs) complete various tasks. Standard methods for this analysis include visualizing attention patterns to examine computational properties (such as locality and time invari- ance) 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 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, 51, 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, c.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.
B Proof of Theorem 2
Theorem 2.
Given graph G (with adjacency matrix A and reachability matrix R! for every E > O, there exists a L-layer, 1-head, and -(bbed-eme size Transformer model that generates valid path for every valid source-target pair (s, 1) with probability at least 1 1- e.
Proof. For simplicity, we omit all layer normalizations in this construction. Suppose the input token sequence is "s uj U2 Uy"" with à 2 0, where s (= ug)) and t are the tokens of the source and target nodes, respectively, and nodes s, ....... ug form 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 of ug such that there exists at least one path from uk+11 to / in G.
In essence, we utilize the attention layer to attend the output solely to the target node This approach allows the distribution of next token U4+11 to become a function of both the current node uy and the target node (as formulated in Section 2). Then, by integrating the adjacency matrix A inue into the FFN layer and the reachability matrix Rime into the matrix WV in the attention layer, we extract row vectors Rime and Aime (u).:) from Rime and A respectively, corresponding to the target node t
(t.))
and current node ug- By selecting proper coefficients, we can let the output be the sum of Rime and
14

---

A ()).))- Following the softmax layer, the non non-negligible entries in the final vector correspond to the feasible next nodes. With this encoding, the Transformer serves as simulator of Algorithm 1 with input A tue and R R
Following our notation in Section 2.1, we adopt d = | 2, M = M and N = k + 3. In the Transformer, there are M | + tokens representing the [V] nodes and the end-of-line "An". Hence, the input tokens can be represented by the one-hot embedding matrix U E RNXM
We let Wt = ( 0 E Mxd and Wp (0 ( CD E22 E Rxd here e2 represents the second unit column vector of dimension & + 3, (A B) is the notation for matrix concatenation by column, and is positive parameter be decided. According to the definition of the Transformer, we now have a matrix Hy such that the first [V] + columns are the tokens of nodes in the sequence and the last column indicates the positions of the target node t. More specifically, have
3
e
Co
Ho
E IR
Nxd
Cup
here Es represents the one-hot token vector for node u (with dimension M = +
Then we construct the attention layer of the Transformer. We only have one head and let W (2 ((1++2)x1 Raxd and W /d Iaxd. Then we can compute Ho W.K (2) co +2)xx 0((V++2)((+D)) i.e., second rows are all og and other rows all O's, and Ho W = Vd- Ho.
Therefore.
HOW' (H.
0
O O1x(4+1)
d co Ca ((+1)x
01x(++1) ((++)x((+11
e ERN
Vd
0
And we can compute the first part of the attention layer
HoW (HoW*)y
k+24200
6 +
1424000
11x(++1)
softmax
-1x((+11)
E RNNN
Vd
2
1+24e M2ztoo (((+1)x(4)))
K0242
1
By setting +o0, obtain:
(HoW ) (HOWK)T
0
1
01x(k+1)
softmax
Vd
0
01x(++1)
= -(0 Riruee
0 0 02x2
Furthermore, we set WV
where
is also a parameter to be decided
2x VI
later. Then after the attention layer, have matrix as
Pttuue
0
0
(t.:)
lim MHA(H,) c1 +00
R Nxd
pirue (1.:)
0
Now we construct the feed-forward layer, which a two-layer MLP.
For the first layer, the weight matrix W1 is set to be,
Wi (2(01-2))(11222) O ((11+2)3((11+2)) E Idxid
and the bias bj -c L1ax1, which implies that 1NXI0 -C1 INxad- When co is large enough, the (k 3)th row of the matrix max (0, (MHA(Ho) + Ho 1Nxib
15

---

is max (0, c1 (R(, 0 (1x(31145)) + (en 01x(311177 -1 1 11x4(11+2)). Since us can reach t, in C1 (R)).) 0 (1x(3))+48) + (e Dix(8V147), only the entry for node us is C1 + while all other entries are max (o, (MHA(Ho)
c1- Therefore, the (A: + 3)th row of the matrix Ho) Wi Ixxib;) can be arbitrarily close (e (01x(11147)) Here eu represents the one-hot token vector for node (with dimension M |/ 1). For the second layer, we
0 plx2 ) W₂ = (111++ ((3(M)+8)22)
A
IR Ridxd,
where 02 is a positive parameter be decided, and b2 = 0. By this way, we have lim (F)N(MHA(Ho)) + Ho))(++3.)) 7 (02 A (uc.)) (1x2) 11 200
Therefore.
lim H1)(443)) + (ar RR. + 02 ((sss) 01x2) + (ewx 10) E M+ +00
where eg represents the one-hot token vector for node u (with dimension M = [V] + 1).
Then we fix C₁ C2 and let them be large enough. In this case, the dominant entries in (H +3+.)) represent the nodes that are both the out-neighhor of u, and reachable to i, since those entries will have the value of 2c, while other entries
most c₁ 1. This means that (H1)(8+3.)) can correctly
indicates the next node d2+1- Specifically, let W. (((*++))(I)))) 0(v1+1)x)) E RdxM Then the final output approaches the following vector
lim
u+++
lim softmax (H, (K+3,) (H11)(44,))) W.)
00.01 100--02-00
00 =02
C (T (mA.)) 1A R(..1) = .IA....,,AAAA,,.VV 1 R(,/VD 1),0),
where is the number of nodes that are both the out-neighbor of uy and reachable to f. Thus, this encoding guarantees that for any > and Q > O, we can always construct a 1-layer, 1-head, and (IV] + -embedddingg-sze Transformer that provides the correct next token with probability at least 1 1- & by selecting large enough parameters co, C12 C2. ZQ
Then we prove that there exists a Q such that this Transformer can output correct path for every valid source and target node pair with probability at least 1 - e. 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 io that the target node is reached within the next |V] generated nodes. Therefore, the
(1
p os
target node reached in c3 : |V] steps with probability at least
where e3 E N is a
positive integer. We let C3 logi-- ivor S and Q = c3 |/.. Then, according to the Union bound, the Transformer can output a correct path in Q steps with an error rate of at most 2Q + = =
Finally, there are two different rules (other than output correct next node): i) when the input sequence is only "s (", the prediction of the next token should be the source node s; ii) when the input sequence is "s / b e l", 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.
C Proof of Theorem 3
Theorem 3. Under the cross-entropy loss E(D), for all (i, k) pairs, i) if No. = 0, then
awar 2f is
DE(D)
(1.M)
always 0; ūi) Ef Nug > 0 bul E, Ni.j = 0, then aE(D) is always positive; iii) if E, Nij. 0.
Sw (i.M)
then aw (6,M)
S((D) is negative when W.dd (1,k) - -c. Similarly, for all (j. pairs, i) if E, Ne. 0. then
16

---

D((D) is always 0: ii) if N.N > 0 but Σ, Ni... = O, then aE(D) OW G.4)
OWY is always positive; iii) if
(3.)
E, Nijaa > 0, then 8((D) is negative when WV (f.k) -00.
SW (34)
Proof. We only prove the first part of this theorem, since the proof of the second part is almost identical.
By the definition of the cross-entropy loss in (4) and the prediction weight vector Eq.(5) for our simplified model, the total cross-entropy loss of the model (with matrices W.M, WV) is
((D)
EEE MED n23
U (,) log ū 1n+,)
&
exp W
+ WV
E ΣEΣ
U Un++1,)) log
(ah k))
(w2,k)
uED R23
Σ. exp(
exp(W
WM M
(u).))
+ W
(uz.t)
exp exp(WMM (WM
WV (1.))
ΣΣΣU
U (n+1M) Σ
Tun = u, 501og
(1.k)
Ee exp(
W
(1.1) -W
MED R23 &
exp(W
(i.k) + (.6))
Σ i.i.k
Najk log
Σ, exp(Wall + W
(1.t)
Σ
(i.A) + W.. (we))
+ Σ
Nijia log eexp(WM)))
(6g) + (i)))
Σ
N (i.) + (.o)
Σ
Nes log Σ
exp(WW (i.e) + W(r))
Jj
i
Then we have that
OE(D)
= - NoJ.t+ + ENS,
-NNss N
WWM WV
(6.))
(aa)
OWM
Σ, wxp.WMM M + (w,))
(i,k)
(i.
In case i), E3 Ni.- = 0 1impliss that E, Ni.j, = 0. Hence
aE(D) is always 0.
awir (6.))
In case ii), Ej No. Ne, > 0 implies that the second term in Eq. (7) is positive, while E, No 0
implies that the first term in Eq. (7) is O. Hence a((D) is always positive. 3w
In case iii), when E3 Ni. 0 and W.M. (2,R) converges to xo, then the second term in Eq. (7)
converges to and it is smaller than Ej No..K 0. Hence, a((D) is negative when W.M converges -0.
SW? (i.M)
D The Reason of Choosing WM and W
Note that in the Transformer layer, the output can be written a
QK
QK Vdz
FFN
softmax
+ x
softmax
V X.
Vd
Also noting that we have verified that the attention is concentrated at the second token, then we let X₂ (2.)) W,, representing the token embedding of the target node, and X,, (n.)) W.. representing the token embedding of the current node.
FFor simplicity, though the layer normalizations LN, ,LN and LN, are used in our experiments, we omit them in the equations in this section.
17

---

C1111
4.031
6:411
03407
20144
4.000
0.11
2.:43
C311
5.00
10110
CM111
1.774
0.11M
14:75
C3111
1807
(a) 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
(d) 400 Nodes
(e) 500 Nodes
Figure 7: Accuracy on the test datasets with embedding size d = 120.
Then we know that
(n+ & (FFN (XeWV + +x,) + XVWV + X,) W..
Table 1: Cosine Similarity of FFN X2WV X,) W. and FFN (X,WV W. + FFN (X,) W.
Graph Average Cosine Similarity
100 Nodes
200 Nodes
300 Nodes
400 Nodes
500 Nodes
0.926
0.924
0.901
0.870
0.889
is straightforward that X,, W. contains the information of the current node, and X VWW contains the information of the target node. As for FFN X2W' + +X,) W.. we choose to use its linear approximation FFN (X2 WV + X., W. R FFN (X, WV) W. + FFN (X,,) W, As shown in Table I (which takes average over all possible X2 's and X, 's), this is good approximation. Then we can treat FFN (X2 WV) W, as the information of the target node, and FFN (X,) W. as the information of the current node.
Because of this, we let W be the matrix whose i-th row is FFN (e, Wo) W. + (e. W.) where e; 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, W. term, and WM' is the same as matrix WM, Similarly, we let W be the matrix whose ith row is FFN ((e. W:) W)) W.. where e; represents the one-hot column vector for
(e, W.WWV node i (with dimension M |V| + 1). Note that in the simplified Transformer model of Theorem 3, there is no FFN (X,W*) VV) W. term, and V is the same matrix W.
E Complete Experimental Results on the Synthetic Datasets
In this section, we state the complete experimental results on the synthetic datasets. All these results conducted on a single 1100 GPU.
The accuracy results all these tests are presented in Figure 7.
The attention results on all the I-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, pairs of the four different categories are shown in Figure 10.
As see, all these results are consistent with our conclusions.
18

---

100 Nodes
(h) 200 Nodes
(c) 300 Nodes
(d) 400 Nodes
(e) 500 Nodes
Figure 8: The average attention in 1-layer and 1-head Transformers.
12
(a) 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
223
12.
(d) 400 Nodes
(c) 500 Nodes
Figure The first 20 rows and columns W matrix the 1 1-layer and 1-head Transformers (the red boxes correspond to 1 in the adjacency matrix A).
19

---

(a) 100 Nodes
(b) 200 Nodes
(c) 300 Nodes
(d) 400 Nodes
(c) +5500 Nodes
Figure 10: The accuracy for (s,t)² t)'s with different degrees.
F Path-planning in Blocksworld
To further validate the theoretical results in Section 3 and the practicability of the proposed path- finding task, we consider Blocksworld benchmark [22]. Blocksworld is a scenario consisting of set of blocks identified by different colors. The blocks are either placed on table or top of another block and the task 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 Gew for the case with 4 blocks, where each node represents a state of the blocks. For example, node 0 refers 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 on top of the yellow block, and the yellow block is on the table". Gaw a directed graph with 73 nodes, and the adjacency matrix of G is presented in Figure 11(a).
In the original Blocksworld task, the answer is sequence of actions, which is equivalent to the notion of edges in Gnw- We reformulated it to let the model output a path from the given source state the given target state, only consisting of the nodes. This can be seen simplified version and 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 layer and head for the convenience of visualization.
F.1 Results
We first present the accuracy results during training when using different embedding sizes d e (30, 60, 120). As shown in Figure (d),), although a smaller embedding size results in a longer time to converge, all models reach 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 WM' matrix for the model with 120 after the entire iterations. In Figure Ic()), we can see that when predicting the tokens the path, almost all the attention weights are 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 (b( almost perfectly aligns to the real adjacency matrix of Gaw. 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 1 Il()).
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 GBw is fully-connected, some reachability are not observed since request that all training data has no cycle. Specifically, in this
20

---

6.0
02
06
0.8
1.0
-7.5
-5.
-25
9,6
0.4
0.6
9.6
1.0
10
10
40
Adjacency Matrix of Gaw
(b) The W Matrix
(c) The Average Attention
Accuravy on Test Set
Average Weight CoP
26
1000
120 Berations
2003
2004
3000
244
3004
20:33
2000
2000
Iterations:
(d) Accuracy Curve
(e) Average Weight Gap
Figure 11: Accuracy, attention, and adjacency matrix results for the experiment on Blocksworld benchmark.
0.6
222
04
06
2.0
-5.0
-25
50
25
50 7.
10.0
70-
19
Acarage Weight
40-
1200
1012
2000
1200
(a) Observed Reachability
(b) The WV Matrix
(c) Average Weight Gap
Figure 12: Experiment for reachability on Blocksworld benchmark.
case, each of the first 24 nodes is not observed reachable to any nodes other than itself. To validate whether the Transformer has captured this information, we construct W matrix through the same method presented in Section 4. As shown Figure 12(b), the first 24 columns of the W matrix are noticeably darker, which aligns with the observed reachability matrix in Figure I 12(a). Furthermore, we plot the gap between the average weight of WV on observed reachability and the average weight of W non-observed reachability in Figure 12(c), and find that this gap keeps increasing for all models. Since there does not exist any test pairs with degree or more (as defined in Section 4), we do not compare the accuracy between different degrees in Blocksworld.
In summary, our experimental results on the Blocksworld benchmark confirm our theoretical analyses (Theorem 3) and empirical results on the synthetic data, and they at least partially explain the planning capability of the Transformer on the Blocksworld scenario.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: These claims can accurately reflect the paper's contributions and scope, Details are in Section 3 and Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss some future research directions in Section 5. These are potential limitations of our current work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer:
[Yes]
Justification: All the assumptions are provided, and the complete proofs are stated in Appendix B and Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The code is uploaded in the supplementary material. All the information needed to reproduce the main experimental results provided.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is uploaded in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Pibllic/guides//oeeSStttii sos.eeeeSuummiiisoooooooioo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp. ccppp.ccpppulcc///eecccc/ geaiiiiiiggiee...eeeee /CodeSubmia agionoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Most of these details are explained in Section 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: is explained that all the accuracy results take average over 10000 trials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computer resources is explained in Appendix E.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips: httpp//ss..pppiiiiccceeeeeetdaaa
Answer: [Yes]
Justification:
The research conducted in our paper conforms with the NeurlPS Code of
Ethics.
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 deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration 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 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.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "8tQnzCjtLw", "reviewer": "Reviewer_T9s7", "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.\n\nMain contributions: \n- This paper initiates the theoretical study of planning in autoregressive language models by abstracting it as a path-finding problem. \n- 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. \n- This paper unveils both analytically and empirically that autoregressive training of language models has limitations in the path-finding task.\n- The paper analyzes the learning dynamics of a simplified Transformer architecture. It highlights the limitation of transformers to identify reachability relationships through transitivity. \n- The theoretical insights are supported by experiments on synthetic path-finding and a real-world planning task (Blocksworld).\n\nThe findings contribute to the broader effort of explaining the power and limitations of large language models.", "questions": "- How do you envision the practical applications of your findings influencing the development of future LLMs, particularly in planning? \n- 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": "The authors addressed the limitations in the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: The approach to studying planning capabilities through path-finding in LLMs is novel and insightful. The theoretical aspects are very interesting and inspiring. \nQuality: The theoretical studies are well-supported by empirical evidence from synthetic and real-world datasets .\nClarity: The paper is well organized, with clear definitions, methodologies, and analysis of results. \nSignificance: Understand from a theoretical perspective and conduct empirical studies may help advance its capability in planning.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable input. Below, we will address your questions and suggestions concerning potential weaknesses in this paper.\n\n---\n\n**Weakness 1**: Broader Validation across Diverse Planning Datasets Can be more Beneficial\n\n**Answer**: As mentioned in Section 5, under Future Works (c), we plan to extend our experiments to include a broader range of planning datasets. We hope that this comprehensive expansion of real-world applications will enhance the robustness of our theoretical findings by validating them across more diverse and representative scenarios, while also sharpening our understanding of the limitations of commonly used transformer-based LLM models.\n\n---\n\n**Weakness 2**: More on Practical Implications Will Strengthen the Paper\n\n**Answer**: While our primary focus was on presenting theoretical analyses aimed at gaining insights into the planning capabilities of language models, we agree that discussing the practical implications is essential. In the final version, we will expand on these aspects; for instance, please refer to the response to Question 1 below.\n\n---\n\n**Question 1**: Practical Applications in Future LLM Development\n\n**Answer**: Our study demonstrates that the current Transformers can learn observed reachabilities but struggle with unobserved ones. \n\nThe latter poses a challenge in planning tasks with limited training data. For instance, given paths \"$a$ $c$ $a$ $b$ $c$\" and \"$c$ $e$ $c$ $d$ $e$\" in the training data, the Transformer may not learn how to transition from $a$ to $e$, since it does not know $b$ can reach $e$. This indicates that the existing Transformer architecture is insufficient for achieving human-like planning capabilities. A practical implication is composition reasoning: if LLMs know the reasoning chain from $a\\rightarrow b \\rightarrow c$ and the chain $c\\rightarrow d \\rightarrow e$, can they perform reasoning $a\\rightarrow b \\rightarrow c \\rightarrow d \\rightarrow e$ through transitivity? The results are consistently negative even for GPT-4 [1,2]. To address this, new Transformer structures that can infer unobserved reachability might be required.\n\nFrom this perspective, the practical applications of our findings include:\n1) Understanding how current language models perform planning, i.e., by encoding observed adjacency and reachability in their weights. This can guide us in designing datasets that enable these models to perform well after training.\n2) By showcasing the limitations of current language models, our study provides a fundamental motivation for future research into models with different Transformer architectures.\n3) Our simplified demonstrative example serves as a simple yet effective testbed for evaluating new models' capacities in planning, facilitating the development of models that can handle unobserved reachabilities.\n\n---\n\n**Question 2**: Experiments on Other Benchmark Datasets\n\n**Answer**: We are planning to experiment on other planning related datasets in our next step of research. We believe that by framing planning tasks as path-finding problems and using a suitable abstraction to represent all states as unique tokens---similar to our approach in the Blocksworld example (Appendix F)---the results will likely align with our current findings. Additionally, exploring whether Transformers can perform abstractions on these datasets and understanding how they might do so presents another interesting avenue for future research, which we are currently actively pursuing.\n\n---\n\n**References**:\n\n[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.\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mMN9lW4Q85", "reviewer": "Reviewer_znJo", "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.", "questions": "- Could you clarify whether your project encompasses theory, algorithms, or insights? \n- Additionally, it would be beneficial to investigate whether the claims presented in your paper hold up under more realistic setup.", "limitations": "- The paper requires a rewrite to better articulate the contributions and clarify the core arguments.\n- Further investigation is necessary to assess whether the claims presented hold up under more realistic conditions.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses a highly significant problem, which is crucial for advancing the field.\n- The experimental setup proposed is straightforward yet appears effective, which is commendable.\n- The authors have made efforts to approach the topic from both theoretical and empirical perspectives, enriching the study.", "weaknesses": "- 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. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your valuable input and helpful suggestions. Below, we will address your questions and concerns regarding potential weaknesses in this paper.\n\n---\n\n**Weakness 1**: About logical connections and the posed broad question: \"Why does next-word prediction generate intelligence?\" \n\n**Answer**: Thank you for highlighting this issue. Yes, we will address it by improving the introduction to better clarify the structure and connections.\n\nTo provide a clearer overview, our research takes a step toward addressing the overarching question: \"Why does next-word prediction generate intelligence?\" Specifically, we explore this through the lens of planning, a critical component of intelligence, by investigating how next-word prediction facilitates planning, conceptualized as path-finding tasks in unknown networks. This conceptualization is motivated by the planning involved in mathematical proofs, task planning in language agents, and controlled experiments in neuroscience (Lines 43-53).\n\nIn this conceptual framework, the language model must effectively learn from path samples of an unknown \"ground truth\" network to solve path-finding problems. In our work, we conduct both theoretical analyses and targeted experiments to understand the expressiveness and limitations of commonly-used Transformer-based language models in learning to solve path-finding problems from observed path samples. Theoretically, in Section 3.1, we establish that Transformers possess sufficient expressive power to adapt their parameter weights to encode adjacency and reachability matrices. Complementarily, our mathematical analysis of training dynamics in Section 3.2 reveals a fundamental limitation: Transformers trained via next-token prediction can learn adjacency and a limited form of reachability but cannot fully capture reachability through transitivity.\n\nTogether, these theoretical analyses establish the following: On one hand, the encoding capabilities of Transformers enable Transformer-based language models to solve path-finding tasks effectively when path samples provide sufficient structural information about the underlying network. On the other hand, due to their limited capacity for transitive inference, commonly used Transformer models may struggle to generalize beyond the observed training data to deduce new reachabilities, unlike human reasoning. A practical implication is composition reasoning: even if LLMs know the reasoning chain $a\\rightarrow b \\rightarrow c$ and the chain $c\\rightarrow d \\rightarrow e$, they cannot perform reasoning $a\\rightarrow b \\rightarrow c \\rightarrow d \\rightarrow e$ through transitivity. This holds for existing LLMs including GPT-4 [1,2].\n\nIn Section 4, we provide targeted experiments to validate these theoretical findings, demonstrating results consistent with our analysis.\n\nWhile our focus is on the power and limitations of the current \"general purpose\" Transformer architecture, which is not specifically designed for path-finding tasks, we hope these findings will contribute to designing enhancements for Transformer-based language models and developing learning models tailored for path-finding (and planning) tasks.\n\n---\n\n**Weakness 2 and Question 1**: About the clarity of writing and what the ALPINE project encompasses.\n\n**Answer**: The project \"ALPINE\", which stands for **A**utoregressive **L**earning for **P**lanning **I**n **NE**tworks, encompasses conceptualizing planning as path-finding in networks, theoretical analysis on the Transformer structure and auto-regressive loss, and empirical validation of the theoretical analysis. The theoretical analysis also give us some insights about \"how the current Transformer do planning\", and \"what are limitations in the planning capacity of current language models\".\n\nWe appreciate your suggestion and will clarify these aspects in the final version to ensure a more precise and comprehensive presentation.\n\n---\n\n**Question 2**: More realistic setup. \n\n**Answer**: We acknowledge the importance of testing our findings in more realistic setups. While our current paper includes an example from Blocksworld from PlanBench in Appendix F, where we use an abstraction to represent all states as unique tokens, we recognize the need for further exploration in more complex and realistic datasets. As mentioned in our future work (c) in Section 5, we plan to extend our research to include such datasets, and aim to investigate whether Transformers can effectively perform abstractions and whether our findings still hold in more realistic scenarios. This line of inquiry, however, is beyond the scope of the current paper and will be summarized into a subsequent paper. Thank you for your suggestion.\n\n---\n\n**References**:\n\n[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.\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YKfD2u5jTc", "reviewer": "Reviewer_wPpp", "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.", "questions": "- Why exactly is it not clear whether or not a Transformer can learn\n  unobserved reachability? Are there any computational structures that suggest\n  that this might be possible, or any domains with a similar kind of inference\n  process where transitivity *was* learned and used?\n\n- What possibility is there for a negative theoretical result, that a\n  Transformer of this kind could *never* learn to use transitivity and\n  therefore infer reachability?\n\n- In Figure 2, why is $R^{obs}(D_3)$ not identical to $R^{true}$, since $D_3$\n  is all possible paths?", "limitations": "The authors did not provide a limitations section -- the technical limitations\nof the work have been addressed in the weakness section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The overall idea of this paper is pretty strong.\n- The specific problem the authors address is important and relevant, especially determining if a transformer can learn to solve novel planning problems by inferring unobserved relations.\n- The formulation of the analysis is reasonably strong. The combination of Theorem 2 and Theorem 3 are a statement about the expressive capacity of the model, but the limitations on the learning process.\n- The experimental results do a reasonable job of supporting the theoretical analysis and claims of the paper.", "weaknesses": "There are unfortunately two fairly substantial weaknesses in this paper.\n\n- 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.\n\nThis 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.\n\n- 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.\n\nThe 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. \n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1**: Need to Improve Logical Connections and Clarity\n\n**Answer**: Thank you for highlighting the need for a clearer introduction and improved logical flow. We will revise the paper accordingly. \n\nYour comment suggests that the inability of LLMs to deduce transitive reachability is reasonable and questions why it is desirable for LLMs to have this capability. We believe this is important because transitivity is a basic property in logic. Since LLMs are often considered close to AGI, it is natural to question whether they can deduce transitivity. Many studies focus on basic properties in logic, such as symmetry [1] and composition [2]. Moreover, we construct a Transformer with perfect performance in path-finding in Theorem 2. This suggests that a Transformer could potentially achieve perfect performance through appropriate training procedures. However, we demonstrate that this is not the case for Transformers trained via next-token prediction.\n\nRegarding the ability to generalize, our analysis shows that no generalizations occur when the embedding size is sufficiently large. A similar phenomenon is reported in [1]. We are unsure if our understanding aligns with your review, particularly the point about the learner's lack of generalization to similar reachable concepts. If you have a different perspective, please feel free to share it with us, and we would be happy to address it during the discussion period.\n\n---\n**Weakness 2**: Network Architecture Beyond Multi-Layer Perceptrons and Theoretical Justification\n\n**Answer**: In this paper, we aim to study the path-finding task capacity and performance of language models based on the standard Transformer architecture, which is a general-purpose design not specifically intended for graph tasks. Given that the standard Transformer, as specified in the original paper [3] and used in most other LLMs such as Llama-3, employs MLPs in their models, we consider MLPs in our study. While using a GNN instead of an MLP in the Transformer architecture may offer some advantages, it can also introduce several additional challenges, such as requiring prior knowledge of the node's degree, which is beyond the scope of our paper.\n\nRegarding the negative result, we emphasize that we have corresponding theoretical analysis to support this outcome. According to Theorem 3, all unobserved reachability terms $W^V_{j,k}$'s always have a positive gradient, meaning they will continuously decrease during a gradient descent learning procedure. Consequently, unobserved reachability will not be learned in theory. Therefore, \"Transformer model has a fundamental difficulty in generating paths for high-degree source-target pairs\" is not merely coincidental.\n\n---\n**Weakness 3**: Experiments on More Domains\n\n**Answer**: We appreciate the feedback on the limitations of our experimental domains. We agree that broader and more realistic datasets are crucial for validating our findings. While our current paper includes a Blocksworld example from PlanBench in Appendix F, we plan to extend our research to encompass a wider range of datasets in future work. This will help us determine whether our findings hold under more complex and realistic scenarios. This line of inquiry, however, is beyond the scope of the current paper and will be summarized into a subsequent paper. \n\n---\n**Question 1 and Question 2**: Possibility of Learning Unobserved Reachability\n\n**Answer**: This is a very good point. In our future work (b), we mentioned that one important future research topic is to improve the Transformer structure to enable the model to learn unobserved reachability.\n\nThe difficulty in learning unobserved reachability with the current Transformer structure arises from the nature of the next-token-prediction loss---learning unobserved reachability results in a higher training loss: \nWhen predicting the next token with current node $i$ and target node $j$, the distribution of the next token that minimizes training loss  follows the corresponding distribution in the train dataset, i.e., $\\Pr[\\text{output} = k | \\text{current node} = i \\text{ and target node} = j] = \\frac{N_{i,j,k}}{N_{i,j}}$. If unobserved reachabilities are recorded, they will alter the distribution from $\\frac{N_{i,j,k}}{N_{i,j}}$, incurring a higher training loss.\n\nTherefore, we believe that the next-token-prediction loss is one of the reasons the model cannot learn unobserved reachability. With this training loss and current Transformer structure, the model cannot learn to use transitivity as it results in a higher training loss.\n\nHowever, if another loss is used, such as the accuracy of paths, the Transformer may be able to learn the unobserved reachability. Additionally, if we can improve the Transformer structure to enable the model to \"deduce\" unobserved reachabilities without recording them, the model may also perform well in the path-finding task.\n\nWe will include a discussion on this topic in our final version. \n\n---\n**Question 3**:  Clarification for $R^{obs}(D_3)$\n\n**Answer**: The distinction between $R^{obs}(D_3)$ and $R^{true}$ arises because $R^{obs}$ includes only the reachability pairs $(j, k)$ where $j$ is a target node and $k$ is a non-source node in the training paths. If $k$ can only be a source node in any path, then reachability $(j, k)$ cannot be included in $R^{obs}$ for any $j$. Consequently, as shown in Figure 2, $R^{obs}(D_3)$ omits all reachabilities involving $k = 0, 1, 4$, since there are no edges pointing to these nodes.\n\n\n---\n**References**:\n\n[1] Zhu H, Huang B, Zhang S, et al. Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics[J]. arXiv preprint arXiv:2405.04669, 2024.\n\n[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.\n\n[3] Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need[J]. Advances in neural information processing systems, 2017, 30.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)