The collective decisions of social insects exemplify how living systems store, process, and propagate information. A keystone of information sharing is recruitment, in which a knowledgeable insect guides one or more naive nestmates. We have applied information theory to reveal the hidden protocols that distinguish the superficially similar tandem run recruitment of termites and Temnothorax ants. We found that information flow is bidirectional in ants, with the leader’s direction predicting that taken by her follower, but the follower’s pausing behavior predicting that of the leader. This is consistent with the leader guiding the follower along a known route, and the follower interposing brief pauses so that she can stop and learn visual cues that she will later use to navigate the same route independently. Termites, in contrast, show information flow strictly from leader to follower, consistent with their use of tandem runs not to teach a route, but simply to keep a newly-mated pair together as they search for a place to nest. This work shows how non-invasive information-theoretic tools can be used to reveal hidden communication protocols that guide complex social interactions.