Dominance hierarchies are group-level properties that emerge from the aggression of individuals. Although individuals can gain critical benefits from their position in a hierarchy, we do not understand how real-world hierarchies form. Nor do we understand what signals and decision-rules individuals use to construct and maintain hierarchies in the absence of simple cues such as size or spatial location. A study of conflict in two groups of captive monk parakeets (Myiopsitta monachus) found that a transition to large-scale order in aggression occurred in newly-formed groups after one week, with individuals thereafter preferring to direct aggression more frequently against those nearby in rank. We consider two cognitive mechanisms underlying the emergence of this order: inference based on overall levels of aggression, or on subsets of the aggression network. Both mechanisms were predictive of individual decisions to aggress, but observed patterns were better explained by rank inference through subsets of the aggression network. Based on these results, we present a new theory, of a feedback loop between knowledge of rank and consequent behavior. This loop explains the transition to strategic aggression and the formation and persistence of dominance hierarchies in groups capable of both social memory and inference.