Prior work has shown the value of changing application fidelity to adapt to varying resource levels in a mobile environment. Choosing the right fidelity requires us to predict its effect on resource consumption. In this paper, we describe a history-based mechanism for such predictions. Our approach generates predictors that are specialized to the hardware on which the application runs, and to the specific input data on which it operates. We are able to predict the CPU consumption of a complex graphics application to within 20% and the energy consumption of fetching and rendering web images to within 15%.