Aspects of the present disclosure provide techniques for efficient location tracking. Embodiments include receiving a device location from a mobile device. Embodiments include identifying a plurality of region definitions and selecting a set of region definitions from the plurality of region definitions based on a proximity of a location of each region definition of the plurality of region definitions to the device location. Embodiments include generating a provisional region definition based on a location of a region definition of the set of region definitions that is farthest from the device location and including the provisional region definition in the set of region definitions. Embodiments include providing the set of region definitions to the mobile device for provisioning and refraining from requesting device locations from the mobile device until receiving a notification from the mobile device that the mobile device has exited a provisional region defined by the provisional region definition.