Blocks of a frame of a video stream can be encoded using lossless inter-frame prediction encoding. The compression ratio of lossless inter-frame encoding can be improved by first examining the magnitude of a motion vector used to perform inter-frame prediction. If the magnitude of the motion vector is small, the residual generated by the inter-prediction can be entropy coded and included in the encoded bitstream. If the magnitude of the motion vector is greater than a threshold, the residual can be encoded using lossy encoding and then decoded and subtracted from the original residual. The resulting difference residual is encoded using lossless encoding and included in the output bitstream along with the lossy encoded residual, permitting the block to be decoded with no loss at a decoder.