Why couldn't you just run physics at the graphics frame rate (or double it if the graphics becomes too slow)? I don't think many games need fully deterministic physics do they?
Like
x += v * dt
draw(x)