While Large Language Models (LLMs) excel at complex reasoning, they often produce factually unreliable outputs due to hallucinations. Knowledge Graphs (KGs) can mitigate this by providing structured factual knowledge, however, their effective integration remains an open problem. Existing methods for Knowledge Graph Question Answering (KGQA) often suffer from insufficient guidance in their reasoning process and incomplete exploration of the knowledge graph, leading to suboptimal performance on complex queries. We introduce Consensus-on-Graph (CoG), a new framework that fundamentally addresses these issues. CoG innovates by employing an LLM to first decompose questions into an execution plan with clear task intents. It then executes these tasks, leveraging a novel consensus decision mechanism to efficiently prune the search space with minimal LLM calls. This plan-driven, consensus-based approach enhances both the precision of reasoning and the overall scalability of the system. Our extensive evaluations on four benchmark datasets confirm that CoG not only achieves state-of-the-art performance, but also demonstrates significant improvements in query efficiency, substantially reducing LLM interaction costs over existing baselines. Our code is available at https://github.com/cskyan/CoG .