Systems, methods, and computer-readable media are described for providing improved video or image encoding, including adaptive prediction structures for encoding video frames. In some examples, systems, methods, and computer-readable media can include obtaining a sequence of frames; determining, based on frame statistics associated with a first frame in the sequence of frames, a prediction structure for encoding the sequence of frames, the prediction structure defining an order in which frames in the sequence of frames are encoded and a prediction distance representing a maximum distance permitted between referencing frames and reference frames in the sequence of frames, and the frame statistics indicating an amount of motion in the first frame. The systems, methods, and computer-readable media can also include encoding one or more of the sequence of frames based on the prediction structure.