Intelligence relies on our ability to find appropriate sequences of decisions in complex problem spaces. The efficiency of a problem solver depends on the speed of its individual decisions and the number of decisions it can explore in parallel. It remains unknown whether the primate brain can consider multiple decisions at the same time. We therefore trained monkeys to navigate through a decision tree with stochastic sensory evidence at multiple branching points and recorded neuronal activity in visual cortical areas V1 and V4. We found a first phase of decision making in which neuronal activity increased in parallel along multiple branches of the decision tree. This was followed by an integration phase where the optimal overall strategy crystallized as the result of interactions between local decisions. The results reveal how sensory evidence is integrated efficiently for hierarchical decisions and contribute to our understanding of the brain mechanisms that implement complex mental programs.