Idk but btrfs and zfs manage to pull it off

Seekable OCI (SOCI) uses an index so I imagine that's an option (real byte range a-b maps to compressed range x-y). Presumably you'd still need to read the header and some additional pieces

afaik, ZFS will read an entire Record at a time- and that's the same granularity as its compression.

It uses some form of keyframing. Not entirely free.