If I'm not mistaken, an APK file is a zip archive, meaning that bsdiff was previously run on compressed stuff. As you can see in the article compressing content

If I'm not mistaken, an APK file is a zip archive, meaning that bsdiff was previously run on compressed stuff. As you can see in the article compressing content tends to make the output greatly differ (so much that gzip has a special option to make it more easily diffable, typically for rsync use). So bsdiff wasn't previously run on a concatenation of file; it was not used optimally.