Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems?
While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities

in realistic parameter regimes is lacking.
investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution.

Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes.

We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks.

We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark.
These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.

§ INTRODUCTION

The transformer neural network architecture, which was initially introduced for neural machine translation <cit.>, quickly became the standard neural network architecture across many fields, powering recent breakthroughs in language modeling <cit.>, computer vision <cit.>, and natural sciences <cit.>.
Across fields, transformers have superseded other architectures, surpassing them in downstream performance while maintaining reasonable computational footprint.

How can we analyze reasoning capabilities of neural networks?
One approach is to study algorithms executable with their internal representations.
Neural algorithmic reasoning <cit.> is a field of research dedicated to exploring such capabilities.
Algorithmic execution is desirable because models use it to generalize out-of-distribution <cit.> and scale to larger problem sizes <cit.>.

In this work, we focus on classes of transformers solving algorithmic reasoning problems on graphs.
Why graph problems in particular?

Recent research by <cit.> suggests that graphs are an ideal abstraction of complex reasoning with dependencies, including chain-of-thought <cit.> and its generalizations <cit.>.

Furthermore, we investigate graph reasoning in order to evaluate transformer capabilities compared to specialized models that explicitly capture the structure of data.
Graph neural networks (GNNs) <cit.> offer strong baselines for algorithmic reasoning <cit.> and comprehensive theoretical frameworks for their capabilities and limitations <cit.>.

The complexity of graph reasoning tasks varies greatly; some are easily solved by non-graph architectures and others require sophistication beyond standard GNNs <cit.>.
This makes graph tasks a compelling testbed for both theoretical and empirical evaluations.

While transformer-based models are commonly optimized for downstream performance <cit.>, theoretical investigations of transformer capabilities in realistic parameter regimes have been limited.

We analyze the capabilities of standard transformer models to solve graph reasoning tasks by employing a graph tokenization scheme similar to <cit.>; see <Ref> for a graph encoding example.
We generalize the insights of <cit.>—which established that graph connectivity can be computed in a more depth-efficient manner with transformers than GNNs—to broader families of graph reasoning tasks.
We also study the representational impacts of blank tokens, which can be thought of as a theoretically-tractable version of either chain-of-thought prompting <cit.>, scratch space <cit.>, or pause/filler tokens <cit.>.

We conduct an extensive study of graph reasoning problems with transformers from both theoretical and empirical perspectives. We summarize our principal contributions as follows:

* We introduce a novel representational hierarchy of graph reasoning tasks that formalizes reasoning capabilities of transformers in several realistic parameter scaling regimes.
This includes two graph reasoning task classes—which we refer to as the parallelizable and search tasks and include well-known algorithmic tasks like connectivity and shortest path respectively.

* We prove that logarithmic-depth transformers are necessary and sufficient to solve parallelizable tasks in a highly parameter-efficient manner; similar constructions for search tasks employ much larger networks.
We distinguish both of these classes from an easier family of problems—retrieval tasks, such as node count and edge existence—by showing that retrieval tasks can be efficiently computed by single-layer transformers, while parallelizable and search tasks cannot.

* We empirically validate our representational contrast by showing that transformers outperform GNNs on tasks that require the analysis of long-range dependencies, including parallelizable tasks like connectivity.
Our experiments suggest that GNNs perform better on simpler tasks that require only local analysis of neighboring nodes in low sample-complexity regimes, benefiting from their well-aligned inductive bias.

§ RELATED WORK

*Fundamental capabilities of transformers.

The graph encoding scheme employed in our theoretical and empirical analysis that presents a graph reasoning task (e.g. connectivity) as a tokenized input to a standard transformer model.

Early representational research <cit.> established the universality of transformers by simulating Turing machines step-by-step, albeit in an unrealistic polynomial-depth scaling regime.
These universality results were extended to bounded-depth transformers with chain-of-thought tokens <cit.>, but with a persistent gap between positive and negative results.

A more fine-grained theoretical approach established the limitations of bounded-size transformers by relating them to threshold circuits, implying that $\L$-complete tasks like graph connectivity are unsolvable by constant-depth transformers <cit.>.
However, these circuit complexity reductions are not bidirectional and their positive results pertaining to classes of regular languages <cit.> reveal little about when tasks like connectivity can be expressed.

The closest analytical framework to ours characterizes transformers as distributed computing protocols by quantifying the informational bandwidth of their self-attention units.
This line of work sharply separates transformers from other architectures and provides width and depth separations <cit.>.
The ability of transformers to simulate finite-state automata in logarithmic depth provides a further roadmap for how transformers efficiently leverage parallel computation <cit.>.

*Empirical analysis of transformer reasoning capabilities.

Multiple empirical investigations explore the algorithmic capabilities of transformer-based models <cit.>.
Graph reasoning problems have been used to evaluate capabilities of transformer-based LLMs <cit.> including works with graph-specific GNN adapters <cit.>.
In the empirical part of our study, we use the GraphQA dataset <cit.>—which was evaluated initially on LLM prompting appraoches and later on GNN-augmented prompts <cit.>—to validate our complexity hierarchy and compare transformers with GNNs and prompt-based LLMs on a selection of graph reasoning tasks.

*Transformers and graph neural networks.

GNNs provide a useful benchmark for model expressivity on graph inputs.
For instance, the inability of GNNs to efficiently solve “global structure” tasks like subgraph connectivity made evident by a connection to the  distributed computing model <cit.>.
A further connection <cit.> to the Weisfeiler-Lehman (WL) isomorphism heuristic <cit.> captures the inability of feature-less GNNs to distinguish certain graph instances <cit.>.
See <Ref> for a further discussion of the representational limitations of GNNs.

Graph transformers <cit.> integrate the transformer architecture with graph-structured data.
While GNNs can simulate the WL test <cit.>, transformers can simulate GNNs and exceed their WL limitations <cit.>; they are strictly more expressive than 2-WL <cit.>.
Despite our focus on standard transformers, our empirical results in <Ref> include comparisons to a wide range of GNNs.

§ HARDNESS TAXONOMY OF TRANSFORMER GRAPH REASONING TASKS

We provide our core result: a rigorous quantification of the hardness of graph reasoning tasks for transformer-based models.
While graph reasoning tasks, like other algorithmic problems, can be categorized into well-known computational and circuit complexity classes (e.g. $\textsf{TC}^0$, $\L$, $\NL$, $\textsf{NP}$, $\textsf{NP}$), the relationship between membership in these classes and the hardness of solving a task with a parameter-efficient neural network is not immediately obvious.
Our hierarchy bridges the gap between these worst-case computational classes and the representational capabilities of bounded-size transformers of different parameter scaling regimes.
These regimes include transformers whose depth $L$ scales with the input sequence length $N$; this contrasts with most theoretical results, which study on the constant-depth regime.

Our positive and negative theoretical results employ the transformer model of <cit.>, which is presented in <Ref> and assumes that the embedding dimension $m$ grows less rapidly than than the sequence length $N$ and that the multi-layer perceptrons (MLPs) are arbitrary functions.
The result is a model of a transformer as a bounded-capacity communication protocol.
In this model, arbitrary functions of each individual embedding vector can be computed, but the interactions between these vectors are restricted by the low-rank of the attention matrix.
The relevance of this model is motivated by the rapid scaling in the context lengths of modern transformers in recent years and the high ratio of MLP parameter count to the embedding dimension each operates on.

This model also permits the inclusion of blank pause token inputs of <cit.>, which provide additional computational power to the transformer model by extending the computational “tape” without introducing new information about the input.

These results divide the tasks that are we empirically investigate in <Ref> into three difficulty families based on the hardness of solving the task with parallel computation.

* Retrieval tasks—including node count, edge count, edge existence, and node degree—are tasks that can intuitively be solved by a single lookup step or global aggregation.
These are the easiest tasks in our framework, and we show in <Ref> that these retrieval tasks can be computed by a single-layer transformer with small embedding dimension. (In contrast, all other examined tasks cannot be solved in that regime.)

* Parallelizable tasks—including connectivity, connected nodes, and cycle check from the experimental results and a host of other graph reasoning tasks, such as bipartiteness, planarity, and minimum spanning forest—are non-trivial tasks that can be solved efficiently in a parallel computation setting. <Ref> establishes that these tasks can be solved by bounded-size transformers with logarithmic depth.

* Search tasks—including shortest path and other tasks like diameter and directed reachability—comprise a harder family of tasks that are less easily solved by parallel algorithms.
In <Ref>, we prove that these tasks belong in an equivalence class and exhibit large-model scaling regimes where they can be computed.

The representational hardness of these classes is quantified by several results that determine whether transformers that obey different parameter scaling rules can compute them.
We define the following scaling regimes for the depth $L$, embedding dimension $m$, and number of “pause” tokens $N'$ of a family of transformers as a function of the size of the input graph, $N = O(|V| + |E|)$.

(D1): Single-layer multi-headed transformers with small embedding dimension $m = O(\log N)$ without any pause tokens.

(LD): Transformers with depth $L = O(\log N)$, embedding dimension $m = O(N^{\epsilon})$ for any fixed $\epsilon > 0$, and no pause tokens.

(LDP): Transformers with the same depth and width constraints as , with at most $N' = \poly(N)$ blank “pause” tokens appended to the input sequence.

(LDW): Transformers with depth $L = O(\log N)$, embedding dimension $m = O(N^{1/2 + \epsilon})$, and no pause tokens.

Our positive and negative results that relate scaling regimes and graph reasoning tasks are displayed in <Ref>.
We present high-level result summaries in the following sections with proofs in Appendix.

The complexity hierarchy

Example tasks and their complexity.

A summary of the theoretical hierarchy of <Ref> that visualizes which type of graph reasoning tasks can be solved in which transformer scaling regime ( (D1),  (LD),  (LDW) and  (LDP)).

The most technically significant results concern  models and are provided in <Ref>.
These bounds are consequences of <Ref>, an improved analysis of the relationship between transformers and the massively parallel computation (MPC) distributed computing model of <cit.>[
MPC is a theoretical model of the MapReduce computational paradigm that distributed computation among a large number of machines with restricted local memory size and communication bandwidth.
We formally introduce the MPC model in <Ref>.
This connection between MPC and transformers is a sharp improvement of a similar result by <cit.>.

For constant $\delta, \epsilon >0$, any $R$-round MPC protocol with $N$ machines with $O(N^\delta)$ bits of local memory each can be simulated by a transformer of depth $L = O(R)$ and embedding dimension $m = O(N^{\delta + \epsilon})$.

Results pertaining to  are stated in detail and proved in <Ref>.
In addition, we discuss the triangle counting task (and the more general clique counting task) in <Ref>, where we show a distinct result for much smaller depth ($L = O(\log\log N)$) that includes pause tokens.

§.§ Parallelizable tasks and  transformers

We define the family of parallelizable tasks to consist of graph reasoning tasks that are $\L$-complete and are equivalent to graph connectivity in $O(1)$-rounds, as proved by <cit.>.
This family includes (but is not limited to): graph connectivity, minimum spanning forest, cycle detection, $st$-connectivity, number of connected components, graph bipartiteness, planarity testing, and one-cycle vs two-cycles testing.
While graph connectivity and minimum spanning forest were shown to be computable by logarithmic depth transformers with small polynomial width () by previous work <cit.>, this poses broader questions:
Are all parallelizable graph reasoning tasks computable by a transformer of logarithmic depth and small embedding dimension? And do sub-logarithmic-depth transformers exist that solve any parallelizable tasks?

We first show that all parallelizable tasks can be solved in two logarithmic-depth scaling settings.

For any parallelizable task, there exists transformers in  and  that solve the task.

<Ref> is stated formally as <Ref> and proved in <Ref>.
Both components of the theorem are a consequence of a novel relationship between the MPC model and transformers (<Ref>) and the analysis of MPC protocols for graph reasoning tasks by <cit.>.
The  result is the direct implication of an $O(1)$-round MPC equivalence (<Ref>) between all parallelizable tasks and an MPC protocol that solves the connectivity task (<Ref>).
The  bound is a consequence of <Ref>, which shows that all languages in $\NC^2$ (including all languages in $\L$ and $\NL$) can be evaluated by an MPC protocol with $O(\log N)$ rounds and with local memory $O(N^{1/2 + \epsilon})$ <cit.>.

We further prove the conditional optimality of logarithmic depth.

Conditional on <Ref>, any transformer that solves some parallelizable task with width $mH = O(N^\epsilon)$ and pause tokens $N' = \poly(N)$ must have depth $L = \Omega(\log N)$.

This result (stated formally as <Ref> is a combination of the conditional depth lower bound on graph connectivity by <cit.> and the $O(1)$-round equivalence between all parallel tasks.

§.§ Search tasks

Search tasks are similarly defined to be those that are $\NL$-complete and equivalent to shortest path in $O(1)$-rounds of MPC and include shortest path, strong connectivity, $st$-reachability, radius, diameter, and median.
Like before, the $O(1)$-round MPC equivalence translates to an $O(1)$-depth equivalence in transformers.
We give a similar positive result for  transformers; whether these tasks can be solved by  transformers is unknown.

For any search task, there exists a transformer in $\logdepthwide{}$ that sovles the task.

This theorem, which is restated in <Ref> as <Ref>, is also an immediate consequence of <Ref>.

While the minimum depth of a transformer with small embedding dimension that solves a search task is not identified, we prove that the minimum depth needed to solve some all search task is approximately equivalent in <Ref>.

§.§ Retrieval tasks and  transformers

Graph tasks whose algorithms consist of a single look-up or aggregation step can be efficiently solved by single-layer transformers.
This result assumes that the graph $G = (V, E)$ is encoded as some input sequence $X$ of length $N = O(|V| + |E|)$ that expresses each edge and vertex a single token.
This encoding scheme is detailed in <Ref>.

For any retrieval task (including node count, edge count, edge existence, and node degree) there exists a transformer in  that solves the task.

We formalize this statement in <Ref> and prove it their in <Ref>.
These rely on proving the existence of a useful input MLP $\phi$ that precomputes embeddings with useful structure for all retrieval tasks.

Note that these results only pertain to approximation.
While small transformers exist that solve tasks like node degree, they imply little about whether those tasks are learnable.
In the previous section, we conjectured that the failure of transformer models to solve node degree as effectively as GNN-based models is due the difficulty of associating degree outputs with corresponding edges.
In contrast, the communication restrictions of GNNs between neighboring nodes is a favorable inductive bias for such locality-based graph reasoning tasks.

In contrast, we show that a collection of parallelizable and search tasks cannot be efficiently solved by transformers in .

Any single-layer transformer that solves the graph connectivity, shortest path, or cycle detection task

has width satisfying $mH = \tilde\Omega(N)$.

The proof of the formal counterpart of this statement (<Ref>) appears in <Ref> and is a consequence of a standard communication complexity argument.
A more generalized result than <Ref> was proved by <cit.>, which establishes that all problems outside of $\NC^1$—which include all $\L$-complete and $\NL$-complete languages, and hence, all parallelizable and search tasks—cannot be solved by constant-depth transformers with polynomial width because they cannot be computed by $\textsf{TC}^0$ (constant-depth threshold circuits).
We nonetheless include this theorem to demonstrate a clean lower bound that applies to very simple input graph instances.

§.§ Triangle counting

We finally construct depth-efficient transformers for triangle counting due to the MPC algorithms of <cit.>.
Unlike previous positive results, which applied uniformly across all graphs instances of bounded size, the complexity of the corresponding transformers for triangle counting is a function of the arboricity[
The arboricity is the minimum number of spanning forests needed to cover the graph, which grows at most linearly with the degree of the graph.
] of the input graph.
When the arboricity grows sub-polynomially with $N$—as is the case for bounded-degree graphs—no pause tokens are necessary.
Unlike the parallelizable and search classes of problems, strictly sub-logarithmic depth is attainable with pause tokens, even for worst-case graphs.

There exists a transformer that computes the number of triangles in any input graph of arboricity $\alpha$ and has embedding dimension $m = O(N^\epsilon)$, depth $L = O(\log\log N)$, and pause tokens
\[N' = \begin{cases}O(\alpha N^{1-\epsilon}) & \text{if $\alpha = \Omega(N^\epsilon)$} \\ 0 & \text{otherwise.}\end{cases}\]

This result is a special case of <Ref>, a more general result about clique counting that appears in <Ref>.

*Theoretical conclusions.

These results provide a tight characterization of the the reasoning capabilities of transformers whose depth, width, and input padding conform to different scaling regimes.
They strengthen the established connection between transformers and massively parallel computation (MPC) <cit.> and generalize the resulting representational bounds to broader categories of graph tasks.
We conclude that the logarithmic-depth regime is apt for for considering tasks in $\L$ and $\NL$, which had previous illuminated the limitations of transformers with constant depth and a limited number of chain-of-thought tokens <cit.>.
While expressivity does not imply learnability, these theoretical benchmarks sharply characterize the fundamental limitations of transformers and coincide with experimental results conveyed in the subsequent section.

§ EMPIRICAL GRAPH REASONING CAPABILITIES

We further illuminate the reasoning capabilities of transformers by conducting an empirical investigation of the abilities of a variety of neural architecture and training settings to learn graph algorithmic tasks.
We use the GraphQA benchmark tasks <cit.> for our experiments. We evaluate standard autoregressive transformers—both small models (at most 60M parameters) trained from scratch and fine-tuned (FT) T5-11B model (with 11B parameters) <cit.>. For the fine-tuned models, we explore task-specific fine-tuning—and contrast those results with graph neural networks (GNNs) and prompting-based methods on pre-trained LLMs.

These experimental results validate key tenets of our theoretical results and demonstrate the utility of transformers' algorithmic reasoning capabilities.
Our principal empirical conclusions are as follows:

* Transformers excel at global reasoning tasks.
Transformers outperform GNNs on tasks that require efficiently aggregating information about distant nodes in a graph, such as connectivity and shortest path.

* GNNs uncover local graph structure with few samples.
While transformers are capable of efficiently expressing all graph learning tasks under investigating, the structural limitations of GNNs provide them with favorable inductive biases for intrinsically local tasks, such as cycle check and node degree, and permit them to outperform transformers in a low-sample regime.

* Trained transformers outperform LLM prompting.
Transformers trained to explicitly solve graph reasoning tasks consistently attain greater accuracy across tasks than a variety of prompting strategies applied to more recent larger LMs.

A comprehensive evaluation of each GraphQA task on every training setting appears in <Ref>, in addition details about transformer training, the GraphQA benchmark, and alternative GNN and prompting approaches.

§.§ Transformers excel at global reasoning tasks

As indicated in <Ref>, graph reasoning algorithms can be categorized based on the extent to which they entail aggregating “local” information about nodes and their immediate neighbors or modeling “global” connections between nodes separated by a long distances.
This section investigates the following question about transformers and long-distance reasoning:

When do transformers outperform GNNs on tasks that require global reasoning?

We consider two tasks that require reasoning across long distances in a graph instance: evaluating connectivity and computing the shortest path between a pair of nodes.
Neither of these tasks can be solved by only investigating the neighbors of the source and sink node, which therefore implies that some analysis of global graph structure is necessary.

<Ref>  displays the accuracy of a variety of trained transformers and GNNs on the connectivity task contrastsing the performance of all such models when trained on 1,000 and 100,000 graph connectivity instances.
In the most restricted sample complexity regime, trained GNNs are consistently more accurate than the small transformer; however, increasing the number of training samples yields a far more substantial improvement in the performance of the small transformer, which outperforms all GNNs trained on 100,000 samples.
Notably, the pre-trained transformer, fine-tuned on just 1000 training instances, nearly solves the connectivity task. This suggests significant enhancements due to the larger model size and the data-rich fine-tuning phase.
<Ref> plots the training and test error of ten small transformers trained on connectivity datasets of increasing size and reveals a sharp and continual improvement in accuracy.
The fine-tuned T5 transformer has similar accuracy to the most sample-rich small transformer and exceeds that of all GNNs.

On the other hand, <Ref> demonstrates that the MPNN GNN models outperform small transformers when trained to compute the shortest path, even on larger training datasets.
However, the fine-tuned T5 model has far higher accuracy than all alternatives, even when trained only 1000 samples.

*Theoretical interpretation:
Because connectivity is the prototypical example of a task in the parallelizable class and can thus be efficiently implemented by  transformers with very small width (<Ref>), the fact that small transformers succeed in solving nearly all connectivity instances is illuminating but not surprising.
In contrast, message-passing GNNs are unable to solve connectivity in a similarly depth-efficient manner due to fundamental capacity limitations.[
See <Ref> for a discussion of prior work on theoretical relationships between GNNs and both the Weisfeiler-Leman graph isomorphism test <cit.> and the  distributed computing model and their implication that GNNs cannot solve connectivity in a parameter-efficient manner.

Shortest path belongs to the search class of graph reasoning tasks and is $\NL$-complete.
<Ref> implies that shortest path is computable by  transformers, which are likely to require very large embedding dimension to be learnable by finite samples.
This task can only be computed in a depth- and parameter-efficient manner if a variety of search tasks, including all-pairs shortest-path and diameter, are as well (<Ref>).
The fact that only the pre-trained model has nearly optimal performance on shortest path reinforces the theoretical intuition that solving shortest path requires a very large number of model parameters.

§.§ GNNs uncover local graph structure with few samples

While small transformers outperform GNNs on graph reasoning algorithms that entail analysis of long-range graph structure, their empirical successes are not uniform.
Here, we investigate the following question:

When do GNNs outperform transformers on graph reasoning tasks?

2cNode Degree     2cCycle Check

(lr)2-3  (lr)4-5
Model     1K    100K     1K    100K

GCN <cit.>     9.8     9.4     83.2     83.2

MPNN <cit.>     99.4     99.8     99.0     100.0

GIN <cit.>     36.2     37.8     98.8      83.2

60M transformer      31.6     91.7     97.1     98.0

11B transformer (FT)     68.8     —     98.0     —

Transformers vs GNNs on cycle check and node degree: GNNs are favorably biased for  local structure.

<Ref> and <Ref> demonstrate that GNNs outperform small transformers in the low-sample regime, despite the sufficient expressivity of transformers.
This gap in performance, which is reinforced for the node degree and cycle check tasks in <Ref>, suggests that GNNs have a beneficial inductive bias for learning graph reasoning tasks that can be solved by attending exclusively to local heuristics.

Just as the bounded kernel size of convolutional neural networks (CNNs) enables the sample-efficient learning of relevant textures and gradients for image analysis, message-passing GNNs are unable to send messages instantaneously across multiple edges, which simplifies a search of the space of “one-hop” graph algorithms and represents a positive inductive bias.
In contrast, the ability of transformers to send information between any pair of input tokens—and the alternative inductive biases suggested by the input positional encoding—likely induces a steeper sample complexity to learn node degree.

*Theoretical interpretation:
While model expressivity is necessary for learnability, it is not sufficient.

The locality constraints of message-passing GNNs likely provides a favorable inductive bias for learning tasks like node degree with an exclusively on local structure that makes learning these tasks possible in a sample-efficient manner.
While cycle check is more representationally difficult for GNNs than transformers in the worst case (see <Ref>), the random graphs sampled for the GraphQA benchmark have very small cycles (<Ref>) and do not resemble the large-diameter worst-case instance.

§.§ Trained transformers outperform LLM prompting

Large language models (LLMs) are regularly evaluated by their reasoning abilities, and it remains an open research question to determine what kinds of training data best teaches models to solve logical problems.
We investigate the extent to which LLMs can already perform graph reasoning tasks without being trained explicitly to do so.

Do transformers trained explicitly to solve graph reasoning tasks outperform prompt-tuning approaches on much larger LLMs?

In <Ref>, we contrast the capabilities of trained transformer models with several prompt-based approaches to querying LLMs.
Task-specific transformers—including the fine-tuned 11B transformers—consistently dominated the prompt-based approaches, despite the vast difference in parameter count and the almost certain presence of graph reasoning in the LLM's corpus.

*Theoretical interpretation:
While the representational capabilities of LLMs to solve reasoning tasks is much greater than that of small transformers, this performance gap suggests that their effective reasoning capacity is much weaker and that it may be improved by a richer training corpus that includes synthetic tasks.

Finally, we observe that the near-perfect performance of trained transformers on the node count, edge count, and edge existence is consistent with the representational easy of those tasks, as suggested by the existence of efficient  transformer implementations.

§ CONCLUSION

This paper provides a comprehensive evaluation of transformer models' graph reasoning capabilities, shedding light on their effectiveness across diverse graph reasoning tasks. By introducing a novel representational hierarchy, the study distinguishes between retrieval, parallelizable, and search reasoning tasks and offers insights into the performance of transformers at varying levels of granularity.
The empirical investigation reveals that transformers exhibit strong performance in graph-based reasoning problems, often matching or surpassing specialized graph models.

Furthermore, the study highlights transformers' exceptional ability to capture global graph patterns effectively, showcasing their capability in understanding long-range dependencies, a critical factor in solving tasks involving global graph structures.

Overall, this work crystallizes precise representational trade-offs that reflect the fundamental reasoning capabilities of transformers and demonstrates that the tasks used to quantify those capabilities are indeed learnable in a sample-efficient and parameter-efficient manner.

While the hierarchy introduced by this work effectively separates graph algorithmic tasks into distinct equivalence classes with significant implications for their computability by transformers, several questions remain for future research.
We focused on graph reasoning tasks due to their relevance to the broader context of transformers, GNNs, and parallel algorithms.
However, the complexity classes presented here could potentially be extended to a wider range of algorithmic problems.
While our assumption of unbounded-size MLPs provides strong lower bounds, further research into whether parallelizable tasks can be represented by transformers with bounded-size MLP units would complement this existing work.
Broader experimental results that empirically evaluate the scaling laws would more directly assess the relevance of representational theoretical results to learnability.

§ THEORETICAL PRELIMINARIES

For some vector $v \in \R^N$, let
\[\sm(v) = \frac{1}{\sum_{i=1}^N \exp(v_i)} \paren{\exp(v_1), \dots, \exp(v_N)} \in \R^N.\]

Let $e_i \in \R^m$ denote the $i$th elementary vector, $\vec1 = (1, \dots, 1) \in \R^m$ and $\vec0 = (0, \dots, 0) \in \R^m$.
Let $[n] = \{1, \dots, n\}$.

§.§ Transformer models

We use a similar theoretical definition of a multi-layer transformer model to the one employed by <cit.>.
We use a bounded communication theoretical model of the standard bidirectional transformer of <cit.>, which assumes that the principal limitation of the transformer's representational power is the low rank of the self-attention matrix.
Several theoretical assumptions are necessary to model transformers in this regime:

* the interleaved element-wise multi-layer perceptron (MLP) units compute arbitrary functions;

* the embedding dimension $m$ and number of heads per layer $H$ are much smaller than the sequence length $N$; and

* all model parameters, inputs, and intermediate products can be represented with $O(\log N)$-bit numbers.

These assumptions are justified in greater detail by <cit.>.

Furthermore, we also model transformers as having $N'$ additional “pause token” inputs, which are embeddings that contain no information relevant information about the input instance, but which provide a longer “work tape” that can be utilized for computational purposes <cit.>.
While structurally similar to chain-of-thought reasoning <cit.>, these pause tokens are not determined by multiple auto-regressive passes over the transformer and do not encode useful information as input.
Such pause tokens exist both in the theoretical results of <Ref> (as blank tokens at the end of the sequence) and in the empirical results of <Ref> (as placeholders between the graph representation and the task query for graphs that can be represented in fewer tokens than the maximum sequence length).

Let $\trans{m, H, L}{N, N'}$ denote the family of all bidirectional transformers with embedding dimension $m$, number of heads $H$, and depth $L$, which operate on input sequences on length $N$ with $N'$ blank pause tokens appended to the end[If $N'=0$, we denote the family as $\trans{m, H, L}{N}$.].
Any transformer $f \in \trans{m, H, L}{N, N'}$ is a function of the form $f: \R^{N \times d} \to \R^N$ for some input dimension $d$, which parameterized by query, key, and value matrices
\[Q_{\ell, h}, K_{\ell, h}, V_{\ell, h} \in \R^{m \times m}, \text{ for $\ell \in [L], \ h \in [H]$},\]

and arbitrary element-wise MLPs with positional embeddings $\phi^0, \dots, \phi^L$ and $\psi$ with

\begin{align*}
\phi^0: &\R^d \times \N \to \R^m, \\
\phi^\ell: &\R^m \times \N \to \R^m, \ \text{for $\ell\in\set{1, \dots, L}$}, \\
\psi: &\R^m \times \N \to \R,
\end{align*}

where for sequence $Y$ of length $N + N'$,
\[\phi^\ell(Y) = (\phi^\ell(y_1, 1), \dots, \phi^\ell(y_{N+N'}, N+ N')).\]

To evaluate $f(X)$ on some input sequence $X = (x_1, \dots, x_N) \in \R^{N \times d}$, we define intermediate embeddings $Y^0, \dots, Y^L \in \R^{(N+N') \times m}$ as follows:

* The initial embedding is computed by applying the first MLP $\phi^0$ to all elements of the input $X$, along with $N'$ “blank” inputs:
\[Y^0 = \phi^0(X) = (\phi^0(x_1, 1), \dots, \phi^0(x_N, N), \phi^0(0, N+1), \dots, \phi^0(0, N + N')).\]

* The intermediate embeddings $Y^{\ell}$ for $\ell \in \set{1, \dots, L}$ are computed by applying a unit of multi-headed attention (parameterized by $Q_{\ell, h}, K_{\ell, h}, V_{\ell, h}$ for all $h \in [H]$) to the previous embedding $Y^{\ell-1}$, followed by an element-wise application of the MLP $\phi^\ell$.
That is,

\begin{align*}
&= \phi^\ell\paren{\sum_{h=1}^H \sm\paren{\phi(Y^{\ell-1}) Q_h K_h^\T \phi(Y^{\ell-1})^\T} \phi(Y^{\ell-1}) V_h}.
\end{align*}

* The output $f(X) \in \R^N$ is computed to be the first $N$ outputs of $\psi(Y^L)$. That is,

\[f(X) = (\psi(Y^L_1, 1), \dots, \psi(Y^L_N, N)).\]

While our theoretical results pertain to the bidirectional regime (where no masking is applied to the self-attention layer), all results in <Ref> and all lower bounds in <Ref> apply to autoregressive transformers as well.
Our empirical results utilize causal masking.

Furthermore, an $L$-layer bidirectional transformer that operates on sequences of length $N$ with $N'$ pause tokens can be simulated by and $L$-layer autoregressive transformer with $O(L \cdot (N + N'))$ pause tokens.
In the regime where $N' = \poly(N)$ and $L = O(\log N)$, any positive results for bidirectional models likewise apply to autoregressive models.

§.§ Graph reasoning tasks

We exclusively consider graph reasoning tasks that apply to undirected and unweighted graphs $G = (V, E)$ of bounded size, i.e. $|V| + |E| = O(N)$ for some size parameter $N$.
We define the tasks used for experimentation as follows:

* Node count: Given graph $G$, compute $|V|$.

* Edge count: Given graph $G$, compute $|E|$.

* Edge existence: Given graph $G$ and vertices $u, v \in V$, return $\indicator{(u, v) \in E}$.

* Node degree: Given graph $G$ and vertex $u \in V$, return $\deg(u)= \abs{(u, v) \in E}$.

* Connectivity: Given graph $G$ and vertices $u, v \in V$, return 1 if there exists a path of edges between $u$ and $v$ and 0 otherwise.

* Cycle check: Given graph $G$, return 1 if there exists a cycle of any length $\geq 3$ and 0 otherwise.

* Shortest path: Given graph $G$ and vertices $u, v \in V$, return the smallest number of edges that forms a path between $u$ and $v$ if one exists and $-1$ otherwise.

* Triangle counting: Given graph $G$, return the number of triangles in the graph: $\abs{\set{(u, v, w): (u,v), (v, w), (u, w) \in E}}$.

These tasks are foundational to computer science and are solved by famous polynomial-time algorithms, such as Dijkstra's algorithm for shortest path and Kruskal's for spanning trees.
Several of these tasks reap significant algorithmic benefits from parallel computing models, including graph connectivity, which can be evaluated in a logarithmic number of rounds by employing an “iterative merging” strategy <cit.>.

The amenability of some of these tasks to parallel computing is the core principle underlying our theoretical results on transformer model capacity and the resulting contrasts with GNNs.
For instance, the iterative merging algorithm for connectivity can be simulated by a logarithmic-depth transformer, but message-passing GNNs cannot do without a substantial width scaling (see <Ref>).
Furthermore, this parallel computing algorithm is widely believed to be optimal, and a crystallization of this as <Ref> is the bedrock of our transformer optimality conjectures.

The multi-layer results of <Ref> are representation-agnostic; the bounds apply to any fixed encoding of vertices and edges as a transformer input sequence $X \in \R^{N \times d}$.
The input representation for <Ref> must satisfy the more specified node/edge encoding scheme, which represents each vertex and edge as a single embedding, followed by a query embedding (with optional blank embeddings as needed).
This encoding scheme is reflected by <Ref> and closely resembles the graph instance encoding used for the experimental results[The empirical encoding scheme uses two tokens—not one—to encode each edge and has fixed size $N$. For all graphs whose encodings do not require all $N$ tokens, the remaining tokens are blank placeholders that precede the query tokens.].

Throughout the paper, we partition these and other graph reasoning tasks into three representational categories: retrieval, parallelizable, and search tasks.
The retrieval category contains only four of the tasks used for experiments:

* Retrieval tasks include node count, edge count, edge existence, and node degree.

On the other hand, the other categories reflect two equivalence classes introduce by <cit.>:

* Parallelizable tasks are defined to be $\L$-complete and equivalent to connectivity in $O(1)$ rounds of MPC.
These tasks include connectivity, cycle check, planarity testing, minimum cut, bipartiteness testing, minimum spanning forest, connected components, one-cycle versus two-cycles (see <Ref>), and # connected components.

* Search tasks are defined to be $\NL$-complete and equivalent to shortest path in $O(1)$ rounds of MPC.
These tasks include shortest path, strong connectivity (for directed graphs), all-pairs shortest path, median, diameter, radius, directed cycle detection, and $st$-reachability.

Triangle counting does not appear in any of these classes and is separately analyzed in <Ref>.

§ MULTI-LAYER TRANSFORMERS AND PARALLELIZABLE/SEARCH GRAPH REASONING TASKS

In this appendix, we formalize and prove all results in <Ref> that pertain to the parallelizable and search categories of graph reasoning tasks.

The primary technical tool used to establish these results is an improved relationship between the MPC model of distributed communication of <cit.> and our theoretical model of a transformers (<Ref>).
This result is presented informally as <Ref>, and formally as <Ref>.
Because graph reasoning tasks are well studied in the MPC model of computation <cit.>, this theorem enables the transfer of those positive results to transformer architectures.
Similarly, negative results that pertain to the MPC model, including those conditioned on the well-known one-cycle versus two-cycle conjecture (<Ref>), imply negative results for transformers.

[Formal version of <Ref>; transformers simulate MPC]
For constants $0 < \delta < \delta' < 1$ and $\gamma > 0$, an $R$-round deterministic $(\gamma, \delta)$-MPC protocol with $n$ inputs can be simulated by a transformer $f \in \trans{m, H, L}{N, N'}$ with depth $L = O(R)$, single heads $H = 1$, embedding dimension $m = O(n^{\delta'})$, context length $N = n$, and blank chain-of-thought tokens $N' = \max(0, O(n^{1 + \gamma - \delta}) - n)$.

We formally introduce the MPC distributed computing model in <Ref>, along with the one-cycle versus two-cycle conjecture and a collection of positive results from <cit.>.
In <Ref>, we formally present the task-specific graph reasoning results introduced in <Ref> and prove them as implications of <Ref>.
We finally contextualize and prove <Ref> in <Ref> by modifying the proof strategy of a similar result <cit.> and by showing that MPC protocols can be simulated by a weaker model of distributed computation.

§.§ MPC preliminaries

The massively parallel computation (MPC) model of <cit.> formalizes distributed computing frameworks such as MapReduce <cit.> as theoretical models that are amenable to rigorous analysis.
MPC pertains to a regime where an input that consists of $n$ “words” is distributed across a very large number of machines $q$ (e.g. $q \approx n^{0.95}$), each of which contains a bounded local memory $s$ (e.g. $s \approx n^{0.1}$) where computation on individual machines is inexpensive but communication between machines is costly.
We use the definition of MPC of <cit.>, which quantifies the complexity of a protocol by the local memory $s = O(n^\delta)$, the global memory $sq = O(n^{1 + \gamma})$, and the number of communication rounds $R$.

For global and local memory constants $\gamma, \delta > 0$ and input size $n$, an $R$-round $(\gamma, \delta)$-MPC protocol specifies a distributed computing protocol over $q = \Theta(n^{1 + \gamma -\delta})$ machines, each of which contains a local memory of size $s = O(n^\delta)$.

* An input to the protocol, which is encoded as a length-$n$ sequence of $p = \Theta(\log n)$-bit words, is distributed across the local memories of the first $\ceil{n / s}$ machines.

* In each of the $R$ rounds, each machine computes an arbitrary function its local memory at the time, which specifies at most $s$ words to be transmitted to other machines.

* Messages are simultaneously transmitted (subject to the constraint that each machine sends and receives at most $s$ words of information), and each machine's new local memory is set equal to the messages received.

* After the final round, the output of the protocol is a concatenation of the local memories of the first $\ceil{n / s}$ machines.

We say that an MPC protocol computes some function $f: \Z_{2^p}^n \to \Z_{2^p}^n$ if for any $X \in \Z_{2^p}^n$ encoded as input to the protocol, the output of the protocol is $f(X)$.

§.§.§ MPC and graph reasoning tasks

In this section, we introduce previously known results about the abilities of Massively Parallel Computation protocols to solve graph reasoning tasks.
The novel results presented in the subsequent section are the primarily the immediate implications of these results and <Ref>.

*MPC round equivalence for parallelizable and search tasks

These results largely reflect the contributions of <cit.>, which establish a hierarchy of graph reasoning tasks that is reflected in our distinction between parallelizable and search tasks.
They show that all parallelizable tasks are equivalent to connectivity in $O(1)$ rounds of MPC and that all search tasks are likewise equivalent to shortest path. (See their Figure 1.)
Concretely, they prove the following for all graphs $G = (V, E)$ with $|V| + |E| = O(n)$.

If there exists an $R$-round $(\gamma, \delta)$-MPC protocol for any parallelizable task—including graph connectivity, $st$-connectivity, cycle detection, formula evaluation, planarity testing, graph bipartiteness, connected components, minimum spanning forest, and minimum cut, one-cycle versus two-cycle testing—for some $\gamma > 0$ and $\delta \in (0, 1)$, then there exists an $R'$-round $(\gamma', \delta)$-MPC protocol for any other other parallelizable task where $R' = R + O(1)$ and $\gamma' = \max(\gamma, 3)$.

If there exists an $R$-round $(\gamma, \delta)$-MPC protocol for any search task—including $st$-reachability (for directed graphs), strong connectivitity, directed cycle detection, shortest path, all-pairs shortest path, diameter, radius, and median—for some $\gamma > 0$ and $\delta \in (0, 1)$, then there exists an $R'$-round $(\gamma', \delta)$-MPC protocol for any other other search task where $R' = R + O(1)$ and $\gamma' = \max(\gamma, 2)$.

The equivalance of <Ref> has more immediate implications for the round complexity of parallelizable tasks than <Ref> does for search tasks because the round complexity of graph connectivity is well-understood to be $O(\log n)$ and thought to be optimal.
We first present a deterministic MPC positive result for graph connectivity.

For any $\gamma > 0$ and $\delta \in (0, 1)$, there exists a deterministic $O(\log n)$-round $(\gamma, \delta)$-MPC protocol that solves graph connectivity on any graph $G = (V, E)$ of size $|V| + |E| = O(n)$.

Hence, all parallelizable tasks can be solved with a logarithmic number of MPC rounds with arbitrarily small polynomial local memory.

For any $\gamma > 0$ and $\delta \in (0, 1)$ and any parallelizable task, there exists a deterministic $O(\log n)$-round $(\gamma', \delta)$-MPC protocol that solves the task on any graph $G = (V, E)$ of size $|V| + |E| = O(n)$ for $\gamma' = \max(\gamma, 3)$.

The optimality of these logarithmic-round protocols is suggested by a conjecture about the hardness of distinguishing between two graphs with $n$ vertices and $n$ edges, one of whose edges are arranged in a single cycle of length $n$ and the other in two disjoint cycles of length $\frac{n}2$.
This is the well-known “one-cycle versus two-cycle conjecture,” which is widely employed as a condition for distributed computing hardness <cit.>.

For any $\gamma > 0$ and $\delta \in (0, 1)$, any $(\gamma, \delta)$-MPC protocol that distinguishes a single length-$n$ cycle from two disjoint length-$\frac{n}2$ cycles uses $R = \Omega(\log n)$ rounds.

Under this conjecture, <Ref> immediately implies the optimality of <Ref>.

Conditional on <Ref>, for any $\gamma > 0$ and $\delta \in (0, 1)$, any $(\gamma, \delta)$-MPC protocol that solves a parallelizable graph task on all graphs $G = (V, E)$ of size $|V| + |E| = O(n)$ uses $R = \Omega(\log n)$ rounds.

The round complexity of search tasks is less understood, and it is unknown if search tasks can be solved by $O(\log n)$-round $(\gamma, \delta)$-MPC protocols if $\delta \in (0, \frac12]$.

*MPC protocols for problems with bounded circuit size

More general MPC constructions are known for problems that solved by bounded-size boolean circuits, which include both parallelizable and search tasks.
The well-known $\NC^i$ classes of Boolean circuits that take $N$ inputs and have $\poly(n)$ gates and depth $O(\log^i n)$ have been shown to be computable by bounded-round MapReduce-like computational protocols <cit.> and by MPC protocols in particular <cit.>.

For any problem in $\NC^{i+1}$ and any $\gamma > 0$ and $\delta \in (\frac12, 1)$, there exists a deterministic $O(\log^i n)$-round $(\gamma, \delta)$-MPC protocol that solves the problem.

Since $\L$ and $\NL$ are known to belong to $\NC^2$, the following corollary is an immediate consequence.

For any parallelizable or search graph reasoning task and any $\gamma > 0$ and $\delta \in (\frac12, 1)$, there exists a deterministic $O(\log n)$-round $(\gamma, \delta)$-MPC protocol that solves the task on all graphs $G = (V, E)$ of size $|V| + |E| = O(N)$.

Note that these results pertain exclusively to the “large local memory regime,” where each machine has memory at $s = \omega(\sqrt{n})$.
Therefore, this does not guarantee the existence of a $O(\log n)$-round MPC solution for any search task or for any parallelizable task with $\gamma < 1$.

*MPC protocol for triangle counting

Finally, the triangle counting task can be solved in the MPC framework by utilizing a special case of a parallel algorithm for clique counting.
These pertain to graphs with bounded arboricity $\alpha$, a quantity that corresponds to the branching factor of a node that is bounded by the degree of the graph; these apply to arbitrary graphs by noting that $\alpha \leq |V|$.

For any $k \geq 3$, $\delta \in (0, 1)$, and $\gamma > 0$, there exists an $O(\log\log n)$-round $(\gamma, \delta)$-MPC protocol that computes the number of $k$-cliques in any graph $G = (V,E)$ with $|V| + |E| = O(n)$ and arboricity $\alpha = O(n^{\gamma/(k-2)})$.

§.§ Positive and negative graph reasoning results for multi-layer transformers

We state formalized versions of the statements of <Ref> and prove them by invoking <Ref> jointly with the relationships between MPC and graph reasoning of <Ref>.

§.§.§ Parallelizable task results (<Ref>)

For the duration of this section, the class of parallelizable tasks includes all of those that are deemed equivalent to graph connectivity in $O(1)$ rounds of MPC by <cit.>, as stated in <Ref>.

We first present a statement that formalizes the existence of logarithmic-depth transformer constructions for solving parallelizable tasks.

For any $\epsilon \in (0, 1)$ and any parallelizable task, there exists a transformer $f \in \trans{m, H, L}{N, N'}$ such that $f(X)$ computes the task where $X \in \R^N$ is some encoding of any graph $G = (V, E)$ with $|V| + |E| = O(N)$ and $f$ has depth $L = O(\log N)$ and heads $H = O(1)$ and embedding dimension $m$ and pause tokens $N'$ satisfying either

* : $m = O(N^\epsilon)$ and $N' = O(N^{4 - \epsilon'})$, where $\epsilon' \in (0, \epsilon)$; or

* : $m = O(N^{\epsilon})$ and $N' = 0$, if $\epsilon > \frac12$.

The first bullet is an immediate implication of <Ref> and <Ref> with $\gamma = 3$, $\delta' = \epsilon$, and $\delta = \epsilon'$.
The second bullet follows from <Ref> and <Ref> with $\gamma = \delta = \frac{\epsilon}2$ and $\delta' = \epsilon$.

We then establish that sub-logarithmic-depth solutions to any parallelizable task are impossible without having linear embedding dimension $m$ or super-polynomial number of pause tokens $N'$, under the assumption that the one-cycle versus two-cycle conjecture holds.

Conditional on <Ref>, for any $\epsilon \in (0, 1)$ and $\gamma > 0$ and any parallelizable task, if there exists a transformer $f \in \trans{m, H, L}{N, N'}$ that solves the task and has width $mH = O(N^\epsilon)$ and pause tokens $N + N' = O(N^{1 + \gamma})$, then its depth satisfies $L = \Omega(\log N)$.

The proof is a consequence of <Ref> and a result of <cit.> that proves the to simulate transformers with MPC protocols, an inversion of <Ref>.
We restate that result as follows.

Fix any transformer $f \in \trans{m, H, L}{N, N'}$ with width $mH = O(N^{\delta})$ for some $\delta \in (0, 1)$ and total sequence length $N + N' = O(N^{1 + \gamma})$ for some $\gamma \geq 0$.
Then, for any $\delta' \in (\delta, 1)$ and $\gamma' = 1 + 2\gamma + \delta'$, there exists an $O(\frac{L(1 + \gamma)}{\delta' - \delta})$-round $(\gamma', \delta')$-MPC protocol that simulates $f$.

Consider a transformer $f \in \trans{m, L, H}{N, N'}$ that solves the task with width $mH = O(N^\epsilon)$ and total sequence length $N + N' = O(N^{1 + \gamma}$ for some constant $\epsilon \in (0, 1)$ and $\gamma > 1$.
Then, there exists an $O_{\epsilon, \gamma}(L)$-round $(1 + 2\gamma + \sqrt{\epsilon}, \sqrt{\epsilon})$-MPC protocol that solves the parallelizable task.
If <Ref> is true, then $L = \Omega(\log N)$.

§.§.§ Search task results (<Ref>)

We present the main result of <Ref> and show an equivalence between the minimum depth transformer needed to solve search tasks in a width-efficient manner.
As before, the class of searchable tasks includes tasks that are equivalent to shortest path in $O(1)$ MPC rounds (<Ref>).

For any $\epsilon \in (\frac12, 1)$ and any search task, there exists a transformer $f \in \trans{m, H, L}{N, N'}$ such that $f(X)$ computes the task where $X \in \R^N$ is some encoding of any graph $G = (V, E)$ with $|V| + |E| = O(N)$, and $f$ has depth $L= O(\log N)$, heads $H = O(1)$, embedding dimension $m = O(N^{\epsilon}$, and no pause tokens ($N' = 0$).

As before, the proof is an immediate consequence of <Ref> and <Ref>.

While both search and parallelizable tasks are computable logarithmic depth of considerable width, the minimum depth transformer of width $O(N^\epsilon)$ for small $\epsilon$ that computes search tasks is unknown.
Despite this deficit, we can still establish the representation similarity of all search tasks by showing that their minimum depths vary by at most a constant additive factor.

Suppose for some $\epsilon \in (0, 1)$ and $\gamma > 0$ there exists a transformer $f \in \trans{m, H, L}{N, N'}$ with embedding dimension $m = O(N^\epsilon)$ and total sequence length $N + N' = O(N^{1+\gamma})$ that computes the some search task on all graphs $G = (V, E)$ of size $|V| + |E| = O(N)$.
Then, for any other search task, there exists some transformer $f' \in \trans{\bar{m}, H, \bar{L}}{N, \bar{N}'}$ with embedding dimension $\bar{m} = O(m)$, depth $\bar{L}= L + O(1)$, and pause tokens $\bar{N}' = N' + O(N^3)$ that computes that search task.

This statement is an immediate consequence of <Ref> and <Ref>.

§.§.§ Clique counting task results (<Ref>)

We prove the existing of doubly-logarithmic-depth transformer that solves the triangle counting task giving a more general result that counts the number of $k$-cliques in any graph of bounded arboricity.

For any fixed $\epsilon \in (0, 1)$ and $k \geq 3$, there exists a transformer $f \in \trans{m, H, L}{N, N'}$ with embedding dimension $m = O(n^\epsilon)$, heads $H = O(1)$, depth $L = O(\log\log n)$, and chain-of-thought tokens
\[N' = \begin{cases} O(\alpha^{k-2} N^{1-\epsilon}) & \text{if $\alpha = \Omega(N^{\epsilon / (k-2)})$,} \\ 0 & \text{otherwise.} \end{cases}\]

that counts the number of $k$-cliques in all graphs $G = (V, E)$ of arboricity $\alpha$ and size $|V| + |E| = O(N)$.

<Ref> follows immediately from taking $k = 3$.

This is the immediate implication of <Ref> and <Ref>.

§.§ Proof of <Ref>

Our principal theoretical result establishes that any MPC protocol with sublinear local memory can be simulated by a transformer with sublinear embedding dimension.

This offers an improvement on Theorem 3.1 of <cit.>, which only guarantees that MPC protocols with local memory $s=O(n^{1/4 - \epsilon})$ (or with $\delta < \frac14$) can be simulated by transformers with sublinear embedding dimension.
This distinction is significant because several positive results for the MPC protocol (e.g. the ability to solve all problems in $\mathsf{L}$ and $\mathsf{NL}$ in a logarithmic number of MPC rounds) require $s = \Omega(N^{1/2})$ local memory, and hence could not be shown to be simulated by transformers of sublinear embedding dimension previously[
For this theoretical model of the transformer to be non-vacuous, the transformer must have embedding dimension $m = o(Nd)$.
Without this, any function over $X \in \R^{N \times d}$ could be solved by a single-layer transformer that concatenates all inputs into a single vector in an attention unit and passes that as input to an MLP that solves the problem.

Including an allowance of $N'$ blank pause tokens permits the simulation of MPC protocol with $\gamma \geq \delta$, i.e. where number of machines $q$ grows super-linearly with $n$.
If $\gamma < \delta$, then the protocol can be simulated without pause tokens (i.e. $N' = 0$) for sufficiently large input sizes $n$.

To prove <Ref>, we define a restriction of the MPC computational model that disallows each machine from communicating with more than $k$ other machines in each round of the protocol.

For constants $\gamma, \delta, \rho > 0$, an $R$-round $(\gamma, \delta, \rho)$-MPC protocol on input sequences of length $n$ is a $(\gamma, \delta)$-MPC protocol (<Ref>) that obeys an additional constraint on the number of outgoing and incoming messages.
Namely, for some capacity $k = O(n^\rho)$, in each round, every machine can send its local memory to and receive information from at most distinct $k$ machines.

<Ref> is an immediate consequence of <Ref>—which establishes that any $(\gamma, \delta)$-MPC protocol can be simulated by a $(\gamma, \delta, \rho)$-MPC protocol—and <Ref>—which shows that any $(\gamma, \delta, \rho)$-MPC protocol can be simulated by a transformer.

[$(\gamma, \delta, \rho)$-MPC simulates $(\gamma, \delta)$-MPC]propositionpropmpcsim
For constants $\gamma, \delta > 0$ and $\rho \in (0, \frac\delta2)$, if $f$ can be computed by an $R$-round $(\gamma, \delta)$-MPC protocol, then there exists a $O(\frac{R(1 + \gamma)^2}{\rho^2})$-round $(\gamma, \delta, \rho)$-MPC protocol that computes $f$ as well.

[Transformers simulate $(\gamma, \delta, \rho)$-MPC]corollarycormpcsht
For constants $\delta \in (0, 1)$ and $\gamma, \rho > 0$, an $R$-round deterministic $(\gamma, \delta, \rho)$-MPC protocol with $n$ inputs can be simulated by a transformer $f \in \trans{m, H, L}{N, N'}$ with depth $L = R + 1$, heads $H = 1$, embedding dimension $m = O(n^{\delta + 4\rho} \log n)$, context length $N = n$, and blank chain-of-thought tokens $N' = \max(0, O(n^{1 + \gamma - \delta}) - n)$.

Let $\rho := \min(\frac\delta2, \frac{\delta' - \delta}4) - \epsilon$ for some small constant $\epsilon$ (e.g. $\epsilon := \min(\frac\delta4, \frac{\delta' - \delta}8)$).
By <Ref>, we can simulate the target $R$-round $(\gamma, \delta)$-MPC protocol with an $R'$-round $(\gamma, \delta, \rho)$-MPC protocol for

\[R'=O\paren{\frac{R(1 + \gamma^2)}{\min((\delta' - \delta)^2, \delta^2)}}.\]

We apply <Ref> to conclude that this latter protocol can be simulated by a transformer of depth $L = R' + 1$ and embedding dimension
\[m = O(n^{\delta + 4 \rho} \log n) = O(n^{\delta'}).\qedhere\]

We prove <Ref> in <Ref> by simulating a single round of a standard MPC with multiple rounds of restricted MPC, where messages are sent to intermediate “neighborhoods”—which contain collections of machines with similar destinations—of increasing fine granularity.
We prove <Ref> in <Ref> by a minor adaptation of the proof of Theorem 3.1 of <cit.>.

§.§.§ Proof of <Ref>

Fix an $R$-round $(\gamma, \delta)$-MPC protocol $\pi$ with input size $n$, $q  = \Theta(n^{1 + \gamma - \delta})$ machines, and $s = O(n^\delta)$ local memory.
To prove <Ref>, it suffices to show that a single round of MPC communication can be simulated an $O(\frac{(1 + \gamma)^2}{\rho^2})$-round $(\gamma, \delta, \rho)$-MPC protocol.

To formalize the communication procedure to simulate, we let $\outbox = (\outbox_1, \dots, \outbox_q)$ denote an encoding of the outgoing “message packets” from each source machine that obeys $\pi$'s local memory constraints. Concretely,

\[\outbox_i = \set{(\msg, \src, \dst): \src = i, \dst \in [q]} \ \st \ \sum_{\msg \in \outbox_i} |\msg| \leq s.\]

Let $\inbox = (\inbox_1, \dots, \inbox_q)$ denote the same collection of message packets, organized by their destination machines.

\[\inbox_i = \set{(\msg, \src, \dst) \in \outbox_\src: \dst = i} \ \st \ \sum_{\msg \in \inbox_i} |\msg| \leq s.\]

It suffices to prove <Ref>.

If $\rho < \frac\delta2$, there exists an $O(\frac{(1 + \gamma)^2}{\rho^2})$-round $(\gamma, \delta, \rho)$-MPC protocol that takes as input any $\outbox$ and returns the corresponding $\inbox$.

We define $r = O(\frac{1 + \gamma}\rho)$ intermediate steps and prove that each of those can be simulated.
The intuition is that each an intermediate step routes each packet $(\msg, \src, \dst)$ to a machine that belongs to the same “neighborhood” as $\dst$.
Each step maps each packet to a neighborhood of smaller radius than the step before, until all packets have been transmitted to their proper destination location.

We define a tree of neighborhoods as follows.
Fix some branching factor $\ell = \Theta(n^{\rho/2})$ and number of intermediate steps $r = \ceil{\frac{\log q}{\log \ell}} = O(\frac{1 + \gamma}\rho)$.
For any step $t = 0, \dots, r$ and neighborhood index $j = 1, \dots, b_t := \ceil{\frac{q}{\ell^{r-t}}}$, we define

\[\nbhd^t_j = \set{(j-1) \ell^{r-t} + 1, (j-1) \ell^{r-t} + 2, \dots, j \cdot \ell^{r-t}} \cap [q]\]

and observe that it satisfies the size constraint $|\nbhd^t_j| \leq \ell^{r-t}$.
We let $\nbhd^t(\dst)$ denote the unique neighborhood $\nbhd^t_j$ satisfying $\dst \in \nbhd^t_j$.
We say that $\nbhd^t_j < \nbhd^t_{j'}$ if $j < j'$ (and equivalently, for all $i \in \nbhd^t_j$ and $i' \in \nbhd^t_{j'}$, $i < i'$).

\begin{align*}
\children(\nbhd^t_j) &= \set{\nbhd^{t+1}_{(j-1)\ell + 1}, \dots, \nbhd^{t+1}_{j\ell}}, \\
\desc^\tau(\nbhd^t_j) &= \set{\nbhd^{\tau}(i): i \in \nbhd^t_j},\\
\parent(\nbhd^t_j) &= \nbhd^{t-1}_{\ceil{j / \ell}}, \\
\ancestor^t(\nbhd^\tau_j) &= \nbhd^t(i) \ \text{for $i \in \nbhd^\tau_j$}.% \\
% \firstchild(\nbhd^t_j) &= \nbhd^{t+1}_{(j-1)\ell + 1} = \min \children(\nbhd^t_j),
% \firstchild(\nbhd^t_j) &= \min \nbhd^t_j = (j-1)\ell^{r-t},
\end{align*}

for some $\tau \geq t$.

Note that the following are true of neighborhoods.

* The initial “step 0” neighborhood contains all machines (i.e. $\nbhd^0_1 = [q]$), and the final “step $r$” neighborhoods contain a single machine (i.e. $\nbhd^r_j = \{j\}$ for all $j \in [q]$).

* For any $t < r$ and $j \in [b_t]$, $\nbhd^t_j$ is the disjoint union of all sets in $\children(\nbhd^t_j)$ and $|\children(\nbhd^t_j)| \leq \ell$.

* $\set{\nbhd^t_1, \dots, \nbhd^t_{b_t}}$ comprise a disjoint union of $[q]$.

* For any $\dst \in [q]$, there exist unique sets $\nbhd^0(\dst), \dots, \nbhd^r(\dst)$ that satisfy
\[\nbhd^r(\dst) \subset \dots \subset \nbhd^0(\dst)\]

and $\nbhd^{t-1}(\dst) = \parent(\nbhd^{t}(\dst))$.

[scale=0.4,->,>=stealth',shorten >=1pt,auto,node distance=3cm,
thick,main node/.style=circle,draw,font=]

[align=center](0) at (3,30)Step $0$
1 $\nbhd$
$q$ machines per $\nbhd$;

[rounded corners=5pt, fill=blue!20] (0,0) rectangle (6,28);
[align=center](0) at (3,27.25)$\nbhd^0_1$;
[draw, rounded corners, align=center, fill=pink] (1) at (3,25.5)Machine 1
[draw, rounded corners, align=center, fill=pink] (2) at (3,22)Machine 2
[draw, rounded corners, align=center, fill=pink] (3) at (3,1.5)Machine $q$
in 7,9,11,13,15,17,19
[black] (3,) circle (2pt);

[align=center](0) at (13,30)Step $1$
$\ell$ $\nbhd$s
$q/\ell$ machines per $\nbhd$;

[rounded corners=5pt,fill=blue!20] (10,17) rectangle (16,28);
[align=center](4) at (13,27.25)$\nbhd^1_1$;
[draw, rounded corners, align=center,fill=pink] (5) at (13,25.5)Machine 1
in 22,22.5,23
[black] (13,) circle (1pt);
[draw, rounded corners, align=center,fill=pink] (6) at (13,19)Machine $q/\ell$
in 12,14,16
[black] (13,) circle (2pt);

[rounded corners=5pt,fill=blue!20] (10,0) rectangle (16,11);
[align=center](0) at (13,10)$\nbhd^1_\ell$;
in 5,6,7,8,9
[black] (13,) circle (1pt);
[draw, rounded corners, align=center,fill=pink] (2) at (13,1.5)Machine $q$

[->] (5.25,25) – (12,2.8);
[->] (5.25,25) – (10.5,20);

[->] (5.25,21) – (12,2.8);
[->] (5.25,21) – (10.5,20);
[->] (5.25,21) – (10.8,24);

[->] (5.25,2) – (10.8,2.4);
[->] (5.25,2) – (10.2,20);
[->] (5.25,2) – (10.5 ,23);

[align=center](0) at (23,30)Step $2$
$\ell^2$ $\nbhd$s
$q/\ell^2$ machines per $\nbhd$;
[rounded corners=5pt,fill=blue!20] (20,24) rectangle (26,28);
[align=center](0) at (23,27.25)$\nbhd^2_1$;
in 25,25.6,26
[black] (23,) circle (1pt);
in 22,22.5,23
[black] (23,) circle (1pt);

[rounded corners=5pt,fill=blue!20] (20,17) rectangle (26,21);
[align=center](0) at (23,20)$\nbhd^2_\ell$;
in 18,18.5,19
[black] (23,) circle (1pt);
in 13,14,15
[black] (23,) circle (2pt);

[rounded corners=5pt,fill=blue!20] (20,7) rectangle (26,11);
[align=center](0) at (23,10)$\nbhd^2_{\ell^2-\ell+1}$;
in 8,8.5,9
[black] (23,) circle (1pt);
in 5,5.5,6
[black] (23,) circle (2pt);

[rounded corners=5pt,fill=blue!20] (20,0) rectangle (26,4);
[align=center](0) at (23,3)$\nbhd^2_{\ell^2}$;
in 1,1.5,2
[black] (23,) circle (1pt);

[->] (15.25,24) – (22,25.4);
[->] (15.25,24) – (20.5,20);
[->] (15.7,19) – (22,24.4);
[->] (15.7,19) – (20.5,19);
[->] (15.25,2) – (22,2);
[->] (15.25,2) – (22,8);
in 27,28,29
[black] (,14) circle (2pt);

in 27,28,29
[black] (,30) circle (1 pt);

[align=center](0) at (33,30)Step $r$
$q$ $\nbhd$s
$1$ machine per $\nbhd$;

[rounded corners=5pt,fill=blue!20] (30,24) rectangle (36,28);
[align=center](0) at (33,27.25)$\nbhd^r_1$;
[draw, rounded corners, align=center,fill=pink] (6) at (33,25.5)Machine $1$
in 7,9,11,13,15,17,19,21
[black] (33,) circle (2pt);

[rounded corners=5pt,fill=blue!20] (30,0) rectangle (36,4);
[align=center](0) at (33,3.3)$\nbhd^r_q$;
[draw, rounded corners, align=center,fill=pink] (6) at (33,1.5)Machine $q$

[->] (28,26) – (31,26);
[->] (28,25) – (31,25);

[->] (28,2) – (31,2);
[->] (28,1) – (31,1);

The neighborhood routing structure.

We define a collection of MPC machine states as “intermediate outboxes” $\outbox^t = (\outbox^t_1, \dots, \outbox^t_q)$ for each step $t$ to represent an assignment of message packets to machines in the same $t$th-level neighborhood as the packet destination.
That is, we require that each $\outbox^t_i$ satisfy

\begin{equation}\label{eq:outbox}
\outbox^t_i = \set{(\msg, \src, \dst): i \in \nbhd^t(\dst)}
\end{equation}

We say that $\outbox^t$ are valid intermediate outboxes for $\outbox$ if:

* $\outbox^t$ satisfies <Ref>;

* there is a one-to-one mapping between packets in $\outbox$ and $\outbox^t$; and

* local memory constraints are maintained up to a factor of two[For the sake of simplicity, we assume that the encoding $\msg$ also contains all relevant metadata about the packet $\src$ and $\dst$. That is, we only track the message size $|\msg|$.]

\[\sum_{\msg \in \outbox^t_i} |\msg| \leq 2s.\]

Note that $\outbox$ satisfies the conditions for $\outbox^0$, and the only sequence of embeddings that satisfies the conditions for $\outbox^r$ is $\inbox$.
An inductive argument that applies <Ref> $r$ times completes the proof.

For any $t \in \set{ 0, \dots, r-1}$ and $\rho < \frac\delta2$, there exists an $O(\frac{1 + \gamma}{\rho})$-round $(\gamma, \delta, \rho)$-MPC protocol that takes as input any satisfactory $\outbox^t$ and returns some satisfactory $\outbox^{t+1}$.

The protocol operates in two phases:

* The pre-computation phase, where relevant message size metadata is computed using $O(r - t)$ rounds of communication.

* The message-passing phase, where all messages are propagated in $r - t$ rounds of communication in order to convert $\outbox^t$ to $\outbox^{t+1}$.

Since $r = O(\frac{1 + \gamma}\rho)$, the bound on total number of rounds is satisfied.

The algorithm maintains the invariant that all communication occurs within $t$-level neighborhoods $\nbhd^t_j$ without any mixing between neighborhoods; this is possible because of the assumed validity of $\outbox^t$, which implies that all messages whose packets appear in $\nbhd^t_j$ of $\outbox^t$ have ultimate destinations in $\nbhd^t_j$.
Concretely, if $(\msg, \src, \dst) \in \outbox^t_i$ and $i \in \nbhd^t_j$, then $\dst \in \nbhd^t_j$.

We first explain the routing strategy for the message-passing phase by describing an itinerary of machines that each message packet will be routed to and proving that this itinerary meets the conditions needed to be executed by an $(r-t)$-round $(\gamma, \delta, \rho)$-MPC protocol.
We then describe how the metadata necessary for the itinerary computations can be obtained during the pre-computation phase.

*Message-passing phase.
We first introduce some packet notation to track all relevant metadata about any message in the $t$th intermediate step.
Fix some particular input $\outbox^t$.

* Let $\packet = (\msg, \src, \dst, \src^t)$ denote a packet that contains a message $\msg$ and metadata concerning its “global” source $\src$ and destination $\dst$ (i.e. $(\msg, \src, \dst) \in \outbox_\src, \inbox_\dst$) and its “local” source $\src^t$ from within $\outbox^t$ (i.e. $(\msg, \src, \dst) \in \outbox^t_{\src^t}$).

* We write $\packet \in \outbox^t_i$ if $\src^t = i$
and $\packet \in \nbhd$ if $\packet \in \outbox^t_i$ for some $i \in \nbhd$.

* Let $\srcnbhd^{t, \tau}(\packet) = \nbhd^\tau(\src^t)$ represent the neighborhood of size $\ell^{r-\tau}$ contains $\packet$ (i.e. $\packet \in \srcnbhd^{t, \tau}(\packet)$) and $\dstnbhd^{t}(\packet) = \nbhd^{t+1}(\dst)$ denote the neighborhood of size $\ell^{r-t-1}$ that contains the ultimate destination $\dst$. Because $\packet \in \nbhd^t_j$ if and only if $\dst \in \nbhd^t_j$, it follows that $\dstnbhd^t(\packet) \subset \srcnbhd^{t, t}(\packet)$.

* Let $|\packet| = |\msg|$ be the total number of bits needed to encode the packet.

* We establish a lexicographical ordering that depends first on $\src^t$ and next on $\dst$.
That is, we say that $P' < P$ for some $P' = (\msg', \src', \dst', \src^{t \prime})$ if $\src^{t\prime} < \src^t$, or if $\src^{t \prime} = \src^t$ and $\dst' < \dst$.

We develop a packet scoring function $z^{t, \tau}(\packet)$, which in turn induces an itinerary function $b^{t, \tau}(\packet) \in [q]$ that assigns an intermediate machine to hold packet $\packet$ after $r-\tau$ communication steps.
These functions are carefully chosen in order to ensure that the local memories of each individual machine are bounded by $O(s)$ and that the number of machine each sends messages to and receives messages from is bounded by $O(\ell^2)$.
Critically, we ensure that $b^{t, \tau}(\packet) \in \srcnbhd^{t, \tau}(\packet)$; that is, we initially rearrange packets within solely within the smallest neighborhoods of $\outbox^t$ and gradually propagate packets more widely.
That way, each packet $\packet$ obeys a trajectory of the following form over $r-t$ MPC rounds:

\begin{multline*}
b^{t, r}(\packet) = \src^t \in \srcnbhd^{t, r}(\packet) \Longrightarrow b^{t, r-1}(\packet) \in \srcnbhd^{t, r-1}(\packet) \Longrightarrow \dots \\  \Longrightarrow b^{t, t+1}(\packet) \in \srcnbhd^{t, t+1}(\packet)  \Longrightarrow b^{t, t}(\packet) \in \dstnbhd^t(\packet).
\end{multline*}

To define these functions, we first define partial sums of message sizes in order to later determine an itinerary of machines that $\packet$ will be routed to in between $\src^t$ and some destination machine in $\dstnbhd^t(\packet)$.
The first term, $\ps^{t, \tau}(\packet)$, sums the size of all “lesser” packets that share a destination neighborhood $\dstnbhd^t(\packet)$ and a $\tau$th level input neighborhood $\srcnbhd^{t, \tau}(\packet)$:

\begin{align*}
\ps^{t, \tau}(\packet) &= \sum_{\substack{\packet' \in \srcnbhd^{t, \tau}(\packet) \\ \dstnbhd^t(\packet') = \dstnbhd^t(\packet) \\ \packet' < \packet}} |\packet'|.
\end{align*}

The second term, $\lds^{t, \tau}(\packet)$, sums the size of all packets that share an input neighborhood but have a “smaller” destination neighborhood than $\packet$:

\begin{align*}
\lds^{t, \tau}(\packet) &= \lds^t(\srcnbhd^{t, \tau}(\packet), \dstnbhd^{t}(\packet)),
\end{align*}

\begin{align*}
% \lds^t(\srcnbhd, \dstnbhd) &= \sum_{\packet' \in \srcnbhd} |\packet'| \cdot \indicator{\dstnbhd^{t}(\packet') < \dstnbhd}.
\lds^t(\srcnbhd, \dstnbhd) &= \sum_{\substack{\packet' \in \srcnbhd \\ \dstnbhd^{t}(\packet') < \dstnbhd}} |\packet'|.
\end{align*}

We now define the packet scoring and itinerary functions for any $\tau \in \set{t, \dots, r}$:

\[z^{t, \tau}(\packet) = \begin{cases}
% 2s \cdot \firstchild(\srcnbhd^{t, \tau}(\packet)) + \lds^{t, \tau}(\packet) + \ps^{t, \tau}(\packet) & \tau \geq t + 1, \\
% 2s \cdot \firstchild(\dstnbhd^{t}(\packet))  + 2 \cdot \ps^{t, \tau}(\packet) & \tau = t.
2s \cdot \min \srcnbhd^{t, \tau}(\packet) + \lds^{t, \tau}(\packet) + \ps^{t, \tau}(\packet) & \tau \geq t + 1, \\
2s \cdot \min \dstnbhd^{t}(\packet)  + 2 \cdot \ps^{t, \tau}(\packet) & \tau = t.
\end{cases}\]

\[b^{t, \tau}(\packet) = \floor{\frac{z^{t, \tau}(\packet)}{2s}}.\]

We prove a series of claims to establish that the packet scoring and itinerary functions are properly defined.

[Itinerary range]
For any $\tau \in \set{t, \dots, r}$, the itinerary function satisfies

\[b^{t, \tau}(\packet) \in \begin{cases}
\srcnbhd^{t, \tau}(\packet) & \tau \geq t + 1 \\
\dstnbhd^t(\packet) & \tau = t.
\end{cases}\]

As an immediate consequence, $b^{t, r}(\packet) = \src^t$ for $\packet = (\msg, \src, \dst, \src^t)$.

We first bound the scoring function $z^{t, \tau}$.
Note that

\begin{align*}
\lds^{t, \tau}(\packet) + \ps^{t, \tau}(\packet)
&\leq \sum_{\packet' \in \srcnbhd^{t, \tau}(\packet)} |\packet'| - |\packet| \\
&\leq |\srcnbhd^{t, \tau}(\packet)| \cdot 2s - |\packet|.
\end{align*}

Therefore, for $\tau > t$,

\begin{equation}\label{eq:src-nbhd-gap}
% z^{t, \tau}(\packet) \in \left[2s \cdot \firstchild(\srcnbhd^{t, \tau}(\packet)), 2s \cdot (\firstchild(\srcnbhd^{t, \tau}(\packet)) +  |\srcnbhd^{t, \tau}(\packet)|) - |\packet|\right],
z^{t, \tau}(\packet) \in \left[2s \cdot \min\srcnbhd^{t, \tau}(\packet), 2s \cdot (\min\srcnbhd^{t, \tau}(\packet) +  |\srcnbhd^{t, \tau}(\packet)|) - |\packet|\right],
\end{equation}

\[b^{t, \tau}(\packet) \in [\min\srcnbhd^{t, \tau}(\packet), \min\srcnbhd^{t, \tau}(\packet) +  |\srcnbhd^{t, \tau}(\packet)|),\]

which proves the first case of the claim.
The second case follows by observing that

\[\ps^{t, t}(\packet) \leq s \cdot |\dstnbhd^t(\packet)| - |\packet|.\]

Were it not true, there would exist at least one machine $i \in \dstnbhd^t(\packet)$ that must receive more an $s$ quantity of messages at the end of the entire round of the protocol $\pi$ (i.e. $\sum_{\msg \in \inbox_i} |\msg| > s$), which contradicts the MPC assumption.

[Gaps between scores]
If $\packet_1 \neq \packet_2$ and $z^{t, \tau}(\packet_1) \leq z^{t, \tau}(\packet_2)$, then
\[ z_{t, \tau}(\packet_1) + |\packet_1| \leq z^{t, \tau}(\packet_2).\]

First, let $\tau > t$.
Consider the case where $\srcnbhd^{t, \tau}(\packet_1) \neq \srcnbhd^{t, \tau}(\packet_2)$.
By <Ref> and our assumption that $z^{t, \tau}(\packet_1) \leq z^{t, \tau}(\packet_2)$, it must be the case that $\srcnbhd^{t, \tau}(\packet_1) < \srcnbhd^{t, \tau}(\packet_2)$.
Hence, we have the following by applying <Ref>.

\begin{align*}
&z^{t, \tau}(\packet_2) - z_{t, \tau}(\packet_1)\\
% &\quad\geq 2s \cdot (\firstchild(\srcnbhd^{t, \tau}(\packet_2)) - \firstchild(\srcnbhd^{t, \tau}(\packet_1)) - |\srcnbhd^{t, \tau}(\packet_1)| + |\packet_1|  \\
&\quad\geq 2s \cdot (\min\srcnbhd^{t, \tau}(\packet_2) - (\min\srcnbhd^{t, \tau}(\packet_1) + |\srcnbhd^{t, \tau}(\packet_1)| - |\packet_1|))  \\
&\quad\geq |\packet_1|.
\end{align*}

Otherwise, if $\srcnbhd^{t, \tau}(\packet_1) = \srcnbhd^{t, \tau}(\packet_2)$, then

\begin{align*}
z^{t, \tau}(\packet_2) - z_{t, \tau}(\packet_1)
&= (\lds^{t, \tau}(\packet_2) + \ps^{t, \tau}(\packet_2)) - (\lds^{t, \tau}(\packet_1) + \ps^{t, \tau}(\packet_1))  \\
&= \sum_{\packet' \in S_2} |\packet'| - \sum_{\packet' \in S_1} |\packet'|,
\end{align*}

for some packet subsets $S_1, S_2 \subset \srcnbhd^{t, \tau}(\packet_1)$.
By further inspecting the respective $\lds^{t,\tau}$ and $\ps^{t, \tau}$ terms, we observe that $S_1 \subset S_2$ and $\packet_1 \in S_2 \setminus S_1$.
The claim immediately follows.

The argument for the case $\tau = t$ is nearly identical.

[Local memory bound]
For any $b \in \N$,

\begin{align*}
% \sum_{\packet} |\packet| \indicator{b^{t, \tau}(\packet) = b} \leq \begin{cases}
\sum_{\packet: b^{t, \tau}(\packet) = b} |\packet| \leq \begin{cases}
2s & \tau \in \set{t, r} \\
3s & \tau \in \set{t + 1, \dots, r}.\\
\end{cases}
\end{align*}

The case $\tau = r$ is an immediate consequence of the inductive assumption that $\outbox^t$ satisfies the desired intermediate properties.

For all other cases, let $\set{\packet_1, \dots, \packet_n}$ denote all packets with $b^{t, \tau}(\packet_i) = b$ and let $z^{t, \tau}(\packet_1) \leq \dots \leq z^{t, \tau}(\packet_n)$ without loss of generality.
We use <Ref>, the assumption that all $|\packet_i| \leq s$, and the boundedness of $z^{t, \tau}(\packet_i)$ from <Ref> to conclude the proof.

\begin{align*}
\sum_{i=1}^n |\packet_i|
&\leq \sum_{i=1}^{n-1} (z^{t, \tau}(\packet_{i+1}) - z^{t, \tau}(\packet_i)) + |\packet_n| \\
&\leq z^{t, \tau}(\packet_{n}) - z^{t, \tau}(\packet_1) + s \\
&\leq \begin{cases}
2s & \tau = t, \\
3s & \tau > t.
\end{cases}\qedhere
\end{align*}

[Intra-class distance preservation]
If $\packet_1$ and $\packet_2$ satisfy $\srcnbhd^{t, \tau+1}(\packet_1) = \srcnbhd^{t, \tau+1}(\packet_2)$ and $\dstnbhd^t(\packet_1) = \dstnbhd^t(\packet_2)$, then

\[z^{t, \tau}(\packet_1) - z^{t, \tau}(\packet_2) = z^{t, \tau+1}(\packet_1) - z^{t, \tau+1}(\packet_2).\]

Since $\srcnbhd^{t, \tau+1}(\packet_1) = \srcnbhd^{t, \tau+1}(\packet_2)$, it follows that $\srcnbhd^{t, \tau}(\packet_1) = \srcnbhd^{t, \tau}(\packet_2)$ and therefore,

\begin{align*}
z^{t, \tau}(\packet_1) - z^{t, \tau}(\packet_2) &= \ps^{t, \tau}(\packet_1) - \ps^{t, \tau}(\packet_2) \\
% &= \sum_{\substack{\packet' \in \srcnbhd^{t, \tau}(\packet_1) \\ \dstnbhd^t(\packet') = \dstnbhd^t(\packet_1)}} |\packet'| \cdot \indicator{\packet_1 \leq \packet' < \packet_2}\\
&= \sum_{\substack{\packet' \in \srcnbhd^{t, \tau}(\packet_1) \\ \dstnbhd^t(\packet') = \dstnbhd^t(\packet_1) \\ \packet_1 \leq \packet' < \packet_2}} |\packet'| \numberthis \label{eq:tau} \\
z^{t, \tau+1}(\packet_1) - z^{t, \tau+1}(\packet_2) &= \ps^{t, \tau+1}(\packet_1) - \ps^{t, \tau+1}(\packet_2) \\
% &= \sum_{\substack{\packet' \in \srcnbhd^{t, \tau+1}(\packet_1) \\ \dstnbhd^t(\packet') = \dstnbhd^t(\packet_1)}} |\packet'| \cdot \indicator{\packet_1 \leq \packet' < \packet_2}.
&= \sum_{\substack{\packet' \in \srcnbhd^{t, \tau+1}(\packet_1) \\ \dstnbhd^t(\packet') = \dstnbhd^t(\packet_1) \\ \packet_1 \leq \packet' < \packet_2}} |\packet'| \numberthis \label{eq:tau1}.
\end{align*}

Because $\packet_1, \packet_2 \in \srcnbhd^{t, \tau+1}(\packet_1)$, the defined packet ordering implies that any $\packet' \in [\packet_1, \packet_2)$ must satisfy $\packet' \in \srcnbhd^{t, \tau+1}(\packet_1)$.
Therefore, <Ref> are equal and the claim holds.

[Distinct recipients bound]
For any $b$,

\[|\set{b^{t, \tau}(\packet): b^{t, \tau+1}(\packet) =  b}| \leq 3\ell.\]

Within each root neighborhood $\nbhd^\tau_j$, there exist at most $\ell$ destination neighborhoods in $\dstnbhd^{t}(\packet)$ for $\packet \in \nbhd^\tau_j$.

Fix some such $\dstnbhd$ and let $\packet_1, \dots, \packet_n$ denote all packets with $b^{t, \tau+1}(\packet) = b$ and $\dstnbhd^{t}(\packet_i) = \dstnbhd$.
Without loss of generality, assume that $z^{t, \tau}(\packet_1) \leq \dots \leq z^{t, \tau}(\packet_n)$.
Because all such packets belong to the same machine in step $r-\tau-1$ (i.e. $b^{t, \tau+1}(\packet_i) = b$ for all $i \in [n]$), they belong share the same source neighborhood of size $\ell^{r - \tau-1}$ (i.e. $\srcnbhd^{t, \tau+1}(\packet_i) = \srcnbhd^{t, \tau+1}(\packet_1)$).
By <Ref> and the definition of $b^{t, \tau}$,

\begin{align*}
b^{t, \tau}(\packet_i) - b^{t, \tau}(\packet_1)
&\leq 1 + \frac1{2s}(z^{t, \tau}(\packet_i) - z^{t, \tau}(\packet_1)) \\
&= 1 +\frac1{2s}( z^{t, \tau+1}(\packet_i) - z^{t, \tau+1}(\packet_1)) \\
&\leq 2 + b^{t, \tau+1}(\packet_i)  - b^{t, \tau+1}(\packet_1) = 2.
\end{align*}

Therefore, there are at most three possible values of $b^{t, \tau}(\packet_i)$.

The claim follows by considering each of the $\ell$ destination neighborhoods separately:

\begin{align*}
\abs{\set{b^{t, \tau}(\packet): b^{t, \tau+1}(\packet) =  b}}
&= \sum_{\dstnbhd} \abs{\set{b^{t, \tau}(\packet): b^{t, \tau+1}(\packet) =  b, \ \dstnbhd^t(\packet) = \dstnbhd}} \\
&\leq 3\ell.\qedhere
\end{align*}

[Distinct senders bound]
For any $b$,

\[|\set{b^{t, \tau+1}(\packet): b^{t, \tau}(\packet) =  b}| \leq 3\ell^2.\]

Within each $\nbhd^\tau_j$, there exist at most $\ell^2$ distinct pairs of destination neighborhoods $\dstnbhd^t(\packet)$ and source neighborhoods $\nbhd^{t, \tau}(\packet)$ for $\packet \in \nbhd^\tau_j$.

As before, we fix some $\dstnbhd$ and $\srcnbhd$ and let $\packet_1, \dots, \packet_n$ all satisfy $b^{t, \tau}(\packet_i) = b$, $\dstnbhd^{t}(\packet_i) = \dstnbhd$, and $\srcnbhd^{t, \tau+1} = \srcnbhd$.
Using the same argument, we show that
\[\abs{\set{b^{t, \tau+1}(P_i): i \in [n]}} \leq 3.\]

We conclude by considering all such pairs.

As a result of Claims <ref>, <ref>, and <ref>, we conclude that each packet $\packet = (\msg, \src, \dst, \src^t)$ can be equipped with some itinerary
\[\src^t = b^{t,r}(\packet), \ b^{t, r-1}(\packet), \dots, b^{t, t+1}(\packet), \ b^{t, t}(\packet) \in \dstnbhd^t(\packet)\]

that properly translates an instances of $\outbox^t$ to $\outbox^{t+1}$ and does so without ever requiring local memory more than $3s = O(N^\delta)$ on any intermediate step or any machine to send or receive messages from more than $3\ell^2 = O(N^\rho)$ other machines.
This itinerary can be executed using an $(r - t)$-round $(\gamma, \delta, \rho)$-MPC protocol.

*Pre-computation phase.
It remains to show that each $b^{t, \tau}$ can be computed for each packet.
To do so, we prove that there exists an $O(r-t)$-round $(\gamma, \delta, \rho)$-MPC protocol that ends with each machine $i$ knowing $\ps^{t,\tau}(\packet)$ and $\lds^{t, \tau}(\packet)$ for each $\packet \in \outbox^t_i$ and $\tau \in \{t, \dots, r\}$.
We design an MPC protocol that uses the tree structure to propagate information about individual child neighborhoods to their parents and vice versa.
We describe recursive relationships that elucidate how to compute the two salient quantities.

First, we introduce a useful intermediate term.

\[\ps^{t, \tau}(i, \dstnbhd) = \sum_{\substack{i' \in \nbhd^\tau(i) \\ i' < i  }} \sum_{\substack{\packet' \in \outbox^t_{i'} \\ \dstnbhd^t(\packet') = \dstnbhd}} |\packet'|,\]

denote the sum of all packet that are contained by “lesser” machines that share source and destination neighborhoods.
Note that $\ps^{t, \tau}(\packet)$ can be computed for any $\packet \in \outbox^t_i$ locally by machine $i$ given prior knowledge of $\ps^{t, \tau}(i, \dstnbhd^t(\packet))$.
Thus, the pre-computation phase need only compute the latter term.

We also introduce a term that represents sum of the sizes of all packets that share source and destination neighborhoods:

\[\ns^t(\srcnbhd, \dstnbhd) = \sum_{\substack{\packet' \in \srcnbhd \\ \dstnbhd^t(\packet') = \dstnbhd}} |\packet'|.\]

Now, we provide the recurrences for any $\tau < r$ (or for any $\srcnbhd$ satisfying $|\srcnbhd| > 1$:

\begin{align*}
&\ps^{t, \tau}(i, \dstnbhd)
\\&\quad=
% \begin{cases}
% \ps^{t, \tau + 1}(i, \dstnbhd) + \ps^{t, \tau}(\firstchild(\nbhd^{\tau+1}(i)), \dstnbhd) \\ %& \tau < r \\
\ps^{t, \tau + 1}(i, \dstnbhd) + \ps^{t, \tau}(\min\nbhd^{\tau+1}(i), \dstnbhd) \\ %& \tau < r \\
% 0 & \tau = r\end{cases}\\
\\&\quad=
\ps^{t, \tau + 1}(i, \dstnbhd) + \sum_{\substack{\srcnbhd \in \children(\nbhd^\tau(i)) \\ \srcnbhd < \nbhd^{\tau+1}(i)}} \ns^t(\srcnbhd, \dstnbhd), \\%& \tau < r \\
% 0 & \tau = r\end{cases}\\
&\ns^t(\srcnbhd, \dstnbhd) =%\\&\quad=
\sum_{\srcnbhd' \in \children(\srcnbhd)} \ns^{t}(\srcnbhd, \dstnbhd), \numberthis \label{eq:ns-rec} \\
&\lds^{t}(\srcnbhd, \dstnbhd) =%\\&\quad=
% \begin{cases}
\sum_{\srcnbhd' \in \children(\srcnbhd)} \lds^{t}(\srcnbhd, \dstnbhd) \numberthis \label{eq:lds-rec}.% & \tau < r \\
% \sum_{\packet' \in \srcnbhd} |\packet'| \cdot \indicator{\dstnbhd^{t}(\packet') < \dstnbhd} & \tau = r.
% \end{cases}
\end{align*}

When $\tau = r$, the terms $\ps^{t, \tau}(i, \dstnbhd)$, $\ns^t(\nbhd^r(i), \dstnbhd)$, and $\lds^t(\nbhd^r(i), \dstnbhd)$ can be computed locally within machine $i$.

We follow a tree-like communication pattern to compute all relevant sums.
Each machine $i \in [q]$ computes
\[\set{\ps^{t, \tau}(i, \dstnbhd): \tau \geq t, \ \dstnbhd \in \children(\nbhd^t(i))}\]

\[\set{\lds^{t}(\nbhd^\tau(i), \dstnbhd): \tau \geq t, \ \dstnbhd \in \children(\nbhd^t(i))}\]

by completing $r-t$ propagate-up rounds, $r-t$ aggregation rounds, and $r-t$ propagate-down rounds.

* The propagate-up rounds compute the neighborhood-wide message-size summations $\ns^t(\nbhd^\tau(i), \dstnbhd)$ and $\lds^t(\nbhd^\tau(i), \dstnbhd)$ in each machine $i$ satisfying

$i = \min\nbhd^\tau(i)$
for each $\tau$ and $\dstnbhd$.

* The aggregation rounds accumulate $\ns$ terms of the same level into specific $\ps$ terms.

* The propagate-down rounds iteratively compute and share the $\ps$ and $\lds$ terms with all relevant machines.

Propagate-up rounds: Fix some neighborhood $\nbhd_j^t$.
After $r-\tau$ propagate-up rounds, the goal is to compute the terms $\ns^t(\srcnbhd, \dstnbhd)$ and $\lds^t(\srcnbhd, \dstnbhd)$ for each relevant destination neighborhood $\dstnbhd \in \children(\nbhd_j^t)$ and source neighborhood $\srcnbhd \in \desc^{\tau}(\nbhd_j^t)$ within a single machine in each source neighborhood,

$\min \srcnbhd$.
We argue that this is possible inductively.

Before performing any computation (that is, after “round 0”), each machine $i$ individually computes $\ns^t(\nbhd^r(i), \dstnbhd)$ and $\lds^t(\nbhd^r(i), \dstnbhd)$ by aggregating the messages encoded in its own representation of $\outbox_i^t$.

We assume that the procedure works as specified for $r - \tau $ rounds of communication.
Fix some $\srcnbhd^{\tau-1} \in \desc^{\tau-1}(\nbhd^t_j)$.
Then, for every $\srcnbhd^\tau \in \children{\srcnbhd^{\tau-1}}$, the quantities

\begin{align*}
&\{\ns^{t}(\srcnbhd^\tau, \dstnbhd): \dstnbhd \in \children(\nbhd^t_j)\} \\
&\quad \cup \{ \lds^{t}(\srcnbhd^\tau, \dstnbhd): \dstnbhd \in \children(\nbhd^t_j)\}
\end{align*}

have already been computed and stored in $\min\srcnbhd^\tau$.

By the recurrence relations of <Ref>, $\ns^t(\srcnbhd^{\tau-1}, \dstnbhd)$ and $\lds^t(\srcnbhd^{\tau-1}, \dstnbhd)$ are functions of those quantities.
Thus, it suffices to have each machine $\min \srcnbhd^\tau$ machine transmit its relevant terms to $\min \srcnbhd^{\tau-1}$.
A round of MPC communication that transmits such messages involves each machine sending most one message of size $\ell$ and receiving at most $\ell$ messages, each of size $O(\ell)$.

Inductively, we ensure that all neighborhood sums are computed after $r-t$ propagate-up rounds.
Because each machine handles at most $\ell$ distinct messages having total size $O(\ell^2)$ per MPC round, this protocol does not violate the bounded message size and bounded distinct message constraints (so long as $\ell^2 \ll s$), which can be guaranteed for sufficiently large $n$, so long as $\ell = O(n^{\rho/2})$.

Aggregation rounds:
After the completion of the aggregation rounds, each machine $i$ computes terms of the form
\[\set{\ps^{t, \tau}(\min\nbhd^{\tau+1}(i), \dstnbhd): \dstnbhd \in \children(\nbhd^t_j)}\]

from relevant $\ns^t$ terms if $i = \min\nbhd^{\tau+1}(i)$.
By the recurrence, it is sufficient for machine $i$ to following $\ell^2$ distinct terms

\[\set{\ns^t(\srcnbhd, \dstnbhd) : \srcnbhd \in \children(\nbhd^{\tau}(i)),  \dstnbhd \in \children(\nbhd^t_j)}.\]

Since all machines $i$ already knows such terms for $\srcnbhd = \nbhd^{\tau+1}(i)$, it can obtain the remaining $\ns^t$ terms by simultaneously sharing information with its “cousin machines:” $\min \srcnbhd$, for all $\srcnbhd \in \children(\nbhd^{\tau}(i))$.

This can be handled by a single round of communication where each “$(\tau+1)$th-level neighborhood representative” machine forwards its sums sums to up to $\ell$ other first representatives, for a total messaging cost of $O(\ell^2)$.

We use $r - t$ separate rounds to repeat this process for each $\tau \geq t$.

Propagate-down rounds:
It remains to compute each $\ps^{t, \tau}(i, \cdot)$ and $\lds^t(\nbhd^\tau(i), \cdot)$ term at each machine $i$.
The relevant $\lds^t$ terms have already been computed by each respective $\min\nbhd^\tau(i)$ machine and can be propagated to machine $i$ by using $r - t$ rounds of tree-propagation through intermediate $\min\nbhd^{\tau'}(i)$ machines.

The same is possible for $\ps^{t, \tau}$ terms, although the individual terms need to be added in order to follow the recurrence.
We propagate the terms in the same way as the $\lds^t$ terms, but we take special care to carry out the extra additions.
This can be accomplished simultaneously to the other propagate-down rounds.
This protocol involves each first-child node sharing at most $\ell$ distinct messages, each of size at most $O((r-t) \ell)$.
As before, every node sends and receives at most $O((r-t)\ell^2) \ll s$ words.

After these $3(r - t)$ rounds have elapsed, each machine $i$ computes $b^{t, \tau}(\packet)$ for each $\packet \in \outbox^t_i$.
Using this itinerary, the machines routes tuples of the form
\[(\packet, b^{t, r}(\packet), \dots, b^{t,t}(\packet))\]

to the respective machine $b^{t, \tau}(\packet)$ in round $r - \tau$.
Due to the arguments presented at the start of the section, this procedure terminates with each $(\msg, \src, \dst)$ tuple being held by some machine $i$ such that the resulting $\outbox^{t+1}_i$ is valid, and the procedure involves at most $O(r - t) = O(\frac{1 + \gamma}\rho)$ rounds of $(\gamma, \delta, \rho)$-MPC computation.

§.§.§ Proof outline of <Ref>

The proof of <Ref> involves an adaptation to the proof of Theorem 3.1 of <cit.>.
To avoid restating the proof in its entirety, we provide a brief outline of the proof of Theorem 3.1 and explain which modification is necessary.

Theorem 3.1 is a consequence of Lemmas B.4, B.5, and B.6 of <cit.>, which establish that there exist single-layer transformers that simulate the initialization, a round of computation and communication, and the output formatting of any fixed $(\gamma, \delta)$-MPC protocol.
The input and output steps of $(\gamma, \delta)$, and $(\gamma, \delta, \rho)$-MPC protocols are identical, only Lemma B.5 needs to be examined.

To simulate a single round of an MPC protocol with a transformer, all local computations are simulated in the element-wise multi-layer perceptron (MLP) units, and all communication is handled in a single multi-headed self-attention layer (Lemma B.7)
Since $(\gamma, \delta, \rho)$-MPC protocols add no restrictions related to local computation, the former can be simulated in exactly the same manner with identical MLPs, and it remains to analyze the construction of Lemma B.7.
We restate Lemma B.7 and provide an replacement lemma that suffices to prove <Ref>.

For any $R$-round MPC protocol with local memory $s$ and $q$ machines and any round $r \in [R-1]$, there exists a single-layer transformer $f \in \trans{m, H, 1}{q, 0}$ with $H = O(\log\log q)$ and $m = O(s^4 \log q)$, which, given as input a length-$q$ encoding of each machine's outgoing messages in round $r$, returns an encoding of each machine's incoming messages in round $r + 1$.

For any $R$-round MPC protocol with local memory $s$, $q$ machines, and a $k$-machine communication limit and any round $r \in [R-1]$, there exists a single-layer single-headed transformer $f \in \trans{m, H, 1}{q, 0}$ with $H = 1$ and $m = O(k^4 s \log q)$, which, given as input a length-$q$ encoding of each machine's outgoing messages in round $r$, returns an encoding of each machine's incoming messages in round $r + 1$.

<Ref> is an immediate consequence of Lemma 3.2 of <cit.>, their main technical result, which already applies to the regime with limits on the number of machines in communication.

By replacing <Ref> with <Ref>, applying the remainder of the proof of Theorem 3.1 of <cit.>, and letting $k = O(n^\rho)$, the proof of <Ref> is complete.

§ SINGLE-LAYER TRANSFORMERS AND GRAPH REASONING TASKS

This appendix presents the results of <Ref>, which separates the collection of graph reasoning tasks into those retrieval tasks that can be efficiently solved by single-layer parameter-efficient transformers—including node count, edge count, edge existence, and node degree—and those parallelizable or search tasks that require deeper constructions—including connectivity, shortest path, cycle check, and triangle count.
Taken together, these results establish that the single-layer transformers of the  regime are capable of solving simple aggregation-based tasks, but that their known limitations in capacity as communication protocols of <cit.> apply to non-trivial graph reasoning tasks.

We specific a particular node/edge encoding of an input graph $G = (V, E)$ and a graph reasoning task using a consistent encoding scheme that closely resembles the encoding used in our graph reasoning experiments and those of <cit.>.
This encoding is distinguished by the fact that each node and vertex of the graph $G$ is represented by exactly one token, rather than the pair of tokens utilized in our experiments.
This choice ensures that any trivial pre-processing of graph inputs (e.g. using a positional embedding to associate each edge token pair) need not count towards the single-layer transformer model.

The node/edge encoding of a graph $G = (V, E)$ with $V \subseteq [n]$ and $|V| + |E| \leq N-1$ and a graph reasoning task $P$ is a sequence
\[X = X(G, P) = (x_1, \dots, x_N) \in \R^{N \times d}\]

where $d = 5$ and each
\[x_i = (x_i^1, x_i^2, \isvertex_i, \isedge_i, \isquery_i) \in \{0, \dots, n\}^2 \times \bit^3 \]

satisfies the following conditions:

* For each $v \in V$, there exists exactly one $i \in [N-1]$ with $x_i = (v, 0, 1, 0, 0)$.

* For each $(u, v) \in E$, there exists exactly $i \in [N-1]$ with $x_i = (u,v,0, 1, 0)$.

* The token $x_N$ encodes a particular instance of the task $P$, by encoding $\isquery_N = 1$ with an optional edge or node encoding.
That is, for tasks without arguments (such as triangle count), $x_N = (0,0,0, 0, 1)$. For tasks with a single node argument $v \in [n]$ (such as node degree), $x_N = (v, 0, 1, 0, 1)$. For tasks with a pair of node arguments $u, v \in [n]$ (such as shortest path and connectivity), $x_N = (u, v,0, 1, 1)$.

* All other tokens satisfy $x_i = (0, 0, 0, 0, 0)$.

We say that a single-layer transformer $f \in \trans{m, H, 1}N$ solves task $P$ on graph $G$ if the output corresponding to the task description $f(X(G, P))_N$ encodes the output of the task. Since $f$ is a single-layer transformer, we can write this output as

\begin{equation}\label{eq:single-output}
f(X)_N = \psi\paren{\sum_{h=1}^H\sm\paren{\phi(x_N)^\T Q_h K_h^\T \phi(X)^\T} \phi(X) V_h}
\end{equation}

for element-wise multi-layer perceptrons
\[\phi: \R^d \to \R^m, \psi: \R^m \to \R\]

broadcasted across each input (i.e. $\phi(X) = (\phi(x_1), \dots, \phi(x_N)) \in \R^{N \times m}$) and weight matrices
\[Q_1, \dots, Q_H, K_1, \dots, K_H, V_1, \dots, V_H \in \R^{m \times m}.\]

Throughout, we assume that all parameters in the transformer model and intermediate numerical quantities can be written using $O(\log N)$-bit floating point numbers.
This assumption can be satisfied for the positive results of <Ref> and is necessary to obtain the negative results of <Ref>.

We permit the element-wise MLPs $\phi$ and $\psi$ to be arbitrary functions for the negative results, while restricting them to be MLPs that can be approximated using bounded-size multi-layer ReLU networks for the positive results.
While we do not make these ReLU networks explicit, we restrict ourselves to simple operations that can be computed using linear transformations and the application of smooth univariate functions.

Finally, we acknowledge that the negative results in are largely superseded by those of <cit.>, which establishes that $\L$-complete languages (including graph connectivity and cycle check) cannot be efficiently solved by constant-depth transformers, let alone single-layer transformers.
We include these bounds anyway to mark a contrast with our positive results; draw further connections to the communication complexity lens on transformers; and exhibit simple task instances $(G, P)$ that require greater depth, including constant diameter and constant degree graphs.

§.§ Positive results for single-layer transformers

[Formal version of <Ref>;  computes retrieval tasks]theoremthmposoneL
Fix any graph reasoning task among node count, edge count, edge existence, and node degree and any graph size $N$.
Then, there exists a single-layer single-headed transformer $f \in \trans{m, 1, 1}{N}$ with embedding dimension $m = O(\log N)$ that solves the task on all graphs $G = (V, E)$ of size $|V| + |E| \leq N-1$ formatted as node/edge embedding sequences.

We prove that a single head of self-attention with input and output MLPs can solve these retrieval and aggregation tasks in a parameter-efficient manner by first carefully designing a universal input MLP $\phi: \R^d \to \R^{m}$ for some $m = O(\log N)$ to produce embeddings that encode useful graph properties.
Then, we define task-specific query, key, and value matrices $Q, K, V: \in \R^{m \times m}$ and output MLPs $\psi: \R^m \to \R$ that produce the correct answers.
While we do not explicitly account for finite-precision computations, all of the operations utilized can be carefully implemented to respect $O(\log N)$-bit floating-point numerical representations using the technical approaches of <cit.>.

*Shared sinusoidal embedding MLP.
We denote the embedding output of the input MLP as

\[\phi(x_i) = (\isquery_i, \isvertex_i, \isedge_i, \phi'(x_i)) \in \R^m\]

for some $\phi'(x_i): \R^d \to \R^{2m'}$ for some $m' = O(\log N)$ and $m = 2m' + 3$.
For some fixed $a_1, \dots, a_{m'} \in [0, 1]$ to be determined, let

\[\phi'(x_i) = \begin{cases}
\eta(x_i^1) & \text{if $\isvertex_i = 1$,}\\
\xi(x_i^1, x_i^2) & \text{if $\isedge_i = 1$,}\\
\vec{0} & \text{otherwise,}
\end{cases}\]

where $\eta$ is a sinusoidal embedding MLP for nodes with

\begin{equation}\label{eq:eta}
\eta(v) =(\sin(2 \pi a_1 v), \cos(2 \pi a_1 v ), \dots, \sin(2 \pi a_{m'} v ), \cos(2 \pi a_{m'} v )) \in \R^{2m'},
\end{equation}

and $\xi$ is an edge embedding satisfying

\[\xi(u, v) = \frac{m'}{m' + \eta(u)^\T \eta(v)}(\eta(u) + \eta(v)).\]

We first show that the node embeddings are approximately orthogonal.
By employing standard trigonometric identities, we obtain
\[\eta(u)^\T \eta(v) = \sum_{j=1}^{m'} \cos(2\pi a_j(u - v)),\]

and note that $\norm[2]{\eta(v)}^2 = m'$.
We use a standard concentration argument to prove that $|\eta(u)^\T \eta(v)| \ll m'$ if $u \neq v$ with high probability.

[Near-orthogonality of embeddings $\eta$]
There exist coefficients $a_1, \dots, a_{m'} \in [0, 1]$ that comprise the embedding $\eta: [n] \to \R^m$ of <Ref> such that

\[\abs{\eta(u)^\T \eta(v)} \leq 2 \sqrt{m' \log n}, \ \text{if $u \neq v$.}\]

We employ the probabilistic method.
Consider $m'$ iid random variables $\ba_1, \dots, \ba_{m'} \sim \unif([0, 1])$ and let $\bfeta$ represent the respective node embedding.
Fix some arbitrary $u, v \in [n]$ with $u \neq v$ and note that

\[\bfeta(u)^\T \bfeta(v)= \sum_{j=1}^{m'} \cos(2\pi \ba_j(u - v)).\]

For any $j \in [m']$, the integrality of $u-v$ implies that

\[\EE[\ba_j]{\cos(2\pi \ba_j(u - v))} = 0.\]

Hoeffding's inequality provides the following bound:

\begin{align*}
\pr{\abs{\bfeta(u)^\T\bfeta(v)} \geq 2 \sqrt{m' \log n}}
&\leq \exp\paren{-\frac{4 m' \log n}{2m'}} \leq \frac{1}{n^2}.
\end{align*}

By applying a union bound to all ${n \choose 2}$ choices of $u$ and $v$, we have the following:

\[\pr{\forall u, v \in [n],\  u \neq v: \ \abs{\bfeta(u)^\T\bfeta(v)} \geq 2 \sqrt{m' \log n}} \leq \frac{n(n-1)}{2n^2} < 1.\]

Hence, there exists a satisfactory set of coefficients $a_1, \dots, a_{m'}$.

For some $\eta$ satisfying <Ref>, let $\chi = \max_{u, v \in [n], u \neq v} |\eta(u)^\T \eta(v)| \leq 2 \sqrt{m' \log n}$.
By taking $m' = O(\log n)$ be sufficiently large, we guarantee that $\chi \leq \frac{m'}c$ for any constant $c \geq 2$.

We then bound all relevant inner products between vertex and edge embeddings for sufficently large $m'$ (and sufficiently small $\chi$).
We assume throughout that $u, u', v, v'$ are distinct and note that $\xi(u, v) = \xi(v, u)$ (and omit symmetric inequalities).

\begin{align*}
\norm[2]{\eta(v)}^2 &= m'. \numberthis \label{eq:eta-same}\\
\abs{\eta(u)^\T \eta(v)} &\leq \chi \leq \frac{m'}{4} . \numberthis \label{eq:eta-diff}\\
\abs{\eta(u)^\T \xi(u, v) - m'}
&=\abs{\frac{m'(m' + \eta(u)^\T \eta(v))}{m' + \eta(u)^\T \eta(v)} - m'} = 0. \numberthis \label{eq:eta-xi-same}\\
\abs{\eta(u)^\T \xi(u', v')}
&= \abs{\frac{m' (\eta(u)^\T \eta(u') + \eta(u)^\T \eta(v'))}{m' + \eta(u')^\T \eta(v')}}
\leq \frac{2m'\chi}{m' - \chi} \leq 4\chi \leq \frac{m'}{4}.
\numberthis \label{eq:eta-xi-diff} \\
\abs{\norm[2]{\xi(u, v)}^2 - 2m'}
&=\abs{\frac{m^{\prime 2}\cdot (2m' + 2 \eta(u)^\T \eta(v)) - 2m'(m' + \eta(u)^\T \eta(v))^2}{(m' + \eta(u)^\T \eta(v))^2} } \\
&\leq \abs{\frac{2m' \eta(u)^\T \eta(v)}{m' + \eta(u)^\T \eta(v)}} \leq \frac{2 m' \chi}{m' - \chi} \leq 4 \chi \leq \frac{m'}4. \numberthis \label{eq:xi-same}\\
\abs{\xi(u, v)^\T \xi(u, v') - m'}
&= \abs{\frac{m^{\prime2}(m' + \eta(u)^\T \eta(v') + \eta(u)^\T \eta(v) + \eta(v)^\T \eta(v'))}{(m' + \eta(u)^\T \eta(v))(m' + \eta(u)^\T \eta(v'))} - m'} \\
&= \abs{\frac{m^{\prime 2}\eta(v)^\T \eta(v') - m' \eta(u)^\T \eta(v) \eta(u)^\T \eta(v')}{(m' + \eta(u)^\T \eta(v))(m' + \eta(u)^\T \eta(v'))}} \\
&\leq \frac{m^{\prime 2} \chi + m' \chi^2}{(m' - \chi)^2}
\leq 4 \chi + 4 \frac{\chi^2}{m'} \leq \frac{m'}{4}. \numberthis \label{eq:xi-diff1}\\
|\xi(u, v)^\T \xi(u', v')|
&=\abs{\frac{m^{\prime 2}(\eta(u)^\T \eta(u') + \eta(u)^\T \eta(v') + \eta(v)^\T \eta(u') + \eta(v)^\T \eta(v')}{(m' + \eta(u)^\T \eta(v))(m' + \eta(u')^\T \eta(v'))}} \\
&\leq \frac{4m^{\prime 2} \chi}{(m' - \chi)^2} \leq 16 \chi \leq \frac{m'}{4}. \numberthis \label{eq:xi-diff2}
\end{align*}

Therefore, we conclude the following bounds:

\begin{align*}
\eta(u)^\T \eta(v), \ \eta(u)^\T \xi(u', v'), \ \xi(u, v)^\T \xi(u', v') &\in \left[-\frac{m'}{4}, \frac{m'}{4}\right], \\
\norm[2]{\eta(v)}^2, \ \eta(u)^\T \xi(u, v), \ \xi(u, v)^\T \xi(u, v') &\in \left[\frac{3m'}{4}, \frac{5m'}{4}\right], \\
\norm[2]{\xi(u, v)}^2 & \in \left[\frac{7m'}{4}, \frac{9m'}4 \right].
\end{align*}

We now apply the above bounds to prove that each task can be solved by a single-headed transformer with weights $Q, K, V \in \R^{m \times m}$, output MLP $\psi: \R^m \to \R$, and shared input MLP $\phi$ discussed previously.

*Node count task.
If $P$ encodes the node count task, we specify weights matrices $Q, K, V$ in order to ensure that $Q^\T \phi(x_N) = m' e_1$[Note that $Q^\T \phi(x_N)$ is the only relevant query embedding to the output $f(X)_N$; see <Ref>.]; $K^\T\phi(x_i) = (\isvertex_i + \isquery_i) \cdot e_1$; and $V^\T\phi(x_i) = \isquery_i \cdot e_1$[While we do not specify the entries of $Q, K, V$, they are clearly linear transformations.].
Then, the following is true of exponentiated key/query inner products and scalings products of value vectors:

\begin{align*}
\exp(\phi(x_N)^\T Q K^\T \phi(x_i))
&= \begin{cases}e^{m'} & \text{if $\isvertex_i=1$ or $i=N$,} \\ 1 & \text{otherwise.}\end{cases} \\
\exp(\phi(x_N)^\T Q K^\T \phi(x_i)) V \phi(x_i) &=
\begin{cases}
e^{m'} \cdot e_1 & \text{if $i = N$,} \\
\vec{0} & \text{otherwise.}
\end{cases}
\end{align*}

The output of the softmax is then

\begin{align*}
\sm\paren{\phi(x_N)^\T Q K^\T \phi(X)^\T} \phi(X) V
&= \frac{\sum_{i=1}^N \exp(\phi(x_N)^\T Q K^\T \phi(x_i)) V \phi(x_i) }{\sum_{i=1}^N  \exp(\phi(x_N)^\T Q K^\T \phi(x_i)) } \\
% &= \frac{\sum_{i=1}^{N-1} \exp(m'\cdot \isvertex_i) \cdot \vec{0} + \exp(m') \cdot e_1}{\sum_{i=1}^{N-1} \exp(m'\cdot \isvertex_i) + \exp(m')} \\
&= \frac{e^{m'}}{e^{m'}\cdot (1 + |V|) + 1 \cdot (N - |V| - 1)} \cdot e_1.
\end{align*}

\[y_N := (\sm\paren{\phi(x_N)^\T Q K^\T \phi(X)} \phi(X) V)_1 \in \R\]

denote the first coordinate of the softmax output.
By taking $m' \geq \log(4N)$, we guarantee that

\begin{align*}
% (\sm\paren{\phi(x_N)^\T Q^\T K \phi(X)} \phi(X) V)_1
&\in \left[ \frac{1}{1 + |V| + N / e^{m'}}, \frac{1}{1 + |V|}\right]
\subseteq  \left[ \frac{1}{\frac54 + |V|}, \frac{1}{1 + |V|}\right].
\end{align*}

By letting the output MLP $\psi$ approximate the function $\psi(z) = \floor{\frac{1}{z_1} - 1}$ for $z_1 \in [1, N+2]$, we can ensure that $f(X)_N = |V|$.

*Edge count task.
We similarly let $Q^\T \phi(x_N) = m' e_1$; $K^\T\phi(x_i) = (\isedge_i + \isquery_i) \cdot e_1$; and $V^\T\phi(x_i) = \isquery_i \cdot e_1$.
By an identical analysis of the attention matrix and $\psi$ construction, we ensure that $f(X)_N = |E|$.

*Edge existence task.
Under the node/edge encoding, we assume that the edge existence task is encoded as $x_N = (x_N^1, x_N^2, 0, 1, 1)$ for some $x_N^1, x_N^2\in V$ and should return $f(X)_N = \indicator{(x_N^1, x_N^2) \in E}$.
We choose our weight matrices to ensure that $Q^\T\phi(x_N) = \phi'(x_N) = \xi(x_N^1, x_N^2)$; $K^\T\phi(x_i) = \phi'(x_i)$, and $V^\T\phi(x_i) = 2(1 - \isquery_i)e_1$.
By applying <Ref> and letting $m' = O(\log N)$ to be sufficiently large, the following is true the query/key inner products:

\begin{align*}
\exp(\phi(x_N)^\T Q K^\T \phi(x_i))
&= \exp(\norm[2]{\xi(x_N^1, x_N^1)}^2)
\geq e^{7m'/4} & \text{if $\set{x_i^1, x_i^2} = \set{x_N^1, x_N^2}$,}\\
\exp(\phi(x_N)^\T Q K^\T \phi(x_i))
&\leq e^{5m'/4} \leq \frac{1}{8N} e^{7m'/4} & \text{otherwise.}
\end{align*}

We can therefore analyze the softmax output $y_N$ to obtain the following bound:

\begin{align*}
%  (\sm\paren{\phi(x_N)^\T Q^\T K \phi(X)} \phi(X) V)_1
%  &\leq \frac{2e^{2m'}\indicator{(x_N^1, x_N^2) \in E} + N \cdot \frac1{2N}e^{2m'}}{e^{2m'}(1 + \indicator{(x_N^1, x_N^2) \in E})} \\
&\leq \frac{2\exp(\norm[2]{\xi(x_N^1, x_N^1)}^2)\indicator{(x_N^1, x_N^2) \in E} + 2N \cdot \frac1{8N}e^{7m'/4}}{\exp(\norm[2]{\xi(x_N^1, x_N^1)}^2)(1 + \indicator{(x_N^1, x_N^2) \in E})} \\
&\leq \frac{2 \indicator{(x_N^1, x_N^2) \in E} + \frac14}{1 + \indicator{(x_N^1, x_N^2) \in E}}
\leq \indicator{(x_N^1, x_N^2) \in E} + \frac14, \\
%  (\sm\paren{\phi(x_N)^\T Q^\T K \phi(X)} \phi(X) V)_1
%  &\geq \frac{2e^{2m'}\indicator{(x_N^1, x_N^2) \in E}}{e^{2m'}(1 + \indicator{(x_N^1, x_N^2) \in E}) + N \cdot \frac1{4N} e^{2m'}} \\
&\geq \frac{2\exp(\norm[2]{\xi(x_N^1, x_N^1)}^2)\indicator{(x_N^1, x_N^2) \in E}}{\exp(\norm[2]{\xi(x_N^1, x_N^1)}^2)(1 + \indicator{(x_N^1, x_N^2) \in E}) + N \cdot \frac1{8N} e^{7m' / 4}} \\
&\geq \frac{2 \indicator{(x_N^1, x_N^2) \in E}}{1 + \indicator{(x_N^1, x_N^2) \in E} + \frac18}
\geq \indicator{(x_N^1, x_N^2) \in E} - \frac14.
\end{align*}

\[y_N \in \begin{cases}
\left[-\frac14, \frac14\right] & \text{if $(x^1_N, x^2_N) \not\in E$,} \\
\left[\frac34, \frac54\right] & \text{if $(x^1_N, x^2_N) \in E$.}
\end{cases}\]

Therefore, it suffices to design a threshold output MLP $\psi$ that satisfies

\[\psi(z) = \begin{cases}
1 & z_1 \geq \frac34, \\
0 & z_1 \leq \frac14,
\end{cases}\]

in order to distinguish between the two possible output ranges.
This can be easily constructed by taking a linear combination of two ReLU neurons.

*Node degree task.
We assume that the task is encoded as $x_N = (x_N^1, 0, 1, 0, 1)$ and should return $f(X)_N = \deg(x_N^1) := \abs{\set{(x_N^1, v) \in E}}$.
We use weight matrices with $Q^\T\phi(x_N) = \phi'(x_N) = \eta(x_N)$; $K^\T\phi(x_i) = \phi'(x_i)$; and $V^\T\phi(x_i) = \isquery_i$.
This ensure that the following is true about the query/key inner products for sufficiently large $m'$:

\begin{align*}
\exp(\phi(x_N)^\T Q K^\T \phi(x_i)) &= e^{m'} & \text{if $i = N$ or $x_N^1 \in \set{x_i^1, x_i^2}$,}\\
\exp(\phi(x_N)^\T Q K^\T \phi(x_i)) &\leq e^{ m'/4} \leq \frac{1}{4N} e^{m'} & \text{otherwise.}
\end{align*}

We similarly ensure that the following holds about the softmax output $y_N$.

\begin{align*}
%  (\sm\paren{\phi(x_N)^\T Q^\T K \phi(X)} \phi(X) V)_1
&\leq \frac{e^{m'}}{e^{m'} \cdot (\deg(x_N^1) + 2)}
= \frac{1}{\deg(x_N^1) + 2}, \\
%  (\sm\paren{\phi(x_N)^\T Q^\T K \phi(X)} \phi(X) V)_1
&\geq \frac{e^{m'}}{(\deg(x_N^1) + 2)e^{m'} + N \cdot \frac1{4N} e^{m'}} \\
&\geq \frac{1}{\deg(x_N^1) + \frac94}.
\end{align*}

We then use the similar approach employed in the node count task to choose an output MLP that approximately computes $\phi(z) = \floor{\frac{1}{z_1} - 2}$.

We thus conclude that there exist single-layer transformers that solve all of the described tasks.

§.§ Negative results for single-layer transformers

[Formal version of <Ref>;  cannot compute search or retrieval tasks]

Fix any graph reasoning task among graph connectivity, shortest path, and cycle detection.
Any single-layer transformer $f \in \trans{m, H, 1}{N}$ with $O(\log N)$-bit precision that solves the task on all graphs $G = (V, E)$ of size $|V| + |E| \leq N-1$ formatted as node/edge embedding sequences has width satisfying $mH = \Omega(N / \log N)$.

Our negative results generalizes and applies the approach of <cit.> to prove negative results for single-layer transformers by communication complexity reductions.
The bounds hinge on the following fundamental fact about the hardness of a two-player game where two agents jointly attempt to compute a set disjointness quantity that depends on both of their inputs with bounded communication.
[Disjointness communication complexity lower bound <cit.>]
Suppose Alice and Bob are given inputs $a, b \in \bit^r$ and wish to jointly compute $\disj(a, b) = \max_i a_i b_i$ by alternately sending single-bit messages to one another.
Any deterministic protocol that computes $\disj(a, b)$ requires at least $r$ rounds of communication, or $r$ bits of information.

We first generalize Theorem 7 of <cit.> to show that no transformer can efficiently solve an embedded set disjointness problem without having a width that scales linearly in $r$.
We prove the theorem and later apply to it prove negative results about relevant graph reasoning tasks.
To demonstrate that the graph reasoning tasks do not require pathological input graphs $G$ to be hard, we exhibit particular input graph instances with constant graph diameter or constant degree where the task cannot be efficiently solved.

For some sequence length, fix two disjoint subsets $A, B \subset [N-1]$, and consider a single-layer transformer $f \in \trans{m, H, 1}{N}$ with $O(\log N)$-bit precision that solves set disjointness, i.e. $f(X)_N = \disj(a, b)$ for any input $X$ where $X_A$ is a function of Alice's input $a \in \bit^r$, $X_B$ is a function of Bob's input $b \in \bit^r$, and $X_{[N] \setminus (A \cup B)}$ is fixed regardless of $a$ and $b$.

Then, $f$ has width satisfying $mH = \Omega(r / \log N)$.

Consider any transformer $f$ that solves $\disj$ as specified in the theorem statement.
We show that this implies the existence of a $O(mH \log N)$-round communication protocol that solves $\disj(a, b)$ for any inputs $a, b \in \bit^{r}$.
An application of <Ref> immediately proves the theorem statement.

If such a transformer $f$ exists, then the following is true for some $\phi, \psi$, and $Q, K, V$:

\begin{align*}
\disj(a, b)
&= \psi\paren{\sum_{h=1}^H\sm\paren{\phi(x_N)^\T Q_h K_h^\T \phi(X)} \phi(X) V_h} \\
&=\psi\paren{\sum_{h=1}^H \frac{Z_{h,A}\exp(L_{h,A}) + Z_{h,B}\exp(L_{h,B}) + Z_{h,[N] \setminus (A \cup B)} \exp(L_{h,[N] \setminus (A \cup B)})}{\exp(L_{h,A}) + \exp(L_{h,B}) + \exp(L_{h,[N] \setminus (A \cup B)})}},
\end{align*}

for partial softmax and normalization terms[
These terms are designed in order to facilitate computation with $\log(N)$-bit floating-point numbers. Note that each $Z_{h,S}$ is a convex combination of value vectors $V_h^\T \phi(x_i)$, which means that $Z_{h,S}$ requires no more bits of precision to accurately approximate than $V_h^\T \phi(x_i)$.
Similarly, each $L_{h, S}$ is within an $O(\log N)$ additive factor of $\max_{i \in S} \phi(x_N)^\T Q_h K_h^\T \phi(x_i)$.
Finally, the output of the softmax term for head $h$ is a convex combination of $Z_{h, A}$, $Z_{h, B}$, and $Z_{h, [N] \setminus (A \cup B)}$, which makes accurate computation of each output possible without requiring greater precision.
] defined as follows for $S \subset [N]$ and $h \in [H]$:

\begin{align*}
Z_{h, S} &= \frac{\sum_{i \in S} \exp(\phi(x_N)^\T Q_h K_h^\T \phi(x_i)) V_h \phi(x_i)}{\sum_{i \in S}  \exp(\phi(x_N)^\T Q_h K_h^\T \phi(x_i))} \in \R^m,\\
L_{h, S} &= \log\paren{\sum_{i \in S}  \exp(\phi(x_N)^\T Q_h K_h^\T \phi(x_i))} \in \R_+.
\end{align*}

The definition of input instances $X$ implies that Alice can compute $Z_{h, A}$ and $L_{h, A}$ as a function of her input $a$; Bob can similarly compute $Z_{h, B}$ and $L_{h, B}$ from $b$; and $Z_{h, [N] \setminus (A \cup B)}$, $L_{h, [N] \setminus (A \cup B)}$, and all implementation details of $f$ are known by all players.
Therefore, Bob can compute $\disj(a, b)$ by an $O(mH \log N)$-round protocol where Alice sends him $(Z_{h, A}, L_{h,A})$ bit-by-bit.

It remains to apply <Ref> to each graph reasoning task by defining graph instance encodings $X$ that encode $\disj(a, b)$ in the solution to the task for some $r = \Theta(N)$.

For each task, we provide a pair of “hard instances:” one with constant degree and one with constant diameter, in order to obey different notions of graph simplicity.

*Graph connectivity task.

For both instances, on any disjointness input $a, b \in \bit^r$, we define a graph $G = (V, E)$ with $|V| + |E| = O(r)$ whose edges encode the input, i.e. $E = E(a, b)$.
We define three fixed disjoint sets of potential edges $\bar{E}_A, \bar{E}_B, \bar{E}_*$ with $|\bar{E}_A| +  |\bar{E}_B| + |\bar{E}_*| = O(r)$ such that $E = E_A(a) \cup E_B(b) \cup \bar{E}_*$, where $E_A(a) \subset \bar{E}_A$ is a function of only Alice's input $a$ and $E_B(b) \subset \bar{E}_B$ is a function of Bob's $b$.

We define an enumeration of all vertices in $V$ and potential edges in $\bar{E}_A, \bar{E}_B, \bar{E}_*$.
We first fix their sizes $|V|, |\bar{E}_A|, |\bar{E}_B|, |\bar{E}_*|$ and then index the vertices and edges in the order $V, \bar{E}_A, \bar{E}_B, \bar{E}_*$.
That is,

\begin{align*}
V &= \set{1, \dots, |V|}, \\
\bar{E}_* &= \set{(u_i, v_i): i \in S_*}, \ \text{for} \ S_* = \set{|V| + 1, \dots, |V| + |\bar{E}_*|},\\
\bar{E}_A &= \set{(u_i, v_i): i \in A}, \ \text{for} \ A = \set{|V|+|\bar{E}_*| + 1, \dots, |V| + |\bar{E}_*| + |\bar{E}_A|}, \\
\bar{E}_B &= \set{(u_i, v_i): i \in B}, \ \text{for} \ B = \set{|V|+|\bar{E}_*| + |\bar{E}_A| + 1, \dots, |V| + |\bar{E}_*| + |\bar{E}_A| + |\bar{E}_B|}.
% \set{(u_{|V| +1}, v_{|V|+1}) \dots, (u_{|V| + |\bar{E}|}, v_{|V| + |\bar{E}|})}\subset V^2 \\
% \bar{E}_A &= \set{(u_{|V| + |\bar{E}| +1}, v_{|V| + |\bar{E}| +1}) \dots, (u_{|V| + |\bar{E}| + |\bar{E}_A|}, v_{|V| + |\bar{E}|+ |\bar{E}_A|})}\subset V^2 \\
\end{align*}

This implies that the following transformer input $X \in R^{N \times d}$ for $N = |V| + |S_*| + |A| + |B| + 1$ is a valid node/edge encoding such that inputs $X_A$ is a function of $a$, $X_B$ is a function of $b$, and $X_{[N] \setminus (A \cup B)}$ is constant:

* For $i \in V$, $x_i = (i, 0, 1, 0, 0)$ encodes a fixed vertex.

* For $i \in S_*$, $x_i = (u_i, v_i, 0, 1, 0)$ encodes a fixed edge.

* For $i \in A$, $x_i$ represents edge $(u_i, v_i)$ if it exists:

\[x_i = \begin{cases}(u_i, v_i, 0, 1, 0) & \text{if $(u_i, v_i) \in E_A(a)$,} \\ (0, 0, 0,0,0) & \text{otherwise.}\end{cases}\]

* For $i \in B$, $x_i$ represents edge $(u_i, v_i)$ if it exists:

\[x_i = \begin{cases}(u_i, v_i, 0, 1, 0) & \text{if $(u_i, v_i) \in E_B(b)$,} \\ (0, 0, 0,0,0) & \text{otherwise.}\end{cases}\]

* $x_N = (u, v,0, 1, 1)$ encodes the task token for some fixed $(u, v) \in V^2$.

Constant-diameter instance:
We define a graph $G$ of diameter at most 8 that encodes an disjointness instance $a, b \in \bit^r$ in an instance of connectivity.

* Let $|V| = 3r + 2$, and let nodes 1 and $3r+2$ denote the “source” and “sink” node respectively.
That is, $x_N = (1, 3r+2, 0, 1, 1)$.

* Edges between the source node 1 and nodes $\set{2, \dots, r+1}$ and between the end node $3r + 2$ and $\set{2r + 2, \dots, 3r+1}$ always are included. That is,
\[E_* = \set{(1, i): i \in \set{2, \dots, r+1}} \cup \set{(3r+2, i): i \in \set{2r+2, \dots, 3r+1}}.\]

* Alice's input is encoded as edges $(i + 1, i + r + 1)$ for $i \in [r]$. That is,

\[E_A(a) = \set{(i + 1, i + r + 1) : a_i = 1} \subset \bar{E}_A = \set{(i + 1, i + r + 1): i \in [r]} .\]

* Bob's inputs are similarly encoded as $(i + r+ 1, i + 2r)$:

\[E_B(b) = \set{(i + r + 1, i + 2r + 1) : b_i = 1} \subset \bar{E}_B = \set{(i + r+ 1, i + 2r + 1): i \in [r]} .\]

We visualize this construction of $G$ in <Ref>.

There exists a path between node 1 and node $3r + 2$ if and only if there exists some $i\in[r]$ such that $(i + 1, i + r+1), (i + r + 1, i + 2r + 1) \in E$, which corresponds to $a_i = b_i = 1$.
Thus, the graph $G$ is connected if and only if $\disj(a, b) = 1$.
Any transformer $f$ that computes
\[f(X)_N = \indicator{1 \text{ and } 3r+2 \text{ are connected in} G}\]

also solves disjointness.
Since $N = |V| + |S_*| + |A| + |B| + 1 = \Theta(r)$, we conclude the proof of hardness of solving graph connectivity on this instance by applying <Ref>.

[scale=0.7,-,>=stealth',shorten >=1pt,auto,node distance=3cm,
thick,main node/.style=circle,draw,font=]

[main node] (1) at (0,2) 1;
[main node] (2) at (2,4) 2;
[main node] (3) at (2,2) 3;
[main node] (4) at (2,0)4;
[main node] (5) at (4,4)5;
[main node] (6) at (4,2) 6;
[main node] (7) at (4,0)7;
[main node] (8) at (6,4)8;
[main node] (9) at (6,2)9;
[main node] (10) at (6,0)10;
[main node] (11) at (8,2)11;
[every node/.style=font=]
(1) edge node[above]  (2)
(1) edge node [left]  (3)
(1) edge node [left]  (4)
(2) edge node [above] $a_1$  (5)
(4) edge node [above] $a_3$  (7)
(5) edge node [above] $b_1$  (8)
(6) edge node [above] $b_2$  (9)
(8) edge node [left]   (11)
(9) edge node [left]   (11)
(10) edge node [left]   (11);

The constant diameter graph construction for $r=3$, $A=(1,0,1)$ and $B=(1,1,0)$. The source $1$ and sink $11$ are connected which is equivalent to $\disj(A,B)=1$ by construction.

Constant-degree instance:
We can define a degree-3 graph $G$ that similarly encodes a disjointness instance $a, b$.
To do so, we modify the previous construction by replacing the fixed edges $E_*$ with two binary trees, each of depth $O(\log r)$, between the source and end nodes as roots and Alice and Bob's nodes incident to $\bar{E}_A$ and $\bar{E}_B$ respectively as leaves.
The remainder of the construction—including the encoding of $E_A(a)$ and $E_B(b)$ and the connectivity analysis—is identical.
Since a binary tree with $r$ leaves has $O(r)$ nodes and edges, the graph $G$ can be similarly encoded as a length-$N$ transformer input for $N = O(r)$.
See <Ref> for a visualization.

[scale=0.5,-,>=stealth',shorten >=1pt,auto,node distance=3cm,
thick,main node/.style=circle,draw,font=]
[main node] (1) at (0,4) $S$;
[main node] (2) at (2,2) ;
[main node] (3) at (2,6) ;
[main node] (4) at (4,1) ;
[main node] (5) at (4,3) ;
[main node] (6) at (4,5) ;
[main node] (7) at (4,7) ;
[main node] (8) at (12,4) $X$;
[main node] (9) at (10,2) ;
[main node] (10) at (10,6) ;
[main node] (11) at (8,1) ;
[main node] (12) at (8,3) ;
[main node] (13) at (8,5) ;
[main node] (14) at (8,7) ;
[main node] (15) at (6,1) ;
[main node] (16) at (6,3) ;
[main node] (17) at (6,5) ;
[main node] (18) at (6,7) ;
[every node/.style=font=]
(1) edge node[above](2)
(1) edge node[above](3)
(2) edge node[above](4)
(2) edge node[above](5)
(3) edge node[above](6)
(3) edge node[above](7)
(4) edge node[above]$a_4$(15)
(6) edge node[above]$a_2$(17)
(18) edge node[above]$b_1$(14)
(17) edge node[above]$b_2$(13)
(8) edge node[above](9)
(8) edge node[above](10)
(9) edge node[above](11)
(9) edge node[above](12)
(10) edge node[above](13)
(10) edge node[above](14) ;

The degree 3 graph construction for $r=4$, $A=(0,1,0,1)$, $B=(1,1,0,0)$. The source node $S$ and sink node $X$ are connected, which is equivalent to $\disj(A,B)=1$ by construction.

*Shortest path task.

We can modify the graph connectivity constructions $G$ to create a decision variant of shortest path, rather than graph connectivity.
Let $D(G)$ be the length of a path between the source and sink node in each connectivity construction, and note that $D(G) = 4$ for the constant-diameter instance and $D(G) = O(\log r)$ for constant-degree.
We design a new graph $G'$ of size $O(r)$ then appends a path of $D(G) + 1$ vertices to $G$.
Then, the shortest path between the source and sink node is $D(G)$ if they are connected and $D(G) + 1$ if not.

If there exists a transformer $f'$ solves shortest path on graphs of the form $G'$, then there exists a minor modification $f$ that solves graph connectivity on graph $G$.

*Cycle check task.

We again modify the graph connectivity constructions.
We produce $G'$ by adding a single edge to $G$ between the source node 1 and the sink node $3r+2$, which ensures that $G'$ has a cycle if and only if $G$ is connected between the source and sink nodes.
Therefore, a transformer $f'$ can only solve check check if there exists a transformer $f$ that solves connectivity.

§ REPRESENTATIONAL GAPS BETWEEN TRANSFORMERS AND GNNS

Our experiments in <Ref> highlight the differences in graph reasoning abilities between vanilla transformers with a naive input graph tokenization and graph neural networks (GNNs).
These distinctions can be understood as the consequences of model capacity or inductive bias between transformers and GNNs.
This appendix contrasts the novel analysis of the capacities of vanilla transformers in <Ref> with previously established limitations on GNNs.
We present two theoretical tools for deriving negative results on GNN capabilities:  distributed computing model and the Weisfeiler-Leman isomorphism test (WL-test).
We discuss the results implied by these frameworks and contrast them with transformer capabilities and limitations.

§.§ Limitations of GNNs via  analogy

The bidirectional relationship between transformers and the massively parallel computation (MPC) distributed computing model of <cit.> was partially inspired by a similar analogy between GNNs and the  model by <cit.>.

The MPC and  distributed computing protocols differ in their models of how messages are passed between machines.
While MPC protocols permit any machine to send a message to any other machine subject to capacity constraints,  protocols operate on a graph topology that restricts machines to send messages exclusively to and from neighbors.
As a consequence, two nodes in a  graph that are separated by a path of length $p$ cannot share information with one another without $\Omega(p)$ rounds of communication; no similar notion of “long-range communication” exists for MPC.

All message-passing GNNs where each node initially knows only its own features can be simulated by a  protocol whose rounds scales linearly in the depth of the GNN <cit.>.
This reduction implies a lower bound on solving several parallelizable and search tasks discussed in <Ref>.

Any graph neural network $f$ with width (message size) $m$ and depth $L$ that computes any of the following tasks on $n$-node graphs has the following size lower bounds:

* Subgraph connectivity, minimum spanning forest, minumum cut, shortest path: $L \sqrt{m} = \tilde\Omega(\sqrt{n})$.

* Cycle detection, diameter computation: $Lm = \tilde\Omega(n)$.

If $L = O(\log N)$, then for all tasks, $m = \tilde\Omega(n)$.

In contrast, the quantitative bounds in <Ref> establish sharp trade-offs between transformers and GNNs for parallelizable tasks and suggest a possible equivalence for search tasks.

All parallelizable tasks—including (subgraph) connectivity, minimum spanning forest, minimum cut, and cycle detection—can be solved by transformers of depth $L = O(\log n)$ and width $m = O(n^{\epsilon})$ for any constant $\epsilon\in (0, 1)$ due to <Ref>.
In contrast, <Ref> requires that a similar-depth GNNs have width $m = \tilde\Omega(n)$, and a GNN of comparable width requires depth $L= \tilde\Omega(n^{1-\epsilon})$.

On the other hand, search tasks, such as shortest path and diamter, are only guaranteed to be solvable by transformers of depth $O(\log n)$ and width $O(n^{1 + \epsilon})$ (for graphs with $|E|=n^2$) by <Ref>.
This statement compares to the GNN negative results of <Ref>.

§.§ Limitations of GNNs via the Weisfeiler-Leman test

A relationship between GNNs and the Weisfeiler-Leman heuristic graph isomorphism test <cit.> (WL test) further establishes representational limitations of message-passing GNNs.
This connection and the rich literature surrounding it is presented in greater detail by <cit.>.

The 1-WL test is a permutation-invariant test for predicting whether two candidate graphs are isomorphic that works by first labeling each node with the empty set $\emptyset$ and then repeatedly replacing each label with a multiset of its neighbors' labels.
A hierarchy of WL test variants exists where the $k$-WL test maintains a label for each $k$-tuple of vertices.
The failure models of these heuristic solutions are well-understood; critically, the 1-WL test cannot distinguish between connected and disconnected graphs.

The abilities of message-passing GNNs without unique node identifiers to determine whether two graphs are isomorphic are limited by the graphs distinguishable by the 1-WL test <cit.>.
As an immediate consequence, such GNNs cannot solve graph connectivity at all, unlike transformers, which can do so with a logarithmic-depth parameter-efficient representation.
The relationship is bidirectional; message-passing GNNs (and transformers as well) admit an efficient approximation of the 1-WL test.

The effectiveness of these bounds is tempered by the assumption that no node includes identifying features, which is easily overcome by standard GNN models.