When Should We Build the Graph? An Amortized Pareto View of Demand-Driven Knowledge Graph Construction

Knowledge graph construction for GraphRAG has traditionally been organized around documents: graphs are materialized offline over a corpus, or updated as new documents arrive. Many retrieval workloads instead reveal information need only through a query stream, raising a complementary question: when should graph structure be constructed? We introduce demand-driven graph construction, in which each query triggers materialization of only the relevant semantic neighborhood; that structure persists in a shared graph and is reused by later queries, so growth is driven by demand rather than document arrival. This formulation treats graph construction as an amortized optimization problem balancing semantic construction cost, graph reuse, and downstream QA quality rather than maximizing graph completeness upfront. We formalize the construction policy and its amortized objective, instantiate it using a pay-as-you-go entity knowledge graph, and introduce workload-level measures that characterize graph growth and stabilization over persistent query streams. Experiments on MuSiQue, HotpotQA, and 2WikiMultiHopQA demonstrate that demand-driven graph construction consistently approaches the performance of fully materialized knowledge graphs while substantially reducing semantic construction cost. We further show that explicit relation extraction is essential for realizing this quality–cost frontier and that the preferred operating point depends on the reasoning characteristics of the workload. These results suggest that GraphRAG systems should be evaluated not only by downstream accuracy, but also by when and where semantic structure is constructed under evolving demand.