We propose Lebesgue Regression, a non-parametric high-dimensional regression method that gives prediction sets instead of a single predicted value. Lebesgue regression first uses the response Y to bin the data (as in Lebesgue integration). From this binning, we construct prediction scores that lead to distribution freeprediction sets with guaranteed prediction coverage at a pre-specified level 1−α. The method is automatically cautious: outliers and attempts to extrapolate yield empty prediction sets. We demonstrate the method on D31, a spatially complexstructured dataset and the Merck dataset, a high dimensional regression problem.