A method comprises associating at least one cache replacement granularity value with a given one of a plurality of content streams comprising a number of segments, receiving a request for a given segment of the given content stream in a network element, identifying a given portion of the given content stream which contains the given segment, updating a value corresponding to the given portion of the given content stream, and determining whether to store the given portion of the given content stream in a memory of the network element based at least in part on the updated value corresponding to the given portion. The at least one cache replacement granularity value represents a given number of segments, the given content stream being separable into one or more portions based at least in part on the at least one cache replacement granularity value.