give it a normal text prompt, and it
    continues that prompt by searching
    for the byte sequences that compress
    best.

So the result only gives us some lower bound of how well gzip works as a "plausibility tester" of a continuation of a text. The space of possible sequences is many orders of magnitude larger than what was searched. So there might be sequences in there that compress much better.

The text mentions beamsearch, but I don't see a discussion about how well beamsearch performs in finding the global optima when it comes to gzip compressibility of a text?

Read to the end: they aren't actually looking for the best-compressing output, because this quickly devolves into aaaaaaaaaaa. They keep a sliding window over a small portion of recent text and use that.

Basically I think the entire premise falls apart due to that choice--they forced an interesting-looking outcome by adjusting the algorithm until gzip started picking random slabs of letters instead of ever-larger repeating runs.

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)