Humans form social coalitions in every society on earth, yet we know very little about how social group boundaries are learned and represented. We derive predictions from a computational model of latent structure learning to move beyond explicit category labels and mere similarity as the sole inputs to social group representations. Four experiments examine (a) how evidence for group boundaries is accumulated in a consequential social context (i.e., learning about others’ political values), (b) to what extent learning about these boundaries drives one’s own choices as well as attributions about other agents in the environment, and © whether these latent groups affect choice even in the presence of group labels that contradict the latent group structure. Our results suggest that people integrate information about how agents in the environment relate to one another in addition to oneself to infer social group structure. We argue that this mechanism is a plausible explanation of other theories of social relations-for example, balance theory.