PaperlayerView exact revision on arXiv

Source-linked AI summary

PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving

Mihir Parmar, Xin Liu, Palash Goyal, Yanfei Chen, Long Le, Swaroop Mishra, Hossein Mobahi, Jindong Gu, Zifeng Wang, Hootan Nakhost, Chitta Baral, Chen-Yu Lee, Tomas Pfister, Hamid Palangi

arXiv:2502.16111v1cs.AIcs.CL

TL;DR

Inference-time planning methods can struggle with weak verification and variation in instance complexity. PlanGEN combines constraint-guided verification with adaptive algorithm selection; it achieves state-of-the-art results across several benchmarks, including an ∼8%↑ average improvement on NATURAL PLAN.

  • Problem

    Inference-time methods for complex planning may lack constraint-aware verification and fail to adapt to instance-level complexity, while natural planning remains under-explored.

    Source: §1 · pp. 1–2

  • Method

    PlanGEN uses constraint and verification agents to improve Best of N, Tree-of-Thought, and REBASE, with a selection agent choosing algorithms based on instance complexity.

    Source: §1 · p. 2, §2.2.3 · p. 5

  • Results

    PlanGEN achieves state-of-the-art results across datasets, including an ∼8%↑ average across NATURAL PLAN categories.

    Source: §1 · p. 3, §5 · p. 11

  • Takeaways & Limitations

    PlanGEN’s Mixture of Algorithms performs best on complex problems, including GPQA and OlympiadBench MATH, while Best of N performs best on NATURAL PLAN.

    Source: §1 · p. 3

    Algorithm selection relies on predefined heuristics that may not generalize optimally across tasks and domains, and computational overhead remains an efficiency concern.

    Source: Limitations · p. 11

Abstract

from arXiv · show

Recent agent frameworks and inference-time algorithms often struggle with complex planning problems due to limitations in verifying generated plans or reasoning and varying complexity of instances within a single task. Many existing methods for these tasks either perform task-level verification without considering constraints or apply inference-time algorithms without adapting to instance-level complexity. To address these limitations, we propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents. Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms--Best of N, Tree-of-Thought, and REBASE. In PlanGEN framework, the selection agent optimizes algorithm choice based on instance complexity, ensuring better adaptability to complex planning problems. Experimental results demonstrate significant improvements over the strongest baseline across multiple benchmarks, achieving state-of-the-art results on NATURAL PLAN ($\sim$8%$\uparrow$), OlympiadBench ($\sim$4%$\uparrow$), DocFinQA ($\sim$7%$\uparrow$), and GPQA ($\sim$1%$\uparrow$). Our key finding highlights that constraint-guided iterative verification improves inference-time algorithms, and adaptive selection further boosts performance on complex planning and reasoning problems.

1. Introduction

The introduction identifies weak verification and limited adaptation to instance complexity as challenges for inference-time planning methods. It presents PlanGEN as a multi-agent framework for natural planning and downstream reasoning.

1. Introduction

  • The paper uses “planning” to mean decomposing tasks and reasoning strategically, aiming to improve natural plans for downstream scientific and financial reasoning.It contrasts natural planning with template-based approaches that may lack generalizability and miss real-world task nuances.Source: §1 · p. 1
  • Inference-time methods may struggle with complex planning because verification is insufficient and they do not account for instance-level complexity within a task.The introduction also notes that natural planning remains under-explored.Source: §1 · pp. 1–2
  • PlanGEN combines constraint, verification, and selection agents with Best of N, Tree-of-Thought, and REBASE inference algorithms.The introduction describes the framework as model-agnostic and scalable, with constraint-based verification and instance-complexity-based algorithm selection.Source: §1 · pp. 2–3
  • ∼8%↑ average across NATURAL PLAN categories, ∼5%↑ on OlympiadBench MATH, ∼4%↑ on OlympiadBench PHYSICS, and ∼7%↑ on DocFinQA are state-of-the-art results.The OlympiadBench results are for the text-only benchmark.Source: §1 · p. 3
  • On GPQA, PlanGEN outperforms Gemini-1.5-Pro by ∼13%↑, GPT-4o by ∼12%↑, and Claude-3.5-Opus by ∼9%↑, and is ∼1%↑ above the vanilla multi-agent baseline.PlanGEN (Best of N) performs best on NATURAL PLAN, while the Mixture of Algorithms performs best on complex problems including GPQA and OlympiadBench MATH.Source: §1 · p. 3

2. PlanGEN

PlanGEN uses specialized LLM agents to extract instance-specific constraints, assess plans, and select inference algorithms. Its frameworks apply these agents to Best of N, Tree-of-Thought, REBASE, or a mixture of algorithms.

2.1. Proposed LLM Agents

  • Each specialized agent uses an off-the-shelf LLM equipped with task-specific prompts.The paper gives Gemini and GPT as examples of underlying LLMs.Source: §2.1 · p. 3

2.1.1. Constraint Agent

  • The constraint agent extracts instance-specific criteria from a problem description to guide verification of generated plans.Examples include schedules, availabilities, and preferences for calendar planning, and concepts, calculation correctness, and formula selection for scientific reasoning.Source: §2.1.1 · p. 3

2.1.2. Verification Agent

  • The verification agent assesses plans against constraints, producing natural-language feedback and a reward score from −100 to 100; a score of 95 or higher exemplifies a verified, high-quality plan.The feedback is intended to be interpretable and to suggest next steps for improving a plan.Source: §2.1.2 · pp. 3–4

2.1.3. Selection Agent

  • A modified UCB policy selects algorithms using historical rewards, exploration, LLM-guided priors, diversity adjustments, and recovery scores.The priors reflect algorithm suitability for the problem and its instance complexity; their weight decays as trials accumulate.Source: §2.1.3 · p. 4

2.2. Proposed Frameworks

  • The framework section lists PlanGEN variants using Best of N, Tree-of-Thought, REBASE, and a Mixture of Algorithms.The mixture adds a selection agent to choose among inference-time algorithms.Source: §2.2 · p. 5

2.2.1. PlanGEN (Best of N)

Best of N

PlanGEN adapts inference-time planning algorithms through constraint-guided verification, with separate procedures for candidate selection, tree search, and complexity-based algorithm choice.

Best of N

  • Best of N generates and scores candidate plans against constraints, then selects the plan with the maximum reward.The verification agent assigns each plan a reward before selection.Source: Best of N · p. 5

2.2.2. PlanGEN (ToT)

  • Tree-of-Thought verifies steps against constraints, then repeatedly expands the most promising path until a valid solution or iteration limit.The method starts from a root problem node and generates multiple possible next steps.Source: §2.2.2 · p. 5

2.2.3. PlanGEN (REBASE)

  • REBASE ranks candidate nodes by verification rewards, limits lower-reward nodes to fewer children, and stops at a complete solution or depth or width limit.A completion check can terminate the search early once a satisfactory solution is identified.Source: §2.2.3 · p. 5

2.2.4. PlanGEN (Mixture of Algorithms)

  • The Mixture of Algorithms selects an inference-time algorithm using instance complexity and historical UCB values, then re-evaluates updated plans in a feedback loop.Initial plans that miss the acceptance threshold enter iterative refinement guided by verification feedback.Source: §2.2.4 · p. 6

3. Experiments and Results

Experiments compare PlanGEN frameworks with single-agent and multi-agent baselines across planning, scientific, mathematical, and financial tasks. The results report consistent baseline outperformance, with algorithm performance varying by task complexity.

3.1. Experimental Setup

  • Experiments use NATURAL PLAN, GPQA, OlympiadBench, and DocFinQA, comparing PlanGEN frameworks with Zero-shot CoT and a Vanilla Multi-Agent Baseline.Gemini-1.5-Pro is the underlying model; reasoning tasks use a plan-generation stage followed by plan execution.Source: §3.1 · p. 6, Figure 5 · p. 7

3.2. Main Results

  • Multi-agent frameworks consistently outperform the baselines across the reported benchmarks.Figure 5 compares proposed frameworks against baselines; experiments use Gemini-1.5-Pro.Source: Figure 5 · p. 7, §3.2 · p. 7
  • 60.70 (Calendar), 43.80 (Meeting), and 41.63 (Trip) are the highest NATURAL PLAN EM scores, all achieved by PlanGEN (Best of N).The frameworks establish state-of-the-art results in all three categories.Source: Figure 5 · p. 7, §3.2 · p. 7
  • 55.94% accuracy in OlympiadBench MATH is highest for PlanGEN (Mixture of Algo.), versus 50.68% for the Multi-Agent Baseline; Best of N leads PHY at 31.78%.In PHY, all multi-agent frameworks surpass Gemini-1.5-Flash, the strongest baseline.Source: Figure 5 · p. 7, §3.2 · p. 8
  • 59.6% accuracy on GPQA is highest for PlanGEN (Mixture of Algo.); on DocFinQA, Best of N leads with 31.16% accuracy and 29.45% F1-Score.All PlanGEN frameworks outperform the strongest DocFinQA baseline by approximately 7%.Source: §3.2 · p. 8
  • For calendar scheduling, ToT performs best on simple problems, Best of N on intermediate problems, and the Mixture of Algorithms as complexity increases.The comparison analyzes inference-time algorithms across complexity levels in NATURAL PLAN.Source: Figure 6 · p. 8, §3.2 · p. 8

4. Analysis and Discussion

The analysis examines verification, algorithm selection, model portability, and the LLM-call/performance trade-off. It reports a correlation between verification rewards and correctness, improvements with selection on NATURAL PLAN, and strong results across models and algorithms.

Importance of Verification Agent

  • Higher verification rewards correlate with higher success probability in a logistic regression analysis of approximately 1,100 DocFinQA and GPQA samples.The plotted points average correctness rates across reward-value buckets, each containing hundreds of samples.Source: Figure 7 · p. 9, §4 · p. 9

Importance of Selection Agent

  • On NATURAL PLAN, verification plus selection improves calendar scheduling to 59.3 EM and trip planning to 41.17 EM, compared with verification-only scores of 56.1 and 35.44 EM, respectively.Figure 8 compares Multi-Agent (Ver.) with Multi-Agent (Ver. + Selection).Source: Figure 8 · p. 9, §4 · p. 9

Model-Agnostic Nature

  • Across underlying models, PlanGEN frameworks report higher scores than the stated model baselines on calendar scheduling, OlympiadBench, and GPQA.Examples include PlanGEN (Best of N) at 68.90 EM versus Gemini-2.0-Flash at 61.10 EM on calendar scheduling, and Mixture of Algo. at 64.10 on MATH versus Gemini-2.0-Flash at 52.13.Source: Table 1 · p. 10, §4 · p. 10

Discussion on LLM calls vs. Performance (%)

  • PlanGEN (Mixture of Algo.) achieves the highest OlympiadBench (MATH) performance, while PlanGEN (ToT) and PlanGEN (REBASE) balance LLM-call efficiency and accuracy.The single-agent system has the lowest performance despite requiring one LLM call; the multi-agent baseline uses the same number of calls as PlanGEN (Best of N), which outperforms it.Source: Figure 9 · p. 10, §4 · p. 10

5. Conclusions

The conclusion presents PlanGEN as a scalable multi-agent approach that combines constraint, verification, and selection agents with inference algorithms. Evaluation across four benchmarks reports strong baseline comparisons and results across different LLMs.

5. Conclusions

  • PlanGEN combines constraint, verification, and selection agents to improve verification in Best of N, Tree-of-Thought, and REBASE frameworks.The conclusion also introduces Mixture of Algorithms, which uses the selection agent to dynamically choose an algorithm.Source: §5 · p. 11
  • The authors evaluate PlanGEN on NATURAL PLAN, OlympiadBench, GPQA, and DocFinQA and report state-of-the-art results across datasets.The conclusion also reports that PlanGEN outperforms strong baselines.Source: §5 · p. 11
  • The conclusion states that the frameworks are scalable and generalizable to different LLMs, improving natural-language planning ability.Source: §5 · p. 11

Limitations

The authors identify predefined selection heuristics and computational overhead as areas for improvement, and outline broader directions for future work.

Limitations

  • Algorithm selection relies on predefined heuristics that may not generalize optimally across all tasks and domains.Source: Limitations · p. 11
  • The frameworks' computational overhead remains an efficiency concern for real-world applications.Source: Limitations · p. 11
  • Future directions include adapting agent strategies with reinforcement or meta-learning, extending to multimodal and multilingual reasoning, and using generated planning trajectories for model training.Source: Limitations · p. 11

Ethics Statement

The ethics statement reports compliance with usage policies for proprietary LLMs and describes AI-assistant use for language editing.

Ethics Statement

  • The authors state that their use of proprietary LLMs, including GPT-4, Gemini, and Claude-3, adheres to the models' usage policies.Source: Ethics Statement · p. 11
  • Grammarly and Gemini were used to address grammatical errors and rephrase sentences.Source: Ethics Statement · p. 11

A. Related Works

Prior planning agents and inference-time algorithms leave gaps in generalizability and iterative plan verification. PlanGEN combines constraint-guided verification with multi-agent collaboration for natural-language planning and downstream reasoning.

A. Related Works

  • Prior planning agents often target domain-specific tasks or limited benchmarks and under-explore iterative plan verification and refinement.Natural-language planning work has also been single-agent or evaluated on domain-specific benchmarks.Source: A. Related Works · p. 15
  • Best of N samples multiple outputs, Tree-of-Thought searches reasoning trees iteratively, and REBASE prunes the search space using reward balancing.Other inference-time approaches discussed include MCTS and test-time optimization.Source: A. Related Works · p. 15
  • PlanGEN combines constraint-guided verification and multi-agent collaboration to improve inference-time algorithms for natural-language planning and downstream reasoning tasks.The paper presents this approach in contrast to prior inference-time work.Source: A. Related Works · p. 15

B. Further Details on LLM Agents

PlanGEN’s agents extract instance constraints, evaluate plans against them, and select inference-time algorithms; its prompts support both agent evaluation and iterative ToT and REBASE search. The full UCB selection variant gains about 3.5% over its version without diversity and recovery terms.

B. Further Details on LLM Agents

  • The constraint agent extracts problem-specific constraints, while the verification agent evaluates plans using dynamically generated constraints and returns a reward score.The constraint prompt is task-specific; the verification prompt is task-agnostic and uses strict evaluation criteria.Source: B. Further Details on LLM Agents · pp. 15–16
  • Constraint formats vary by task: NATURAL PLAN uses task-specific constraint types, DocFinQA adds formatting instructions, and GPQA and OlympiadBench use the general prompt.The verifier and selector prompts are task-agnostic.Source: B. Further Details on LLM Agents · pp. 15–16
  • The selection prompt uses verifier feedback and problem context to score algorithm suitability, while modified UCB combines reward, exploration, diversity, recovery, and LLM-guided priors.The strategy selects the algorithm with the highest combined UCB score.Source: B. Further Details on LLM Agents · pp. 16–17
  • ∼3.5% performance gain came from adding diversity and recovery terms to UCB, compared with the UCB variant without those terms.LLM-guided priors remain in both variants; Figure 10 presents the ablation comparison.Source: Figure 10 · p. 17, B. Further Details on LLM Agents · pp. 17–18

C. Prompts for Proposed Frameworks

  • For ToT and REBASE, step prompts generate the next action, reward prompts assess intermediate steps against the problem and constraints, and completion prompts check for a full solution.Exploration stops when a solution is found; otherwise it continues.Source: C. Prompts for Proposed Frameworks · p. 18

D. Details on Benchmarks and Experiments

Experiments use evaluation sets from NATURAL PLAN, GPQA, OlympiadBench, and DocFinQA, primarily with Gemini-1.5-Pro. Task-specific metrics and fixed inference settings define the evaluation setup.

D. Details on Benchmarks and Experiments

  • The evaluation covers 1,000 Calendar Scheduling and 1,000 Meeting Planning instances, 1,600 Trip Planning instances, 198 GPQA Diamond instances, 674 OlympiadBench MATH problems, 236 PHY problems, and 922 DocFinQA examples.OlympiadBench excludes text problems requiring a theorem prover.Source: D. Details on Benchmarks and Experiments · p. 19
  • Gemini-1.5-Pro is the primary evaluation model; a case study with Gemini-2.0-Flash and GPT-4o examines PlanGEN’s model-agnostic nature.All experiments use task-specific metrics: Exact Match for NATURAL PLAN, micro-average accuracy for OlympiadBench, and accuracy for GPQA and DocFinQA, with DocFinQA also reporting F1.Source: D. Details on Benchmarks and Experiments · p. 19
  • Inference settings use five Best of N samples, three ToT children per root, and REBASE width 10, decremented by one after each expansion call.All agents use temperature 0 for deterministic behavior; inference-time algorithms use temperature 0.7.Source: D. Details on Benchmarks and Experiments · p. 19

E. Additional Analysis

Additional analyses examine algorithm selection, performance by problem complexity, verifier rewards, and inference-time hyperparameters. They also provide examples of generated constraints, verification, and plans across planning and reasoning tasks.

E. Additional Analysis

  • In meeting planning, Best of N performs best on simple and intermediate problems while the mixture performs better on complex ones; for very complex meeting and trip instances, all algorithms perform poorly.For trip planning, Best of N and the mixture outperform other approaches across all complexity levels.Source: Figure 12 · p. 20, E. Additional Analysis · p. 20
  • Success outcomes are associated with rewards around 80–100 and failures primarily with rewards around 20–40, though some failures receive high rewards.The reward distributions differ significantly (Mann–Whitney U = 116128.0, p < 0.0001); the high-reward failure cases warrant further investigation.Source: E. Additional Analysis · pp. 19–20, Figure 11 · p. 20
  • Increasing Best of N samples, ToT steps, or REBASE refinements yields marginal OlympiadBench gains, so the authors use lower settings to balance efficiency and performance.Table 2 reports the hyperparameter comparison.Source: Table 2 · p. 20, E. Additional Analysis · p. 20

F. Various Examples for Different Components of PlanGEN

  • Examples span generated constraints for NATURAL PLAN and reasoning tasks, verifier evaluation of a calendar plan, and generated plans for NATURAL PLAN, GPQA, DocFinQA, and OlympiadBench.The plan examples use PlanGEN (Best of N); downstream reasoning examples also show plan execution to derive answers.Source: F. Various Examples for Different… · p. 21

E. Additional Analysis

  • PlanGEN (ToT) is selected most often for NATURAL PLAN, OlympiadBench, and GPQA, while PlanGEN (Best of N) dominates DocFinQA; REBASE is selected least across datasets.The authors interpret this pattern as dataset-dependent algorithm effectiveness and adaptive selection.Source: Table 3 · p. 21, E. Additional Analysis · p. 21

I. Mathematical Reasoning Constraints:

  • The prime-sequence example’s mathematical criteria include correct recurrence use, primality reasoning, a base case, a search and termination strategy, and an optimality argument.Its computational criteria address primality testing, implementation, resource use, and search range.Source: §I · p. 25
Loading 2502.16111v1…