Complex problems in science, business, and engineering typically require some tradeoff between exploitation of known solutions and exploration for novel ones, where, in many cases, information about known solutions can also disseminate among individual problem solvers through formal or informal networks. Prior research on complex problem solving by collectives has found the counterintuitive result that inefﬁcient networks, meaning networks that disseminate information relatively slowly, can perform better than efﬁcient networks for problems that require extended exploration. In this paper, we report on a series of 256 Web-based experiments in which groups of 16 individuals collectively solved a complex problem and shared information through different communication networks. As expected, we found that collective exploration improved average success over independent exploration because good solutions could diffuse through the network. In contrast to prior work, however, we found that efﬁcient networks outperformed inefﬁcient networks, even in a problem space with qualitative properties thought to favor inefﬁcient networks. We explain this result in terms of individual-level explore-exploit decisions,which we ﬁndwereinﬂuenced by the network structure as well as by strategic considerations and the relative payoff between maxima. We conclude by discussing implications for real world problem solving and possible extensions.