acceptodds
Under review as a conference paper at ICLR 2027

The Context of Theseus: Learning Selective Discrete Recurrence in Autoregressive Transformers

Abstract

Evolving programs, proofs, and plans often requires iteratively expanding and revising intermediate structures. Standard autoregressive decoding, however, restricts sequence evolution to monotonic prefix extension, binding logical sequence order to causal generation order and indefinitely accumulating superseded drafts in context. To address this problem, we introduce Theseus-AR, which fine-tunes pretrained autoregressive Transformers for selective discrete recurrence: iteratively evolving an explicit sequence state through in-place transitions that selectively retain, revise, or retire predecessor content to condition subsequent steps. Through RoPE manipulation and active key–value reorganization, Theseus-AR maintains a topologically coherent representation across transitions without re-encoding successor states from scratch. To train this recurrence efficiently, we develop Replay Attention, which compiles dynamic topology views along the full sequence of state transitions into parallel replay units that reuse shared representations, restoring token-level parallel training with exact-arithmetic equivalence to online execution while reducing visible query–key attention pairs from quadratic in transcript length to workload-bounded . Across programmatic testbeds, Theseus-AR matches the Transition Trace validation-error level with up to fewer supervised target tokens in surgical in-place rewrites, reaches comparable validation error with 54%–87% fewer visible attention pairs in complex regimes, improves deep-horizon transition validity under Stepwise Transition Evaluation, and reduces peak active context tokens at inference by 59%–88%.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Autoregressive Transformers, Selective Discrete Recurrence, Non-Prefix Sequence Generation, Efficient Attention, KV Cache Optimization

Reviews

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

This paper proposes Theseus-AR, which enables autoregressive Transformers to edit their active context while reusing retained KV representations through dynamic RoPE updates. It also introduces Replay Attention for parallel training over editing trajectories. Experiments on ListOps, SAT variable elimination, and typed lambda-calculus reduction show reduced active context and attention-pair counts, with task-dependent improvements in sample efficiency and oracle-anchored single-step accuracy.

Critical strengths
  1. The method jointly addresses inference-time context editing and parallel training, with Replay Attention supporting changing token visibility and logical positions.
  2. The paper provides an exact-arithmetic equivalence argument between replay and online execution, supported by numerical checks of attention outputs and gradients.
Critical weaknesses

The Stepwise Transition Evaluation anchors predictions to oracle states, preventing errors from propagating across transitions. While useful diagnostically, it is not supplemented by free-running end-to-end comparisons between Theseus-AR and Transition Trace. This leaves unclear whether the stepwise gains translate into better long-horizon task performance.

Questions for authors

Could you report free-running end-to-end success rates for Theseus-AR and Transition Trace on the three tasks, without resetting intermediate states to the oracle, to assess whether the stepwise gains translate into better complete-task performance?

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

The paper raises the concern that standard LLMs can only work in an autoregressive way to append one token at a time, resulting in messy, ever-growing outputs. To overcome this, the authors propose Theseus-AR, a technique to fine-tune the model to edit its own output (keep, replace, insert, delete) while efficiently updating their internal memory so the edited state doesn't have to be recomputed. While the idea behind the work is good, the paper lacks clear motivation, and the experimental setting needs a heavy restructuring before it reaching the bar of a successful submission. Experiments are conducted on tasks spanning works from 1960s. Moreover, there is no comparison done on either recent benchmarks on long-horizon or agentic tasks (where the mentioned concern will be most paramount) or with other contemporary methods.

Critical strengths
  • The paper raises an important concern in autoregressive models about only predicting the next token, thereby making a cascading effect in a previously generated wrong token worse.
Critical weaknesses
  • The paper is extremely difficult to follow. The motivation in the introduction calls out standard LLMs can only append, which forces messy, ever-growing outputs. There are so many works on LLM context management regarding KV-cache, various attention mechanisms like Sliding Window, Linear Attention, Flash Attention etc, and positional encoding mechanisms like RoPE that tackle this. What is the novelty here?
  • Furthermore, the paper suggests Theseus-AR fine-tunes them to edit their own output (keep, replace, insert, delete) while efficiently updating their internal memory so the edited state doesn't have to be recomputed. This is still autoregressive token prediction, so its not very clear about the main contribution of this approach.
  • The experimental setup is again very hard to follow. There are no comparisons on standard long context or agentic benchmarks, making it a big gap between motivation in the introduction and main results.
  • Regarding the results, there are no ablation analysis, and very little discussion of the results.
Questions for authors
  • There are several variables proposed in Introduction and Section 3 which are not clearly explained. Pretty much none of the variables are explained. The authors should really consider defining these better in the paper.
  • Please add more details regarding the experimental datasets and have analysis on more recent benchmarks on agentic and long-horizon tasks.
Reviewer_qPxWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work introduces Theseus-AR, which overcomes monotonic prefix extension in autoregressive Transformers by maintaining an explicit active sequence state. At inference, dynamic RoPE and KV-cache reorganization retain, replace, or drop tokens in-place instead of accumulating all history. For training, Replay Attention compiles multi-step state-transition trajectories into parallelizable units, reducing attention complexity from quadratic in total history length to linear in active state size. On three programmatic tasks, it cuts peak active context tokens by 59–88% and visible attention pairs by 54–87%, while improving validity in deep-horizon steps.

Critical strengths

The core problem is well-motivated: iterative tasks like program synthesis, proof refinement, and structured planning don't fit left-to-right generation, and standard prefix extension wastes resources on obsolete content.

Critical weaknesses
  • No wall-clock speedup: Triton prototype shows algorithmic gains but no end-to-end speedup over mature kernels like FlashAttention-2; practical efficiency remains theoretical.
  • Restricted architecture scope: Works only with full-attention backbones; incompatible with SSMs, linear attention, and GQA variants.
  • Narrow evaluation: Testbeds are synthetic, deterministic, oracle-driven programmatic tasks; generalization to open-ended language and real code is unclear.
  • High complexity: Replay Attention needs custom routing, trajectory compilation, and non-standard kernels; overhead vs. baselines is not fully quantified.
Questions for authors

What concrete roadmap would turn reduced attention-pair count into measured wall-clock latency gains, and what speedup magnitude do you expect with optimized kernels?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.