Ideas for Sampling Strategies

[nrfulton]

Mellea has a SamplingStrategy interface, which can be used to define prompting-based methods for sampling.

There are currently only a few strategies either implemented or currently in PR stage. We should add support for additional strategies.

We should additionally make it easy to use these "what's my goal?" strategies (e.g., fix each requirement sequentially) together with "how do I sample?" methods (eg top-k).

Let's use this discussion as a place to collect various extensions to the stdlib samplers.

[nrfulton]

Requirement Fixing

When an Instruction has a set of requirements, and more than one of those requirements fails, there are a number of things that can be done:

• resample without any reference to the failed requirements (this is RejectionSamplingStrategy).
• try to fix the requirements sequentially (prompt the model to repair WRT the first failed requirement, or WRT a randomly selected failed requirement)
• try to fix all of the requirements at once (prompt the model to repair WRT a list of all failed requirements
• try to fix each failed requirement requirement separately, and proceed along each successful branch

There are many variations that combine these three approaches, and the last method in particular requires some care.

[nrfulton]

Sampling Methods

The "Requirement Fixing" message addresses the "what are we trying to do?" aspect of a sampling strategy; in that case, we're sampling with the goal of finding an output that satisfies the requirement.

This raises an obvious question: "how do we sample?". We should at least implement top-k and top-p, but there's an entire design space here that can be explored as soon as we're exposing necessary info in ModelOutputThunk.