PaperlayerView exact revision on arXiv

Source-linked AI summary

The Markovian Thinker: Architecture-Agnostic Linear Scaling of Reasoning

Milad Aghajohari, Kamran Chitsaz, Amirhossein Kazemnejad, Sarath Chandar, Alessandro Sordoni, Aaron Courville, Siva Reddy

arXiv:2510.06557v3cs.LGcs.AIcs.CL

TL;DR

LongCoT reasoning makes the RL state grow with the full trace, imposing quadratic compute on attention-based policies. The paper proposes Markovian Thinking and implements it in Delethink through fixed-size reasoning chunks with a short carryover. Delethink matches or surpasses LongCoT-RL at a 24K budget and scales better at test time, with lower estimated training cost at long thinking lengths.

  • Problem

    In standard reasoning RL, the state includes the prompt and all prior reasoning tokens, so it grows without bound and makes attention-based compute quadratic as thoughts lengthen.

    Source: §1 · p. 1

  • Method

    Markovian Thinking bounds the policy state, and Delethink trains reasoning in chunks with a reset context and a short textual carryover between chunks.

    Source: §1 · p. 1, §4.1 · p. 6

  • Results

    At a 24K thinking budget, Delethink matches and surpasses LongCoT-RL on math benchmarks; estimated training cost at an average 94K thinking length is 27 H100-months for LongCoT-RL versus 7 for Delethink.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results show that reasoning length can be decoupled from context size, yielding linear compute and constant memory with thinking length.

    Source: §1 · p. 2, §8 · p. 14

    The authors offer only a speculative explanation for Delethink’s advantage over LongCoT-RL 24K: pretraining on shorter contexts might have played a role.

    Source: §8 · p. 14

Abstract

from arXiv · show

Reinforcement learning (RL) has recently become a strong recipe for training reasoning LLMs that produce long chains of thought (LongCoT). Yet the standard RL "thinking environment", where the state is the prompt plus all prior reasoning tokens, makes the state unbounded and forces attention-based policies to pay quadratic compute as thoughts lengthen. We revisit the environment itself. We propose Markovian Thinking, a paradigm in which the policy advances reasoning while conditioning on a constant-size state, decoupling thinking length from context size. As an immediate consequence this yields linear compute with constant memory. We instantiate this idea with Delethink, an RL environment that structures reasoning into fixed-size chunks. Within each chunk, the model thinks as usual; at the boundary, the environment resets the context and reinitializes the prompt with a short carryover. Through RL, the policy learns to write a textual state near the end of each chunk sufficient for seamless continuation of reasoning after reset. Trained in this environment, an R1-Distill 1.5B model reasons in 8K-token chunks yet thinks up to 24K tokens, matching or surpassing LongCoT-RL trained with a 24K budget. With test-time scaling, Delethink continues to improve where LongCoT plateaus. The effect of linear compute is substantial: we empirically estimate at 96K average thinking length LongCoT-RL costs 27 H100-months vs. 7 for Delethink. Analysis at RL initialization shows off-the-shelf reasoning models (1.5B-120B) often sample Markovian traces zero-shot across diverse benchmarks, providing positive samples that make RL effective at scale. Our results show that redesigning the thinking environment is a powerful lever: it enables very long reasoning without quadratic overhead and opens a path toward efficient, scalable reasoning LLMs.

1 Introduction

The standard reasoning RL state grows with the full reasoning trace, making attention-based compute quadratic. Markovian Thinking bounds the state, and Delethink applies it through chunked reasoning with short carryover.

1 Introduction

  • Delethink divides reasoning into fixed-size chunks, resetting the context at each boundary and carrying forward a short textual state learned through RL.The policy writes this state near the end of a chunk so reasoning can continue after the reset.Source: §1 · p. 2, Figure 1 · p. 2
  • At an average 94K thinking length, estimated training cost is 27 H100-months for LongCoT-RL versus 7 for Delethink.The paper reports quadratic cost growth for LongCoT and linear growth for Delethink.Source: §1 · p. 2, Figure 2 · p. 3
  • At RL initialization, R1-Distill models from 1.5B to 14B parameters already sample zero-shot Markovian traces, while GPT-OSS 120B shows the behavior across diverse tasks.The paper reports that the R1-Distill family recovers most standard LongCoT performance without additional training or prompting.Source: §1 · p. 2
  • The results identify the RL environment as a lever for reasoning efficiency and suggest Markovian thinking could let models think for millions of tokens in principle.The paper also suggests non-quadratic sequence architectures may particularly benefit because thinking can be made effectively Markovian.Source: §1 · p. 2
  • Markovian Thinking bounds the policy’s input state, yielding linear compute and constant memory as thinking length grows.It decouples how long the model thinks from how much context it processes.Source: §1 · pp. 1–2
  • 8K-token chunks let R1-Distill 1.5B think up to 24K tokens, matching and surpassing LongCoT-RL on math benchmarks at the same 24K budget.The paper reports that Delethink continues improving with test-time scaling where LongCoT-RL plateaus.Source: §1 · p. 2, Figure 2 · p. 3

2 Related Works

Prior efficiency work shortens or prunes reasoning under LongCoT, while Delethink changes how the RL environment carries reasoning forward. Related work also includes architecture-level alternatives to quadratic attention and approaches that summarize or constrain inference-time traces.

Efficient RL training of LongCoT

Inference Time Efficient Thinking

  • Inference-time efficiency work shortens traces, controls their length, structures reasoning, selects or compresses tokens, or evicts tokens after training.These approaches are used to speed inference after RL training.Source: §2 · p. 3

Making Room for Extra Thinking

  • Prior work also prunes or summarizes reasoning segments, whereas InftyThink uses a fixed style distilled from a hand-crafted dataset; Delethink learns Markovian thinking through RL.The cited summary approaches include Lin et al. (2025), Xiao et al. (2025), and Yan et al. (2025).Source: §2 · p. 3

Linear Architectures

  • Sliding or sparse attention, linear attention, and state-space models avoid quadratic attention interactions, but Delethink instead decouples reasoning length from context length without modifying the architecture.The passage presents Delethink as evidence that constant-token reasoning may also benefit these alternative architectures.Source: §2 · p. 4

3 Background

Standard LongCoT RL represents each state as the prompt plus all generated tokens, so context grows throughout reasoning. For attention-based policies, this entails quadratic compute as thinking length increases.

3 Background

  • The standard generation state concatenates the prompt with all prior tokens, so its size grows with each action.The process starts at the prompt and appends each sampled token to form the next state.Source: §3 · pp. 4–5
  • For thinking length nS, LongCoT uses O(n²S²) FLOPs and O(nS) memory, while Delethink uses O(n²S) FLOPs and O(n) memory.The table also reports backward and generation times scaling as O(TB S²) and O(TG S²) for LongCoT, versus O(TB S) and O(TG S) for Delethink.Source: §3 · p. 5
  • Attention-based policies incur quadratic compute as reasoning tokens accumulate in the unbounded state.The final response token is generated with a context containing the prompt and the preceding response.Source: §3 · p. 5

4 Delethink

Delethink makes reasoning Markovian by dividing it into fixed-size chunks and carrying a short textual state across context resets. Its training objective covers all chunks, while its bounded context yields compute and memory advantages as traces lengthen.

4 Delethink

  • Delethink trains policies to reason in fixed-size chunks, resetting context between chunks and carrying forward a short textual state.The policy learns what to write into the carryover so it can continue reasoning from bounded context.Source: §4 · p. 5

4.1 Delethink Tracing

  • Each trace starts from the query, then builds later prompts from the query and the previous chunk’s last m tokens until EOS or the iteration cap.The model generates up to C tokens in the first chunk and up to C−m new thinking tokens in later chunks.Source: §4.1 · pp. 5–6

4.2 Policy Gradient

  • The Delethink policy-gradient objective sums contributions across chunks because each chunk contributes to the trace’s final reward.The estimator adapts standard policy-gradient training to Delethink dynamics and is intended to fit existing infrastructure.Source: §4.2 · p. 7

4.3 Computational Cost of Scaling Thinking

  • As thinking scales from n to nS tokens, both generation and backward stages scale linearly for Delethink but quadratically for LongCoT.With C = n and m = n/2, Delethink’s FLOPs are O(n²S); each token is generated once and reprocessed as the next chunk’s prompt.Source: §4.3 · p. 8
  • Delethink keeps only the current chunk’s KV cache, so peak memory remains constant, while LongCoT’s cache grows with thinking length.A 1M-token LongCoT trace on R1-Distill 1.5B can fill an H100 with KV cache alone.Source: §4.3 · p. 8
  • Delethink’s generation time scales linearly in S, while LongCoT’s scales quadratically because its growing KV cache lowers throughput.The analysis assumes an infinite stream of requests saturating the GPU; Delethink’s throughput remains constant per chunk.Source: §4.3 · p. 8
  • Changing chunk size alters Delethink’s FLOP constant without changing its linear scaling in S.With context C = 2n, FLOPs are O(4n²S); smaller contexts and states can also remain linear in S.Source: §4.3 · p. 8

5 Experimental Setup

The experiments train R1-Distill 1.5B on competition-level math problems and compare Delethink with LongCoT-RL under matched thinking budgets. Evaluation covers in-distribution math and out-of-distribution science and code tasks, with accuracy reported as sampled Pass@1.

5 Experimental Setup

  • RL training uses approximately 40K curated competition-level math problem–answer pairs from DeepScaleR and initializes from R1-Distill 1.5B.The models are full-parameter fine-tuned.Source: §5 · pp. 8–9
  • Beyond its training budget, Delethink continues to improve accuracy through 128K thinking tokens, while LongCoT-RL 24K and 8K plateau.Within their training budgets, both Delethink 24K and LongCoT-RL improve as thinking tokens increase.Source: Figure 7 · p. 9
  • Evaluation covers AIME’24, AIME’25, and HMMT’25, plus GPQA Diamond and LiveCodeBench as out-of-distribution tests.LiveCodeBench questions are restricted to dates 2024-08-01–2025-02-01.Source: §5 · p. 9
  • Delethink is compared with LongCoT-RL at matched maximum thinking budgets of 24K and 8K tokens, using sampled Pass@1 accuracy.Checkpoints are selected on AIME’24 validation; reported avg@128 estimates average correctness across 128 independently sampled responses.Source: §5 · p. 9
  • Training runs for 1000 steps with 1024 episodes per step, using 8K Delethink contexts, five iterations, and state size m = C/2.This Delethink configuration permits up to 24K thinking tokens; training uses 8 H100 GPUs and disables the KL penalty.Source: §5 · p. 9

6 Results

With an equal 24K-token budget, Delethink matches or outperforms LongCoT-RL and continues improving beyond its training limit. Results also show efficient scaling to longer traces, including a 96K-trained model, while smaller chunk contexts remain effective but trail the larger ones.

6 Results

  • At a 24K budget, Delethink matches or outperforms LongCoT-RL 24K at equivalent RL steps, with each Delethink step costing less.LongCoT-RL 8K underperforms Delethink by 5.5%.Source: §6 · pp. 9–10

6.1 Task Performance

  • On AIME’24, AIME’25, and HMMT’25, Delethink scores higher than LongCoT-RL 24K; on GPQA-Diamond and LiveCodeBench, gains are modest but it matches or slightly surpasses that baseline.LongCoT-RL 8K consistently underperforms on these comparisons.Source: §6.1 · p. 10

6.2 Test-Time Scaling

  • Delethink continues improving with sequential test-time scaling beyond its 24K training limit, while LongCoT-RL 24K and 8K plateau at their respective limits.Some AIME’25 problems are solved only after up to 140K thinking tokens, despite 24K-token training.Source: §6.2 · p. 10

6.3 Empirical Compute

  • Delethink completes an RL step in 215s versus 248.5s for LongCoT-RL 24K and generates 8,500 versus 6,000 tokens per second per H100.The backward pass takes 80s for Delethink and 70s for LongCoT-RL 24K; beyond 32K tokens, Delethink becomes increasingly faster, reaching 17× lower FLOPs at one million tokens.Source: §6.3 · pp. 10–11

6.4 Context Size Ablation

  • With a total 24K budget, 4K contexts perform similarly to 8K, while 2K trails both but improves beyond the base model.The ablation sets state size m to half the context size.Source: §6.4 · p. 11

6.5 Scaling Delethink to 96K

  • After 150 training steps, Delethink 96K matches or exceeds test-time-scaled Delethink 24K at a 128K budget and reaches mean traces of 36K on AIME’24 and 42K on AIME’25.The 96K run continues from the Delethink 24K checkpoint and uses OpenMath training data.Source: Figure 8 · p. 10, §6.5 · p. 11

7 Why Delethink Works?

Delethink Tracing often works from zero-shot initialization, while strong state-of-the-art models also show Markovian behavior. Its performance depends on context size and task: it scales beyond LongCoT on some settings but struggles more when tasks require persistent memory.

7 Why Delethink Works?

  • Zero-shot R1-Distill models already produce Markovian traces, often recovering or exceeding standard LongCoT performance and providing positive samples for RL initialization.This initialization is the proposed explanation, at least in part, for successful Delethink training.Source: §7 · p. 12, §7.2 · p. 12

7.1 R1-Distill

  • 8K Delethink Tracing matches LongCoT across tasks at up to 128K thinking tokens, while 4K falls behind only on GPQA-Diamond and surpasses it elsewhere.On AIME’24 and AIME’25, Delethink Tracing also surpasses LongCoT as test-time thinking increases, whereas LongCoT quickly plateaus at 32K tokens.Source: §7.1 · p. 12

7.2 Will Delethink Scale?

  • At RL initialization, Delethink Tracing with 16K context recovers most original performance for GPT-OSS 120B and Qwen3 30B-A3B; 8K remains a reasonable lower-compute option.With 16K context, tracing matches or exceeds LongCoT on Qwen3 and almost matches it on GPT-OSS; 8K lags behind LongCoT.Source: §7.2 · pp. 12–13
  • Problem coverage is similar between Delethink and LongCoT on AIME’24, AIME’25, and GPQA-Diamond for GPT-OSS and Qwen3.For GPQA-Diamond, GPT-OSS solves 161 problems with Delethink versus 159 with LongCoT; Qwen3 solves 138 with both.Source: §7.2 · p. 13, Figure 11 · p. 13
  • On CrossWordBench, Delethink remains broadly comparable to LongCoT on 7 × 7 puzzles but declines on harder 14 × 14 puzzles, where maintaining a live grid can exceed carried-state capacity.Both models still produce a nontrivial number of valid Markovian traces on the harder puzzles.Source: §7.2 · p. 13, Figure 11 · p. 13

8 Discussion

The discussion argues that bounded-state thinking can reduce the cost of extending reasoning, while the appendices derive the training objective and analyze throughput and FLOP scaling. Delethink has a short-sequence cost crossover, after which its linear compute scaling is more efficient than LongCoT’s quadratic scaling.

8 Discussion

  • Markovian Thinking decouples thinking length from context size, enabling linear compute and constant memory and suggesting that non-quadratic sequence architectures may benefit from reasoning workloads.The discussion presents these as a potential path toward reasoning across millions of tokens, not a demonstrated million-token result.Source: §8 · p. 14

A Deriving Delethink Loss

  • Delethink’s training loss is derived as a policy-gradient objective, then modified with PPO clipping, response-token normalization, and a KL term, which bias the gradient away from the exact policy gradient.The derivation is included for completeness and is described as closely following standard policy-gradient reasoning.Source: A Deriving Delethink Loss · pp. 21–22

B Deriving Throughput Relation

  • In the long-thinking regime, attention-based decoding throughput is approximately inversely proportional to decoding length because KV-cache memory and its memory-time cost grow with decoded tokens.The throughput relation is derived under a GPU memory constraint with fixed per-batch overhead and a per-unit-memory time cost.Source: B Deriving Throughput Relation · pp. 22–23

C Delethink FLOPs Crossover vs. LongCoT 24K

  • Delethink’s FLOPs are slightly higher than LongCoT’s up to roughly 30K tokens, but beyond that crossover it is linearly more efficient; at 96K, LongCoT-RL could not be trained within the available compute resources.Delethink’s repeated chunk-input processing doubles non-attention-layer costs, while attention’s quadratic cost overtakes this for longer sequences.Source: C Delethink FLOPs Crossover vs.… · p. 23, Figure C.1 · p. 23
  • Although FLOPs track total backward time, LongCoT generation can remain slower because generation throughput is limited by memory-access and memory-footprint bottlenecks.The authors report that Delethink 96K is significantly faster than its LongCoT-RL 96K counterpart in both backward pass and generation.Source: C Delethink FLOPs Crossover vs.… · p. 23

D Detailed RL Training Setup

The training setup uses R1-Distill 1.5B, competition-style math data, and matched LongCoT-RL comparisons. Delethink’s 8K chunk and 4K carried-state configuration is chosen to match a 24K thinking budget.

D Detailed RL Training Setup

  • Training starts from R1-Distill 1.5B with full-parameter fine-tuning, using roughly 40K curated competition-style math problem–solution pairs and held-out AIME’24, AIME’25, and HMMT’25 evaluation.The training data is DeepScaleR; checkpoints are selected using the held-out AIME’24 validation set.Source: D Detailed RL Training Setup · pp. 23–24
  • Delethink-RL and LongCoT-RL are compared under matched maximum thinking budgets and closely matched training conditions, with LongCoT-RL’s 24K-token budget as the main baseline.Accuracy is reported as bootstrap-aggregated avg@128 from 256 responses per prompt, with standard deviations below 0.004.Source: D Detailed RL Training Setup · p. 24, Table D.1 · p. 25
  • Each RL step samples 8 traces for 128 prompts and applies two optimizer updates; training runs for 1000 steps with KL penalty disabled and truncated importance sampling.The PPO clip-high ratio is tuned from 0.2 to 0.28 to maintain entropy stability.Source: D Detailed RL Training Setup · p. 25
  • Delethink-RL uses C = 8K, m = C/2, and at most five iterations, allowing up to 24K reasoning tokens to align with the LongCoT-RL budget.The setup describes the reasoning context size as chosen for effectiveness under a 24K-token budget with the base model.Source: D Detailed RL Training Setup · p. 25

D.1 Hyperparameters

  • At fixed 8K chunk context, R1-Distill models show stable accuracy across small carried states, while Qwen3 benefits from larger states; at 4K context, R1-Distill models also show state-size sensitivity.The figure captions identify these as carried-state-size ablations; the 8K and 4K settings are shown separately.Source: Figure E.3 · p. 26, Figure E.4 · p. 26

E Markovian State Size Ablation

The ablation varies carried-state size while holding chunk context and total token budget fixed. Its results show that the useful state size depends on model family and chunk context.

E Markovian State Size Ablation

  • The ablation holds C = 8K and the overall token budget constant while sweeping m from 1K to 7K, adjusting the iteration cap to match budgets.It evaluates R1-Distill 1.5B, 7B, and 14B and Qwen3 30B-A3B on AIME’24, AIME’25, GPQA-Diamond, and LiveCodeBench.Source: E Markovian State Size Ablation · p. 26
  • With C = 8K, R1-Distill accuracy is essentially flat as carried state shrinks from 7K to 1K, while Qwen3 accuracy improves with larger states on AIME’24, AIME’25, and LiveCodeBench.The authors relate Qwen3’s sensitivity to its 256K native context and longer Delethink traces on AIME and LiveCodeBench.Source: E Markovian State Size Ablation · p. 26
  • At C = 8k, reducing carried state from 7k to 1k has negligible effect on all R1-Distill tasks; at C = 4k, they show Qwen3-like sensitivity, suggesting interplay between context size and average response length.Source: E Markovian State Size Ablation · p. 26

E.1 Thinking Context Size Ablation

The ablation finds that suitable chunk sizes let off-the-shelf R1 models scale with thinking budget, while 2k chunks constrain stable reasoning. Delethink tracing also lets a LongCoT checkpoint improve beyond its trained budget.

E.1 Thinking Context Size Ablation

  • The ablation varies per-chunk context C across three R1–Distill sizes and four benchmarks, holding carried state at m = C/2.Smaller C requires more iterations to reach the same total token budget.Source: §E.1 · p. 27
  • For R1 models, C = 4k can outperform C = 8k on several tasks at 1.5B, while C = 8k is typically best or tied at 7B and 14B.All models improve with increased budget, and many cases surpass the LongCoT baseline.Source: §E.1 · pp. 27–28
  • C = 2k rarely approaches LongCoT and almost never terminates within budget, consistent with difficulty finalizing reasoning under a short local horizon.The figure reports lower EOS rates and much longer responses at 2k than at 4k or 8k.Source: §E.1 · p. 28, Figure E.6 · p. 28

F Delethink Tracing on LongCoT checkpoints

  • Delethink tracing raises the LongCoT-24K checkpoint’s performance by nearly 4% beyond its trained budget, with C = 8k yielding a larger gain than C = 16k.The passage reports that this gain is nearly as large as the checkpoint’s gain from RL training, without additional training cost.Source: F Delethink Tracing on LongCoT… · p. 28

G Budget Force Ablation: Does S1 work on R1?

Budget-Force increases response length but generally underperforms Long-CoT, while longer Delethink traces improve accuracy on some AIME’25 problems. Small-k evaluation is especially noisy on small test sets.

G Budget Force Ablation: Does S1 work on R1?

H AIME’25 detailed Length vs. Accuracy

  • On AIME’25, several problems become more accurately solvable with longer Delethink traces, while LongCoT points concentrate at shorter lengths and lower accuracy.The per-problem analysis samples 128 responses for each of 30 questions; the effect is not universal across items.Source: H AIME’25 detailed Length vs. Accuracy · p. 30, Figure H.10 · p. 32

I Variance from small k in avg@k

  • Small k increases avg@k variance, especially on small test sets such as AIME with Q = 30; the study reports avg@128 in its main results.The authors recommend at least k ≥64 and bootstrap uncertainty bands when smaller k is unavoidable.Source: I Variance from small k in avg@k · p. 30, Figure I.11 · p. 32

J The Difference Between Delethink and Window Attention

Delethink changes the RL environment to pass an explicit textual state across fixed-size chunks, unlike sliding or streaming attention’s continuous token stream and implicit retention. The approaches are orthogonal, and an efficient KV-state variant remains future work.

J The Difference Between Delethink and Window Attention

  • Delethink carries explicitly written textual state across resets; sliding-window and streaming attention retain information implicitly within a continuous token stream.Under Delethink, no cross-chunk key/value state survives the reset.Source: J The Difference Between Delethink and… · pp. 32–33, Figure J.12 · p. 34
  • Delethink can be combined with full, sliding-window, or streaming attention, and its benefits do not depend on a specific attention variant.Applying windowed or streaming attention within chunks can further reduce within-chunk cost.Source: J The Difference Between Delethink and… · p. 33
  • An efficient KV-state MDP is left for future work because practical use requires GPU kernels across inference and training stacks that current systems do not provide.How effectively such an MDP trains compared with LongCoT-RL is beyond the paper’s scope.Source: J The Difference Between Delethink and… · p. 33
  • Delethink demonstrates Markovian Thinking without changing model architecture, using separate chunk passes and textual state.The figure contrasts this with full attention’s single pass.Source: J The Difference Between Delethink and… · pp. 32–34

Related papers

Loading 2510.06557v3…