Thanks for your reply and advice! I guess what you describe as "impossible" is the case I am mostly interested in, though more for non-executable binary data. If I am not mistaken, this goes under the term "file fragment classification", but I have been wondering if practitioners might have figured out some better ways than what one can find in scholarly articles.
And yes, searching for the reimplementation beforehand would have saved me some hours :D
It's not about the data being executable. It's about having access to whatever reads or writes this data.
Whatever reads or writes this data has to be able to compress or decompress it. And with any luck, you'll be able to take the compression magic sauce from there.
I understood "binaries" in "compressed binaries" as "executables", e.g. like a packed executable, but I see that you mean indeed a binary file (and not e.g. a text file).
Reread that just now, sorry for not making it clearer. I kind of just used "binaries" in both senses? Hope the context clears it up.