A media stream delivery system encodes numerous media streams into media stream fragments. The media stream delivery system may encode each media stream into a number of variants each having different resolutions, frame rates, audio quality levels, etc. Devices access the media stream fragments from a fragment server in order to reconstruct a particular media stream for playback. A device may perform caching of media stream fragments so that particular fragments need not be accessed from a fragment server. The device monitors and analyzes media streams and viewing characteristics to intelligently select fragments that will likely be needed again, such as fragments associated with repeated advertisements, introduction sequences, and end sequences.