PaperlayerView exact revision on arXiv

Source-linked AI summary

Can We Further Elicit Reasoning in LLMs? Critic-Guided Planning with Retrieval-Augmentation for Solving Challenging Tasks

Xingxuan Li, Weiwen Xu, Ruochen Zhao, Fangkai Jiao, Shafiq Joty, Lidong Bing

arXiv:2410.01428v1cs.CL

TL;DR

Challenging reasoning tasks can expose cascading reasoning errors and retrieval mistakes in existing methods. CR-Planner iteratively plans reasoning and retrieval with fine-tuned critics, trained using MCTS-collected trajectories. The paper reports a 10.06% average improvement over baselines across its challenging-task experiments.

  • Problem

    Existing methods often struggle with domain-knowledge-intensive, reasoning-heavy tasks, where flawed reasoning can cascade and misguide retrieval.

    Source: §1 · p. 2

  • Method

    CR-Planner iteratively selects reasoning, query generation, or retrieval sub-goals and uses fine-tuned critics to select actions and executions, with MCTS collecting training trajectories.

    Source: §1 · p. 2

  • Results

    CR-Planner outperforms baselines by 10.06% on average across competitive programming, math reasoning, and complex retrieval.

    Source: §1 · p. 3

  • Takeaways & Limitations

    CR-Planner does not require fine-tuning the base model and is described as applicable to open-source or closed-source models.

    Source: §4.2 · p. 9

    The evaluation excludes Self-RAG because its required base-model training was infeasible in this setup.

    Source: §3.2 · p. 7

Abstract

from arXiv · show

State-of-the-art large language models (LLMs) exhibit impressive problem-solving capabilities but may struggle with complex reasoning and factual correctness. Existing methods harness the strengths of chain-of-thought and retrieval-augmented generation (RAG) to decompose a complex problem into simpler steps and apply retrieval to improve factual correctness. These methods work well on straightforward reasoning tasks but often falter on challenging tasks such as competitive programming and mathematics, due to frequent reasoning errors and irrelevant knowledge retrieval. To address this, we introduce Critic-guided planning with Retrieval-augmentation, CR-Planner, a novel framework that leverages fine-tuned critic models to guide both reasoning and retrieval processes through planning. CR-Planner solves a problem by iteratively selecting and executing sub-goals. Initially, it identifies the most promising sub-goal from reasoning, query generation, and retrieval, guided by rewards given by a critic model named sub-goal critic. It then executes this sub-goal through sampling and selecting the optimal output based on evaluations from another critic model named execution critic. This iterative process, informed by retrieved information and critic models, enables CR-Planner to effectively navigate the solution space towards the final answer. We employ Monte Carlo Tree Search to collect the data for training the critic models, allowing for a systematic exploration of action sequences and their long-term impacts. We validate CR-Planner on challenging domain-knowledge-intensive and reasoning-heavy tasks, including competitive programming, theorem-driven math reasoning, and complex domain retrieval problems. Our experiments demonstrate that CR-Planner significantly outperforms baselines, highlighting its effectiveness in addressing challenging problems by improving both reasoning and retrieval.

1 INTRODUCTION

Existing CoT and retrieval-augmented methods can falter on challenging tasks when reasoning errors cascade and retrieval is misdirected. CR-Planner uses fine-tuned critics to plan both reasoning and retrieval, and the paper reports improved performance across challenging domains.

1 INTRODUCTION

  • Existing methods often handle relatively simple reasoning, but challenging tasks can suffer cascading reasoning errors and retrieval of misinformation.A flawed reasoning step can misguide query generation, while erroneous document selection can ground later reasoning in the wrong information.Source: §1 · p. 2
  • CR-Planner iteratively selects among REASON, GENQUERY, and RETRIEVE, then uses an execution critic to choose among sampled outputs.A sub-goal critic scores the action choice; an execution critic selects a candidate execution such as a rationale or search query.Source: §1 · pp. 2–3
  • A large generator produces candidate executions, while smaller domain-fine-tuned critics evaluate them and guide planning.The paper describes this division as combining generalist generation strengths with critics that are easier to train on domain-specific critiquing knowledge.Source: §1 · p. 3
  • MCTS collects critic-training trajectories by estimating long-term rewards from simulated outcomes and propagating them back to earlier steps.The paper motivates this approach by the limited availability and high human-annotation costs of step-wise reward data.Source: §1 · p. 3
  • CR-Planner outperforms baselines by 10.06% on average across competitive programming, math reasoning, and complex retrieval.The paper reports this average improvement across its challenging-task experiments.Source: §1 · p. 3

2 CRITIC-GUIDED PLANNING WITH RETRIEVAL-AUGMENTATION

CR-Planner treats reasoning and retrieval as an iterative planning problem, using specialized critics to select sub-goals and their executions. MCTS supplies training data for the critics by exploring trajectories and their longer-term rewards.

2 CRITIC-GUIDED PLANNING WITH RETRIEVAL-AUGMENTATION

  • CR-Planner alternates between choosing a reasoning, query-generation, or retrieval sub-goal and selecting its best execution with specialized critics.A general generator proposes plans, while the critics guide routing and execution selection.Source: §2 · p. 3

2.1 PROBLEM FORMULATION

  • The planning environment is an MDP whose state records the action-observation history and whose transitions produce rationales, queries, documents, or predefined sub-goals.Fine-tuned critics estimate rewards for actions, and the plan seeks a trajectory that maximizes total expected reward.Source: §2.1 · pp. 3–4

2.2 INFERENCE OF CR-PLANNER

  • At each step, critics assess available actions by expected reward, guiding whether to reason, generate a query, retrieve information, or select an execution.The process ends when an observation contains the answer or, at the step limit, an LLM is prompted to conclude.Source: §2.2 · p. 5
  • State transitions use a generator for rationales or queries, a retriever for documents, and a rule-based function for sub-goals.The generator produces RATIONALE or QUERY outcomes; the retriever produces DOC, while the rule-based function outputs a predefined natural-language SUBGOAL.Source: §2.2 · p. 5

2.3 THE CRITIC MODELS

  • MCTS collects critic-training trajectories by balancing exploration and exploitation, simulating candidate paths to terminal answers, and backpropagating their outcomes.It forms pairwise examples from higher- and lower-scoring observations that share a parent node.Source: §2.3 · pp. 5–6
  • Critics are trained separately with pairwise ranking loss, and execution examples use preceding trajectory observations as context for evaluation.Rationale candidates are evaluated with prior rationales, query candidates with the preceding rationale, and document candidates with the preceding rationale and query.Source: §2.3 · p. 6

3 EXPERIMENTS

The experiments evaluate CR-Planner on competitive programming, theorem-driven math, and complex domain retrieval, using comparisons with prompting and retrieval-based baselines.

3.1 SETUP

  • The setup uses GPT-4 for generation and fine-tuned Skywork-Reward-Llama-3.1-8B critics; methods are zero-shot by default, and Self-RAG is excluded because base-model training was infeasible.The experiments compare standard prompting, CoT, Reflexion, RAG, and CoK.Source: §3.1 · pp. 6–7, §3.2 · p. 7

3.2 COMPETITIVE PROGRAMMING

  • CR-Planner improved overall USACO performance by 7.49% over standard prompting and improved performance by 9.44% when combined orthogonally with Reflexion.Table 1 reports Pass@1 on USACO.Source: §3.2 · pp. 7–8, Table 1 · p. 7

3.3 THEOREM-DRIVEN MATH PROBLEMS

  • On TheoremQA-Math, CR-Planner improved accuracy by 13.59% over standard prompting, while standard RAG and CoK also improved performance.The authors attribute retrieval methods’ gains to shorter retrieved math documents, which are easier for the model to assess.Source: §3.3 · p. 8, Table 2 · p. 8

3.4 REASONING-HEAVY DOMAIN RETRIEVAL

  • On StackBio and StackEcon, CR-Planner improved over BM25 by 10.31% and 7.9%, respectively.CoK improved on BM25 but did not consistently outperform CoT; the authors cite potential noise from multiple suboptimal retrieval results.Source: Table 3 · p. 8, §3.4 · p. 9

4 ANALYSIS

The analysis finds that fine-tuned critics outperform GPT-4 critics, CR-Planner gains vary across base models, retrieval helps when accurate, and execution-sampling gains level off near three candidates.

4.1 DOMAIN-SPECIFIC CRITIC MODELS

  • Fine-tuned critics consistently outperform GPT-4 critics, with larger gains on domain-knowledge-intensive StackBio than on USACO.GPT-4 critics improve over the baseline, but do not match the fine-tuned critics.Source: Figure 3 · p. 9, §4.1 · p. 9

4.2 FLEXIBILITY OF CRITIC MODELS ON VARIOUS BASE MODELS

  • 7.49% for GPT-4 exceeded CR-Planner’s 4.56% improvement for Claude-3.5 and 2.61% for Llama-3.1.The authors attribute the smaller gains on other models partly to critics trained on GPT-4-collected data; CR-Planner does not require fine-tuning the base model.Source: Table 4 · p. 9, §4.2 · p. 9

4.3 RETRIEVE OR NOT TO RETRIEVE

  • Without retrieval, performance is lower, while inaccurate retrieval could also impair performance.The comparison emphasizes the importance of accurate retrieval in CR-Planner.Source: Table 5 · p. 9, §4.3 · p. 10

4.4 EXECUTION SAMPLING

  • On USACO, execution-sampling gains are substantial from one to two candidates but converge around three, the selected inference setting.The authors cite generator reasoning limits and retriever accuracy as constraints on further gains, and do not ablate training-phase sampling because of cost.Source: §4.4 · p. 10

5 RELATED WORK

Related work develops reasoning through stepwise prompting and process supervision, and improves retrieval through specialized subtasks; CR-Planner instead trains critics to guide planning across actions.

Reasoning methods

  • Chain-of-Thought prompting elicits stepwise reasoning, while Tree-of-Thought structures multiple thought paths and lets LLMs self-evaluate their next course.The passage cites Wei et al. (2022) for CoT and Yao et al. (2023a) for Tree-of-Thought.Source: §5 · p. 10

Process supervision

  • Process-supervision methods guide reasoning with future-reward estimates or ranked trajectories, but DPO-based tuning requires training the base model.RAP estimates future rewards with a world model; Jiao et al. (2024) learn from ranked trajectories, with tuned 7B models reported to surpass GPT-3.5-Turbo.Source: §5 · p. 10

Retrieval-augmented generation

  • RAG methods optimize pre-retrieval analysis, query generation, or document selection separately, whereas CR-Planner learns rewards for individual actions based on overall performance.The passage gives Self-ask, Chain of Knowledge, and RePlug as examples of locally optimized subtasks.Source: §5 · p. 10

6 CONCLUSIONS

The conclusion presents CR-Planner as a flexible framework for challenging tasks that combines fine-tuned critics for reasoning and retrieval with MCTS-based critic-data collection.

6 CONCLUSIONS

  • CR-Planner combines fine-tuned critics that guide reasoning and retrieval with MCTS for systematic critic-training data collection, and reports substantial improvements across competitive programming, math reasoning, and complex domain retrieval.The conclusion describes the framework as flexible and scalable for problems requiring intricate reasoning and accurate knowledge retrieval.Source: §6 · p. 11

A PROMPTS USED IN DIFFERENT METHODS

The appendix prompts specify staged solution instructions, available sub-goals, and formats for generating rationale and query candidates.

A.1.1 INSTRUCTION

  • The general instruction asks for a plain-English restatement and solution concept, pseudocode, and one Python 3 code block without outside libraries.It requires the full solution to appear in exactly one code block.Source: §A.1.1 · p. 14

A.1.2 SUBGOAL SELECTION

  • Sub-goal selection offers REASON as the action for providing a reasoning step.Source: §A.1.2 · p. 14
  • The available actions also include GENQUERY for generating an external-knowledge query and RETRIEVE for fetching documents using it.Source: §A.1.2 · p. 14

A.1.3 EXECUTION SELECTION - RATIONALE SAMPLING

  • Rationale sampling reuses the staged plain-English, pseudocode, and Python 3 solution instruction.Source: §A.1.3 · p. 14
  • The rationale-sampling prompt requests exactly one next reasoning step, delimited by BEGIN REASON and END REASON, and forbids subsequent steps.Source: §A.1.3 · p. 14

A.1.4 EXECUTION SELECTION - QUERY SAMPLING

  • Query sampling asks for a conceptual, relevant query without specific numbers or entities from the reasoning step, delimited by BEGIN QUERY and END QUERY.Source: §A.1.4 · p. 14

A.2 COT

The prompt specifies a stepwise solution format, from plain-English restatement through pseudocode to a Python 3 implementation.

A.2 COT

  • The prompt requests a plain-English restatement, conceptual solution, pseudocode, and one complete Python 3 code block without outside libraries.It also asks the model to reason step by step.Source: §A.2 · p. 15

A.3 CHAIN-OF-KNOWLEDGE

These prompts specify how to generate an initial rationale, correct a rationale using external knowledge, and generate a next rationale. The next-rationale template marks preceding rationales with start and end delimiters.

A.3.1 REASONING GENERATION

  • The reasoning-generation prompt requests a stepwise explanation, pseudocode, and a complete Python 3 solution without outside libraries.It asks for a plain-English restatement and conceptual solution before the code.Source: §A.3.1 · p. 15

A.3.2 RATIONALE CORRECTION

  • The rationale-correction prompt instructs the model to correct a sentence using external knowledge and provides a template for the sentence, knowledge, and edited sentence.Source: §A.3.2 · p. 15

A.3.3 NEXT RATIONALE GENERATION

  • The next-rationale prompt requests a stepwise solution and brackets preceding rationales with explicit start and end markers.Source: §A.3.3 · p. 15

A.4 REFLEXION

The Reflexion prompts describe code revision using a prior function implementation, unit-test results, and self-reflection. Separate templates identify Actor and Self-Reflection generations.

A.4.1 ACTOR

  • The Actor prompt asks a Python writing assistant to revise a prior function using unit-test results and self-reflection, returning only the improved function body.The response should omit the signature and begin with four spaces of indentation.Source: §A.4.1 · p. 16

A.4.2 SELF-REFLECTION

  • The Self-Reflection prompt likewise frames revisions around a prior function, test results, and self-reflection, and labels the generation as Self-Reflection.Source: §A.4.2 · p. 16

B A RUNNING EXAMPLE

The running example applies CR-Planner to finding the longest substring without repeated characters. It illustrates repeated choices among reasoning, query generation, retrieval, and candidate executions.

B A RUNNING EXAMPLE

  • The example problem is to find the longest substring without repeated characters in optimal time complexity.Source: B A RUNNING EXAMPLE · p. 16
  • The sequence compares rationale candidates at O(n2), O(n), and O(n3), offers three substring-search queries, then retrieves documents with examples and O(n) pointer and sliding-window guidance.Source: B A RUNNING EXAMPLE · pp. 16–17
  • Step 7 again offers REASON, GENQUERY, and RETRIEVE, while Step 8 contrasts an insufficient-document rationale with a sliding-window solution and code.Source: B A RUNNING EXAMPLE · p. 17
  • Steps 9–10 continue sub-goal and execution selection, with a candidate plan tracking character positions and moving the window boundary past repeats.Source: B A RUNNING EXAMPLE · pp. 17–18

C CR-PLANNER STATE TYPES AND ACTION SPACES

This section points to Table 6 for detailed information on CR-Planner’s state types and action spaces.

C CR-PLANNER STATE TYPES AND ACTION SPACES

Loading 2410.01428v1…