The Markovian Thinker
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.
68e75ca67ae125f9582e6b3d
Milad Aghajohari
claimed_verified
2025-10-09T12:48:16.729Z
6197f5213619d373ad154f73
https://cdn-avatars.huggingface.co/v1/production/uploads/6197f5213619d373ad154f73/PzMlx-n984x03Ldy34Xdi.jpeg
Milad Aghajohari
user
miladink
68e75ca67ae125f9582e6b3e
Kamran Chitsaz
claimed_verified
2025-10-09T12:48:20.598Z
6303d7dd0547362a22a59ac2
https://cdn-avatars.huggingface.co/v1/production/uploads/6303d7dd0547362a22a59ac2/iHV2VKEUXxoM47aNnzn-P.jpeg
Kamran Chitsaz
user
kmchiti
68e75ca67ae125f9582e6b3f
Amirhossein Kazemnejad
claimed_verified
2025-10-09T12:48:22.726Z
63458f12d54fb141dedac508
/avatars/3946fb9c23d1cd24037770cc0a3489bf.svg
Amirhossein Kazemnejad
user
kazemnejad
68e75ca67ae125f9582e6b40
Sarath Chandar
68e75ca67ae125f9582e6b41
Alessandro Sordoni
68e75ca67ae125f9582e6b42
Aaron Courville
68e75ca67ae125f9582e6b43
Siva Reddy
The Markovian Thinker
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.
Markovian Thinking, implemented in Delethink, enables efficient and scalable reinforcement learning for long-chain-of-thought reasoning in LLMs by decoupling thinking length from context size, resulting in linear compute and constant memory usage.
Reinforcement learning reasoning LLMs LongCoT Markovian Thinking attention-based policies Delethink fixed-size chunks R1-Distill test-time scaling RL initialization reasoning models