Multi-label classification is the task where a single instance may belong to multiple classes simultaneously. The Label Powerset approach (LP) allows to apply Inductive Conformal Prediction (ICP) on multi-label classification tasks, by considering each label set as a single class and by assigning a non-conformity score to each of them. The construction of the prediction set \(\mathcal {C}\) requires selecting all the label sets –represented as binary vectors– that satisfy a given conformity criterion. Since the number of possible outputs is exponentially growing with the number of classes, constructing \(\mathcal {C}\) by testing the conformity criterion on all cases is unaffordable. We propose an algorithm that efficiently computes \(\mathcal {C}\) , even in the difficult case where the non-conformity score involves label interactions. It is based on a customized partial order relation on the set of binary vectors coupled with a monotone lower bound of the non-conformity score. Our tests confirm the algorithm’s efficiency, even with a high class count.