When animals interact with complex environments, their neural circuits must separate overlapping patterns of activity that represent sensory and motor information. Pattern separation is thought to be a key function of several brain regions, including the cerebellar cortex, insect mushroom body, and dentate gyrus. However, recent findings have questioned long-held ideas on how these circuits perform this fundamental computation. Here, we re-evaluate the functional and structural mechanisms underlying pattern separation. We argue that the dimensionality of the space available for population codes representing sensory and motor information provides a common framework for understanding pattern separation. We then discuss how these three circuits use different strategies to separate activity patterns and facilitate associative learning in the presence of trial-to-trial variability. Pattern separation is a fundamental neural computation thought to facilitate associative learning. Cayco-Gajic and Silver review recent theoretical and experimental advances on the key determinants of pattern separation in the cerebellar cortex, insect mushroom body, and dentate gyrus.