Source-linked AI summary
Evolving Deeper LLM Thinking
Kuang-Huei Lee, Ian Fischer, Yueh-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuurmans, Xinyun Chen
TL;DR
Natural-language planning requires solving interconnected constraints without explicit formalizations, motivating inference-time search that can exploit evaluators. Mind Evolution uses an LLM to evolve, recombine, and refine candidate solutions through evolutionary search. It significantly outperforms Best-of-N and sequential revision on the reported planning benchmarks, while remaining limited to settings with programmatically evaluable solutions.
Problem
Natural-language planning tasks contain interconnected global and local constraints without explicit formalizations, making effective inference-time search an important research problem.
Method
Mind Evolution uses an evolutionary search strategy in which an LLM generates, recombines, and refines candidate solutions using evaluator feedback.
Results
Mind Evolution significantly outperforms Best-of-N and sequential revision, achieving 100% success on TravelPlanner and 98.4% on Meeting Planning in its two-stage Gemini 1.5 Pro evaluation.
Takeaways & Limitations
Evolutionary exploration and refinement can substantially improve natural-language planning without explicitly leveraging a formal solver.
Takeaways & Limitations
The current method is limited to natural-language planning problems whose proposed solutions can be programmatically evaluated and critiqued.
Abstract
from arXiv · showhide
We explore an evolutionary search strategy for scaling inference time compute in Large Language Models. The proposed approach, Mind Evolution, uses a language model to generate, recombine and refine candidate responses. The proposed approach avoids the need to formalize the underlying inference problem whenever a solution evaluator is available. Controlling for inference cost, we find that Mind Evolution significantly outperforms other inference strategies such as Best-of-N and Sequential Revision in natural language planning tasks. In the TravelPlanner and Natural Plan benchmarks, Mind Evolution solves more than 98% of the problem instances using Gemini 1.5 Pro without the use of a formal solver.
1. Introduction
Mind Evolution scales inference-time compute through evolutionary exploration and iterative refinement of natural-language solution candidates, targeting planning problems that lack explicit formalizations. Across TravelPlanner, Natural Plan, and StegPoet, it achieves strong success rates without relying on a formal solver.
- Motivation and contribution: Mind Evolution combines stochastic exploration with iterative refinement by generating, recombining, and improving a diverse population of candidate solutions using an LLM and evaluator feedback.The approach is framed as combining divergent exploration with convergent evaluation and selection.
- Motivation and contribution: Unlike Best-of-N and sequential reasoning, Mind Evolution searches broadly and deeply while refining complete solutions with only a global solution evaluator.It does not require evaluation of individual reasoning steps or a stepwise process reward.
- Motivation and contribution: Mind Evolution applies evolutionary search directly in natural-language space, enabling tasks that are difficult to formalize when a programmatic evaluator is available.The paper focuses on planning problems whose objectives, constraints, and variables are expressed in natural language.
- Results: 100% success on TravelPlanner and 98.4% on Meeting Planning are achieved by a two-stage system using Mind Evolution with Gemini 1.5 Pro on unsolved instances.The reported two-stage results follow Gemini 1.5 Flash performance of 95.6% on TravelPlanner and 85.0% on Meeting Planning under controlled inference cost.
- Motivation and contribution: Mind Evolution directly optimizes natural-language solutions, avoiding the translation into formal representations required by comparable solver-based approaches.The paper identifies formalization as requiring significant effort and expertise.
- Results: 87% success is achieved by Gemini 1.5 Pro on StegPoet, a new benchmark requiring hidden-message encoding in natural-language creative writing.The task is intended to demonstrate search beyond domains that are easily formalized.
2. Related Work
Related work combines LLMs with evolutionary search, evaluators, verifiers, and prompt optimization, but Mind Evolution applies evolutionary search directly to natural-language plans. Prior feedback mechanisms broaden applicability but may introduce noisy or unreliable guidance.
- Evolutionary search with LLMs: Prior LLM-evolution work primarily searches formal program spaces using execution feedback or code explanations.Other studies also examine numerical and combinatorial optimization, while Mind Evolution targets natural-language planning.
- Prompt and agent optimization: EvoAgent evolves LLM agents into a multi-agent system, whereas Mind Evolution evolves plans directly.On the TravelPlanner validation set, EvoAgent achieved 7.2% with GPT-4, while Mind Evolution achieved over 95% with Gemini 1.5 Flash.
- Evaluators and feedback: Program-based evaluators provide execution-style feedback during search, extending a pattern widely used in code-generation research.The evaluator integration supports refinement by exposing errors or constraint violations to the model.
- Evaluators and feedback: Learned verifiers, reward models, and self-evaluation can support refinement and search across wider domains, but their feedback may be noisy and unreliable.The paper leaves approximate feedback mechanisms for future work.
3. Method
Mind Evolution represents candidate solutions as natural language and evolves them through evaluator-guided selection, recombination, refinement, and island operations. Its pipeline combines genetic-search structure with LLM-based critical conversation and programmatic fitness evaluation.
- Representation and search: Mind Evolution uses a genetic search strategy in which an LLM orchestrates solution search for natural-language planning tasks.The method builds on populations of candidate solutions evolved toward higher fitness.
- Representation and search: Natural-language candidates let the LLM implement recombination, mutation, and island-reset operations through prompting.The representation leverages the model’s language understanding and generation capabilities.
- Termination and budget: The evolution process stops when a valid solution is found or N_gens generations are completed, after which the best-scoring candidate is returned.The default hyperparameter product permits up to 800 generated candidate solutions.
- Fitness evaluation: The fitness function scores solution quality, verifies constraints, and provides textual feedback for subsequent refinement.The evaluator can in principle be any function that assesses solution quality, including an LLM evaluator.
- Fitness evaluation: Textual evaluator feedback is empirically important for the method’s performance.The paper reports this finding from an ablation study.
- Population initialization: Initialization generates N_convs × N_seq candidate solutions, forming the first island’s initial population.Independent solutions may undergo sequential Refinement through Critical Conversation before entering the population.
- Refinement through Critical Conversation (RCC): Refinement through Critical Conversation has a critic analyze candidates and feedback, followed by an author proposing a single refined solution.The process iterates, and recombination applies it to selected parent candidates.
- Evolutionary operations: Boltzmann tournament selection favors higher-fitness parents while retaining occasional lower-fitness selections for diversity, and recombination produces new children through RCC.Island populations evolve independently between migration events, with selected solutions transferred cyclically across islands.
4. Experiments
Mind Evolution is evaluated against several search baselines on three natural-language planning tasks, with results showing strong performance, scaling benefits, and contributions from iterative refinement and evolutionary design choices.
- Experimental Setup: Mind Evolution is compared with 1-Pass, Best-of-N, and Sequential-Revision+ using success rate and inference-cost measures.The experiments report validation and test success rates alongside LLM calls, token counts, and API costs.
- TravelPlanner: Over 95% Success Rate is achieved on TravelPlanner, compared with almost 83% for Sequential-Revision+ and 55.6% for Best-of-N.The comparison supports a broad-plus-deep evolutionary search strategy combining stochastic exploration with solution refinement.
- TravelPlanner: 100% validation and 99.9% test success are achieved by the two-stage Mind Evolution approach using Gemini 1.5 Pro on unsolved problems.These results are reported as comparable to a formal-solver approach while not requiring a formal solver.
- Natural Plan: 96.2% validation and 94.1% test success are achieved on Trip Planning, while the two-stage approach reaches 100% and 99.6%, respectively.Mind Evolution also outperforms the reported baselines, and its relative advantage appears to increase with the number of cities.
- Scaling: Success rates improve steadily as the number of generations increases, indicating benefits from additional evolutionary search.The scaling analysis measures Mind Evolution across the planning tasks as a function of generation count.
- Scaling: Mind Evolution is more effective than baseline strategies at reaching a specified success rate with fewer candidate solutions across the planning tasks.Overall success rates and average task evaluation scores improve monotonically with more proposed solutions across search methods.
- Ablations: The critic step and textual evaluator feedback are the most critical components, while the island model significantly improves performance.Ablations also suggest that deeper search helps, while maintaining broad exploration within each generation remains important.
5. A Challenging New Task: StegPoet
StegPoet introduces a difficult creative-writing task in which a hidden numerical message must be encoded through a generated text and substitution cipher. Mind Evolution remains effective despite the task’s difficult formalization, achieving strong validation and test success.
- Task Definition: StegPoet requires encoding a hidden numerical message into an essay, story, or poem using a number-to-word substitution cipher.The generated output must provide both the cipher and creative text that encodes the message.
- Task Definition: StegPoet difficulty varies with message length, number repetition, proximity of repeated numbers, and the mean distance between cipher words.The message length is set between 10 and 30 numbers, while repetition and writing-form constraints affect difficulty.
- Evaluation: The benchmark contains 101 validation instances and 245 test instances.The evaluation is divided into separate validation and test splits.
- Results: 87.1% validation and 79.2% test success are achieved by two-stage Mind Evolution (+pro), whereas Best-of-N solves only 1% of validation tasks.Performance is reported by difficulty level in Figure 11 and in the detailed results table.
6. Conclusion
Mind Evolution is presented as an evolutionary search approach for challenging natural language planning problems that scales inference-time compute through stochastic exploration and iterative refinement. Across TravelPlanner, Natural Plan, and StegPoet, it significantly outperforms Best-of-N and sequential revision without explicitly using a formal solver, while remaining focused on tasks with programmatically evaluable solutions.
- Mind Evolution scales inference-time compute through stochastic exploration and iterative refinement for challenging natural language planning problems.
- Across TravelPlanner, Natural Plan, and StegPoet, Mind Evolution significantly outperforms Best-of-N and sequential revision.
- Mind Evolution achieves this level of success without explicitly leveraging a formal solver.
- The current work focuses on natural language planning problems whose proposed solutions can be programmatically evaluated and critiqued.
A. Implementation Details
The implementation uses structured prompts that provide task instructions, examples, parent solutions, evaluation feedback, and critical-thinking guidance. These prompts support refinement through critical conversation for Meeting Planning and the same overall structure for TravelPlanner.
- The implementation details describe Mind Evolution, with code stated to be made available.
- Meeting Planning prompts include general instructions, a problem definition, few-shot examples, and a task description.Few-shot examples help the LLM generate solutions closer to the desired formats.
- Parent solutions and corresponding evaluation feedback are followed by critical-thinking instructions that guide refinement through critical conversation.The prompts also include problem-specific Strategy/Question prompts based on validation-set findings.
- TravelPlanner prompts use the same structure as the Meeting Planning prompts.
A.2. Evaluation Functions
The evaluation functions score candidate plans, verify constraint satisfaction, and provide textual feedback. Separate implementations adapt this framework to TravelPlanner, Trip Planning, and Meeting Planning, including optimization objectives where applicable.
- Evaluation functions score solutions, verify constraints, and provide textual feedback.They penalize unsatisfied constraints, unmaximized objectives, and failures to follow required formats.
- TravelPlanner: TravelPlanner evaluation outputs cumulative scores reflecting all unsatisfied constraints and textual feedback for violated constraints.The evaluator expects travel plans in JSON format and modifies the original benchmark code.
- Trip Planning: Trip Planning evaluation scores unsatisfied constraints and JSON-format compliance while providing corresponding textual feedback.
- Meeting Planning: Meeting Planning evaluation scores missed meetings, schedule conflicts, and repeated meetings while optimizing the number of friends met.
B. Data Splits
The benchmarks use separate validation and test splits, with dataset sizes and split procedures varying across TravelPlanner, Trip Planning, and Meeting Planning. Validation examples support prompt development before evaluation on held-out test examples.
- TravelPlanner: TravelPlanner contains 45 training tasks, 180 validation tasks, and 1,000 test tasks.
- Natural Plan – Trip Planning: Trip Planning has 1,600 tasks across eight difficulty levels, with 320 validation and 1,280 test examples.The first 40 examples per difficulty level are used for validation, and the last 160 for testing.
- Natural Plan – Meeting Planning: Meeting Planning has 1,000 tasks across ten difficulty levels, split into 500 validation and 500 test examples.The first 50 examples per difficulty level are used for validation, and the last 50 for testing.
C. GPT Results
Mind Evolution substantially improves GPT-4o-mini’s planning performance across the reported benchmarks, despite weak one-pass results.
- GPT-4o-mini baseline: GPT-4o-mini achieves 0% on TravelPlanner, 9.1% on Trip Planning, and 20.2% on Meeting Planning with one-pass inference.These results show that GPT-4o-mini struggles with planning tasks before evolutionary search is applied.
- Evolutionary search results: Mind Evolution improves GPT-4o-mini performance by over 100% relatively across different benchmarks.
D. Model Pricing and API Cost Curves
The paper reports model API pricing from October 2024 and uses these prices to interpret API-cost differences across inference strategies.
- API cost curves: Figure 25 relates API cost per task to validation-set success rate with Gemini 1.5 Flash.API cost combines input and output token counts weighted by model base rates.
- Model pricing: Table 8 reports the API pricing of the evaluated models at the time of writing in October 2024.
- API cost: API cost is used as a proxy for real computational cost differences among models.
E. Additional Examples
The additional examples illustrate qualitative planning outputs, StegPoet’s prompt and evaluation design, and the scoring and feedback used to refine solutions.
- Planning examples: Tables 9 and 10 provide example TravelPlanner and Meeting Planning tasks with solutions from Mind Evolution and baseline methods.
- StegPoet evaluation: StegPoet solutions contain a cipher and text component, with the encoded message recovered through capitalization-agnostic character matching.
- Validity constraints: Invalid StegPoet solutions fail when parsing or constraints are violated, including repeated cipher words or words shorter than four characters.
- Scoring: The StegPoet score combines the first mismatch position with a scaled Levenshtein distance between the intended and recovered messages.
- Revision feedback: Revision requests also provide textual feedback without numeric penalties to guide the language model.
- Prompt design: The StegPoet prompt specifies one-to-one number-to-word mappings, ordered encoding, alphabetic single-word cipher entries, and explicit poem delimiters.
- Prompt design: Figure 26 presents an example initial prompt for StegPoet, with one of three examples shown.