<p>Sensory experiences are encoded as memories, not as verbatim copies, but through interpretation and transformation. Rate distortion theory frames this process as compression in which irrelevant details are discarded. Despite the successes of approaches based on rate–distortion theory in aligning with empirical findings, these approaches assume that environmental regularities are known and unchanging and that surprising experiences are dismissed. However, the brain’s model of environmental regularities (semantic memory) is continually learned and refined, and surprising events have a pivotal role in this learning. In this Perspective, we offer a normative framework that addresses the interplay between semantic and episodic memory in the context of this computational problem that encompasses memory distortions, curriculum effects and prioritized replay. We propose to consider memory as solving an online structure learning problem, with semantic and episodic memory each having a role. We argue that semantic memory must learn the regularities that enable the efficient encoding of experience and that episodic memory supports this process by preserving surprising experiences in a relatively raw format for later interpretation. This framework opens up avenues towards understanding how adaptive compression and surprise shape the trajectory of learning and memory distortions.</p>