During operant transitive inference experiments, subjects are trained on adjacent stimulus pairs in an implicit linear hierarchy in which responses to higher ranked stimuli are rewarded. Two contrasting forms of cognitive representation are often used to explain resulting choice behavior. Associative representation is based on memory for the reward history of each stimulus. Relational representation depends on memory for the context in which stimuli have been presented. Natural history characteristics that require accurate configural memory, such as social complexity or reliance on cached food, should tend to promote greater use of relational representation. To test this hypothesis, four corvid species with contrasting natural histories were trained on the transitive inference task: pinyon jays, Gymnorhinus cyanocephalus; Clark’s nutcrackers, Nucifraga columbiana; azure-winged magpies, Cyanopica cyanus; and western scrub jays, Aphelocoma californica. A simplified computer model of associative representation displayed a characteristic pattern of accuracy as a function of position in the hierarchy. Analysis of the deviation of each subject’s performance from this predicted pattern yielded an index of reliance on relational representation. Regression of index scores against rankings of social complexity and caching reliance indicated that both traits were significantly and independently associated with greater use of relational representation.