A system and method are described below for encoding interactive low-latency video using interframe coding. For example, one embodiment of a computer-implemented method for performing video compression comprises: detecting a maximum data rate of a communication channel between a server and a client; dynamically selecting a tile size for encoding a sequence of images based on the detected maximum data rate; logically subdividing each of the sequence of images into a plurality of tiles sized according to the selected tile size, each of the tiles having a defined position within each of the sequence of images; encoding each tile within each image of the sequence of images using a first compression format or a second compression format, wherein a tile at a particular position of a first image in the sequence of images is encoded using the first compression format and the same tile within one or more subsequent images is encoded using the second compression format.