A growing number of studies indicate that aspects of psychology and cognition influence network structure, but much remains to be learned about how network information is stored and retrieved from memory. Are networks recalled as dyads, as triads, or more generally as sub-groups? We employ an experimental design coupled with exponential random graph models to address this issue. We find that respondents flexibly encode social information as triads or groups, depending on the network, but not as dyads. This supports prior research showing that networks are stored using “compression heuristics”, but also provides evidence of cognitive flexibility in the process of encoding relational information.