Effective collective response in multi-agent systems critically depends on suitable information transfers among agents, and thus on the topology of their interaction network. Here, we present an archetypal model of distributed decision-making—the leader-follower linear consensus—and discuss how the network topology affects the collective capacity of the system to follow a dynamic driving signal (the “leader”). The collective frequency response obtained for a range of network topologies and system sizes is used to uncover the nontrivial relationship between optimal topology and frequency of the driving signal. Interestingly, the response is optimal when each individual interacts with a certain number of agents which decreases monotonically with the frequency and, for large enough systems, is independent of the number of agents. This phenomenology is also investigated in experiments of collective motion using a swarm of land robots. The emergent collective response to both a slow- and a fast-changing leader is measured and analyzed for a range of interaction topologies. These results have far-reaching practical implications for the design and understanding of distributed systems, since they highlight that a dynamic rewiring of the interaction network is paramount to the effective collective operations of multi-agent systems at different time-scales.