PaperlayerView exact revision on arXiv

Source-linked AI summary

RL of Thoughts: Navigating LLM Reasoning with Inference-time Reinforcement Learning

Qianyue Hao, Sibo Li, Jian Yuan, Yong Li

arXiv:2505.14140v3cs.AI

TL;DR

LLMs’ token-level autoregressive nature constrains complex reasoning, while existing inference-time logical structures are manually designed and task-agnostic. RLoT trains an RL navigator to adaptively select and combine logic blocks into task-specific structures; across benchmarks and LLMs, it outperforms established inference-time techniques by up to 13.4%.

  • Problem

    LLMs’ token-level autoregressive nature constrains complex reasoning, and existing inference-time techniques use manually designed, task-agnostic structures that lack adaptability across diverse tasks.

    Source: §1 · p. 1

  • Method

    RLoT trains a lightweight RL navigator to dynamically select and combine five human cognition-inspired logic blocks into task-specific reasoning structures.

    Source: §1 · p. 2

  • Results

    Across reasoning benchmarks and multiple LLMs, RLoT outperforms established inference-time techniques by up to 13.4%.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The navigator transfers across LLMs and unseen tasks, and with fewer than 3K parameters can help sub-10B LLMs attain performance comparable to models with up to 10 times the parameter size.

    Source: §1 · p. 2, §6 · p. 10

Abstract

from arXiv · show

Despite rapid advancements in large language models (LLMs), the token-level autoregressive nature constrains their complex reasoning capabilities. To enhance LLM reasoning, inference-time techniques, including Chain/Tree/Graph-of-Thought(s), successfully improve the performance, as they are fairly cost-effective by guiding reasoning through sophisticated logical structures without modifying LLMs' parameters. However, these manually predefined, task-agnostic frameworks are applied uniformly across diverse tasks, lacking adaptability. To improve this, we propose RL-of-Thoughts (RLoT), where we train a lightweight navigator model with reinforcement learning (RL) to adaptively enhance LLM reasoning at inference time. Specifically, we design five basic logic blocks from the perspective of human cognition. During the reasoning process, the trained RL navigator dynamically selects the suitable logic blocks and combines them into task-specific logical structures according to problem characteristics. Experiments across multiple reasoning benchmarks (AIME, MATH, GPQA, etc.) with multiple LLMs (GPT, Llama, Qwen, and DeepSeek) illustrate that RLoT outperforms established inference-time techniques by up to 13.4%. Remarkably, with less than 3K parameters, our RL navigator is able to make sub-10B LLMs comparable to 100B-scale counterparts. Moreover, the RL navigator demonstrates strong transferability: a model trained on one specific LLM-task pair can effectively generalize to unseen LLMs and tasks. Our code is open-source at https://github.com/tsinghua-fib-lab/RL-LLM-Reasoning for reproducibility.

1 INTRODUCTION

LLMs’ token-level autoregressive design limits complex reasoning, while existing inference-time logical structures are manually designed and task-agnostic. RLoT uses reinforcement learning to build task-specific structures, with reported gains across tasks and models, transferability, and parameter efficiency.

1 INTRODUCTION

  • LLMs’ token-level autoregressive nature limits complex reasoning that requires sophisticated logical structures and long-term dependencies.Fine-tuning can improve reasoning but requires substantial computational resources and large datasets; inference-time methods are lighter but use manually designed, task-agnostic structures.Source: §1 · p. 1
  • Reasoning tasks differ across domains and evolve over multiple steps, making fixed structures difficult to design for each task and adjust as problem-solving progresses.These challenges motivate more adaptive inference-time techniques.Source: §1 · pp. 1–2
  • RLoT trains an inference-time RL navigator to adaptively construct task-specific logical structures from five human cognition-inspired basic logic blocks.The navigator dynamically selects and combines blocks during reasoning.Source: §1 · p. 2
  • RLoT outperforms established inference-time techniques by up to 13.4% and works with multiple widely known LLMs.The navigator also transfers across LLMs and tasks; with fewer than 3K parameters, it helps sub-10B models reach performance comparable to counterparts with 10× more parameters.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries describe LLMs as next-token predictors and introduce the Markov Decision Process framework for sequential decisions and accumulated rewards.

2.1 LARGE LANGUAGE MODELS (LLMS)

  • LLMs are neural networks trained primarily through next-token prediction, outputting the next token given the preceding sequence to maximize corpus observation likelihood.Related work cited includes inference-time CoT and ToT methods and fine-tuning approaches using ORM and PRM.Source: §2.1 · p. 2

2.2 MARKOV DECISION PROCESS (MDP)

  • A Markov Decision Process is defined by state, initial-state distribution, action space, transition probabilities, and reward function for sequential decisions.At each step, an agent selects an action in its state, receives a reward, and transitions to a new state.Source: §2.2 · p. 3
  • The MDP objective is to maximize accumulated discounted rewards, with the discount factor weighting future rewards.The cumulative reward at time t sums rewards from that step onward, discounted by powers of γ.Source: §2.2 · p. 3

3 METHODS

RLoT models long-sequence reasoning as an MDP and trains a navigator to construct task-specific logical structures. It uses self-evaluation to track reasoning state and selects among logic blocks as the process unfolds.

3.1 OVERVIEW

  • RLoT uses an RL navigator to dynamically select and combine logic blocks, constructing task-specific reasoning structures for LLMs.The sequence of navigator decisions corresponds to generating a logical structure for the task.Source: Figure 1 · p. 3, §3.1 · p. 3

3.2 LLM REASONING AS MDP

  • The MDP maps long-sequence reasoning to sequential decisions, with each episode’s action sequence generating a logical structure.Its design specifies states, actions, rewards, and transitions.Source: §3.2 · pp. 3–4
  • The state summarizes the current solving status through LLM self-evaluation of reasoning steps across three major and seven detailed aspects.Scores from 1 to 3 for each detailed aspect are aggregated into a low-dimensional state that supports subsequent strategy adjustment.Source: §3.2 · p. 4
  • Five flexible action blocks form the navigator’s action space: reason one step, decompose, debate, refine, and terminate.The blocks can be selected and cascaded to create reasoning pathways from the original problem to a final solution.Source: §3.2 · p. 4
  • A PRM scores intermediate results after each action to provide its single-step reward, while the next reasoning state comes from self-evaluation.Transitions prohibit further actions after an answer appears except termination; a first-step Refine becomes Reason one step, and a maximum action limit triggers termination.Source: §3.2 · pp. 4–5

3.3 TRAINING OF THE NAVIGATOR MODEL

  • Navigator training is a discrete-action RL problem and can use arbitrary off-the-shelf RL algorithms.For challenging tasks, training uses hard questions the LLM cannot answer when directly prompted, sampled and repeated across episodes.Source: §3.3 · p. 5
  • During training, pretrained LLM and PRM parameters remain fixed while only the navigator is updated; after training, the PRM is no longer needed.At inference, the navigator repeatedly selects actions from intermediate states to guide the LLM with task-specific logical structures.Source: §3.3 · p. 5

4 EXPERIMENTS

Across multiple LLMs and reasoning tasks, RLoT generally outperforms established inference-time baselines, with a reported 13.4% GPQA boost for Llama3.1-8B-Instruct. The experiments also examine model-size efficiency, transferability, generated reasoning patterns, and logic-block ablations.

4.1 EXPERIMENTAL SETTINGS

  • Evaluation spans math, STEM, and commonsense benchmarks using multiple LLMs and compares RLoT with single-round and multi-round inference-time baselines.The benchmarks include AIME24, AMC23, GSM8K, MATH, MMLU-STEM, GPQA, and StrategyQA; the baselines include Direct QA, CoT variants, CoT-SC, and ToT.Source: §4.1 · pp. 5–6

4.2 TRAINING DETAILS

  • The navigator is a 2,566-parameter, three-layer Dueling MLP trained for 3,000 episodes with Double-Dueling-DQN and Math-Shepherd rewards.Training uses Qwen2.5-14B-Instruct on MATH; the reported learning curves indicate strong convergence, and Math-Shepherd supplies process-reward signals.Source: §4.2 · p. 6, Figure 2 · p. 6

4.3 OVERALL PERFORMANCE

  • 13.4% performance boost on GPQA with Llama3.1-8B-Instruct; RLoT outperforms established inference-time baselines across almost all reasoning tasks and various LLMs.Table 2 reports overall performance; CoT-SC is the best baseline across most tasks, while ToT performs poorly on many.Source: §4.3 · pp. 6–7, Table 2 · p. 7

4.4 PARAMETER SIZE EFFICIENCY

  • With fewer than 3,000 navigator parameters, RLoT significantly enhances sub-10B LLMs, making them comparable to counterparts with around 10× more parameters.The comparisons use Few-shot CoT performance and report that enhanced models compensate for most of the performance gap or sometimes surpass larger counterparts.Source: §4.4 · p. 7

4.5 TRANSFERABILITY

  • Navigators trained on one LLM transfer to other LLMs on MATH, and enhanced models outperform the best-known inference-time baseline in all tested cases.The cross-tests use navigators trained with Qwen2.5-14B-Instruct, Llama3.1-8B-Instruct, and GPT-4o-mini.Source: §4.5 · p. 8, Table 3 · p. 8
  • Task transfer remains largely consistent across training and test tasks, surpassing the best-performing inference-time baseline in most cases, but transfer from StrategyQA is relatively limited.MATH- and GPQA-trained navigators transfer better to each other than StrategyQA-trained navigators do to those domains.Source: §4.5 · p. 8, Table 4 · p. 8

4.6 TYPICAL REASONING PATTERNS

  • Reason-Refine appears frequently in two-step patterns, while Decompose and Debate often appear in three-step patterns, with Refine used around them.The authors report that Reason-Refine compensates for weaker calculation abilities in MATH and GPQA, and that these patterns are interpretable.Source: §4.6 · p. 9, Table 5 · p. 9

4.7 ABLATION STUDIES, ANALYSES, AND DISCUSSIONS

  • Removing each logic block and retraining a navigator confirms that all blocks are effective.The paper also discusses block contributions, self-evaluation-state reliability, the necessity of RL, and the PRM’s role in training.Source: §4.7 · p. 9, Table 6 · p. 9

5 RELATED WORKS

Existing inference-time reasoning methods use fixed logical structures, while newer adaptive approaches can incur substantial search costs. RLoT applies RL to train a navigator that assembles task-specific structures, rather than updating each LLM’s parameters.

5.1 INFERENCE-TIME REASONING OF LLMS

  • CoT, CoT-SC, ToT, and GoT use task-agnostic structures across diverse tasks, limiting their flexibility (Wei et al., 2022; Wang et al., 2023; Yao et al., 2023; Besta et al., 2024).CoT-SC generates multiple reasoning chains and filters for self-consistency; ToT and GoT support exploration and backtracking.Source: §5.1 · p. 10
  • Adaptive approaches dynamically compose structures, but search-and-trial designs add computational cost; RLoT instead uses a trained navigator to select and combine logic blocks directly (Xue et al., 2024; Wu et al., 2024; Wang et al., 2024a).The cited adaptive approaches include a decompose-analyze-rethink procedure and Monte Carlo Tree Search.Source: §5.1 · p. 10

5.2 RL AND LLMS

  • RLHF aligns LLMs using human-preference feedback, while outcome and process reward models provide signals for RL-based reasoning fine-tuning (Christiano et al., 2017; Ouyang et al., 2022; Kazemnejad et al., 2024; Lightman et al., 2023).These approaches update LLM parameters, and applying fine-tuning to each pretrained model demands substantial computational resources.Source: §5.2 · p. 10
  • RLoT trains a lightweight navigator with RL at inference time rather than fine-tuning the full LLM, supporting low-cost use across pretrained models.The navigator constructs task-specific logical structures by selecting and combining basic logic blocks.Source: §5.2 · p. 10

6 CONCLUSIONS

RLoT uses inference-time RL to train a navigator that constructs task-specific reasoning structures. Experiments report improved reasoning across LLMs and benchmarks, transfer to unseen tasks and models, and comparable performance for sub-10B models with a navigator under 3K parameters.

6 CONCLUSIONS

  • RLoT trains an inference-time RL navigator to adaptively construct task-specific logical structures and enhance LLM reasoning.The conclusion presents experiments across various benchmarks and widely known LLMs.Source: §6 · p. 10
  • The trained navigator transfers across different LLMs and unseen reasoning tasks.The conclusion also reports that RLoT improves reasoning capability across various benchmarks and widely known LLMs.Source: §6 · p. 10
  • With fewer than 3K parameters, the navigator enables multiple sub-10B LLMs to attain performance comparable to larger models with up to 10 times the parameter size.Source: §6 · p. 10

ETHICS STATEMENT

The statement reports that the study uses open-source or publicly available models and datasets under their respective licenses. The appendix reports convergence of navigator training and analyzes training duration and algorithm choice.

ETHICS STATEMENT

  • The study reports using open-source or publicly available models and datasets under their respective licenses, with resources cited in Sections 1 and 4.It describes the selected datasets and models as well-established, representative, and free from bias or discrimination.Source: ETHICS STATEMENT · p. 11

A.1 LEARNING CURVES

A.2 ANALYSIS

Training curves indicate convergence around 3,000 episodes, with only marginal gains afterward; Double-DQN ultimately reaches performance comparable to Double-Dueling-DQN. A MATH case study contrasts Few-shot CoT’s incorrect geometry with RLoT’s refinement and plan selection.

A.2 ANALYSIS

  • Around 3,000 episodes, the navigator essentially converges, with only marginal gains through 5,000; Double-DQN is slightly less stable but ultimately reaches comparable performance to Double-Dueling-DQN.Source: §A.2 · p. 17, Figure 4 · p. 17

B.1 CORRECT CASES

  • RLoT’s case-study pathway combines Reason-Refine-Debate: Refine clarifies intermediate results, and Debate favors the rhombus area formula over dividing it into triangles.Source: §B.1 · p. 18
  • In the representative MATH case, Few-shot CoT misidentifies the shaded region’s shape and gives an incorrect result, whereas RLoT identifies it as a rhombus and answers correctly.Source: §B.1 · p. 18, Figure 5 · p. 18

B.2 FAILURE CASES

RLoT failures stem from noisy state self-evaluation or suboptimal action selection. The examples show how either can divert otherwise stepwise reasoning, although the authors report these cases are a minority of inference trajectories.

B.2 FAILURE CASES

  • Failures arise from both noisy self-evaluation and suboptimal action selection, with noise steering the navigator away from needed refinement.In the example, an incorrect equation is rated “True,” leading the navigator to choose Debate instead of Refine.Source: §B.2 · p. 18
  • With accurate state information, an unnecessary Refine action can replace a correct intermediate result with an erroneous identity.This over-correction causes the solution to fail.Source: §B.2 · p. 19
  • The authors report that these failure cases are a minority of inference trajectories and that RL training and structured self-evaluation are designed to mitigate them.RL training targets action-selection errors, while the structured prompt aims to reduce state-noise errors.Source: §B.2 · p. 19

C COMPUTATIONAL OVERHEAD AND LATENCY

RLoT-enhanced sub-10B models are reported as comparable to counterparts with roughly 10× more parameters. The navigator also reduces inference-time token use relative to ToT, while its training cost is shared across test questions.

C COMPUTATIONAL OVERHEAD AND LATENCY

D PERFORMANCE COMPARISON WITH LARGER LLMS

E.1 TEST-TIME SCALING BASELINES

Across the reported baseline comparisons, RLoT outperforms test-time scaling methods on representative datasets and inference-time math baselines. The appendices also examine self-evaluation reliability, sensitivity to noisy states, and alternative evaluation designs.

E.1 TEST-TIME SCALING BASELINES

  • RLoT outperforms all listed baseline methods on GSM8K, GPQA, and StrategyQA.The authors describe its task-specific logical trajectories as offering better performance at similar or lower cost than search-based methods.Source: §E.1 · p. 22, Table 10 · p. 23

E.2 MATH DOMAIN BASELINES

  • On MATH and GSM8K, RLoT outperforms all inference-time baselines and reaches performance comparable to some fine-tuning methods with substantially lower computational consumption.The comparison uses Llama3.1-8B-Instruct; baseline scores are taken from the original papers.Source: Table 12 · p. 24, §E.2 · p. 24

F.1 RELIABILITY

  • The LLM’s self-assessments were accurate in 82 of 100 sampled intermediate reasoning texts, and it identified and classified deliberately introduced modeling and calculation errors.The authors regard the validation as support for using self-evaluation to extract navigator states.Source: Table 13 · p. 25, §F.1 · p. 25

F.2 NOISE IMPACT

  • With 50% state noise, RLoT averages 64.99% accuracy; with 30% noise, it reaches 69.11%.Replacing state vectors with random values drops performance below DirectQA; the authors use binary rather than fine-grained self-evaluation to reduce calibration demands.Source: §F.2 · p. 25, Table 14 · p. 26

F.3 ALTERNATIVE DESIGNS

  • The fixed LLM self-evaluation performs badly and the fine-tuned LLM alternative performs worse; the authors attribute their design’s advantage to explicit structured evaluation at low cost.The fine-tuned alternative evaluates raw text implicitly, which the authors describe as more complex and requiring more parameters to tune.Source: Table 15 · p. 26, §F.3 · p. 26

G ANALYSES ON THE ROLE OF RL IN TRAINING THE NAVIGATOR

The analyses report that RL-based navigation outperforms alternative decision methods, while PRM rewards outperform ORM rewards. They also examine PRM transfer across domains, reward quality, and the effect of using longer logic-block sequences.

G ANALYSES ON THE ROLE OF RL IN TRAINING THE NAVIGATOR

H.1 THE ROLE OF PRM

  • Using a PRM to train the navigator outperforms using an ORM, which the authors say indicates the importance of step-level reward signals.Source: Table 17 · p. 28, §H.1 · p. 28

H.2 GENERALIZATION CAPABILITY OF PRM

  • Intermediate PRM scores correlate positively with final-answer correctness across tested benchmarks, including out-of-domain GPQA and StrategyQA.The authors say the math-trained PRM’s feedback on these tasks helps explain the navigator’s transferability.Source: Table 18 · p. 28, §H.2 · p. 28

H.3 IMPACT OF PRM QUALITY

  • Higher-quality PRMs benefit the navigator, but a lower-quality PRM remains beneficial when its reward signal is directionally meaningful.Source: §H.3 · p. 28, Table 19 · p. 29

I.1 EFFECT OF LOGIC BLOCK NUMBER

I.2 ROLE OF DIFFERENT LOGIC BLOCKS ON DIFFERENT DATASETS

This section examines how the usefulness of logic blocks varies by task and evaluates additional blocks, while documenting the navigator’s implementation and prompts and reporting performance after prompt rephrasing. It also records the role of LLMs in writing and literature retrieval and the authors’ role in research ideation.

I.2 ROLE OF DIFFERENT LOGIC BLOCKS ON DIFFERENT DATASETS

  • Debate is most useful for math, Decompose for STEM, and Refine for common-sense reasoning, based on average PRM reward gain.Figure 9 reports the contribution of each logic block in the reasoning sequence.Source: Figure 9 · p. 30, §I.2 · p. 30

I.3 ALTERNATIVE BLOCKS

  • Rephrasing is beneficial, whereas Follow-up-question and Compression are not; the authors present additional blocks as an extensibility path for RLoT.Follow-up-question proposes and answers a sub-question; Rephrasing reorganizes reasoning; Compression condenses it.Source: Table 20 · p. 30, §I.3 · pp. 30–31

J.1 SETTINGS

  • The appendix provides implementation settings in Table 21, illustrates the full pipeline, and describes prompt-template conventions for problem-specific content.Text in braces denotes problem-specific content, while the remaining prompt text is fixed.Source: Table 21 · p. 32, §J.1 · p. 32, §J.2 · p. 32

1 DATA CONSTRUCTION

  • Navigator training uses hard problems that Qwen2.5-14B-Instruct answers incorrectly under direct prompting, and trains from individual questions rather than supervised input-output pairs.The question outputs are evaluated to generate rewards, which are fed back into training.Source: §1 · p. 32

2 STATE SELF-EVALUATION (STATE SPACE)

  • A prompted LLM self-evaluation compresses the problem and current reasoning into a 7-aspect state vector for more tractable policy learning.The evaluation scores aspects of correctness, complexity, and completeness.Source: §2 · p. 33, §K.1 · p. 36

5 DEFINITION OF MDP

  • The MDP uses the self-evaluated vector as its state, one of five logic blocks as its action, and a PRM score of reasoning-step quality as its reward.The blocks draw on cognitive strategies and are operationalized as prompts with a shared problem-and-reasoning input and new-reasoning output.Source: §4 · p. 33, §3 · p. 33, §5 · p. 34

6 TRAINING PROCESS

  • The navigator is trained with Deep Q-Learning by repeatedly selecting a block from the current state, extending reasoning, and using the PRM reward to update its MLP.At inference, it repeats the state-action-reasoning loop until an answer is reached, then applies self-consistency to select a final answer.Source: §6 · p. 34, §7 · p. 34, §8 · p. 34

K.2 PROMPTS FOR ACTIONS

  • Action prompts constrain Reason one step to a single step, Decompose to breaking down and executing subtasks, and Debate to generating, comparing, and advancing a selected plan.Decompose summarizes subtask results, while Debate retains the final one-step reasoning for subsequent actions.Source: §K.2 · pp. 36–37
  • Action prompts direct the LLM to take one planned reasoning step, refine existing reasoning for clarity and correctness, or terminate by producing a dataset-formatted answer.The terminate prompt’s output format varies according to dataset requirements.Source: §K.2 · p. 38

K.3 SENSITIVE TO ACTION-PROMPTS PHRASING.

  • Rephrased action prompts yield average accuracy very similar to the original, which the authors attribute to adaptive logical structures rather than prompt-specific overfitting.The authors describe RLoT as robust to prompt variations and not reliant on extensive prompt engineering.Source: Table 23 · p. 40, §K.3 · p. 40

L USE OF LLMS

  • The authors report using LLMs to aid or polish writing and retrieve literature, while stating that the research ideation was completed entirely by the authors.They say all content and related work were reviewed by the authors.Source: L USE OF LLMS · p. 41
Loading 2505.14140v3…