Procedural Knowledge at Scale Improves Reasoning

1. Problem Statement

Current test-time scaling methods for Large Language Models (LLMs) improve reasoning performance by allocating more compute per instance (e.g., generating longer chains of thought or sampling multiple trajectories). However, these methods suffer from two critical limitations:

• Isolation: They treat each problem instance in isolation, failing to reuse knowledge from prior reasoning trajectories.
• Underutilization of Procedural Knowledge: Existing Retrieval-Augmented Generation (RAG) systems primarily retrieve factual knowledge (definitions, formulas) or full reasoning trajectories. They fail to explicitly retrieve procedural knowledge: the high-level strategies on how to reframe a problem, decompose it into subquestions, choose an approach, or verify/backtrack.
• Misalignment: Standard document-level RAG often provides generic background context that is weakly aligned with the model's current reasoning state, leading to limited gains or even performance degradation in reasoning models.

2. Methodology: Reasoning Memory

The authors propose Reasoning Memory, a RAG framework designed to explicitly retrieve and reuse procedural knowledge at scale during inference. The framework consists of three main stages:

A. Procedural Knowledge Datastore Construction

Instead of indexing raw documents or full trajectories, the authors decompose existing reasoning corpora into atomic, reusable units.

• Source: They utilize the Nemotron V1 corpus (containing math, science, and coding trajectories) to build a datastore of 32 million entries.
• Decomposition: Each reasoning trajectory is processed by a teacher model (QwQ-32B) to extract:
  1. Subquestions (SQ): Self-contained descriptions of intermediate goals (e.g., "How to convert a number from base $b$ to decimal?").
  2. Subroutines (SR): Concise, high-level procedural hints describing the strategy to solve the subquestion, abstracting away specific numbers or local calculations.
• Result: A massive datastore of $(SQ, SR)$ pairs that serve as compact procedural priors.

B. In-Thought Active Retrieval

At inference time, the model is guided to retrieve relevant procedures within its own reasoning trace.

• Query Verbalization: A lightweight "thought-hijacking" prompt encourages the model to verbalize its current subquestion as a natural language query (e.g., "Let me frame a search query for a similar basic problem...").
• Retrieval: The model's generated query is used to retrieve the top-$k$ matching subroutines from the datastore using a dense retriever (ReasonIR-8B).
• Injection: The retrieved subroutines are injected directly into the reasoning stream as hints (e.g., [hint] Here is a problem solving procedure...). This acts as an implicit prior, guiding the model's subsequent reasoning steps.

C. Test-Time Scaling with Diversity

The framework scales inference compute by exploring multiple reasoning paths under diverse retrieved procedures.

• Sampling: Given a budget of $m$ samples and $k$ retrieved subroutines, the model generates $\lfloor m/k \rfloor$ trajectories for each subroutine.
• Filtering: A length-based uncertainty heuristic is used to filter candidates. The intuition is that confident reasoning tends to produce shorter, more direct traces, while uncertain reasoning leads to excessive backtracking and longer traces.
• Selection: The system retains the top-$n$ highest-confidence trajectories (shortest normalized lengths) for the final answer.

3. Key Contributions

1. Procedural Knowledge at Scale: The creation of a 32-million-entry datastore of decomposed subquestion-subroutine pairs, shifting the focus from factual retrieval to strategic guidance.
2. In-Thought Retrieval Mechanism: A novel method for integrating retrieval directly into the model's "thinking" process via query verbalization, ensuring the retrieved knowledge is tightly aligned with the current reasoning state.
3. Diversity-First Scaling: A strategy that allocates compute budget across diverse retrieved procedures rather than deepening a single trajectory, demonstrating that exploring different strategies is more effective than simply thinking longer on one path.
4. Empirical Validation: Comprehensive evaluation showing that procedural retrieval outperforms document retrieval, full trajectory retrieval, and template-based approaches.

4. Experimental Results

The method was evaluated on frontier reasoning benchmarks across Math (AIME 2024/2025, MATH500), Science (GPQA-Diamond), and Coding (LiveCodeBench) using three open-weight reasoning models (DeepSeek-R1-Distill-Llama-8B, OpenThinker3-7B, Qwen3-32B).

• Performance Gains:
  • Reasoning Memory consistently outperforms No RAG by up to 19.2% (e.g., +19.0% on Math, +28.9% on Coding with larger budgets).
  • It outperforms the strongest compute-matched baseline (Length Scaling without retrieval) by 7.9% on average.
  • It significantly beats standard Document RAG (which often degrades reasoning model performance) and Trajectory RAG.
• Scaling Behavior:
  • Performance improves monotonically with larger inference budgets ($m$).
  • A Diversity-First strategy (using many different retrieved subroutines) yields better scaling than an Intensity-First strategy (focusing compute on few subroutines).
• Datastore Composition:
  • Larger and more diverse datastores yield better results.
  • Cross-domain transfer is effective; code-only or science-only subroutines often improve performance on math tasks, suggesting that procedural strategies are domain-agnostic.
• Ablation Studies:
  • Decomposition is Critical: Removing the subquestion decomposition (indexing by full questions) causes significant performance drops, proving that granular procedural matching is essential.
  • Query Generation: Self-verbalized queries outperform using the original problem statement as the query, as they better capture the specific reasoning bottleneck.
  • Model Size: The datastore generation model can be smaller (Qwen3-8B) with minimal performance loss, indicating the knowledge resides in the source trajectories.

5. Significance and Conclusion

This paper fundamentally shifts the paradigm of test-time scaling for reasoning models. It demonstrates that the bottleneck in complex reasoning is often not a lack of facts, but a lack of procedural guidance on how to approach a problem.

• Efficiency: By reusing structured procedural knowledge, models can solve problems more efficiently without needing to "rediscover" strategies from scratch.
• Generalizability: The approach is model-agnostic and works across different reasoning architectures and domains.
• Future Direction: It establishes a new direction for the RAG community: moving beyond factual retrieval to building systems that accumulate, retrieve, and reuse reasoning strategies and workflows over time.

In summary, Reasoning Memory proves that equipping reasoning models with a massive, structured library of "how-to" strategies significantly enhances their ability to solve complex math, science, and coding problems, outperforming both standard retrieval and brute-force test-time scaling.