We discuss the problem of parity tree selection for lossless compaction of the output responses of a circuit. Earlier methods assume off-chip storage of the correct compacted responses and therefore minimize the number of necessary parity trees. In contrast, our method targets on-chip generation of the correct compacted responses and therefore minimizes the actual implementation cost of the corresponding parity prediction functions. We present a systematic search approach that exploits the correlation between the hardware cost of a function and its entropy, in order to select parity trees that minimize the incurred cost, while achieving lossless compaction. Experimental results demonstrate that our method achieves significant hardware reduction over methods that minimize the number of parity trees.