What is the fastest temperature sensor?
A Sous-Vide is just a water bath. Easy to control. 

No way you need the "fastest" sensor. Whatever you're using as a control algorithm is probably your problem. Presumably this probe is inside a metal tube and has limited heat transfer. 

The main thing from a controls pov is that your sensor should be much faster than the actuator- I don't think you can heat the water from 0°C to 100°C in a minute. If so maybe you should cut back on your heater power from however many kW it is.