acceptodds
Under review as a conference paper at ICLR 2027

Agentic Transformers Provably Learn to Search via Reinforcement Learning

Abstract

Tree search is a central abstraction behind many language-agent reasoning and decision-making tasks: agents must explore actions, remember failures, and backtrack toward promising alternatives. Yet, we lack a theoretical understanding of how transformer-based policies acquire such search capabilities from the training dynamics of reinforcement learning (RL). We study this question in a stochastic -ary tree environment, where an agentic transformer observes only its trajectory history through interaction and receives a terminal reward for reaching a hidden leaf goal node. We first construct a two-head transformer that implements randomized depth-first search (DFS): one head tracks previous actions, while the other detects failure outcomes and triggers backtracking. We then analyze the training dynamics of policy gradient under a depth-wise curriculum, showing that this same DFS mechanism emerges in stages from sparse reinforcement feedback without expert demonstrations. The resulting policy exhibits depth generalization: after training only on depth- and depth- trees, it succeeds on deeper full trees. We further show that, under imbalanced goal distributions, discounting the return leads to a ranked DFS policy that prioritizes higher-probability branches. Overall, our results identify a mechanistic normal form for transformer-based search, in which attention heads specialize and cooperate to extract decision-relevant traces from context and convert them into agentic action selection via RL training.

Primary area:
learning theory
Keywords:
transformer, training dynamics, reinforcement learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_s4k7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies whether policy-gradient training with a two-head transformer can search a hidden tree. With DFT, the training learns to avoid some actions and backtracking. The results also generalizes from depth-1 and depth-2 trees.

Critical strengths
  1. The paper gives a nontrivial analysis connecting policy-gradient updates to a search mechanism.

  2. The explanation of why depth-1 training fails to generalize, and how depth-2 training corrects the parameter imbalance, is particularly interesting.

Critical weaknesses
  1. The environment does not repeated actions, which forces successful policies to follow DFS. With the predefined head roles, it's confusing on whether this significantly restrict the policy search space.
  2. The analysis requires careful constructions of the transformer. While this isn't unusual for related works in the literature, I wonder if this theoretical construction is validated to perform well empirically (maybe i'm missing this information from appendix E).
Questions for authors
  1. Since the no-repeat rule forces successful policies to follow DFS, which insights from the analysis are expected to extend to environments allowing revisits and other search strategies?
1 comment
AuthorsOpenReview ↗

Response to Reviewer s4k7

We thank the reviewer for the positive assessment and for recognizing the contribution of our policy-gradient analysis. We clarify the two concerns below.

Regarding whether the no-repeat rule forces DFS and restricts the policy space.

An important distinction is that the no-repeat rule does not enforce DFS at the policy level. In particular, illegal actions are not masked from the transformer's output distribution (Eqs. 9–10). The agent can still select previously tried actions or backtrack prematurely, resulting in failure. Thus, the policy must learn to suppress these actions and identify when backtracking is appropriate, solely through terminal reward.

Moreover, the predefined head roles do not hard-code the search algorithm: the attention and output matrices B,C,P,QB,C,P,Q are learned from zero initialization. Indeed, Theorem 2 shows that depth-1 training fails to generalize despite learning basic backtracking and action avoidance, while Theorem 3 establishes that depth-2 training learns the missing internal-node backtracking mechanism and generalizes to deeper trees. This distinction is central to our contribution.

Regarding extension to environments allowing revisits and alternative search strategies.

The key transferable insight is how RL trains attention to retrieve action histories and failure outcomes, and combines them into search decisions (Theorem 1, Fig. 2).

In our static-tree setting, revisiting an already explored branch provides no new information, so redundant revisits are unnecessary for efficient search. If revisits were permitted, avoiding such redundant exploration would remain beneficial. More generally, while richer environments may favor other search strategies, the learned primitives of history-dependent action selection and outcome-conditioned backtracking remain relevant.

Our imbalanced extension already demonstrates that the framework is not limited to uniform random DFS: Proposition 2 and Theorem 4 establish ranked DFS, which prioritizes more promising branches to minimize expected search length.

Regarding empirical validation of the theoretical construction.

We indeed provide empirical validation in Appendix E, using stochastic policy gradient with batch size 256 rather than the population gradients assumed in the analysis.

  • Figure 3 shows that training on depth-1 and depth-2 trees achieves high success rates on unseen trees of depths 3–4.
  • Figures 4–5 visualize the learned attention/output matrices, showing agreement with the predicted DFS mechanism.
  • Figures 6–7 further validate ranked DFS under imbalanced goal distributions, including experiments that update all four matrices throughout both training stages.

These experiments support both the predicted training dynamics and depth generalization, rather than merely verifying that the hand-constructed parameters can execute DFS.

We hope these clarifications address the concerns and further highlight that our main contribution is explaining how RL learns the search mechanism, rather than assuming it is already present.

Reviewer_HzihOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how transformers learn to search via RL (as opposed to supervised learning). They construct a simple k-ary tree environment, provide a construction for a simplified 2-head transformer that provably learns DFS, and show it depth-generalizes. They then train transformers of their simplified form and show they learn a search mechanism similar to the construction.

Critical strengths

The paper provides a clean construction of search in the (simple) k-ary tree setting implemented by a 2-head transformer, and also show it is learnable via gradient descent. Though the transformer architecture they use is stylized/simplified, it at least keeps the core attention mechanism intact.

Critical weaknesses

The construction and results are presented for a stylized/simplified transformer where head 1 is constrained to look at actions and head 2 is constrained to look at labels (so some task-specific knowledge has been "built in"). The authors briefly cite prior work "following standard simplification for theoretical analysis" but I would like to see some justification for why results with this simplification might extend to standard more complex transformers with full architecture and training machinery. Also is this construction learnable without the inductive bias of head 1 looking only at actions and head 2 at labels?

Questions for authors
  • Some of the notation is hard to follow and I feel there is insufficient guiding text to motivate the constructions, for example all the variable names B, C, P, Q, induced matrices. Can you provide intuitive explanations for these (and in the text to make it clearer)?
  • How general do you hypothesize the mechanism from the construction is? e.g. what would happen with more layers, more heads, etc. And what if you remove the constraint in eq 7 that head 1 only looks at actions and head 2 only at labels?
  • Did you try training a standard transformer on this task and does it find a similar mechanism to the proposed construction?
2 comments
AuthorsOpenReview ↗

Response to Reviewer Hzih

Thank you for the positive assessment of our theoretical soundness and the learnability of the search mechanism. We appreciate the questions and clarify the role of the architectural simplifications below.

1. Regarding the task-specific inductive bias and extension to standard transformers.

The architectural constraints do not hard-code DFS. They specify which information each head can access, but not how to use it. In particular, all four matrices B,C,P,QB,C,P,Q are learned from zero initialization using sparse terminal rewards (Sec. 4):

  • BB: learns to retrieve action history associated with the current node.
  • CC: learns to distinguish failure and internal-node outcomes.
  • P,QP,Q: learn how retrieved information determines action logits.

Crucially, Theorem 2 (Eq. 22) proves that depth-1 training alone does not yield general search, while Theorem 3 (Eq. 23) establishes that depth-2 training learns the missing backtracking behavior and achieves R≥1−ϵR\ge 1-\epsilon on deeper trees. Thus, the search algorithm is learned through RL, not built into the architecture.

These constraints isolate an interpretable attention mechanism and make its nonconvex policy-gradient learning dynamics analytically tractable (App. A.3).

2. Regarding additional layers/heads and removing head specialization.

The proposed mechanism is not inherently limited to two heads. A larger transformer has sufficient representational flexibility to implement the same computation: additional heads can retrieve other information, while additional layers can compose or refine the retrieved features.

Importantly, our mechanism relies on two functional primitives—retrieving previously tried actions and identifying failure/backtracking conditions—rather than on a specific number of heads. We hypothesize that unconstrained transformers can learn equivalent primitives, potentially distributed across multiple heads and layers.

The distinction is between representational capability and provable learnability: our analysis establishes the latter for a tractable parameterization, while extending the optimization guarantees to unrestricted attention remains a separate problem.

3. Regarding experiments with standard transformers.

Our experiments focus on the architecture in Eq. (10), allowing direct comparison with the theoretical predictions, rather than training a fully unrestricted transformer.

Nevertheless, the training experiments already relax some analytical constraints: Fig. 3 and App. E train both B,PB,P during depth-2 training, and Figs. 6–8 train all four matrices B,C,P,QB,C,P,Q throughout both stages. The predicted search behavior and depth generalization persist.

4. Regarding notation and presentation.

The induced matrices in Eq. (12) simply express the learned parameters in token coordinates: AB,ACA_B,A_C describe attention matching, while AP,AQA_P,A_Q describe how retrieved actions and outcomes affect logits. Fig. 2 illustrates their interaction, and Lemma 1 (Eqs. 88–91) provides explicit policy expressions. We will make these intuitive interpretations more prominent in the main text.

Overall, our main contribution is not merely a two-head DFS construction, but a provable account of how sparse-reward RL learns and composes the memory-retrieval and backtracking primitives needed for interactive search.

Thank you for your clarifications. I will maintain my positive score.

Reviewer_14JyOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The authors present a potential mechanism for a transformer learning to search in agentic settings. They provide an explicit construction of a simplified transformer with just an attention layer with two heads that implements randomized DFS over a rooted tree, and construct a two-stage curriculum (training on depth-1 trees then depth-2) with certain parameters frozen where the transformer learns that DFS algorithm that generalizes to arbitrary depth.

Critical strengths
  1. The authors provide a simple and intuitive construction that shows how a simplified 2-layer transformer variant could be trained to learn a general search algorithm over trees.
Critical weaknesses
  1. My main concern is that there’s no evidence that the presented mechanism is actually the mechanism by which search capabilities emerge in RL post-training of reasoning models — there’s a large gap between the simplified setting the authors study and actual training of reasoning models. To bridge this gap, the authors would need to formulate specific falsifiable predictions from their mechanism, and empirically test those hypotheses on actual RL reasoning post-training. Without empirical validation of the mechanism in more realistic scenarios, the paper’s central claim, especially how it’s described in the title of the paper, is an overclaim.
Questions for authors
  1. For tractability, the theoretical analyses are specific to the particular simplified architecture and training curriculum the authors present, and with simplifying assumptions, diverging from actual transformer architectures and their training. Here are a few questions on how much the theoretical analysis (or its derived insights) rely on details in those divergences:
  • The analysis assumes a particular encoding of the history, where a transition tuple (n, a, n’, c) is a single token. What about alternative encodings? Is there a general method for constructing the transformer for a wide range of encodings, and does training still recover the randomized DFS algorithm or some general search algorithm?
  • Many weights are frozen to 0 during training, and the two phases of training don’t freeze the same set of weights. There are also implicit freezings of attention output projection weights from the fact that the value matrices are E_a and E_c in Eq. (7). How much does the success of learning the randomized DFS algorithm depend on freezing those weights?
  • The training is split into two phases — the first training on depth-1 trees and the second training on depth-2 trees. How much does the success of learning depend on this two-phase split?

If some of the questions above are intractable theoretically, experimental evidence that the predicted mechanisms are present would be valuable.

  1. What is ap,2a_{p,2} at line 366? It appears undefined up until this point.

Suggestions:

  1. The causal attention mask is missing in Eq. (7), but this is ultimately harmless as the step-by-step generation process during inference (Eq. (10)) effectively applies a causal attention mask.
  2. The presentation of the construction could be improved to be easier to understand. For example, the authors could provide expressions for intermediate results like the attention map, the attention output before the P and Q transformations, and the final logits. A diagram showing how the attention mechanism implements the desired logic would help.

Potential fixable mistake (reported by AI — I haven’t checked this myself): Eq. (40) assumes nsn_s is deterministic, but it is still random when conditioned on ss as the unexplored subtrees are still random.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 14Jy

Thank you for the careful review. We hope the following clarifications address your concerns, particularly regarding the distinction between theoretical soundness and applicability to real-world reasoning models, and would appreciate your reconsideration of the rating in light of these points.

1. Regarding relevance to RL post-training and overclaiming.

Our claim is that RL can provably learn interactive search in a transformer, not that we have identified the circuit inside frontier LLMs. Theorem 1 constructs DFS; Theorems 2–3 establish its emergence under policy gradient from sparse terminal rewards, with R≥1−ϵR\ge1-\epsilon on unseen deeper trees (Eq. 23). Crucially, the tree is hidden and discovered through interaction, unlike prompt-revealed or fixed-graph abstractions (Sec. 2; App. A.2). Thus the central criticism concerns external validity, not a flaw in these results. Testable predictions follow: disrupting action-history retrieval should increase repeated actions; disrupting failure-label retrieval should impair backtracking. The title is qualified by the paper's stated assumptions.

2. Regarding history encoding.

Eq. (5) groups a transition into one feature column; this is not a requirement for an atomic tokenizer token. Theorem 1 requires only full-column-rank embeddings. Its expressivity construction survives invertible linear re-encodings x′=Rxx'=Rx with W′KQ=R−⊤WKQR−1W'^{KQ}=R^{-\top}W^{KQ}R^{-1} and corresponding output reparameterization. Our optimization proof additionally assumes orthonormal embeddings (Assumption 1); parsing arbitrary multi-token histories is a separate representation-learning question.

3. Regarding frozen weights and projections.

P,QP,Q are trainable output maps (Eqs. 6–10); fixed value channels Ea,EcE_a,E_c do not pre-encode DFS. Additional projections can be absorbed into effective output maps at the representation level, although training dynamics may differ. Crucially, experiments already relax freezing: balanced depth-2 training updates B,PB,P (Fig. 3; App. E), while imbalanced training updates all four B,C,P,QB,C,P,Q in both stages (Fig. 6; App. E). Freezing in the theorem isolates coupled gradient terms; it is not required for the observed behavior (App. A.3).

4. Regarding the two-stage curriculum.

The split exposes a meaningful compositional learning barrier. Depth-1 training learns failure backtracking and repeat avoidance but does not generalize: R=O(k−(l−1))R=O(k^{-(l-1)}) for l≥2l\ge2 (Theorem 2, Eq. 22). Depth-2 training learns backtracking from exhausted internal nodes, yielding R≥1−ϵR\ge1-\epsilon on deeper trees (Theorem 3, Eq. 23; Fig. 3). This demonstrates that DFS is learned, not hard-coded. The curriculum is a sufficient schedule; we do not claim necessity.

5. Regarding the AI-reported Eq. (40) issue.

Determinism of nsn_s is unnecessary. Write the exploration length as random NsN_s. The second term of Gπ′γ(s)G_{\pi'}^\gamma(s) is (1−ps)E[γNsX∣Esc,s](1-p_s)\mathbb E[\gamma^{N_s}X\mid E_s^c,s], where X≥0X\ge0 is the continuation return. Eq. (45) already bounds Ns≤Ms:=r(2+hd−1)N_s\le M_s:=r(2+h_{d-1}) pointwise. Since 0<γ<10<\gamma<1, γNs≥γMs\gamma^{N_s}\ge\gamma^{M_s}, giving

Gπ′γ(s)−Gπγ(s)≥psRγ(s)−(1−ps)(1−γMs)Rγ′(s).G_{\pi'}^\gamma(s)-G_\pi^\gamma(s)\ge p_sR_\gamma(s)-(1-p_s)(1-\gamma^{M_s})R'_\gamma(s).

This is the bound used in the subsequent proof, so Proposition 2's conclusion is unchanged. The conditional-expectation notation can be made explicit.

6. Regarding notation and presentation.

ap,2a_{p,2} is the common off-diagonal entry of AP=PVA_P=PV (App. C.2, Eq. 79). Causality is enforced by the autoregressive prefix E(h)E^{(h)} (Eqs. 5, 10). Fig. 2 already diagrams both heads, and attention/logit expressions appear in App. C.3.1, Eqs. 202–204, and Lemma 1, Eqs. 88–91; we can foreground these references.

In sum, the paper contributes an optimization-level account of acquiring interactive DFS from sparse RL feedback, beyond an expressivity construction. The realism questions identify future extensions, not refutations of the proved mechanism.

I thank the authors for their response and apologize for the delay in my response.

  1. The overclaiming half of my concern is resolved assuming the authors make sure to qualify wordings (e.g. in the title) with the assumptions. The other half of my concern -- that the gap between theory and practice is too large for the insights gained from the theory to be useful -- remains unaddressed. The authors provide testable predictions in their rebuttal, but for the gap to be bridged they would need to "empirically test those hypotheses on actual RL reasoning post-training" as I've stated in my review.

  2. Regarding history encodings, I was referring more to the fact that the paper groups the 4 elements of the transition tuple into a single feature vector (apologies for my inaccurate use of the word "token"). More realistic encodings would have the different elements spread across multiple token positions, so when my question asked about alternative "encodings" I was referring more to splitting the transition tuple into multiple embedding vectors in the sequence (alternative tokenizations, if you will).

My remaining concerns have been addressed and questions answered in a satisfactory manner.

I appreciate the theoretical contribution, with my remaining reservation being what I perceive to be a large gap between theory and practice that makes it unclear to me how well the theoretical insights generalize to realistic scenarios. I have increased my overall score to 2 (weak reject).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.