# The Markovian Thinker: Architecture-Agnostic Linear Scaling of Reasoning

arXiv: https://arxiv.org/abs/2510.06557 · HTML: https://mlsanity.com/paper/2510.06557/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 41 of its 64 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 41)

- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [HybridFlow: A Flexible and Efficient RLHF Framework](https://mlsanity.com/paper/2409.19256/) (2024)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [gpt-oss-120b & gpt-oss-20b Model Card](https://mlsanity.com/paper/2508.10925/) (2025)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [PyTorch FSDP: Experiences on Scaling Fully Sharded Data Parallel](https://mlsanity.com/paper/2304.11277/) (2023)
- [The Entropy Mechanism of Reinforcement Learning for Reasoning Language Models](https://mlsanity.com/paper/2505.22617/) (2025)
- [GLM-4.5: Agentic, Reasoning, and Coding (ARC) Foundation Models](https://mlsanity.com/paper/2508.06471/) (2025)
- [Jamba: A Hybrid Transformer-Mamba Language Model](https://mlsanity.com/paper/2403.19887/) (2024)
- [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025)
- [O1-Pruner: Length-Harmonizing Fine-Tuning for O1-Like Reasoning Pruning](https://mlsanity.com/paper/2501.12570/) (2025)
- [TokenSkip: Controllable Chain-of-Thought Compression in LLMs](https://mlsanity.com/paper/2502.12067/) (2025)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [Compressed Chain of Thought: Efficient Reasoning Through Dense Representations](https://mlsanity.com/paper/2412.13171/) (2024)
- [ThinkPrune: Pruning Long Chain-of-Thought of LLMs via Reinforcement Learning](https://mlsanity.com/paper/2504.01296/) (2025)
- [AIMO-2 Winning Solution: Building State-of-the-Art Mathematical Reasoning Models with OpenMathReasoning dataset](https://mlsanity.com/paper/2504.16891/) (2025)
- [DAST: Difficulty-Adaptive Slow-Thinking for Large Reasoning Models](https://mlsanity.com/paper/2503.04472/) (2025)
- [NoLiMa: Long-Context Evaluation Beyond Literal Matching](https://mlsanity.com/paper/2502.05167/) (2025)
- [S-GRPO: Early Exit via Reinforcement Learning in Reasoning Models](https://mlsanity.com/paper/2505.07686/) (2025)
- [InftyThink: Breaking the Length Limits of Long-Context Reasoning in Large Language Models](https://mlsanity.com/paper/2503.06692/) (2025)
- [Jamba-1.5: Hybrid Transformer-Mamba Models at Scale](https://mlsanity.com/paper/2408.12570/) (2024)

## Built on by (most cited first, 13 of 13)

- [Reasoning Cache: Continual Improvement Over Long Horizons via Short-Horizon RL](https://mlsanity.com/paper/2602.03773/) (2026)
- [Test-time Recursive Thinking: Self-Improvement without External Feedback](https://mlsanity.com/paper/2602.03094/) (2026)
- [Accordion-Thinking: Self-Regulated Step Summaries for Efficient and Readable LLM Reasoning](https://mlsanity.com/paper/2602.03249/) (2026)
- [LongCoT: Benchmarking Long-Horizon Chain-of-Thought Reasoning](https://mlsanity.com/paper/2604.14140/) (2026)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Learning to Correct: Calibrated Reinforcement Learning for Multi-Attempt Chain-of-Thought](https://mlsanity.com/paper/2604.17912/) (2026)
- [Prefix Sliding for efficient test-time scaling](https://mlsanity.com/paper/2608.26070/) (2026)
- [LEAD: Breaking the No-Recovery Bottleneck in Long-Horizon Reasoning](https://mlsanity.com/paper/2603.06870/) (2026)
- [Message Passing Enables Efficient Reasoning](https://mlsanity.com/paper/2607.01077/) (2026)
- [Rotate2Think: Geometric Priming via Orthogonal Rotation to Improve Language Model Reasoning](https://mlsanity.com/paper/2606.09873/) (2026)
- [R2-Searcher: Calibrating Retrieval and Reasoning Boundaries for Agentic Search](https://mlsanity.com/paper/2606.28566/) (2026)
- [VIG: Visual Information Gain as a Reward Signal for Multimodal Chain-of-Thought Compression](https://mlsanity.com/paper/2608.21883/) (2026)
- [Latest Exact Match Attention](https://mlsanity.com/paper/2609.25802/) (2026)

## Abstract (arXiv)

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.