Embodiments are directed to decoding incomplete video data. In one scenario, a computer system receives a piece of a frame (e.g. a video frame). The frame includes multiple frame pieces, where each frame piece is encoded so as to be individually decodable. The computer system decodes the received frame pieces while waiting for at least one additional frame piece to be received. Then, when a condition occurs indicating that the frame is incomplete, the computer system synthesizes frame pieces to replace the additional frame piece that has not yet been received.