Reverse-geocoding performs an important function for many mobile applications, converting geographic latitude & longitude coordinates into real-world physical locations. While the resulting reverse-geocoded locations can be invaluable for many mobile apps, the process comes at a high cost: either battery power must be expended to invoke a cloud server, or local storage must be used to keep detailed cartographic data to run the process on the phone. In our work we reduce these costs by exploiting the user's geolocality and perform on-smartphone caching of reverse-geocoded locations obtained from calls to the cloud. To that end, we configured three different geospatial region-definition schemes (convex hulls, radial boundaries, and our own cartographic sparse hashes), implemented Android software to perform this caching, and explored cache propagation via preemptive pushing. We evaluated our system using a data set of 1.1 million geotagged photos taken with smartphones and show that our caching: (1) reduces the number of cloud server calls by over 70% for neighborhood granularity and by over 85% for city granularity; and (2) consumes less than 1MB of hash-encoded data even for a complete precomputation of the San Francisco Bay Area.