ONTOS: Candidate-First Knowledge Graph Question Answering with Ontology-Constrained Program Synthesis

Knowledge graph question answering requires translating a question's intent into executable programs over a large graph schema. Direct query generation must resolve schema identifiers and query structure, while LLM-guided exploration repeatedly interleaves planning with graph traversal. We present Ontos, an ontology-driven, candidate-first framework that separates conceptual planning from initial program construction. An LLM produces an abstract derivation sketch without graph identifiers. A dual-track synthesizer then combines sketch-guided, schema-filtered search with type-checked instantiation of program structures from annotated training questions. The resulting candidates are executed and presented to the LLM for selection, with low-confidence selections routed to a bounded, ontology-grounded program-repair stage. Across 6,159 evaluation questions from CWQ, WebQSP and GrailQA, Ontos achieves pooled Hits@1 of 83.3%, 87.6% and 89.1% with Qwen2.5-7B, Qwen3.5-9B and Qwen3.5-27B, respectively, without task-specific LLM fine-tuning; on CWQ, all three exceed the results reported for the baselines we compare with, including GPT-4-based agents. With the 27B backbone, repair increases pooled Macro-F1 from 79.2% to 81.6% while processing 26.7% of questions. Stage-level ablations show complementary contributions from the two synthesis tracks. These results support ontology-constrained candidate construction and LLM-based selection as an effective division of work for knowledge graph question answering.