Techniques to efficiently deliver interactive program guide (IPG) to a number of terminals. Each IPG page can be decomposed into a guide portion that is specific to each IPG page and a background portion that is common for all IPG pages. The background portion can be further decomposed into a time-varying video portion and other static portions. In one method for regenerating a selected IPG page, packets with a first PID for a first sequence of pictures having included therein one or more slices defined for at least a time-varying portion (e.g., the video portion) retrieved and decoded. Packets with a second PID for a second sequence of pictures having included therein one or more slices defined for at least a portion specific to the selected IPG page (e.g., the guide portion) are also retrieved and decoded. The second sequence can be coded with one I, P, or B picture for each GOP, and can be combined as and replaces an I, P, or B picture, respectively, in the first sequence or the last picture in the GOP. The second sequence can also be coded as a one-picture GOP that can replace a B-picture, or be inserted between pair of pictures, in the first sequence.