In an experimental study, we test the hypothesis that constitutive properties of social interaction - such as diversity in cognitive styles, knowledge and experience - enhance cognitive processes of abstraction. Through three sessions, individuals and dyads categorized aliens based on combinations of features such as the shape and color of their body parts. We manipulated relations among the features to elicit increasingly complex categories. Furthermore, to assess the character of participants’ evolving categories, after each training session they were presented to a new test set of aliens that differed in appearance, but shared relations among features with aliens from the training set. We found that dyads outcompete individuals in categorization accuracy across levels of complexity. We also found that this effect is due to the more abstract and rule-based character of dyads emerging representations as evidenced by their performance on test items.