Mutualisms such as those between flowering plants and their pollinators are common in nature. Yet, understanding their persistence in the face of cheaters and identifying the mechanisms behind their stunning diversity provide formidable challenges for evolutionary biologists. To shed light into these questions, we introduce an individual-based model of two coevolving species in which individuals of one species use a Boolean circuit to discriminate between cooperators and cheaters in the other species. This conveys the idea that interactions are often mediated by complex biological processes rather than simple trait matching, as often assumed in models of coevolution. Our results show that cheating promotes diversification and complex discrimination mechanisms at the cost of a higher risk for mutualism to collapse. This result is mediated by an inverse relationship between mutational robustness and organismal complexity.