Comment by akoboldfrying

Makes sense. It might be possible to develop a codec that, in addition to being constant-time, has the property that every prefix of the bits encoding a unit (e.g., a frame or block within a frame) encodes an approximate version of that unit, where the longer the prefix the more faithful the approximation is. Then each unit could be output in full to storage, and the "output file pointer" could then be wound back to a point dependent on how many bits are actually required to represent it accurately -- so keeping the full amount for a full scene change, or just a few bits for the "same as last time" common case.