Then fall back to downloading the full OS image. Then the worst case would be about the same as today, while the common (99.9%+) case would be fast and bandwidth-cheap.

(Optimization: hash tree, figure out which specific files are broken and download only those.)

Then abort the update? I'm not objecting to A/B partitions or filesystem snapshots or boot environments or however you want to implement it, I'm just saying that you can reconstruct the install image on the machine rather than downloading the whole thing over the wire.

Use a Merkle tree.

Maybe checksum before updating? Or revert the patch if it fails?