Described are methods and apparatuses, including computer program products, for personalizing media content. A server determines content data likely to be requested by users, and generates common sets of information using the content data. The server receives a request for a digital media stream from a client device, and generates a first set of frames which include content data specific to the user and keys corresponding to a selected common set of information. The server combines the first set of frames and the requested stream to generate a personalized stream. The server transmits the personalized stream to a downstream device, which generates a second set of frames using content data corresponding to the one or more keys. The downstream device combines the second set of frames and the personalized stream to generate an updated stream, and transmits the updated stream to the client device.