Can Past Experience Accelerate LLM Reasoning?

Bo Pan, Liang ZhaoarXiv 2025 · DOI · arXiv

Abstract

Current Large Language Model (LLM) reasoning relies heavily on test-time scaling, which incurs significant computational costs. This paper introduces SpeedupLLM, a framework that enables LLMs to achieve "reasoning speedup" by leveraging past experiences to solve future problems more efficiently. By integrating adaptive compute allocation with diverse memory mechanisms, the framework achieves up to a 56% reduction in compute costs while simultaneously improving accuracy. Our findings suggest a synergistic relationship between speed and correctness, where experience allows models to reach quality thresholds faster and more reliably.

1. Introduction

While "test-time scaling" methods like Chain-of-Thought (CoT) have set new benchmarks for complex problem-solving, they are fundamentally inefficient. Current systems treat every prompt as an isolated event and typically employ static compute budgets, such as a fixed "Best-of-N" sample count. In contrast, human cognition exhibits reasoning speedup: as we gain proficiency in a domain, we solve familiar problems with increasing speed and less effort. This research explores whether LLMs can emulate this behavior by using memory of past successes to reduce the computational overhead of future reasoning tasks.

2. The SpeedupLLM Framework

SpeedupLLM is built upon two primary pillars:

2.1 Adaptive Compute Budget Allocation

Rather than generating a fixed number of responses, SpeedupLLM uses an evaluation function (e.g., an LLM judge or reward model) to score candidate answers. The process "early-stops" as soon as a candidate exceeds a predefined quality threshold ($\tau$). This allows the system to save compute when a correct answer is found early in the search process.

2.2 Memory Mechanisms

The framework benchmarks five distinct methods for retaining experience:

  • Parametric (SFT): Fine-tuning the model on its successful trajectories.
  • In-Context Learning (ICL): Including previous successful examples in the prompt (episodic memory).
  • Reflection-based Methods: Using the model to generate high-level rules or iteratively update a "running reflection" of strategies (semantic memory).

3. Experimental Setup

The authors evaluated the framework using a specialized dataset derived from the MATH dataset. To measure the impact of experience, they created variations of "backbone" questions across four similarity levels:

  • S1 (Identical): Exact matches.
  • S2 (Rephrased): Semantic variations with identical logic and numbers.
  • S3 (Structural): Identical logic but different numerical values.
  • S4 (Conceptual): Shared underlying knowledge with different structures.

4. Results and Analysis

4.1 The Speed-Accuracy Synergy

A key finding of this study is the strong negative correlation (-0.41) between compute budget and accuracy. As models gain experience, they not only become more accurate but also reach the required quality threshold significantly faster.

Heatmaps of percentage change in compute budget (left) and accuracy (right) across memory mechanisms and search strategies.

As shown in the heatmaps above, the In-Context Learning mechanism combined with Depth-First Search (DFS) proved exceptionally effective, yielding a 56% reduction in compute for structurally similar (S3) tasks.

4.2 Temporal Dynamics of Experience

Reasoning speedup is a dynamic process. The effectiveness of memory mechanisms generally improves as the model encounters more questions within a specific category.

Compute budget and accuracy trends across sequential question indices, demonstrating the progression of reasoning speedup.

The longitudinal data indicates that episodic memory (ICL) provides rapid initial gains but is eventually constrained by the context window. Conversely, parametric memory (SFT) shows more consistent long-term efficiency improvements. However, at low similarity levels (S4), memory can occasionally introduce interference, leading to increased compute or reduced accuracy.

5. Conclusion

SpeedupLLM demonstrates that LLMs can indeed "learn to reason faster." By combining adaptive stopping with memory, we can transition from static, expensive inference to a more human-like, efficient reasoning paradigm. Future work will focus on optimizing memory formats to overcome context limitations and refining reflection strategies to better balance specificity and generalizability.

Summary updated

BibTeX
@misc{pan2025can,
  author = {Bo Pan and Liang Zhao},
  title = {{Can Past Experience Accelerate LLM Reasoning?}},
  year = {2025},
  eprint = {2505.20643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.20643},
}
Figure