Gene regulatory networks underlie every aspect of life; better understanding their assembly would better our understanding of evolution more generally. For example, evolutionary theory typically assumed that low-fitness intermediary pathways are not a significant factor in evolution, yet there is substantial empirical evidence of compensatory mutation. Here we revise theoretical assumptions to explore the possibility that compensatory mutation may drive rapid evolutionary recovery. Using a well-established in silico model of gene regulatory networks, we show that assuming only that deleterious mutations are not fatal, compensatory mutation is surprisingly frequent. Further, we find that it entails biases that drive the evolution of regulatory pathways. In our simulations, we find compensatory mutation to be common during periods of relaxed selection, with 8-15% of degraded networks having regulatory function restored by a single randomly-generated additional mutation. Though this process reduces average robustness, proportionally higher robustness is found in networks where compensatory mutations occur close to the deleterious mutation site, or where the compensatory mutation results in a large regulatory effect size. This location- and size-specific robustness systematically biases which networks are purged by selection for network stability, producing emergent changes to the population of regulatory networks. We show that over time, large-effect and co-located mutations accumulate, assuming only that episodes of relaxed selection occur, even very rarely. This accumulation results in an increase in regulatory complexity. Our findings help explain a process by which large-effect mutations structure complex regulatory networks, and may account for the speed and pervasiveness of observed occurrence of compensatory mutation, for example in the context of antibiotic resistance, which we discuss. If sustained by in vitro experiments, these results promise a significant breakthrough in the understanding of evolutionary and regulatory processes.