BTW, if we can cope with strict bytestrings (if we don't have a too big input), would you recommend binary or cereal?

What would you use to auto-derive the Binary/Serialize classes?

The 'derive' package? The problem is that it has a lot of dependencies you maybe don't need if you jut want serialization, plus it relies on TH so it grows both compilation time and executable size.