Codecs with allow fast backwards stepping frame by frame with mpv According to https://github.com/mpv-player/mpv/issues/4019 backward stepping for example with H264 codec is slow compared to forward stepping. Other codecs, for example mjpeg works a bit better.

For which other codecs/codec settings backward stepping is fast?
As @Mulvya says it depends greatly on the GOP size, but you can insure that stepping is easy at the expense of file size, by using an 'all-I' codec like Motion JPEG. In such codecs every frame appears whole and entire so there is no dependence on previous or subsequent frames.