A computer-implemented method for provisioning frequently used image segments from caches, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising: storing a representation and a use counter for an image segment that is hosted on a storage system in a list of representations and use counters for image segments hosted on the storage system, wherein the representation comprises any data that uniquely identifies the image segment; incrementing a current value of the use counter for the image segment in the list of data and use counters each time a call, to a provisioning system for virtual machines, includes information about the image segment; incrementing a current value of the use counter for the image segment in the list of representations and use counters each time the image segment is provisioned from the storage system by the provisioning system for virtual machines; determining that the current value of the use counter for the image segment has met a predetermined threshold for frequent image-segment provisioning; hosting the image segment in a cache that enables quicker provisioning by the provisioning system for virtual machines than the storage system enables; provisioning, by the provisioning system for virtual machines, the image segment from the cache in response to a request to provision the image segment; and removing the image segment from the cache in response to determining that the current value of the use counter for the image segment no longer meets the predetermined threshold for frequent image-segment provisioning, wherein the current value of the use counter is lower than a predetermined lower threshold for two consecutive provisioning periods. storing a representation and a use counter for an image segment that is hosted on a storage system in a list of representations and use counters for image segments hosted on the storage system, wherein the representation comprises any data that uniquely identifies the image segment; incrementing a current value of the use counter for the image segment in the list of data and use counters each time a call, to a provisioning system for virtual machines, includes information about the image segment; incrementing a current value of the use counter for the image segment in the list of representations and use counters each time the image segment is provisioned from the storage system by the provisioning system for virtual machines; determining that the current value of the use counter for the image segment has met a predetermined threshold for frequent image-segment provisioning; hosting the image segment in a cache that enables quicker provisioning by the provisioning system for virtual machines than the storage system enables; provisioning, by the provisioning system for virtual machines, the image segment from the cache in response to a request to provision the image segment; and removing the image segment from the cache in response to determining that the current value of the use counter for the image segment no longer meets the predetermined threshold for frequent image-segment provisioning, wherein the current value of the use counter is lower than a predetermined lower threshold for two consecutive provisioning periods.