mlsanityData to 14 Oct 2026

Reasoning without Regret

arXiv 2504.09777 ↗First posted 14 Apr 2025cs.LG cs.AIcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Chain-of-thought reasoning enables large language models to solve multi-step tasks by framing problem solving as sequential decision problems. Outcome-based rewards, which provide feedback only on final answers, show impressive success, but face challenges with credit assignment and slow convergence. In contrast, procedure-based rewards offer efficient step-level feedback, but typically require costly human supervision. We introduce Backwards Adaptive Reward Shaping (BARS), a no-regret framework that converts sparse outcomes-based rewards into effective procedure-based signals. BARS uses sparse rewards generated from terminal-state priors and cover trees to scale rewards while preventing exploitation. With Bellman contraction and (Delta, ε)-gap rewards, our backward Euler solver achieves ε-accuracy in Oleft((Rmax/Delta)log(1/ε)right) iterations with O(log T) dynamic regret over T rounds. Our analysis, based on generic chaining, continuous scaling limits, and non-linear Feynman-Kac bounds, connects recent outcome-based methods' empirical successes with the benefits of intermediate supervision. Combined, this provides the first rigorous no-regret algorithm for outcome reward shaping, providing a theoretical foundation for the empirical success of DeepSeek's R1.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 51 of its 76 references that are in the map. First posted on arXiv 14 Apr 2025.

Builds on

51 of 76 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025The relationship between reasoning and performance in large language models--o3 (mini) thinks harder, not longer21 Feb
  2. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May
  3. 2022STaR: Bootstrapping Reasoning With Reasoning28 Mar

Other references · 48

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  4. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  5. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  6. 2023Let's Verify Step by Stepcited by 3,789
  7. 2015Trust Region Policy Optimizationcited by 2,580
  8. 2024DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligencecited by 1,181
  9. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 928
  10. 2022Solving math word problems with process- and outcome-based feedbackcited by 901
  11. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  12. 2017Spectrally-normalized margin bounds for neural networkscited by 686
36 more
  1. 2025Towards Large Reasoning Models: A Survey of Reinforced Reasoning with Large Language Modelscited by 293
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  3. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 279
  4. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoningcited by 279
  5. 2024RLHF Workflow: From Reward Modeling to Online RLHFcited by 267
  6. 2015The Benefit of Multitask Representation Learningcited by 195
  7. 2018RUDDER: Return Decomposition for Delayed Rewardscited by 173
  8. 2024Secrets of RLHF in Large Language Models Part II: Reward Modelingcited by 171
  9. 2024Recursive Introspection: Teaching Language Model Agents How to Self-Improvecited by 165
  10. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  11. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 125
  12. 2025Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuningcited by 123
  13. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 118
  14. 2023Confronting Reward Model Overoptimization with Constrained RLHFcited by 96
  15. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  16. 2025Process Reward Models for LLM Agents: Practical Framework and Directionscited by 85
  17. 2024InfoRM: Mitigating Reward Hacking in RLHF via Information-Theoretic Reward Modelingcited by 79
  18. 2024Can large language models explore in-context?cited by 76
  19. 2023A Survey of Temporal Credit Assignment in Deep Reinforcement Learningcited by 59
  20. 2025Satori: Reinforcement Learning with Chain-of-Action-Thought Enhances LLM Reasoning via Autoregressive Searchcited by 53
  21. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  22. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  23. 2024Do LLM Agents Have Regret? A Case Study in Online Learning and Gamescited by 35
  24. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  25. 2024Optimal Design for Reward Modeling in RLHFcited by 25
  26. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  27. 2024Improving Reinforcement Learning from Human Feedback Using Contrastive Rewardscited by 23
  28. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  29. 2019Prediction with Expert Advice: a PDE Perspectivecited by 17
  30. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 17
  31. 2020Optimal anytime regret with two expertscited by 16
  32. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 15
  33. 2025Early External Safety Testing of OpenAI's o3-mini: Insights from the Pre-Deployment Evaluationcited by 13
  34. 2020A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Expertscited by 7
  35. 2020Malicious Experts versus the multiplicative weights algorithm in online predictioncited by 6
  36. 2023Comparison of viscosity solutions for a class of second order PDEs on the Wasserstein spacecited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Rewarding Structural Conformance of Reasoning using Process Mining
  2. 2025Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoning
  3. 2025Learn to Reason Efficiently with Adaptive Length-based Reward Shaping
  4. 2025Thinking Fast and Right: Balancing Accuracy and Reasoning Length with Adaptive Rewards
  5. 2026Stepwise Penalization for Length-Efficient Chain-of-Thought Reasoning
  6. 2026Beyond Penalizing Mistakes: Stabilizing Efficiency Training in Large Reasoning Models via Adaptive Correct-Only Rewards
  7. 2026ETR: Entropy Trend Reward for Efficient Chain-of-Thought Reasoning
  8. 2025Rethinking Reasoning Quality in Large Language Models through Enhanced Chain-of-Thought via RL