speed up Elias gamma compression
Rather strange to encode as a number instead of a (bit)string. And the way you do it takes quadratic time in the size of your list (because both the + and the &lt;&lt; in bitstream += encoded_number &lt;&lt; bitstream_length are linear). You could do it in linear time by building a string and then turning it into a number at the end.
This should take only a few seconds for your large test (removing the docstring just for brevity here):
def compress(numbers: List[int]) -&gt; int:
    bitstream = []
    previous_number = 0
    for number in numbers:
        delta = number - previous_number # store deltas, much smaller numbers
        N = delta.bit_length() - 1
        encoded_number = bin(delta)[:1:-1] + '0' * N
        bitstream.append(encoded_number)
        previous_number = number
    bitstream.reverse()
    return int(''.join(bitstream), 2)

For decompression, I'd accordingly first turn the number into a string and then work with that.
Optimized version should take less than a second:
def compress(numbers: List[int]) -&gt; int:
    bitstream = []
    append = bitstream.append
    memo = {}
    lookup = memo.get
    previous_number = 0
    for number in numbers:
        delta = number - previous_number # store deltas, much smaller numbers
        if not (encoded_number := lookup(delta)):
            N = delta.bit_length() - 1
            memo[delta] = encoded_number = bin(delta)[:1:-1] + '0' * N
        append(encoded_number)
        previous_number = number
    bitstream.reverse()
    return int(''.join(bitstream), 2)