I assume it doesn't record what happens every frame, but specific events. That way if you don't move, it doesn't write anything until you do. Some record systems only record player input.
Jonathan Blow gave a tech talk at GDC about how the rewind mechanic was implemented. It turns out that he does in fact save the non-constant game state of every frame. Around 6:20 is where he talks about it. https://www.youtube.com/watch?v=tSeYShR-OG0