  The accurate predictions and principled uncertainty measures provided by GP
regression incur O(n^3) cost which is prohibitive for modern-day large-scale
applications. This has motivated extensive work on computationally efficient
approximations. We introduce a new perspective by exploring robustness
properties and limiting behaviour of GP nearest-neighbour (GPnn) prediction. We
demonstrate through theory and simulation that as the data-size n increases,
accuracy of estimated parameters and GP model assumptions become increasingly
irrelevant to GPnn predictive accuracy. Consequently, it is sufficient to spend
small amounts of work on parameter estimation in order to achieve high MSE
accuracy, even in the presence of gross misspecification. In contrast, as n
tends to infinity, uncertainty calibration and NLL are shown to remain
sensitive to just one parameter, the additive noise-variance; but we show that
this source of inaccuracy can be corrected for, thereby achieving both
well-calibrated uncertainty measures and accurate predictions at remarkably low
computational cost. We exhibit a very simple GPnn regression algorithm with
stand-out performance compared to other state-of-the-art GP approximations as
measured on large UCI datasets. It operates at a small fraction of those other
methods' training costs, for example on a basic laptop taking about 30 seconds
to train on a dataset of size n = 1.6 x 10^6.
