1. A method of processing a video stream, comprising: (a) detecting a request to playback a particular frame; and (b) determining whether a decoded version of the particular frame is in a decoded frame cache, and if it is not (i) determining a frame dependency for the particular frame; (ii) determining which of the frames in the frame dependency are in the decoded frame cache; (iii) decoding any frame in the frame dependency that is not in the decoded frame cache and placing it in the decoded frame cache; and (iv) using at least some of the decoded frames in the frame dependency to decode the particular frame to create a decoded version of the particular frame.