How do I create binary patches?

Check out bsdiff and bspatch (website, manpage, paper, GitHub fork).

To install this tool:

• Windows: Download and extract this package. You will also need a copy of bzip2.exe in PATH; download that from the "Binaries" link here.
• macOS: Install Homebrew and use it to install bsdiff.
• Linux: Use your package manager to install bsdiff.

Courgette, by the Google Chrome team, looks like most efficient tool for binary patching executables.

To quote their data:

Here are the sizes for the recent 190.1 -> 190.4 update on the developer channel:

• Full update: 10,385,920 bytes
• bsdiff update: 704,512 bytes
• Courgette update: 78,848 bytes

Here are instructions to build it. Here is a Windows binary from 2018 courtesy of Mehrdad.