You missed that the noise function is given n-dimensional coordinates as an argument. Rather than picturing an RNG, you can think of it as a texture unit that samples from an n-dimensional image of some noise with certain characteristics.

The order in which sample values are retrieved doesn't matter — of course it doesn't! It's important that fragments (think 'pixels' in case you're wondering what fragments are) can be evaluated independently and in any order, as computing fragments is supposed to be a massively parallel operation.

It this context, you have to throw out the concept of 'previous' sample values and replace it with 'nearby' values.