Speed up prefill stage

[benlebrun]

For long prompts, the prefill stage, in which we create a beam state corresponding to an input byte sequence in preparation for conditional generation, can be quite slow.

We should think about faster alternatives which do not involve processing the input byte sequence byte-by-byte, but rather use a modified version of the token healing heuristic to initialize the beam (modified so that it doesn't suffer from the degenerate cases we have identified with this heuristic).

Tagging @chanr0

[timvieira]

This method is nothing more than a faster—but less accurate—version of ordinary character-level conditioning so it should probably have a similar name and/or be an argument to the conditioning method. Supporting tokenize-and-pray, token healing (± adaptive backtracking), and beam summing seem like good options.

[timvieira]

A good compromise method for prefilling is to sample a batch of possible members of the prompt's covering. That's essentially what this paper does: Decoding-Free Sampling Strategies for LLM Marginalization