That's a fair question. Suppose we have a way to find a byte sequence x that globally minimises len(gzip(context + prompt + x)) over all sequences x of length n. Here + denotes string concatenation.

It's unclear if this is very useful.

The reason it may not be very useful is that one of Deflate's ingredients is a pass that replaces repeated substrings with backreferences to the earlier occurrence in the plaintext input stream.

E.g. suppose we want to find an n=200 byte sequence x that minimises len(gzip(context+prompt+x)).

If there exists any 200 byte sequence y such that prompt+y is a substring of context, then Deflate can encode prompt+y as a backreference to that earlier sequence - it needs to store a match-length & a distance-length, encoded using its Huffman trees. This candidate solution y may not be a global minima to our stated objective function, but if not, it's probably going to be a very good near-optimal approximate solution.

Taking a step back, repeating huge chunks of the input context produces something that's great for minimising compressed output size but doesn't seem particularly helpful as a generative model.

edit:

Yep, I tried it out by running an experiment. Searching for the prompt in the context & then copying the following text as the solution produces solutions that are much better, in the sense of minimising the compressed output length, than beam search, while also being unhelpful as a generative tool.

With the same example as the blog post:

  context: first 30,000 bytes of tinyshakespeare.txt
  prompt: 'MENENIUS:\n'

Let L(x) denote len(gzip(context+prompt+x)), our objective function

Let's call the proposed search method of searching for the prompt in the input rfind (after python's str.rfind).

Then we have

   search method      soln               soln length   feasible?     objective value      search time (wall clock, s)
   -------------      ----               -----------   ---------     ---------------      ---------------------------
   emptystring        ""                          0          no              13,023                     0.04s
   gzipt beam search  see blog post             200         yes              13,051                    11.93s
   rfind              see below                 200         yes              13,026                     0.04s

Here's the solution 'generated' by rfind copying and pasting from the input context, starting from the rightmost occurrence of "MENENIUS:"

   MENENIUS:
   O, true-bred!
   
   First Senator:
   Your company to the Capitol; where, I know,
   Our greatest friends attend us.
   
   TITUS:
   
   COMINIUS:
   Noble Marcius!
   
   First Senator:
   
   MARCIUS:
   Nay, let them follow:
   The Volsces 

    def find_candidate_solution_from_context(context, prompt, length):
        n = len(context)
        i = context.rfind(prompt, 0, n-length)
        if i < 0:
            return b''
        i += len(prompt)
        return context[i:i+length]

    out += find_candidate_solution_from_context(corpus_window, prompt, length)