A video coding system may initiate coding of a new coding session with reference to an “inferred key frame” that is known both to an encoder and a decoder before a coding session begins. The inferred key frame need not be transmitted between the encoder and decoder via the channel. Instead, the inferred key frame may be stored locally at the encoder and the decoder. Frames coded at the onset of a video coding session may be coded with reference to the inferred key frame, which increases the likelihood a decoder will receive a frame it can decode properly and accelerate the rate at which the decoder generates recovered video data. Inferred key frames may be used as prediction references to recover from transmission errors.