betaFeedback

WorksComputer Science

Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth

Abstract

Large Language Models (LLMs) have achieved remarkable progress on complex reasoning tasks, yet the mechanisms by which they acquire reasoning capabilities and the efficiency of their reasoning remain poorly understood. In this paper, we investigate the path-finding problem over directed graphs, a symbolic abstraction of multi-step reasoning. We first characterize the architectural requirements for this task, proving that one-layer transformers require Ω(N2)Ω(N^2) size on dense graphs to implement the key DFS child-selection primitive. While a two-layer transformer implements full DFS with O(Nlog⁡(N))O(N\log(N)) size. Thus, a second layer is necessary and sufficient for near-linear DFS reasoning. We then extend this expressivity analysis to deeper models: for every k≥3k\geq3, a kk-layer transformer implements a bounded-reachability DFS policy with look-ahead horizon 1+2k−31+2^{k-3}, establishing an exponential increase in reachability horizon with depth. Finally, going beyond expressivity, given appropriately curated training data, we show that two-layer transformers can provably learn to execute DFS via gradient flow and generalize to unseen graphs. Together, our results provide a mechanistic account of how transformers implement graph search, how depth expands bounded look-ahead, and how such reasoning algorithms can emerge through training.

Introduction

Large Language Models (LLMs) have demonstrated striking reasoning capabilities across mathematics, code, scientific question answering, and planning, especially when equipped with chain-of-thought (CoT) prompting [39] and test-time scaling of intermediate reasoning steps [10]. Yet our theoretical understanding of these capabilities remains incomplete. We still lack precise answers to several basic questions: how can a transformer implement a multi-step reasoning algorithm, why does architectural depth improve reasoning efficiency, and under what conditions can such an algorithm be acquired through gradient-based training?

A growing body of theoretical work studies these questions through symbolic reasoning tasks, where the algorithmic structure is explicit enough to analyze. Prior results have clarified important aspects of transformer expressivity, showing both limitations of constant-depth models on inherently sequential tasks and the additional power obtained from chain-of-thought computation [8, 17, 22]. Other work has examined depth–width tradeoffs for graph algorithms [27, 42], sample complexity for reasoning tasks [40], and training dynamics for algorithmic primitives such as induction heads, sparse token selection, in-context regression, and Markov-chain structure learning [35, 25, 4, 38].

Despite this progress, graph search remains poorly understood. This setting is especially important because it captures a central difficulty of reasoning: the model must not merely follow a single predetermined chain, but must choose among alternatives, remember what has already been explored, and backtrack when a branch fails. In other words, graph search formalizes the kind of committed exploration and revision that appears in planning, proof search, and multi-step deduction.

Existing theory leaves three gaps. First, most provable learning results for path-finding focus on trees, where there is at most one path between two vertices and the need for genuine search is largely absent [41]. Directed graphs are qualitatively harder: they contain branching, cycles, and dead ends, so a successful algorithm must maintain a visited set and decide when to move forward or backtrack. Second, although prior work shows that constant-depth transformers can implement DFS [22], the architectural threshold for efficient graph search is not known. It is unclear whether one layer suffices, why two layers should be special, and how additional layers translate into improved search efficiency. Third, recent work has analyzed reachability with continuous chain of thought [Zhu et al., 2025a], but the corresponding learnability question for standard discrete CoT traces remains open.

In this paper, we give a theoretical account of how transformers implement, scale, and learn depth-first search (DFS) on directed graphs. We focus on DFS because it is the canonical sequential search algorithm: it combines branching, memory of visited states, forward exploration, and backtracking, while naturally producing a discrete CoT trace. Our results connect three aspects of reasoning—architecture, depth, and training dynamics—within a single graph-search framework.

Our contributions.

  • We identify a sharp depth threshold for efficient DFS. We prove that a one-layer transformer cannot implement even a basic DFS child-selection primitive on dense directed graphs without quadratic representation size, measured as heads ×\times width ×\times precision. In contrast, we construct a two-layer transformer that implements full DFS with near-linear representation size. The separation concerns the width a single attention layer needs, not parameter count or running time, and it shows that the second layer is not merely a convenience: it is necessary and sufficient for exact DFS with sub-quadratic width in our setting.

  • We show that depth gives an exponential increase in look-ahead horizon. Beyond the two-layer DFS construction, we prove that additional layers can perform parallel bounded-reachability computation. After explicit neighbor aggregation, each propagation layer doubles the radius represented in source and child memories. For every k≥3k \ge3, a kk-layer transformer implements a bounded-reachability DFS policy with horizon 1+2k−31+2^{k-3}. This establishes a depth–horizon tradeoff. We distinguish it from worst-case search-efficiency guarantees, which require additional control over the distances of the selected branches.

  • We prove that DFS behavior can emerge through gradient-based training. For a two-layer transformer trained on a permutation-symmetric DFS curriculum, we analyze the gradient-flow dynamics of the relevant attention parameters. The dynamics preserve a low-dimensional invariant structure, and the resulting model generalizes from the training curriculum to unseen graphs and DFS traces. Thus, the construction is not only expressive: it can be learned under a mathematically analyzable training process.

Together, these results provide a mechanistic account of transformer-based graph search. They show that efficient DFS requires a genuine two-layer mechanism, that additional depth yields exponentially larger look-ahead, and that the corresponding search behavior can arise from gradient-based training on discrete chain-of-thought traces. More broadly, our analysis uses directed-graph path finding as a clean theoretical proxy for understanding how reasoning capabilities depend on architecture, depth, and training data.

Preliminaries

Notation. For N∈NN \in\mathbb{N}, let [N]={1,…,N}[N] = \{1,\ldots,N\}. We use A\mathcal{A} to denote the token vocabulary, reserving V\mathcal{V} for the vertex set of a graph. For a finite set K\mathcal{K}, let SK\mathcal{S}_{\mathcal{K}} denote the set of all permutations on K\mathcal{K}. We write τPrompt\tau_{\mathrm{Prompt}} for a prompt, viewed as a sequence of tokens. Throughout the paper, I\boldsymbol{I} denotes the identity matrix, and E\boldsymbol{E} denotes an all-ones matrix of the appropriate size.

Directed graphs and permutations. A directed graph of order NN is an ordered pair G=(V,E)\mathcal{G} = (\mathcal{V},\mathcal{E}), where V=[N]\mathcal{V} = [N] is the vertex set and E⊆V×V\mathcal{E} \subseteq\mathcal{V} \times\mathcal{V} is the edge set. A path from a source node nsn_s to a target node ntn_t is a sequence of vertices

p=(n1,n2,…,nk)p = (n_1,n_2,\ldots,n_k)

with n1=nsn_1 = n_s and nk=ntn_k = n_t, such that (ni→ni+1)∈E(n_i \to n_{i+1}) \in\mathcal{E} for every i∈[k−1]i \in[k-1]. A shortest path is any such path with the minimum number of vertices. For any permutation π\pi of V\mathcal{V}, we define the permuted graph by

π(G)=(V,π(E)),π(E)={(π(u)→π(v)):(u→v)∈E},\pi(\mathcal{G}) = (\mathcal{V},\pi(\mathcal{E})), \qquad\pi(\mathcal{E}) = \{(\pi(u) \to\pi(v)) : (u \to v) \in\mathcal{E}\},

and define the permuted path as π(p)=(π(n1),…,π(nk))\pi(p) = (\pi(n_1),\ldots,\pi(n_k)).

Path-finding problem and depth-first search. Given a directed graph G\mathcal{G}, a source node nsn_s, and a target node ntn_t, the path-finding problem asks for a path from nsn_s to ntn_t, if one exists. Depth-first search (DFS) is a recursive search procedure for this problem. Starting from nsn_s, DFS repeatedly explores outgoing edges from the current node nn. If there exists an unvisited child vv with (n→v)∈E(n \to v) \in\mathcal{E}, the search moves to vv, marks it as visited to avoid cycles, and continues recursively. If no unvisited child remains, the search backtracks to the parent of nn in the current search stack and explores alternative branches. This forward-and-backtracking process terminates either when ntn_t is found, yielding a valid ns→ntn_s \to n_t path, or when the search returns to nsn_s after exhausting all reachable branches.

Multi-head transformer architecture. An LL-layer transformer with HH attention heads is a sequence-to-sequence model. Given an input sequence X=[x1,…,xT]∈Rd×TX = [x_1,\ldots,x_T] \in\mathbb{R}^{d \times T}, the model computes hidden states X(l)∈Rd×TX^{(l)} \in\mathbb{R}^{d \times T} as follows. Let X(1)=XX^{(1)} = X, and for every l∈[L]l \in[L],

X(l+1)=X(l)+σ(Atten⁡(l)(X(l))),(1)X^{(l+1)} = X^{(l)} + \sigma\left(\operatorname{Atten}^{(l)}(X^{(l)})\right), \tag*{(1)}
Atten⁡(l)(X(l))=WO(l)[Head⁡1(l)(X(l))⋮Head⁡H(l)(X(l))],(2)\operatorname{Atten}^{(l)}(X^{(l)}) = W_O^{(l)} \begin{bmatrix} \operatorname{Head}_1^{(l)}(X^{(l)}) \\ \vdots\\ \operatorname{Head}_H^{(l)}(X^{(l)}) \end{bmatrix}, \tag*{(2)}
Head⁡h(l)(X(l))=WV(l,h)X(l)ϕ(l)((X(l))T(WK(l,h))TWQ(l,h)X(l)).(3)\operatorname{Head}_h^{(l)}(X^{(l)}) = W_V^{(l,h)} X^{(l)} \phi^{(l)}\left((X^{(l)})^{T}(W_K^{(l,h)})^{T}W_Q^{(l,h)}X^{(l)}\right). \tag*{(3)}

Here σ\sigma is an element-wise activation function; throughout, we take σ(x)=ReLU⁡(x)=max⁡{0,x}\sigma(x) = \operatorname{ReLU}(x) = \max\{0,x\}. The map Atten⁡(l)\operatorname{Atten}^{(l)} denotes the attention block at layer ll, WO(l)W_{\mathrm{O}}^{(l)} is the output projection, WV(l,h)W_{\mathrm{V}}^{(l,h)}, WK(l,h)W_{\mathrm{K}}^{(l,h)}, and WQ(l,h)W_{\mathrm{Q}}^{(l,h)} are the value, key, and query matrices for head hh, and ϕ(l)\phi^{(l)} is an element-wise attention activation, possibly with normalization.

The transformer output logits are

TF⁡(X;θ)=WRTX(L+1),(4)\operatorname{TF}(X;\theta) = W_{\mathrm{R}}^{T}X^{(L+1)}, \tag*{(4)}

where θ\theta denotes the trainable parameters and WR∈Rd×∣A∣W_{\mathrm{R}} \in\mathbb{R}^{d\times|\mathcal{A}|} is the readout matrix. The next-token distribution is the softmax over these logits:

pθ(v;X)=exp⁡(TF⁡(X;θ)v)∑v′∈Aexp⁡(TF⁡(X;θ)v′),(5)p_{\theta}(v;X) = \frac{\exp(\operatorname{TF}(X;\theta)_v)}{\sum_{v'\in\mathcal{A}}\exp(\operatorname{TF}(X;\theta)_{v'})}, \tag*{(5)}

where TF⁡(X;θ)v\operatorname{TF}(X;\theta)_v is the logit assigned to token vv.

Prompt format and chain of thought. Following Zhu et al. [2025b,a], the transformer path-finding prompt has three parts: (1) a beginning-of-sequence token <s>; (2) a graph-description segment containing MM edges, where each edge is represented by a source token sis_i, a target token tit_i, and a special edge token <e>; and (3) a task-description segment containing the target token nTarn_{\mathrm{Tar}}, a start-reasoning token <r>, and the root token nRootn_{\mathrm{Root}}. We denote the full prompt by τPrompt\tau_{\mathrm{Prompt}}, i.e.,

τPrompt=⟨s⟩,s1,t1,⟨e⟩,⋯ ,sM,tM,⟨e⟩,nTar,⟨r⟩,nRoot.(6)\tau_{\mathrm{Prompt}} = \langle\text{s}\rangle, s_1, t_1, \langle\text{e}\rangle, \cdots, s_M, t_M, \langle\text{e}\rangle, n_{\mathrm{Tar}}, \langle\text{r}\rangle, n_{\mathrm{Root}}. \tag*{(6)}

Starting from nRootn_{\mathrm{Root}}, the transformer predicts tokens autoregressively, generating a chain-of-thought (CoT) trace n1,n2,…,nTn_1, n_2, \ldots, n_T. Generation terminates when the model reaches the target nTarn_{\mathrm{Tar}}, or when it returns to the root nRootn_{\mathrm{Root}} after all of the root’s child nodes have been explored.

Expressivity

Although Merrill and Sabharwal [ [22] showed that constant-depth transformers can perform DFS, the minimal architectural requirements remain unclear. In this section, we first prove that any one-layer transformer that performs DFS on directed graphs of order NN must have Ω(N2)\Omega(N^2) representation size, i.e., heads ×\times width ×\times precision, in the dense-graph regime. This lower bound shows that at least two layers are needed for DFS with sub-quadratic representation size. We then give a two-layer construction with near-linear representation size, and finally show that additional layers provide an exponential improvement in look-ahead depth.

One-layer lower bound for DFS child selection

To formalize the size measure, we first specify the numerical precision of a transformer.

Definition 3.1 (pp-bit precision). A transformer uses pp bits of precision if all coordinates produced by WKW_{\mathrm{K}}, WQW_{\mathrm{Q}}, WVW_{\mathrm{V}}, WOW_{\mathrm{O}}, and the attention heads, after rounding, can be represented with pp bits without changing the computed input-output function. As in Sanford et al. [ [28], attention sums are accumulated in pp-bit fixed-point arithmetic: for an input of length TT, every unnormalized attention weight wjw_j and every summand wjWVxjw_jW_{\mathrm{V}}x_j of an attention numerator is rounded to a pp-bit fixed-point number, and p≥log⁡2Tp \ge\log_2 T. Consequently, the partial sum of an attention numerator or normalizer over any subset of positions is exactly representable with p+⌈log⁡2T⌉=O(p)p+\lceil\log_2 T\rceil= O(p) bits per coordinate. The value dimension of every head is at most dd.

Size measure. As in Sanford et al. [ [28], we quantify a transformer layer by HdpHdp, the number of heads times the embedding dimension times the precision, and call this its representation size; it is the quantity that Sanford et al. [ [28] call simply the size, and we use the longer name because it is a measure of width and precision rather than of parameters or running time. It is the number of bits that one layer of attention can deliver to a single position, which is exactly the quantity controlled by the communication-complexity argument below, and we claim no separation in parameter count or running time. Dense d×dd \times d projection matrices have Θ(d2)=Θ(N2)\Theta(d^2) = \Theta(N^2) entries in the one-layer and in the two-layer setting alike (the matrices of our construction are built from identity and all-ones blocks, but they are still N×NN \times N), and on a dense graph the prompt itself has length Θ(N2)\Theta(N^2), so any model processes Θ(N2)\Theta(N^2) tokens. The separation below is therefore a statement about depth versus width: a single attention layer must route Ω(N2)\Omega(N^2) bits to the output position, whereas with two layers O(Nlog⁡N)O(N \log N) bits per layer suffice, which is within a logarithmic factor of the Ω(N)\Omega(N) bits needed to represent the visited set at all (Section B.3).

We next define a restricted task that isolates the retrieval of an outgoing child.

References

  1. [1]Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In International Conference on Machine Learning, 2024.arxiv.org/abs/2403.06963
  2. [2]Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. Advances in Neural Information Processing Systems, 36: 1560–1588, 2023.arxiv.org/abs/2306.00802
  3. [3]Jannik Brinkmann, Abhay Sheshadri, Victor Levoso, Paul Swoboda, and Elias Bareinboim. A mechanistic analysis of a transformer trained on a symbolic multi-step reasoning task. arXiv preprint arXiv:2402.11917, 2024.arxiv.org/abs/2402.11917
  4. [4]Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Unveiling induction heads: Provable training dynamics and feature learning in transformers. In Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2409.10559
  5. [5]Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and variable creation in self-attention mechanisms. In International Conference on Machine Learning, 2022.arxiv.org/abs/2110.10090
  6. [6]Ezra Edelman, Benjamin L. Edelman, Surbhi Goel, Eran Malach, and Nikolaos Tsilivis. The evolution of statistical induction heads: In-context learning Markov chains. In Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2402.11004
  7. [7]Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In International Conference on Learning Representations, 2024.arxiv.org/abs/2310.04560
  8. [8]Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2305.15408
  9. [9]Arvid Frydenlund. The mystery of the pathological path-star task for language models. arXiv preprint arXiv:2410.13779, 2024.DOI
  10. [10]Daya Guo et al. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.DOI
  11. [11]Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, 2020.DOI
  12. [12]Yixiao Huang, Hanlin Zhu, Tianyu Guo, Jiantao Jiao, Somayeh Sojoudi, Michael I. Jordan, Stuart Russell, and Song Mei. Generalization or hallucination? Understanding out-of-context reasoning in transformers. In Advances in Neural Information Processing Systems, 2025.arxiv.org/abs/2506.10887
  13. [13]Yixiao Huang, Hanlin Zhu, Zixuan Wang, Jiantao Jiao, Stuart Russell, Somayeh Sojoudi, and Song Mei. Transformers probably learn to internalize chain-of-thought. arXiv preprint arXiv:2605.28600, 2026.arxiv.org/abs/2605.28600
  14. [14]Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. LLMs can’t plan, but can help planning in LLM-Modulo frameworks. arXiv preprint arXiv:2402.01817, 2024.arxiv.org/abs/2402.01817
  15. [15]Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331–360. Elsevier, 1997.
  16. [16]Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul McVay, Michael Rabbat, and Yuandong Tian. Beyond A*: Better planning with transformers via search dynamics bootstrapping. arXiv preprint arXiv:2402.14083, 2024.arxiv.org/abs/2402.14083
  17. [17]Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In International Conference on Learning Representations, 2024.arxiv.org/abs/2402.12875
  18. [18]Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In International Conference on Learning Representations, 2023.arxiv.org/abs/2210.10749
  19. [19]Xutao Ma, Yixiao Huang, Hanlin Zhu, and Somayeh Sojoudi. Breaking the reversal curse in autoregressive language models via identity bridge. In International Conference on Machine Learning, 2026.arxiv.org/abs/2602.02470
  20. [22]William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. International Conference on Learning Representations 2024, 2024.arxiv.org/abs/2310.07923
  21. [23]William Merrill and Ashish Sabharwal. Exact expressive power of transformers with padding. arXiv preprint arXiv:2505.18948, 2025.arxiv.org/abs/2505.18948
  22. [24]Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. In International Conference on Learning Representations, 2023.arxiv.org/abs/2301.05217
  23. [25]Eshaan Nichani, Alex Damian, and Jason D. Lee. How transformers learn causal structure with gradient descent. In International Conference on Machine Learning, 2024.arxiv.org/abs/2402.14735
  24. [26]Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. Transformer Circuits Thread, 2022. arXiv:2209.11895.arxiv.org/abs/2209.11895
  25. [27]Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In Advances in Neural Information Processing Systems, 2024a.arxiv.org/abs/2405.18512
  26. [28]Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induction heads task. arXiv preprint arXiv:2408.14332, 2024b.arxiv.org/abs/2408.14332
  27. [29]Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. arXiv preprint arXiv:2402.09268, 2024c.arxiv.org/abs/2402.09268
  28. [30]Abulhair Saparov and He He. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. In International Conference on Learning Representations, 2023.arxiv.org/abs/2210.01240
  29. [31]Abulhair Saparov, Richard Yuanzhe Pang, Vishakh Padmakumar, Nitish Joshi, Mehran Kazemi, Najoung Kim, and He He. Testing the general deductive reasoning capacity of large language models using OOD examples. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2305.15269
  30. [32]Abulhair Saparov, Srushti Pawar, Shreyas Pimpalgaonkar, Nitish Joshi, Richard Yuanzhe Pang, Vishakh Padmakumar, Seyed Mehran Kazemi, Najoung Kim, and He He. Transformers struggle to learn to search. arXiv preprint arXiv:2412.04703, 2024.arxiv.org/abs/2412.04703
  31. [33]Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. GPT-4 doesn’t know it’s wrong: An analysis of iterative prompting for reasoning problems. arXiv preprint arXiv:2310.12397, 2023.arxiv.org/abs/2310.12397
  32. [35]Yuandong Tian, Yiping Wang, Beidi Chen, and Simon S. Du. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2305.16380
  33. [36]Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models—a critical investigation. In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2305.15771
  34. [37]Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In Advances in Neural Information Processing Systems, 2023.arxiv.org/abs/2305.10037
  35. [38]Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D. Lee. Transformers provably learn sparse token selection while fully-connected nets cannot. arXiv preprint arXiv:2406.06893, 2024.arxiv.org/abs/2406.06893
  36. [39]Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, 2022.arxiv.org/abs/2201.11903
  37. [40]Noam Wies, Yoav Levine, and Amnon Shashua. Sub-task decomposition enables learning in sequence to sequence tasks. In International Conference on Learning Representations, 2023.arxiv.org/abs/2204.02892
  38. [41]Tong Yang, Yu Huang, Yingbin Liang, and Yuejie Chi. Multi-head transformers provably learn symbolic multi-step reasoning via gradient descent. arXiv preprint arXiv:2508.08222, 2025. NeurIPS 2025.arxiv.org/abs/2508.08222
  39. [42]Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher, Orr Fischer, Ran Gilad-Bachrach, and Amir Globerson. Depth-width tradeoffs in algorithmic reasoning of graph tasks with transformers. arXiv preprint arXiv:2503.01805, 2025.arxiv.org/abs/2503.01805
  40. [43]Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2020.arxiv.org/abs/1912.10077

Paper details

vlnc:W_ehwrr82k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents