FunSearch

From https://pub.towardsai.net/inside-funsearch-google-deepminds-new-llm-that-is-able-to-discover-new-math-and-computer-science-2484b7dd89ad


The operation of FunSearch involves a combination of evolutionary methods and Language Models (LLMs) to discover new algorithms.

Problem Specification:
  Users provide a problem statement in the form of an 'evaluate' function. 
  This function rates potential solutions based on specific criteria.
  An initial, often simple, program is included as a seed to kickstart the evolution process.

Pre-Trained LLM (Codey):
  FunSearch relies on a pre-trained Language Model called Codey. 
  Codey is built on the PaLM2 model family and has undergone extensive training on a wide array of code.
  Codey suggests enhancements to functions without requiring specific training tailored to the given problem.

Evaluation:
  Programs generated by Codey are evaluated based on certain inputs. 
  The evaluation involves scoring programs according to the criteria defined by the 'evaluate' function.

Programs Database:
  A database maintains a collection of accurate programs. This database is crucial 
  for generating new prompts and avoiding local optima in the evolutionary process.

Prompt:
  FunSearch uses a method called 'best-shot prompting.'
  Programs from the database are selected and ranked based on their performance.
  Each program is assigned a version number based on its score.

Distributed System:
  FunSearch operates as a distributed system with three main components: a program database, samplers, and evaluators.
  The database stores and dispenses programs, samplers use Codey to create new functions, and evaluators judge the efficacy of these programs.
  The system works asynchronously to manage the evolutionary process.

Iteration:
  The process iterates, with Codey suggesting enhancements, programs being evaluated, and successful programs being stored in the database.
  The system evolves and refines programming ideas over multiple iterations.

Application to Problem-Solving:
  FunSearch is applied to specific problems in mathematics and computer science, such as the cap set problem or the bin packing problem.
  It aims to discover new, efficient algorithms for these problems by leveraging the capabilities of Codey and the evolutionary approach.
  Overall, FunSearch combines the power of pre-trained LLMs with evolutionary techniques to automate the generation and improvement of 
  computer programs, particularly for complex problem-solving scenarios in mathematics and computer science.

** FunSearch is not a specific model; instead, it's a method or approach developed by Google DeepMind. 
   It combines evolutionary methods and Language Models (LLMs), such as the pre-trained model Codey, to discover new algorithms.
   It's a methodology designed to leverage the capabilities of language models for automated algorithm discovery in various problem-solving domains.