Simplicity guides the discovery and use of compositionality

Human cognition derives great power from compositionality, often formalized through probabilistic Languages of Thought. However, identifying useful compositional representations is computationally demanding, requiring search over vast, combinatorial hypothesis spaces. Simplicity biases are a key signature of human behaviour in such settings, however many forms of simplicity are unreasonably complex to compute. Across three maze-navigation experiments, we examined how people generate and deploy compositional hypotheses under time pressure (Exp.~1), without instruction (Exp.~2), and in statistically matched non-compositional environments (Exp.~3). Through both behavioural analyses and computational modeling, we show that behaviour was best predicted in all settings by a novel heuristic measure of fragment simplicity. Simplicity in this form avoids the need to identify globally minimal expressions, and was both robust to time pressure and generally accelerated response times. This pattern was observed at multiple scales of behaviour, for both individual actions and abstract sequences of spatial primitives (templates), with participants exhibiting a robust bias towards simpler hypotheses than warranted by the structure of the mazes. Together, our results suggest that by adopting a heuristic form of simplicity, we overcome the difficulty of generating compositional hypotheses.