MarkovScale: Towards Optimal Sequential Scaling at Inference Time

Youkang Wang, Jian Wang, Rubing Chen, Tianyi Zeng, Xiaoyong Wei, Li QingSubmission to ICLR 2026 · Rejected

TL;DR

Researchers have introduced MarkovScale, a principled framework that models iterative LLM reasoning as a two-state Markov process. By moving away from heuristic "think more" strategies, this method provides closed-form solutions to predict when more computation will actually help, when it will hurt, and exactly when the model should stop "thinking" to maximize accuracy while saving up to 70% in token costs.

What Problem Does This Paper Address?

"Inference-time scaling"—the idea that an LLM can perform better if you give it more "thinking" time or computational budget at the moment of generation—is the current frontier of AI research (exemplified by models like OpenAI’s o1). Generally, this happens in two ways: parallel scaling (generating many answers and picking the best) and sequential scaling (iteratively refining a single answer).

While sequential scaling is more token-efficient, it is notoriously unstable. Current methods rely on heuristics—basically just telling the model to "think again"—which often leads to diminishing returns or even "overthinking," where a model flips a correct answer to an incorrect one. Until now, we lacked a mathematical foundation to determine the theoretical limits of these methods or a principled way to decide when a model has "thought enough."

Methods

The authors propose modeling the sequential reasoning process as a discrete-time, two-state Markov Chain.

  1. The Two States: At any iteration $i$, the model's answer is either Correct (C) or Wrong (W).
  2. Transition Probabilities: They define two key variables:
  3. $a$: The probability of moving from Correct to Wrong (the "forgetting" or "error" rate).
  4. $b$: The probability of moving from Wrong to Correct (the "self-correction" rate).
  5. Closed-Form Solutions: Using this matrix, they derive a formula to calculate the probability of being correct at any step $i$. This allows them to calculate the theoretical upper bound of a model's accuracy ($L = b / (a+b)$).
  6. MarkovScale System: They implement three versions of their system:
  7. MarkovScale$^t$ (Gating): Bypasses scaling entirely if the initial answer is likely correct enough.
  8. MarkovScale$^*$ (MAP): Uses Maximum A Posteriori estimation and Process Reward Models (PRMs) to dynamically update the probability of correctness and stop at the mathematically optimal iteration.
  9. MarkovScale$^0$ (Training-Free): A variant that estimates these probabilities on the fly without needing offline training data.

Datasets

The framework was evaluated on five rigorous reasoning and mathematics benchmarks:

  • MATH-500: 500 high-school competition problems.
  • GSM8K: 8.5K grade-school math word problems.
  • AIME 2024 & 2025: Pre-Olympiad level mathematics.
  • AMC 2023: Intermediate-level American Math Competitions.

The authors tested these across three backbone models: DeepSeek-R1-Distill-Llama-8B, DeepSeek-R1-Distill-Qwen-7B, and the larger QwQ-32B.

Key Insights and Ideas

  • Predictable Convergence: The most striking insight is that sequential scaling performance isn't random. It converges exponentially toward a fixed point determined by the model's inherent "self-correction" vs. "error" ratio.
  • The "Benefit Function": The authors prove that scaling is only beneficial if the initial zero-shot accuracy is below a certain threshold ($p_0 < b/(a+b) + \sigma$). If a model is already very good at a task, more "thinking" is statistically more likely to degrade the answer than improve it.
  • Theoretical vs. Empirical Match: Their theoretical predictions of accuracy matched actual experimental results with a Mean Absolute Error (MAE) of only 2.88%, proving that the Markov simplification actually captures the core dynamics of LLM reasoning.
  • Pareto Optimality: MarkovScale consistently finds the "sweet spot" on the accuracy-vs-token curve, outperforming parallel methods (like Best-of-N) by achieving higher accuracy with significantly fewer tokens.

Key Results

  • Accuracy Gains: MarkovScale improved accuracy by an average of 19.7% on the DeepSeek-Llama-8B model and 7.7% on the much stronger QwQ-32B model.
  • Efficiency: On the MATH-500 benchmark, MarkovScale achieved 97% accuracy while saving 70% of the tokens used by the "Multi-Round Thinking" baseline.
  • Robustness: The system consistently outperformed state-of-the-art methods like Self-Consistency and Adaptive Self-Consistency across all tested budget levels ($N=8$ to $N=64$).

Limitations and Future Work

  • Binary State Simplification: The model assumes a binary "Correct vs. Wrong" state. In reality, reasoning paths are more complex, and a "Wrong" answer might be "closer" to correct than another, which a two-state model doesn't capture.
  • Verifier Dependency: The MAP estimation relies on the quality of external verifiers (like PRMs). If the verifier is biased or inaccurate, the stopping criterion will be sub-optimal.
  • Future Directions: The authors suggest expanding the framework to multi-state Markov models to account for different types of reasoning errors and exploring how this theory applies to multi-agent debates.

Summary updated

Abstract

Sequential scaling is a prominent inference-time scaling paradigm, yet its performance improvements are typically modest and not well understood, largely due to the prevalence of heuristic, non-principled approaches that obscure clear optimality bounds. To address this, we introduce a principled framework that models sequential scaling as a two-state Markov process, uncovering its fundamental properties and providing closed-form expressions for key aspects, including the conditions under which sequential scaling enhances accuracy, the theoretical accuracy upper bound, and the convergence rate. Leveraging this formulation, we develop MarkovScale, a practical system that applies these optimality criteria to achieve a theoretically grounded balance between accuracy and efficiency. Comprehensive experiments across 3 backbone LLMs and 5 benchmarks show that MarkovScale consistently outperforms state-of-the-art parallel and sequential scaling methods, representing a significant step toward optimal and resource-efficient inference in LLMs. The source code will be open upon acceptance at https://open-upon-acceptance.
BibTeX
@misc{wang2026markovscale,
  author = {Youkang Wang and Jian Wang and Rubing Chen and Tianyi Zeng and Xiaoyong Wei and Li Qing},
  title = {{MarkovScale: Towards Optimal Sequential Scaling at Inference Time}},
  year = {2026},
  eprint = {2602.01120},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.01120},
}
Figure