Implement FunSearch in DSPy about dspy

[darinkishore]

@mattredlon

Spitballing, but take a look at this issue/PR combo. Would this be what you were thinking about for item 1? (Signatures would need the ability to use an “immutable” prompt “skeleton”.)

darinkishore#68

darinkishore#69

[okhat]

Hey @mattredlon,

teleprompter is where we would want to execute and score each variant and then persist the “program” along with its evaluation score. We would perhaps then implement our genetic algorithm / island strategy as a retriever to select the example "programs" to include from the module, but someone could tell me this belongs in teleprompter as well.

With the big caveat that I (i) read your post carefully (ii) never read the FunSearch paper or any content about it yet unfortunately, I think this all belongs in a new teleprompter.

We'll rename teleprompters to optimizers so let me start using that term now. Basically I can imagine a dspy.optimize.FunSearch optimizer. It will take FunSearch(**general_config_and_hyperparams) and will have .compile(program, trainset) as usual.

In terms of the original design, Signatures in DSPy are stateless and immutable.* The optimized parts are held inside the modules, basically/mainly dspy.Predict. (Other modules generally use dspy.Predict in different ways.)

The main things that can be optimized are typically instructions and demonstrations (or the LM weights if we're finetuning). I assume FunSearch is more about the instructions?

Footnote: Even I think eventually signatures should be stateless and immutable in principle, we took some shortcuts in SignatureOptimizer where it does mutate the instruction of the signature. Probably not the right long-term thing to do.

[mattredlon]

These are excellent, @darinkishore! I am not fluent enough in the code base or design principles of DSPy yet to be confident in my evaluation of your issue/PR so please be patient with me, however, there was one element where I wasn't sure if it should be addressed in the Signature, in the Module (perhaps leveraging a new genetic/islands retriever), or in the Teleprompter/compiler. You included it as:

Specifications
Sample Signatures: Create a method to sample k signatures based on certain logic, akin to DeepMind's priority functions sorting and selection.

Action Items
Design and implement the sampling of signature variations and the prompt construction methodology.

Are you envisioning the Signature itself being responsible for sampling k "programs" (to use FunSearch vernacular) each hop? If so, would you envision the Module as the location for executing the Python generated via the latest Signature/"program" variant? If so, where in the process would we persist the latest "program" and what would the role of the Teleprompter/compiler be?