acceptodds
Withdrawn from ICLR 2027

Work on Stacks: Transformers Can Do Pushdown Updates but Struggle to Learn Them

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Transformers are remarkably capable sequence models, but reliably maintaining and updating state over long contexts remains challenging. In this paper, we show that while Transformers can represent exact pushdown state-update computations, learning and executing these computations reliably can be substantially more difficult. We study bounded pushdown updates with complete action–state histories retained in context, without any external symbolic memory or retrieval, and construct a Transformer that implements the update exactly. Empirically, we find that learning succeeds reliably when the required routing computation is provided, but becomes much less reliable when the model must acquire that computation itself. A separate end-to-end study finds increasing training requirements with stack depth and alphabet size, extending the acquisition difficulty beyond unary stacks. Finally, we evaluate pretrained language models and find that pushdown state updates become unreliable in long contexts even when the relevant state can still be recovered. Overall, these experiments show a fundamental gap between representing state and reliably using it for sequential computation.

Primary area:
learning theory
Keywords:
Deterministic Pushdown Memory, Transformer, Explanability

Reviews

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

This paper studies how Transformers do stack updates when giving a sequence of push/pop operations. This paper starts from providing a positive result that Transformers are expressive enough to perform this task. Next, on small Transformers, this paper shows several results on small Transformers: (1) only train on specific parts while keeping other parts same as construction; (2) intervene a real model by filtering out the dimensions that did not used by oracle construction; (3) train from scratch. Experiments on Qwen3 shows how increasing context length will affect the performance on this task.

Critical strengths

None.

Critical weaknesses
  1. As a submission selecting learning theory as its primary area, this paper is insufficient in theoretical analysis. The results regarding difficulty of acquisition, reliable updates, etc. are all empirical without any formal theorems and proofs. The only theoretical results demonstrated in the submission is about expressivity. However, this proposition also requires more formal descriptions and proofs; and the full expressiveness result is insufficient as well.

  2. The problem setting requires further justification. In the setup, the current stack is provided after each operation, which substantially reduces the state maintenance requirement.

  3. Sections and experimental results are weakly connected. Although all experiments shares the same task on working on stacks, the experimental setup are significantly different from subsections to subsections. This make it difficult to determine whether the findings are general or not.

Questions for authors

Please refer to the weaknesses part.

  1. Could the authors provide further details regarding the expressiveness result? Specifically, could the authors provide detailed constructions (in appendix) and state the theorems more clearly (for instance, the requirement of model depth and width w.r.t. input size)? The current construction in Appendix A.2 (read specific positions, use specific attention scores) is insufficient for formal theoretical results.

  2. Could the authors explain why they give current stack status in the context after each operation?

Reviewer_5hXBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper constructs an exact stack-update Transformer with explicit action-state histories, then studies learning through component resets and end-to-end training. Matched-history evaluations of two Qwen models show that obsolete history can change updates, while separate extraction prompts often still recover the relevant state. The results distinguish representability, acquisition, and reliable state use.

Overall, it is primarily an empirical case study of Transformers’ ability to perform the elementary stack-pushdown and stack-pop operations. The contribution is mainly empirical, supported by a constructive representability result whose theoretical contribution is limited.

Critical strengths

I find the second finding, specifically "when tested on existing pretrained Qwen models without task-specific fine-tuning, histories with the same current state and action can nevertheless produce different update", most informative. I wonder whether this phenomenon still occurs when other real-world LLMs, like GPT or DeepSeek, are tested.

Critical weaknesses

I do not find other findings quite surprising. For example, the paper shows that Transformers have enough expressiveness through an explicit construction, and also shows that learning is substantially easier when the required attention computation is supplied. However, the general message that “representability does not imply easy acquisition” is unsurprising and, by itself, offers limited novelty. The separate finding that training costs increase with stack depth and alphabet size is also expected and thus, in my opinion, provides limited explanatory insight.

Questions for authors

See "Critical Strengths". Specifically, I wonder whether the second finding is general across different real-world LLMs.

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

This paper studies theoretically and experimentally whether transformers can recognize languages that involve stack operations. First they construct a transformer that solves the problem exactly; then, they try to learn various parts of this transformer automatically. Finally, they test pretrained language models. The main finding is that representing the stack might be easier than extracting relevant information from it.

Critical strengths

Studying stack-like behavior is an interesting problem. The promised separation between being able to store a representation of a stack versus being able to extract information from it is a valuable observation.

Critical weaknesses

The paper is very difficult to follow and exhibits many writing problems typical of language models. In particular, it does not precisely state the actual problem that the transformer is trying to solve, except in the (small and faint) example in Figure 1. The analytic solution in 2.2 is terse and unclear. This makes the experimental sections nearly impossible to follow.

Questions for authors

I have many clarification questions, but think that a resubmission will be required in order to answer all of them.

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

Related papers

Discussion (0)

Sign in to comment.