Collaborators generally coordinate their activities through communication, during which they negotiate a shared lexicon for activity-related objects. This social-pragmatic activity both recruits and affects cognitive and social-cognitive processes ranging from selective attention to perspective taking. We ask whether negotiating reference also facilitates category learning or might private verbalization yield comparable facilitation? Participants in three referential conditions learned to classify imaginary creatures according to combinations of functional features -- nutritive and destructive -- that implicitly defined four categories. Remote partners communicated in the Dialogue condition. In the Monologue condition, participants recorded audio descriptions for their own later use. Controls worked silently. Dialogue yielded better category learning, with wider selective attention. Monologue offered no benefits over working silently. We conclude that negotiating reference compels collaborators to find communicable structure in their shared activity; this shareability constraint accelerates category learning and likely provides much of the benefit recently ascribed to learning labeled categories.