Motivation:

• Challenge to guide LLMs to engage in deeper thinking to enhance problem-solving capabilities
• Existing research exhibit various strategies to leverage inference-time compute: chain-of-thought prompting, sequential revision based feedback
• Deploying a search strategy like Mind Evolution offers an advantage as they can improve problem-solving abilities by exploring a larger set of solution candidates

Conceptual Walkthrough: Here’s how the Mind Evolution tackles a problem like TravelPlanner

• Analyzes Problem: User query with travel preferences and constraints, and a set of options for travel, accommodation, food, attractions
• Generates Initial Solutions: Mind Evolution creates an initial set of diverse candidate trip plans
• Evaluate and Refine: Each plan is evaluated by a program that:
  • Checks how well the plan meets the user’s requirements and preferences
  • Gives scores and provides textual feedback on any issues.
• Simulates a critical conversation: Mind Evolution uses the LLM to act as both a “critic” and an “author.”
  • The critic analyzes the plan, understands the evaluator’s feedback, and suggests ways to fix problems.
  • The author takes the critic’s advice and creates an improved version of the plan.
  • This back-and-forth continues for several rounds.

• Evolves solutions over generations: Mind Evolution repeats the process of generating, evaluating, and refining solutions over multiple “generations,” like an evolutionary process.
  • Better-scoring plans are more likely to be selected for further refinement.
  • Parts of different plans can be combined (crossover) and small changes can be introduced (mutation) to explore new possibilities.
• Uses multiple “islands” for diversity: Solutions are evolved on multiple independent “islands” to prevent getting stuck in a rut.
  • The best solutions from each island are shared with others (migration), encouraging exploration of a wider range of ideas.
• Resets islands for efficiency: Islands with poorly performing solutions are periodically reset.
  • This involves replacing the bad solutions with good ones from the global population.
• Stops when a solution is found or after a set number of generations.
  • The best plan is then presented as the solution to the TravelPlanner problem.

This approach has the following set of hyperparameters:

Findings/Results:

• Mind Evolution excels in solving complex NL planning problems, surpassing baseline methods like Best-of-N and Sequential Revision on benchmarks like TravelPlanner and Natural Plan

• Eliminates need for formal solvers or problem translation, which often demand significant domain expertise and effort. It achieves this by leveraging an LLM to generate, recombine, and refine candidate responses based on feedback from an evaluator
• Emphasizes the significance of combining divergent and convergent thinking in problem-solving. Uses a genetics-based approach that iteratively evolves a population of candidate solutions towards higher quality
• Success rates increase as number of candidate solutions increase

• Mind Evolution’s effectiveness is further validated through a new benchmark, StegPoet, a challenging task involving the encoding of hidden messages in creative writing, demonstrating the approach’s applicability beyond conventionally formalized domains