Abstract Users often have very specifific visual content in mind that they are searching for. The most natural way to communicate this content to an image search engine is to use keywords that specify various properties or attributes of the content. A naive way of dealing with such multi-attribute queries is the following: train a classififier for each attribute independently, and then combine their scores on images to judge their fifit to the query. We argue that this may not be the most effective or effificient approach. Conjunctions of attribute often correspond to very characteristic appearances. It would thus be benefificial to train classififiers that detect these conjunctions as a whole. But not all conjunctions result in such tight appearance clusters. So given a multi-attribute query, which conjunctions should we model? An exhaustive evaluation of all possible conjunctions would be time consuming. Hence we propose an optimization approach that identififies benefificial conjunctions without explicitly training the corresponding classififier. It reasons about geometric quantities that capture notions similar to intra- and inter-class variances. We exploit a discriminative binary space to compute these geometric quantities ef- fificiently. Experimental results on two challenging datasets of objects and birds show that our proposed approach can improve performance signifificantly over several strong baselines, while being an order of magnitude faster than exhaustively searching through all possible conjunctions.