Research map / Large language models / Reasoning and chain of thought

The Markovian Thinker

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: RL with verifiable rewards for reasoning

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Delethink, an RL environment that splits long chain-of-thought reasoning into fixed-size chunks with a short textual carryover, letting R1-Distill 1.5B think up to 24K tokens with 8K chunks at linear compute cost.

Problem

Reasoning LLMs trained with RLVR and long chain-of-thought face quadratic compute growth because the RL state (prompt plus all prior thinking tokens) grows unboundedly, making long-thinking RL and test-time scaling expensive.

Approach

Redefine the thinking RL environment as a Markovian process: generation proceeds in fixed-size chunks, and at each boundary the context is reset to the query plus a short carryover (last m tokens), so the policy learns to write a textual state that lets reasoning continue; this yields linear compute and constant memory in thinking length, with a derived policy gradient for the chunked trajectories

Key results

• Delethink 24K (8K chunks) matches or surpasses LongCoT-RL 24K on AIME/HMMT math benchmarks while using less compute per RL step (215s vs 248.5s).
• Delethink 96K reaches 49% on AIME'24 with average trace length around 36K tokens after 150 additional RL steps.
• Empirically estimated training cost at 96K average thinking is 27 H100-months for LongCoT-RL versus 7 for Delethink.

Surprising findings

• Off-the-shelf reasoning models (R1-Distill 1.5B-14B, GPT-OSS-120B, Qwen3-30B-A3B) already sample Markovian traces zero-shot, recovering most of LongCoT performance without training.
• Delethink Tracing applied to a LongCoT-RL 24K checkpoint raises AIME'25 performance by nearly 4% at test time without additional training.

Limitations

• Experiments limited to small R1-Distill 1.5B for full RL training; larger models were not trained due to compute.
• Smaller chunk sizes (2K) cause models to rarely terminate within budget and degrade accuracy.
• Performance on tasks requiring live memory (CrossWordBench 14x14) declines relative to LongCoT.

Experimental setup

Datasets: DeepScaleR OpenMath

Benchmarks: AIME'24 AIME'25 HMMT'25 GPQA-Diamond LiveCodeBench CrossWordBench

Metrics: Pass@1 accuracy (avg@128) training reward training cost (H100-months) throughput FLOPs

Baselines: LongCoT-RL 24K LongCoT-RL 8K R1-Distill 1.5B LongCoT

Builds on: GRPO DeepScaleR PPO verl

Closest papers by meaning

• Markovian Transformers for Informative Language Modeling (ICLR 2026 · similarity 0.90)
• RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning (ICLR 2026 · similarity 0.89)
• Don’t Think Longer, Think Wisely: Optimizing Thinking Dynamics for Large Reasoning Models (NeurIPS 2025 · similarity 0.89)
• Thinkless: LLM Learns When to Think (NeurIPS 2025 · similarity 0.89)
• DeepCompress: A Dual Reward Strategy for Dynamically Exploring and Compressing Reasoning Chains (ICLR 2026 · similarity 0.89)
• Think Deep, Not Just Long: Measuring LLM Reasoning Effort via Deep-Thinking Tokens (ICML 2026 · similarity 0.89)