Isn't this the idea behind MIPMAPS in computer graphics?

In the tracing world, I believe the opensource pulseview/sigrok does this. It makes the UI very responsive even with gigabytes of data. I just wish it also integrated data compression of some kind so I could fit more trace than I have RAM (it can't be all that hard to intelligently compress a super repetitive signal in a way which still allows this fast zooming and scrolling - replacing some tree nodes with LZ77 style backreferences ought to do the trick)

What do you mean by needing to fit more trace than you have RAM? Are you saying those systems require you to load the entire raw trace into RAM before constructing the relevant data structures for efficient zooming? If so, that seems very limited since you can just use a storage-friendly data structure that also supports efficient zoom so you can put the bulk of the data on disk or across the network and just use your RAM as a cache for the full data structure. This is no worse than a RAM-only solution and allows you to operate on effectively arbitrarily sized traces for when you need to handle those hundred TB traces.

The use case is "I have binary data coming in at 5 Gbytes/sec from a logic analyzer, and I normally want say 30 seconds of trace"

That data is too big for RAM, and coming in too fast to write to disk. But the data is usually very compressible. Some channels will be a million '0's. Other channels will be a clock signal of '0 1 0 1 0 1' forever. Other signals will be more complex, but probably still be near repeats of patterns.

I just want to compress it in realtime in such a way the GUI tools I want to use can still work. They need to do fast-ish random access on the data, and answer questions about chunks of the data (eg. is all the data between time X and time Y all 0's).