Pith. sign in

REVIEW 1 major objections 3 minor 51 references

Fixed-precision Transformers are exactly as powerful as their transcript manager allows: append-only and monotone multi-agent transcripts realize only finite-state transductions, one pop-enabled channel raises acceptance to the deterministi

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 05:49 UTC pith:Z772YTOW

load-bearing objection The monotone collapse theorem is new and correct; the DCFL/RE hierarchy is classical and the paper says so; the only real flaw is a discussion-level overreach about tool loops. the 1 major comments →

arxiv 2607.29496 v1 pith:Z772YTOW submitted 2026-07-31 cs.LG cs.FLcs.MA

Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts

Sergey Salishev This is my paper
classification cs.LG cs.FLcs.MA MSC 68Q4568Q05
keywords transcript managementTransformer expressivityPopContextfinite-state collapsedeterministic context-free languagesTuring completenessmulti-agent orchestrationpushdown automata
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper asks what one specific operation, added to the way a Transformer deployment manages its stored context (its transcript), changes about the computations the model can perform. The answer it defends: if the transcript manager can only append, route, and copy the blocks currently visible, then no matter how many agents are involved or how long the transcript grows, the whole system realizes exactly the finite-state transductions — no more than a deterministic finite automaton with output. If the manager is allowed one new primitive, PopContext, which deletes the newest block on a channel and exposes the block beneath it, a single pop-enabled channel immediately raises acceptance power to the deterministic context-free languages; two pop-enabled channels — whether in one agent or in two orchestrated agents — make the system Turing-complete. The paper's own novel theorems are the finite-state collapse and the equivalence between k orchestrated agents and one controller with k channels; the DCFL and RE levels are transferred from the classical one-stack and two-stack results through a compilation lemma.

Core claim

Central claim: under fixed finite precision, bounded block sizes and visible windows, and a fixed finite agent population, the transcript-management layer around a Transformer is the whole story of its asymptotic expressivity. A pop-free transcript (RTMT_k) realizes exactly Trans(FST), the deterministic finite-state transductions, for every fixed number of channels k (Theorem 1); the same holds for any fixed finite population under a monotone protocol of append, route, and visible-copy (Theorem 2, the 'monotone multi-agent collapse'). Adding the PopContext operation to even one channel turns that channel into a stack, and via Lemma 1 the classical hierarchy transfers: one pop-enabled channel

What carries the argument

The central object is the Transcript-Managed Transducer TMT_k (Definition 1): one finite controller with k transcript channels, each holding bounded blocks, with per-round actions stay, push, and pop, and a caller-driven status map deciding which rounds consume input. The 'pop' action is named PopContext (P_c), and it is exactly the operation the append-only layer omits. Two pieces of machinery carry the argument. Proposition 1 recodes any fixed visible radius into a single finite 'window symbol', so a bounded physical transcript becomes an abstract stack over a finite alphabet. Lemma 1 compiles this normal form into the classical top-replacement presentation of pushdown and multi-pushdown a

Load-bearing premise

The load-bearing premise is that every single transition consults only a fixed finite amount of exact state — finite precision, bounded visible window, no exact access to buried blocks, and a fixed finite population — and if any deployment lets the consulted state grow with context, the finite-state collapse and the DCFL/RE classification both fail.

What would settle it

Implement the paper's monotone protocol (Definition 7) with exactly two agents and bounded blocks, and search for a transduction that accepts a^n b^n for all n; the theorem predicts no such program exists, so any working construction would falsify the central collapse claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any append-only or monotone multi-agent deployment with fixed precision and bounded visibility has exactly the transduction power of a finite-state machine, regardless of how long the retained transcript grows; it cannot parse general programming languages no matter how many finite-state agents are added.
  • Admitting PopContext on a single transcript channel is a minimal, token-protocol-preserving change that lifts acceptance from regular to deterministic context-free — enough for deterministic parsing of structured instruction languages.
  • Two pop-enabled channels (in one agent or two orchestrated agents) suffice for Turing completeness, so a deployed two-agent or two-channel system can, in principle, simulate any effective procedure.
  • The simulation overhead is small: one TMT_k round costs at most k orchestration steps, a classical pushdown transition expands to O(1) rounds, and one Turing-machine step costs O(1) two-agent steps, so the stack power is reached without changing model weights or the token protocol.
  • Fixed block size and visible radius are irrelevant to the classification (Proposition 1): any fixed radius packs into a finite alphabet symbol, so the hierarchy is stable under resizing those bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The collapse result gives a concrete design principle the authors only hint at: if an application needs context-free behavior, the cheapest route is to add a pop capability in the transcript manager (or let the orchestrator pop an agent's transcript), rather than increasing context length or changing the architecture.
  • The paper's fixed, caller-driven status map is a strong premise; an editorial extension to test is whether a learned or adaptive status map — e.g., a controller that learns when to issue pop — could push a fixed-precision, pop-enabled system beyond DCFL toward RE with only one channel, since the classical one-stack bound assumes a fixed controller.
  • Corollary 1 (append-only CoT cycles) suggests a practical test: monitor long-running tool-use agents and instrument the exact transcript window; the theorem predicts eventual periodic repetition of states and actions once the input is consumed — a signature that could be detected in deployment logs.
  • The paper's boundary between finite consulted state and growing exact context implies that emerging long-context models with uncapped KV caches live in a different resource regime; for them the finite-state collapse does not apply, so extrapolating these bounds to such deployments would be a misuse of the theorem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper proposes a transducer normal form TMT_k for the transcript-management layer of fixed finite-precision causal Transformers: one finite controller with k channels, each channel a stack over a finite block alphabet, with per-round stay/push/pop and a fixed status map. The pop-free restriction RTMT_k is the append-only layer; MON_m is the class of monotone multi-agent protocols; OTM_k is the class of k one-channel agents under one orchestration controller. Main results: Trans(RTMT_k)=Trans(FST) for every fixed k; Trans(MON_m)=Trans(FST) for every fixed m; Trans(OTM_k)=Trans(TMT_k); and, via a compilation to the Hopcroft–Ullman presentation, Acc(TMT_1)=DCFL and Acc(TMT_k)=RE for k≥2. Proposition 1 gives a bounded-transcript realization of the management layer; Proposition 2 gives simulation costs. The paper is explicit that the DCFL/RE levels are classical results imported through Lemma 1, and its own theorems are the collapse, the correspondence, and the compilation.

Significance. If correct, the paper provides a clean and useful classification: without pop, any fixed finite population of agents using append/copy/route operations is no more powerful than a finite-state transducer, however long the retained transcript grows; one pop-enabled channel reaches DCFL; two reach RE. The proof strategy is direct and transparent: Theorem 1's summary-space argument, Theorem 2's global-summary collapse, and Theorem 3's simulations are all elementary and checked. The paper is unusually careful about scope: it states the finite-consulted-state condition (Definition 3), fixes precision and population, and identifies the escape routes (growing exact context, hidden-block access, writable stores, unbounded Spawn). It also explicitly credits the classical results, so there is no circularity. The main theoretical claims are sound and the paper is a useful contribution to the formal-language analysis of transcript-managed Transformers.

major comments (1)
  1. [Section V.b, abstract, Section V.i] The claim that Corollary 1 predicts eventual repetition of tool-and-thought loops in deployed agents is an over-application. Corollary 1 applies to an autonomous deterministic finite-state transition after a finite input has been consumed. In a tool loop, each tool output is a new external input symbol; a finite-state transducer driven by an unbounded input stream need not be ultimately periodic. The corollary therefore does not license the prediction of cyclic tool loops. Please revise the relevant sentences to restrict the claim to pure chain-of-thought with no further external inputs, or state explicitly that tool outputs are outside the corollary's hypothesis.
minor comments (3)
  1. [Definition 9 / Theorem 3] The phrase 'whose finite input interface selects stay or push of a specified b∈Λ' is confusing because the orchestration-level push(i,b) is performed directly by the controller, not through the agent's transition interface. Clarify that the one-state agents are placeholders and the actual stack update is done by the orchestration action.
  2. [Lemma 1 proof] The constant '2' in the bound 2+k(L+1) is not explained. A one-line clarification (dispatcher selection and final output emission) would help.
  3. [Table I] The row for Oren et al. records the idealized uncapped KV cache as RE while the text notes a real bounded cache is finite-state. This is a reasonable reading of the table's 'Representative power' column, but the table could be more explicit that this is an idealized resource reading, not a claim about the cited work's experiments.

Circularity Check

0 steps flagged

No significant circularity: Theorems 1–3 are proved directly in the paper's normal form; the DCFL/RE acceptance levels are explicitly imported from classical one- and two-stack results, not derived from the paper's own fitted assumptions.

full rationale

The derivation chain is self-contained. Theorem 1 constructs a finite summary space from the finite controller, finite stack alphabet, and the fact that pop is absent, so no buried symbol can return; this is a direct proof, not an input fitted to the conclusion. Theorem 2 uses the same finite-summary argument for monotone orchestrations, with Proposition 1 explicitly encoding bounded-transcript controllers into RTMT_k. Theorem 3 is a step-for-step simulation between OTM_k and TMT_k, not a definitional identification. Lemma 1 is a normal-form compilation with stated step bounds, and the paper explicitly says the acceptance classifications are classical: 'The two acceptance identities are the classical one- and two-stack classifications, transferred to this normal form by Lemma 1 and recorded in Corollary 3 and Theorem 4.' This is legitimate import of known results, not circularity. There are no fitted parameters and no self-citations in the reference list. The paper is also explicit about its scope: Section I.c and Section V.a state that unbounded exact context, writable stores, and unbounded Spawn break the finite-consulted-state assumption, and Section II.c disclaims any uniqueness claim for PopContext. The only soft spot is a discussion-level over-application of Corollary 1 to tool loops in Section V.b, where tool outputs inject new input symbols each round; that is a scoping concern, not a circular step in the theorem chain.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 1 invented entities

No fitted parameters anywhere: the paper is a pure classification argument, and its model constants (block bound B, visible radius r, channel count k, precision F, context length N) are fixed scope parameters the theorems are invariant over (Proposition 1), not values fitted to data. The axioms are mostly standard automata theory plus the explicitly scoped domain assumptions; the only introduced primitive is PopContext, whose power is carried by the classical stack hierarchy it is defined to match.

axioms (5)
  • standard math Classical automata hierarchy: one deterministic stack accepts exactly DCFL; two stacks simulate a Turing machine and accept exactly RE (Minsky 1967; Hopcroft-Motwani-Ullman 2007).
    Imported at Corollary 3 / Theorem 4 after Lemma 1 compiles the TMT normal form into the Hopcroft-Ullman multi-pushdown presentation; not re-proved in the paper.
  • domain assumption Finite consulted state (Definition 3): the exact joint configuration consulted in one transition ranges over a finite set.
    Load-bearing scope condition: the collapse to FST (Theorems 1-2) and the bounded-Transformer instantiation (Remark 2, finite precision F and context N) require it. The paper itself lists the failure modes: exact real/unbounded-precision arithmetic, growing exact KV cache, writable stores, unbounded Spawn (Section I.c, V.a).
  • domain assumption The execution schedule / status map chi is fixed and nontrainable; input is presented once with right-end marker, and runs halt exactly on chi=halt after consuming the marker.
    Definition 1 and scope item 4. The completed-run convention is what aligns the normal form with the classical DPDA acceptance convention used by Lemma 1; an adaptive or learned schedule is outside the model.
  • domain assumption Monotone protocol visibility restriction: a copy source must be a currently exposed block; no step may delete or reveal buried blocks.
    Definition 7; this is exactly the condition that makes Theorem 2's finite-summary invariant hold, and the paper notes it is essential (unbounded Spawn breaks it).
  • standard math Classical separation facts: {a^n b^n} is not regular, DCFL is strictly contained in CFL, and regular languages are contained in DCFL.
    Used in Theorem 1's closing remark and in Table I to position the hierarchy levels; standard textbook facts.
invented entities (1)
  • PopContext (P_c): a transcript operation deleting the newest block on channel c and exposing its predecessor. no independent evidence
    purpose: Restores a stack to the append-only transcript layer, yielding DCFL (one channel) and RE (two channels); proposed as the minimal primitive to add to deployed transcript managers.
    Definition 5. The claimed power is carried by the classical one-/two-stack hierarchy via Lemma 1, not by any prediction or measurement in this paper; it is a fully specified abstract operation, not an empirically anchored entity with an external falsifiable handle.

pith-pipeline@v1.3.0-daily-deepseek · 19514 in / 32699 out tokens · 346943 ms · 2026-08-03T05:49:49.196339+00:00 · methodology

0 comments
read the original abstract

We study transcript management for fixed, finite-precision causal Transformers. A transcript is partitioned into channels of bounded blocks. Each transition consults a fixed visible suffix and may append one block, leaving the model, weights, and token protocol unchanged. The operation $P_c:=\PopContext(c)$ deletes the newest block on channel $c$ and exposes its predecessor. We model the layer by the Transcript-Managed Transducer $\TMTn{k}$: one finite controller, $k$ channels, and per-round actions from stay, push, and pop under a caller-driven status map. Fixed visible windows encode as finite symbols. The pop-free Restricted Transcript-Managed Transducer $\RTMTn{k}$ is the standard append-only layer and, for every fixed $k$, realizes exactly the deterministic finite-state transductions. The same holds for every fixed finite agent population under a monotone protocol that appends, routes, and copies visible blocks. Admitting $\{P_c\}_{c=1}^k$ restores pop. Newest-first, a pop-enabled channel is a stack; compiling to the Hopcroft--Ullman presentation transfers the classical hierarchy: $\DCFL$ for $k=1$ and $\RE$ for every $k\ge2$. Orchestrated one-channel agents match one controller with $k$ channels, so two pop-enabled transcripts---in one agent or two---suffice for universality. Simulation costs and invariance to fixed block size and visible radius are stated. The bounds fix precision, alphabets, blocks, visibility, controller state, and population; growing exact context, hidden-block access, writable stores, and unbounded \textbf{Spawn} add further state.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 2 linked inside Pith

  1. [1]

    Attention is all you need,

    A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” inAdvances in Neural Information Processing Systems 30, 2017

    2017

  2. [2]

    Language models are unsupervised multitask learners,

    A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever, “Language models are unsupervised multitask learners,” OpenAI technical report, 2019. [Online]. Avail- able: https://cdn.openai.com/better-language-models/language models are unsupervised multitask learners.pdf

    2019

  3. [3]

    Language models are few-shot learners,

    T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- V oss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Am...

    2020

  4. [4]

    ReAct: Synergizing reasoning and acting in language models,

    S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y . Cao, “ReAct: Synergizing reasoning and acting in language models,” in International Conference on Learning Representations, 2023

    2023

  5. [5]

    AutoGen: Enabling next-gen LLM applications via multi- agent conversation,

    Q. Wu, G. Bansal, J. Zhang, Y . Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, A. H. Awadallah, R. W. White, D. Burger, and C. Wang, “AutoGen: Enabling next-gen LLM applications via multi- agent conversation,” inFirst Conference on Language Modeling, 2024

    2024

  6. [6]

    When agents do not stop: Uncovering infinite agentic loops in LLM agents,

    X. Hou, S. Wang, Y . Zhao, and H. Wang, “When agents do not stop: Uncovering infinite agentic loops in LLM agents,” 2026

    2026

  7. [7]

    Syntax-guided synthesis,

    R. Alur, R. Bodik, G. Juniwal, M. M. K. Martin, M. Raghothaman, S. A. Seshia, R. Singh, A. Solar-Lezama, E. Torlak, and A. Udupa, “Syntax-guided synthesis,” inProceedings of the 2013 Formal Methods in Computer-Aided Design, 2013, pp. 1–17

    2013

  8. [8]

    Towards neural- network-guided program synthesis and verification,

    N. Kobayashi, T. Sekiyama, I. Sato, and H. Unno, “Towards neural- network-guided program synthesis and verification,”Formal Methods in System Design, 2025

    2025

  9. [9]

    Neu- ral networks and the Chomsky hierarchy,

    G. Del ´etang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, J. Veness, and P. A. Ortega, “Neu- ral networks and the Chomsky hierarchy,” inInternational Conference on Learning Representations, 2023

    2023

  10. [10]

    On the translation of languages from left to right,

    D. E. Knuth, “On the translation of languages from left to right,” Information and Control, vol. 8, no. 6, pp. 607–639, 1965

    1965

  11. [11]

    A survey and classification of controlled natural languages,

    T. Kuhn, “A survey and classification of controlled natural languages,” Computational Linguistics, vol. 40, no. 1, pp. 121–170, 2014

    2014

  12. [12]

    On systematically building a controlled natural language for functional requirements,

    A. Veizaga, M. Alf ´erez, D. Torre, M. Sabetzadeh, and L. Briand, “On systematically building a controlled natural language for functional requirements,”Empirical Software Engineering, vol. 26, no. 5, p. 90, 2021

    2021

  13. [13]

    Retrieval-augmented generation for knowledge-intensive NLP tasks,

    P. Lewis, E. Perez, A. Piktus, F. Petroni, V . Karpukhin, N. Goyal, H. K ¨uttler, M. Lewis, W. tau Yih, T. Rockt ¨aschel, S. Riedel, and D. Kiela, “Retrieval-augmented generation for knowledge-intensive NLP tasks,” inAdvances in Neural Information Processing Systems 33, 2020

    2020

  14. [14]

    Transformers are multi-state RNNs,

    M. Oren, M. Hassid, N. Yarden, Y . Adi, and R. Schwartz, “Transformers are multi-state RNNs,” inProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, 2024, pp. 18 724– 18 741

    2024

  15. [15]

    Theoretical limitations of self-attention in neural sequence models,

    M. Hahn, “Theoretical limitations of self-attention in neural sequence models,”Transactions of the Association for Computational Linguistics, vol. 8, pp. 156–171, 2020

    2020

  16. [16]

    Saturated transformers are constant-depth threshold circuits,

    W. Merrill, A. Sabharwal, and N. A. Smith, “Saturated transformers are constant-depth threshold circuits,”Transactions of the Association for Computational Linguistics, vol. 10, pp. 843–856, 2022

    2022

  17. [17]

    The parallelism tradeoff: Limitations of log-precision transformers,

    W. Merrill and A. Sabharwal, “The parallelism tradeoff: Limitations of log-precision transformers,”Transactions of the Association for Computational Linguistics, vol. 11, pp. 531–545, 2023

    2023

  18. [18]

    Hierarchies of memory limited computations,

    R. E. Stearns, J. Hartmanis, and P. M. Lewis, II, “Hierarchies of memory limited computations,” in6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 179–190

    1965

  19. [19]

    Formal language recognition by hard attention transformers: Perspectives from circuit complexity,

    Y . Hao, D. Angluin, and R. Frank, “Formal language recognition by hard attention transformers: Perspectives from circuit complexity,” Transactions of the Association for Computational Linguistics, vol. 10, pp. 800–810, 2022

    2022

  20. [20]

    What formal languages can transformers express? A survey,

    L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin, “What formal languages can transformers express? A survey,”Transactions of the Association for Computational Linguistics, vol. 12, pp. 543–561, 2024

    2024

  21. [21]

    On the ability and limitations of transformers to recognize formal languages,

    S. Bhattamishra, K. Ahuja, and N. Goyal, “On the ability and limitations of transformers to recognize formal languages,” inProceedings of the 2020 Conference on Empirical Methods in Natural Language Process- ing, 2020, pp. 7096–7116

    2020

  22. [22]

    Simplicity bias in transformers and their ability to learn sparse Boolean functions,

    S. Bhattamishra, A. Patel, V . Kanade, and P. Blunsom, “Simplicity bias in transformers and their ability to learn sparse Boolean functions,” inProceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2023, pp. 5767– 5791

    2023

  23. [23]

    M. L. Minsky,Computation: Finite and Infinite Machines. Prentice- Hall, 1967

    1967

  24. [24]

    J. E. Hopcroft, R. Motwani, and J. D. Ullman,Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson, 2007

    2007

  25. [25]

    Visibly pushdown languages,

    R. Alur and P. Madhusudan, “Visibly pushdown languages,” inPro- ceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004, pp. 202–211

    2004

  26. [26]

    Model-checking of ordered multi-pushdown automata,

    M. F. Atig, “Model-checking of ordered multi-pushdown automata,” Logical Methods in Computer Science, vol. 8, no. 3, pp. 1–31, 2012

    2012

  27. [27]

    Extracting automata from recur- rent neural networks using queries and counterexamples,

    G. Weiss, Y . Goldberg, and E. Yahav, “Extracting automata from recur- rent neural networks using queries and counterexamples,” inProceedings of the 35th International Conference on Machine Learning, 2018

    2018

  28. [28]

    Attention is Turing-complete,

    J. P ´erez, P. Barcel ´o, and J. Marinkovic, “Attention is Turing-complete,” Journal of Machine Learning Research, vol. 22, no. 75, pp. 1–35, 2021

    2021

  29. [29]

    Learning to transduce with unbounded memory,

    E. Grefenstette, K. M. Hermann, M. Suleyman, and P. Blunsom, “Learning to transduce with unbounded memory,” inAdvances in Neural Information Processing Systems 28, 2015

    2015

  30. [30]

    Inferring algorithmic patterns with stack- augmented recurrent nets,

    A. Joulin and T. Mikolov, “Inferring algorithmic patterns with stack- augmented recurrent nets,” inAdvances in Neural Information Process- ing Systems 28, 2015

    2015

  31. [31]

    Learning context-free languages with non- deterministic stack RNNs,

    B. DuSell and D. Chiang, “Learning context-free languages with non- deterministic stack RNNs,” inProceedings of the 24th Conference on Computational Natural Language Learning, 2020, pp. 507–519

    2020

  32. [32]

    Turing completeness of bounded- precision recurrent neural networks,

    S. Chung and H. T. Siegelmann, “Turing completeness of bounded- precision recurrent neural networks,” inAdvances in Neural Information Processing Systems 34, 2021, pp. 28 431–28 441

    2021

  33. [33]

    Stack attention: Improving the ability of transformers to model hierarchical patterns,

    B. DuSell and D. Chiang, “Stack attention: Improving the ability of transformers to model hierarchical patterns,” inInternational Conference on Learning Representations, 2024

    2024

  34. [34]

    Pushdown layers: Encoding recursive structure in transformer language models,

    S. Murty, P. Sharma, J. Andreas, and C. D. Manning, “Pushdown layers: Encoding recursive structure in transformer language models,” in Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023, pp. 3233–3247

    2023

  35. [35]

    Recursive transformer: Boosting reasoning ability with state stack,

    K. Zhang, G. Li, J. Li, H. Zhang, Y . Dong, J. Li, J. Xu, and Z. Jin, “Recursive transformer: Boosting reasoning ability with state stack,” in Advances in Neural Information Processing Systems 38, 2025

    2025

  36. [36]

    Transformer-XL: Attentive language models beyond a fixed-length context,

    Z. Dai, Z. Yang, Y . Yang, J. Carbonell, Q. V . Le, and R. Salakhutdinov, “Transformer-XL: Attentive language models beyond a fixed-length context,” inProceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019, pp. 2978–2988

    2019

  37. [37]

    Compressive transformers for long-range sequence modelling,

    J. W. Rae, A. Potapenko, S. M. Jayakumar, C. Hillier, and T. P. Lill- icrap, “Compressive transformers for long-range sequence modelling,” inInternational Conference on Learning Representations, 2020

    2020

  38. [38]

    Pretraining context compressor for large language models with embedding-based memory,

    Y . Dai, J. Lian, Y . Huang, W. Zhang, M. Zhou, M. Wu, X. Xie, and H. Liao, “Pretraining context compressor for large language models with embedding-based memory,” inProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2025, pp. 28 715–28 732

    2025

  39. [39]

    On the computational power of transformers and its implications in sequence modeling,

    S. Bhattamishra, A. Patel, and N. Goyal, “On the computational power of transformers and its implications in sequence modeling,” inProceedings of the 24th Conference on Computational Natural Language Learning (CoNLL), 2020, pp. 455–475

    2020

  40. [40]

    Universal transformers,

    M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and Ł. Kaiser, “Universal transformers,” 2018, arXiv:1807.03819. [Online]. Available: https://arxiv.org/abs/1807.03819

    Pith/arXiv arXiv 2018

  41. [41]

    The expressive power of transformers with chain of thought,

    W. Merrill and A. Sabharwal, “The expressive power of transformers with chain of thought,” inInternational Conference on Learning Rep- resentations, 2024

    2024

  42. [42]

    Efficient Turing machine simulation with Trans- formers,

    Q. Li and Y . Wang, “Efficient Turing machine simulation with Trans- formers,” inInternational Conference on Learning Representations, 2026

    2026

  43. [43]

    Do transformers need deep long-range memory?

    J. W. Rae and A. Razavi, “Do transformers need deep long-range memory?” inProceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020, pp. 7524–7529

    2020

  44. [44]

    Train short, test long: Attention with linear biases enables input length extrapolation,

    O. Press, N. A. Smith, and M. Lewis, “Train short, test long: Attention with linear biases enables input length extrapolation,” inInternational Conference on Learning Representations, 2022

    2022

  45. [45]

    The impact of positional encoding on length generalization in transformers,

    A. Kazemnejad, I. Padhi, K. N. Ramamurthy, P. Das, and S. Reddy, “The impact of positional encoding on length generalization in transformers,” inAdvances in Neural Information Processing Systems, vol. 36, 2023

    2023

  46. [46]

    RoFormer: En- hanced transformer with rotary position embedding,

    J. Su, M. Ahmed, Y . Lu, S. Pan, W. Bo, and Y . Liu, “RoFormer: En- hanced transformer with rotary position embedding,”Neurocomputing, vol. 568, p. 127063, 2024

    2024

  47. [47]

    Base of RoPE bounds context length,

    M. Xu, X. Men, B. Wang, Q. Zhang, H. Lin, Y . Lu, X. Han, and W. Chen, “Base of RoPE bounds context length,” inAdvances in Neural Information Processing Systems, vol. 37, 2024

    2024

  48. [48]

    Rotary positional embeddings as phase modulation: Theoretical bounds on the RoPE base for long-context transformers,

    F. Liu, “Rotary positional embeddings as phase modulation: Theoretical bounds on the RoPE base for long-context transformers,” 2026. [Online]. Available: https://arxiv.org/abs/2602.10959

    arXiv 2026

  49. [49]

    Towards re- vealing the mystery behind chain of thought: A theoretical perspective,

    G. Feng, B. Zhang, Y . Gu, H. Ye, D. He, and L. Wang, “Towards re- vealing the mystery behind chain of thought: A theoretical perspective,” inAdvances in Neural Information Processing Systems, vol. 36, 2023

    2023

  50. [50]

    Benefits and limitations of communication in multi-agent reasoning,

    M. Rizvi-Martel, S. Bhattamishra, N. Rathi, G. Rabusseau, and M. Hahn, “Benefits and limitations of communication in multi-agent reasoning,” 2025. [Online]. Available: https://arxiv.org/abs/2510.13903

    Pith/arXiv arXiv 2025

  51. [51]

    Modeling tool use in transformers via computation oracles,

    U. Tiwari, S. S. Nalli, and A. Deshpande, “Modeling tool use in transformers via computation oracles,” inLatent and Implicit Thinking Workshop at ICLR, 2026

    2026