Humans and animals routinely generalize their behavior to situations they have never encountered before, often by understanding them in terms of familiar components arranged in unfamiliar combinations. This kind of compositional generalization is thought to be a cornerstone of intelligent behavior. Uncovering the underlying neural mechanisms is a long-standing challenge in computational neuroscience, and both theoretical and experimental works have suggested that subjects generalize in part through learning a representation that encodes the compositional structure (Whittington et al., 2020; Ito et al., 2022). However, some compositional tasks can also be solved by simpler linear readout models with a fixed representation (Lippl et al., 2024). Thus, it has remained unclear when representation learning is actually necessary for compositional generalization. To address this gap, we present a general theory of compositional generalization in linear readout models with fixed, nonlinearly mixed representations. We find that these models are constrained to compositional generalization strategies that weight different representational components and add them together ("conjunction-wise additivity"). While a surprisingly broad range of compositional tasks can be solved with this simple mechanism, it also imposes fundamental restrictions: for example, linear readout models are unable to transitively generalize on equivalence relations. We then show that even for conjunction-wise additive tasks, generalization can be highly sensitive to representational geometry and training data. Finally, we show that representation learning in neural networks enables them to generalize on transitive equivalence by learning an abstract relational representation. Overall, our work clarifies how representational geometry and task statistics influence compositional generalization, and when representations that encode the task structure are necessary for successful generalization. This has important practical implications: in particular, empirical studies should design non-additive tasks to investigate the importance of representation learning for compositional generalization.