# Efficiently Scaling LLM Reasoning with Certaindex

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

## Key facts

- Cited by 58 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 47 of its 80 references that are in the map.
- First posted on arXiv 30 Dec 2024.

## Placed in

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

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [A Diverse Corpus for Evaluating and Developing English Math Word Problem Solvers](https://mlsanity.com/paper/2106.15772/) (2021)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [LEVER: Learning to Verify Language-to-Code Generation with Execution](https://mlsanity.com/paper/2302.08468/) (2023)
- [Self-Evaluation Guided Beam Search for Reasoning](https://mlsanity.com/paper/2305.00633/) (2023)
- [SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills](https://mlsanity.com/paper/2308.16369/) (2023)
- [Generative Reward Models](https://mlsanity.com/paper/2410.12832/) (2024)

## Built on by (most cited first, 30 of 58)

- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Deep Think with Confidence](https://mlsanity.com/paper/2508.15260/) (2025)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [Reasoning Models Know When They're Right: Probing Hidden States for Self-Verification](https://mlsanity.com/paper/2504.05419/) (2025)
- [THOUGHTTERMINATOR: Benchmarking, Calibrating, and Mitigating Overthinking in Reasoning Models](https://mlsanity.com/paper/2504.13367/) (2025)
- [Retro-Search: Exploring Untaken Paths for Deeper and Efficient Reasoning](https://mlsanity.com/paper/2504.04383/) (2025)
- [Mitigating Overthinking in Large Reasoning Models via Manifold Steering](https://mlsanity.com/paper/2505.22411/) (2025)
- [Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models](https://mlsanity.com/paper/2505.16122/) (2025)
- [Metacognitive Reuse: Turning Recurring LLM Reasoning Into Concise Behaviors](https://mlsanity.com/paper/2509.13237/) (2025)
- [BudgetThinker: Empowering Budget-aware LLM Reasoning with Control Tokens](https://mlsanity.com/paper/2508.17196/) (2025)
- [The Geometry of Reasoning: Flowing Logics in Representation Space](https://mlsanity.com/paper/2510.09782/) (2025)
- [HAPO: Training Language Models to Reason Concisely via History-Aware Policy Optimization](https://mlsanity.com/paper/2505.11225/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [LIMOPro: Reasoning Refinement for Efficient and Effective Test-time Scaling](https://mlsanity.com/paper/2505.19187/) (2025)
- [Kinetics: Rethinking Test-Time Scaling Laws](https://mlsanity.com/paper/2506.05333/) (2025)
- [Hawkeye:Efficient Reasoning with Model Collaboration](https://mlsanity.com/paper/2504.00424/) (2025)
- [Don't Think Longer, Think Wisely: Optimizing Thinking Dynamics for Large Reasoning Models](https://mlsanity.com/paper/2505.21765/) (2025)
- [Exploring the System 1 Thinking Capability of Large Reasoning Models](https://mlsanity.com/paper/2504.10368/) (2025)
- [Understanding and Steering the Cognitive Behaviors of Reasoning Models at Test-Time](https://mlsanity.com/paper/2512.24574/) (2025)
- [Conformal Thinking: Risk Control for Reasoning on a Compute Budget](https://mlsanity.com/paper/2602.03814/) (2026)
- [How Far Are We from Optimal Reasoning Efficiency?](https://mlsanity.com/paper/2506.07104/) (2025)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [PATS: Process-Level Adaptive Thinking Mode Switching](https://mlsanity.com/paper/2505.19250/) (2025)
- [TERMINATOR: Learning Optimal Exit Points for Early Stopping in Chain-of-Thought Reasoning](https://mlsanity.com/paper/2603.12529/) (2026)
- [Early Stopping for Large Reasoning Models via Confidence Dynamics](https://mlsanity.com/paper/2604.04930/) (2026)
- [SPORK: Self-Speculative Forking to Accelerate Agentic LLM Inference](https://mlsanity.com/paper/2607.03333/) (2026)
- [Queueing, Predictions, and LLMs: Challenges and Open Problems](https://mlsanity.com/paper/2503.07545/) (2025)
- [PREMISE: Scalable and Strategic Prompt Optimization for Efficient Mathematical Reasoning in Large Models](https://mlsanity.com/paper/2506.10716/) (2025)
- [Less is More: Improving LLM Reasoning with Minimal Test-Time Intervention](https://mlsanity.com/paper/2510.13940/) (2025)
- [Fantastic Reasoning Behaviors and Where to Find Them: Unsupervised Discovery of the Reasoning Process](https://mlsanity.com/paper/2512.23988/) (2025)

## Abstract (arXiv)

Test-time reasoning algorithms such as chain-of-thought, self-consistency, and MCTS enhance LLM problem-solving but can wastefully generate many tokens without improving accuracy. At the same time, we observe that these algorithms exhibit answer stabilization: their intermediate solutions often cease to change after a certain point, and further investment of compute does not change their final answer. To quantify this phenomenon, we introduce Certaindex, an algorithm-agnostic metric measuring this evolving stability, signaling when further computation is unlikely to alter the final result. Certaindex is lightweight, can accelerate reasoning program inference via early exit, and further enables dynamic token allocation, gang scheduling, and many opportunities when integrated with real-world LLM serving systems. To quantify real-world benefits, we built Certaindex as a scheduler into Dynasor, our reasoning-aware LLM serving system, and demonstrate up to 50% compute savings and 3.3x higher throughput in real workloads with no accuracy drop. Our code is available at https://github.com/hao-ai-lab/Dynasor.git