Assistants that answer from a knowledge graph (a database of facts stored as entity–relation–entity triples) have a predictable failure. When the one fact they need is missing, they either stop or invent something. That trade-off is sharp. Constraining a language model to output only paths that exist in the graph makes every reasoning step verifiable, but it also makes a missing fact impossible to recover. Loosening the constraint brings back hallucination. In a conversation there is a third option that batch question answering lacks: the system can set the blocked task aside, ask the person something useful, keep talking about whatever the person raises in the meantime, and return to the task when the gap is closed. Older dialogue systems that planned their turns explicitly treated this kind of pause-and-resume as their core job. Modern graph-grounded systems never do it.
The claim of this note is that a broken graph traversal produces a precise, structured signal. The signal says which hop failed, from which entity, along which relation, and toward what kind of answer. That signal is a better trigger for clarification than the model's own uncertainty, and it can be routed to whichever party can actually supply the fact: the graph through rule inference, outside text, or the user. We propose to turn each blocked hop into a "gap record" that sits on an explicit dialogue agenda. A small set of agents resolves or routes the record. We then test whether this beats strong monolithic and multi-agent baselines on accuracy, on asking the user only when the user can answer, and on resuming threads after digressions.
Core Claim
Two specific predictions make the idea testable.
The first prediction is that clarification triggered by a gap record keeps the same precision as the conversation gets longer, while triggers based on predictive uncertainty lose precision. Aligning Predictive Uncertainty with Clarification Questions in Grounded Dialog uses entropy and ensemble disagreement to decide when to ask. It finds near-perfect detection on single-turn ambiguity in IGLU-MINI, a Minecraft building benchmark, at "92-95%". On multi-turn data, however, separation between clear and ambiguous turns falls to an AUC "between 0.56 and 0.65", because uncertainty rises with dialogue history length whatever the instruction says. A failed graph lookup does not depend on how long the conversation has been, so it should not show this drift.
The second prediction is that routing gaps by type beats both "always fall back to text and the model's own memory" and "always ask the user". We distinguish three kinds of gap. A world-fact gap is something the user is unlikely to know, such as a missing release-year edge. A linking or intent gap is something only the user can resolve, such as which of two entities named "Paris" they meant, or which constraint matters to them. A derivable gap is one that can be inferred from other paths, such as deriving "uncle" from "parent" followed by "sibling". Each kind has a different best resolver.
Relation to Prior Work
The dialogue side supplies the control structure. Plan Revision in Person-Machine Dialogue and Planning for Problem Formulation in Advice-Giving Dialogue maintain an expectation stack, which records the replies the system expects from the user. When a user utterance does not match those expectations, they apply revision metaplans: rules that either push an embedded sub-dialogue or reorder the remaining agenda. Freedman's APE planner adds reactive operators. Its Retry-at operator backtracks to an earlier choice point, and its Prune-replace operator swaps out stale goals. Generating Interactive Explanations separates choosing what to say from managing the conversation. We reuse these operators almost directly. What these systems lacked was a source of interruption other than the user and a way to scale past hand-authored recipes. We supply both. The interruption comes from the graph executor, and the stack entries come from the structured gap record rather than from authored recipes.
The incompleteness side supplies the resolvers, and it motivates the work by showing that the problem has so far been framed only as offline question answering. Debate over Mixed-knowledge (DoM) pairs a graph-querying agent with a text-retrieval agent under a judge agent. It reaches 84.5% Hits@1 on its incomplete-graph benchmark IKGWQ, against 49.5% for the GoG baseline. Its judge falls back to the model's parametric memory when both sources fail and never consults a person. GR-Agent recovers deleted edges by searching for relation-path patterns and grounding them in surviving entities, reaching 0.77 Hits@Any on incomplete FB15k-237 (ToG 0.36, PoG 0.43). We use a GR-Agent-style path explorer as the resolver for derivable gaps and a DoM-style retriever as the resolver for world-fact gaps. The new piece is the decision of which resolver to use, together with an option to defer the gap and keep the conversation going.
The graph-grounded dialogue side constrains the design. Graph-constrained Reasoning (GCR) shows that decoding through a prefix tree of valid graph paths gives a 100% faithful reasoning ratio, against roughly 48–62% for unconstrained decoding. It also shows that missing facts become unreachable under such decoding. In the same paper, iterative agent methods are about 4.5 times slower and use about 30 times more input tokens than constrained decoding, which is a warning about the cost of multi-agent loops. We therefore keep constrained decoding as the executor, so that a failure is crisp and cheap to detect, rather than replacing it. DialogGSR generates the relevant subgraph turn by turn over multi-turn OpenDialKG dialogues, and SURGE filters out irrelevant neighbours, finding that 87.4% of 1-hop facts around the conversation's entities are irrelevant. Both are single models without an agenda, and both revert to parametric memory when the graph is silent. AGENTiGraph is the closest conversational multi-agent graph system and can insert user-supplied facts into the graph. It handles each request turn by turn, however, with no notion of a paused thread and no reasoning about whether the user is the right source for a given fact.
Research Program
The system has three roles connected by a shared agenda.
The executor parses the current goal and attempts constrained traversal in the style of GCR over the graph. On failure it emits a gap record. The record contains the anchoring entity (or a flag that linking failed), the relation it needed, the expected answer type, the parent goal, and the dialogue turn at which the gap arose.
The resolver classifies the record as derivable, world-fact, or user-resolvable. It runs relation-path search for the first type and text retrieval with a separate checking step for the second. For the third type it returns a question to ask. Every non-user resolution is labelled with its provenance so that the final answer can state which facts came from the graph, from text, or from inference.
The dialogue manager holds the agenda as a stack of threads. It pushes clarification sub-dialogues and lets user digressions push new threads. It applies Retry-at when a resolved gap reopens the parent goal and Prune-replace when the user's reply makes the goal obsolete. When a deferred gap record is resolved, the corresponding thread is popped back onto the agenda.
We do not assume that splitting the system into separate agents is what makes it work. The central ingredient is the gap record and the stack that holds it. Whether isolating these roles in separate agents adds anything beyond a single model that sees the same records is an open question that the ablations below address directly.
The analysis concentrates on three questions. The first is how often each gap type occurs under realistic rather than random deletion. The second is how well the resolver's typing agrees with an oracle that knows which simulated party holds the missing fact. The third is how clarification precision varies with turn index under each trigger mechanism.
Benchmarks
No existing benchmark tests clarification of graph gaps in interactive dialogue, so we build two from resources in the file.
The first, interactive IKGWQ, takes DoM's IKGWQ questions, which contain realistic Freebase gaps derived from Wikipedia updates. Each question's constraints are split across three to six user turns. A user simulator built on a language model holds some facts privately: it knows the intended entity and the user's own constraints, and in an "expert" persona it also knows some domain facts. It injects off-topic digressions at controlled positions.
The second, incomplete OpenDialKG, deletes edges on the gold dialogue walks in OpenDialKG in two ways. One is rule-head deletion in the style of GR-Agent, which by construction leaves derivable gaps. The other is random deletion, which leaves underivable gaps. Deletion rates sweep from 0% to 80%, matching DoM's extreme setting.
Metrics fall into five groups. Answer accuracy is Hits@1 for IKGWQ and knowledge-QA exact match for OpenDialKG. Faithfulness is the fraction of asserted facts traceable to the graph, verified text, or the user. Clarification quality is measured as precision (the share of questions the simulator could answer) and recall (the share of user-resolvable gaps that the system actually asked about). Thread resumption is the share of interrupted goals completed after a digression. Cost covers turns, tokens, and wall-clock time.
Baselines
The naive reference point is constrained decoding in the GCR style with no recovery, run per turn over the conversation so far. Its accuracy on gap-bearing items should approach zero by construction. It sets the floor and confirms that the deletion protocol actually blocks the answers. For context, GCR reports 92.6 Hit on complete WebQSP.
The strongest existing method for incompleteness is DoM. Its reported 84.5% Hits@1 on single-turn IKGWQ comes from Debate over Mixed-knowledge. We run it with the same backbone model, the same retrieval corpus, and the same per-dialogue token budget. In the interactive setting we give it the concatenated history at each turn. We also check that our reimplementation reproduces approximately the reported single-turn number before trusting any interactive comparison. Beating DoM means higher final Hits@1 on interactive IKGWQ at equal or lower tokens, with the margin concentrated on user-resolvable gaps. On derivable and world-fact gaps we expect parity, and any loss there would count against the proposal.
The strongest existing graph-grounded dialogue model is DialogGSR, which reports knowledge-QA exact match of 54.61 and path@1 of 28.96% on complete OpenDialKG in Generative Subgraph Retrieval for Knowledge Graph-Grounded Dialog Generation. We reproduce it on complete OpenDialKG as a sanity check and then evaluate it at each deletion rate. Beating it means a slower decline in exact match as deletion rises and a lower rate of unsupported assertions.
The strongest competitor for the clarification trigger is uncertainty-based asking. It uses ensemble disagreement over the backbone's next-hop prediction, following Eberhard et al., with its threshold tuned on the same development split as our resolver. No result on graph-grounded dialogue for this method is reported on Lacuna. The comparison is clarification precision as a function of turn index.
Two ablations isolate the key ingredient. The first, the single-agent ablation, gives one model the same tools and the same gap records and stack in its prompt, but no role separation. The second, the no-record ablation, keeps the multi-agent structure but removes the structured gap record, so that agents see only free-text failure messages. If the single-agent ablation matches the full system, the contribution is the record and the stack, not the multi-agent design, and we would report it that way.
Why not just…?
Why not just prompt a strong single model to ask the user whenever it lacks information? This is the most serious threat. The single-agent ablation is built to settle it at two strengths: once with the gap records in the prompt, and once with the plain instruction alone. Prior evidence points against the plain version. Zero-shot GPT-4o trails AGENTiGraph's decomposed pipeline on graph interaction, at 77.12% against 90.45% execution success. None of that evidence concerns clarification, though. If the plain prompt matches us on clarification precision and thread resumption, the contribution narrows to the executor's failure signal, and the note will say so.
Why not just let a DoM-style judge fall back to retrieval and parametric memory without bothering the user? For world-fact and derivable gaps, this is close to what our resolver does, and we expect parity there. The difference lies in linking and intent gaps, such as an ambiguous entity or an unstated constraint. No corpus can resolve these, so falling back amounts to guessing. Splitting the IKGWQ results by gap type shows whether such gaps are common enough to matter. If they make up only a small fraction of realistic gaps, the case for asking the user weakens accordingly.
Why not just trigger clarification from the model's own uncertainty? The multi-turn AUC of 0.56–0.65 reported by Eberhard et al. already suggests that the signal degrades with history length. Our turn-indexed precision curve tests whether the degradation carries over to graph dialogue and whether gap-record triggers avoid it. A fair outcome could also favour a hybrid that uses the gap record to decide whether to ask and uncertainty to decide what to ask. We would evaluate that hybrid rather than dismiss it.
Why not just fine-tune an end-to-end dialogue model on incomplete-graph dialogues? GR-Agent reports that training-free agentic reasoning matches or beats KGQA-tuned models such as RoG and GNN-RAG when target links are deleted. This suggests that tuning learns the shortcuts of a particular graph. We do not run a fine-tuning baseline on the interactive benchmarks, because no interactive training data exists. We treat this as a stated limitation rather than a refuted alternative.
Decisive Checks
Three results would decide the question. The first is the turn-indexed clarification precision curve: we expect a flat line for gap-record triggers and a declining one for uncertainty triggers. The second is final accuracy on user-resolvable gaps in interactive IKGWQ against DoM at matched token budget. The third is thread resumption after injected digressions, compared with the no-stack ablation. If the first two hold but the single-agent ablation ties the full system, we will report a simpler finding: the useful object is the graph's own account of what is missing, carried on an explicit agenda. If gap typing agrees poorly with the oracle, routing is the bottleneck. We would then study it on its own before claiming any system-level benefit.
References
- Aligning Predictive Uncertainty with Clarification Questions in Grounded Dialog
- Plan Revision in Person-Machine Dialogue
- Planning for Problem Formulation in Advice-Giving Dialogue
- Plan-Based Dialogue Management in a Physics Tutor
- Generating Interactive Explanations
- Debate over Mixed-knowledge: A Robust Multi-Agent Reasoning Framework for Incomplete Knowledge Graph Question Answering
- GR-Agent: Adaptive Graph Reasoning Agent under Incomplete Knowledge
- Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models
- Generative Subgraph Retrieval for Knowledge Graph-Grounded Dialog Generation
- Knowledge-Consistent Dialogue Generation with Language Models and Knowledge Graphs
- AGENTiGraph: A Multi-Agent Knowledge Graph Framework for Interactive, Domain-Specific LLM Chatbots
- OpenDialKG: Explainable Conversational Reasoning with Attention-based Walks over Knowledge Graphs