New video codecs typically offer more options for how to represent the current frame in terms of other frames. That typically means more processing for the encoder, because it can check for all the similarities to see what works best; there's also harder math for arithmetic coding of the picture data. It will be more work for the encoder if it needs to keep more reference images and especially if it needs to do harder transformations, or if arithemetic decoding gets harder.

Clever matters a lot more for encoding. If you can determine good ways to figure out the motion information without trying them all, that gets you faster encoding speed. Decoding doesn't tend to have as much room for cleverness; the stream says to calculate the output from specific data, so you need to do that.