Abstract kNN embedding methods, such as the state-ofthe-art LM-kNN and SLEEC, have shown impressive results in multi-label learning. Unfortunately, these approaches suffer expensive computation and memory costs in large-scale settings. To fill this gap, this paper proposes a novel deep binary prototype compression (DBPC) for fast multi-label prediction. DBPC compresses the database into a small set of short binary prototypes, and uses the prototypes for prediction. The benefit of DBPC comes from two aspects: 1) The number of distance comparisons is reduced in the prototype; 2) The distance computation cost is significantly decreased in the Hamming space. We propose to jointly learn the deep latent subspace and binary prototypes within a unified framework. The encoding and decoding neural networks are employed to make deep binary prototypes well represent the instances and labels. Extensive experiments on several large-scale datasets demonstrate that DBPC achieves several orders of magnitude lower storage and prediction complexity than state-of-the-art multi-label methods, while achieving competitive accuracy.