Length decoding is a finite state machine, and the transition function of finite state machines is associative, which means you can actually compile them into a reduction tree to do it in parallel.

I don't think the x86 decoder is actually a particularly complex state machine (I haven't attempted to actually build it), so it's probably overall far less complex than most people assume it is.