Described herein are classifiers that are used to determine whether or not to partition a block in frame during prediction using recursive partitioning. Blocks of training video frames are encoded using recursive partitioning to generate encoded blocks. Training instances are generated for the encoded blocks that include values of features extracted from each encoded block and a label indicating whether or not the encoded block is partitioned into smaller blocks in the recursive partitioning. The classifiers are trained for different block sizes using the training instances associated with the block size as input to a machine-learning process. When encoding frames of a video sequence, the output of the classifiers determines whether input blocks are partitioned during encoding.