VP9 is an open-source video codec released by Google. It introduces superblocks (SBs) of size 64 × 64, and uses a recursive decomposition scheme to break them all the way down to 4 × 4 blocks. This provides a large efficiency gain for VP9. However, it also brings large computational complexity when encoding because of the rate distortion (RD) optimization on prediction blocks. This paper proposes a method that can early terminate the block partitioning process based on the information of the current block. We first model the early termination decision as a binary classification problem. Second, to solve this classification problem, a weighted linear Support Vector Machine (SVM) is trained whose weights are determined by the RD cost increase caused by misclassification. Finally, we model the parameter selection of the SVM as an optimization problem, which can enable us to control the trade-off between time saving and RD cost increase. Experimental results on standard HD data shows that the proposed method can reduce the complexity of partitioning prediction blocks while maintaining comparable coding performance - The Bjøntegaard delta bit rate is ∼1.2% for ∼30% encoding time reduction.