When a chatbot looks up outside knowledge mid-conversation, it usually builds its search query from the raw transcript or from a rewritten one-line question. That query carries every entity the user mentioned, but not whether the user affirmed it, denied it, or later took it back. "I have stomach pain but no fever, and the nausea went away" becomes a bag of words: pain, fever, nausea. Dense retrievers handle negation poorly. The system then fetches evidence about febrile illness and offers advice built on a symptom the patient explicitly ruled out.
We propose to treat the tracked dialogue state, meaning the running record of which entities are affirmed, denied, uncertain, or superseded, as the control signal for retrieval over a knowledge graph. A knowledge graph here is a network of entities joined by typed relations, with each fact linked back to the text passage it came from. Affirmed entities seed the graph search. Denied entities prune paths that depend on them. Uncertain entities steer retrieval toward evidence that would tell competing explanations apart, which also supplies material for the next clarifying question. The claim is narrow and testable: on turns where the conversation contains negations or revisions, status-aware graph retrieval returns less contradictory context and produces fewer state-violating responses than retrieval driven by a rewritten query, at equal or lower cost.
Core Claim
Three lines of prior work each solve part of this problem, and none combines the parts.
Graph-guided retrieval is the first. KG²RAG extracts triples from a text corpus offline. At query time it finds seed passages by vector search, expands along graph edges with breadth-first search, and prunes with a maximum spanning tree. It reports at least 8% F1 gain on HotpotQA Fullwiki. It is strictly single-turn, so its seeds are a question, not a conversation.
Knowledge-grounded dialogue is the second. SURGE retrieves context-relevant subgraphs for dialogue. It documents that 87% of one-hop facts around dialogue entities on OpenDialKG are irrelevant. It still reads the history as a flat window of utterances, and it searches only one hop.
Medical dialogue systems are the third. MedKP queries the CMEKG knowledge graph for entities extracted from the dialogue and predicts the doctor's next clinical action before generating a reply. It extracts entities without their conversational status, and it does no passage retrieval. DMIE does the opposite: it extracts medical items together with their status (patient-positive, patient-negative, and so on) at 82.54% macro-F1, but it never retrieves or generates anything.
Our contribution sits in the join. Status labels of the DMIE kind become first-class retrieval operators over a KG²RAG-style passage graph, maintained incrementally as the conversation unfolds.
The motivation for caring about noise rather than just recall comes from U-NIAH. It reports that hallucinations surge by over 355% when the noise ratio in retrieved context exceeds 97% at long context lengths, and that reasoning models over-analyze irrelevant retrieved material. Multi-turn dialogue is a natural noise generator: roughly 40% of MedDG consultations are chit-chat according to MedDG. Evidence about denied symptoms is worse than noise, because it contradicts the conversation outright.
Research Program
The system has three parts.
The first part is a state tracker. After each turn it outputs a set of entity anchors in the knowledge graph, each with a status of affirmed, denied, uncertain, or superseded. For the medical setting we train it on MIEACL, the benchmark used by DMIE, collapsing its five labels to our four. We also compare against an LLM prompted to emit the same structure, in the semi-structured JSON style of RA-Rec. That system stores free-text state values and maps them to dense review retrieval, but it has no graph and no explicit polarity.
The second part is the knowledge graph and passage index. For MedDG we use CMEKG, as MedKP does. Because MedKP has no passage layer, we add a Chinese medical text corpus that we construct ourselves and process with KG²RAG's offline triple extraction, so every edge points to its source passage. We report the corpus construction in full, since it is our addition rather than a benchmark resource.
The third part is status-conditioned expansion. It starts from affirmed anchors, expands up to two hops, and scores each candidate path $p$ as
$$s(p) = \mathrm{sim}(p, x_t) + \alpha\,|p \cap A_t| - \beta\,|p \cap D_t| + \gamma\,\mathrm{disc}(p, U_t),$$
where:
- $x_t$ is the current utterance;
- $A_t$, $D_t$ and $U_t$ are the affirmed, denied and uncertain anchor sets at turn $t$;
- $\mathrm{disc}(p, U_t)$ counts the candidate conclusions (diseases, items) currently supported by the state that $p$ links to an uncertain entity, so that it rewards evidence that splits the current hypotheses.
A path whose conclusion requires a denied entity as a premise is removed outright rather than down-weighted. Surviving passages are ordered by spanning-tree pruning as in KG²RAG and passed to the generator. We use ChatGLM3-6B with LoRA so the comparison with MedKP is like-for-like.
Because the state changes by only a few anchors per turn, the explored subgraph is cached. Only the delta is re-expanded: new affirmed anchors are expanded, and paths through newly denied ones are invalidated. We measure whether this keeps per-turn latency near that of single-shot dense retrieval. Latency is the known weakness of LLM-based state tracking, noted for the multi-pass rescoring in RefPyDST.
The second domain is OpenDialKG, using the Freebase graph that SURGE uses. Here statuses are user preferences, which users routinely revise ("actually, not horror"). This tests whether the mechanism is more than a medical trick.
Baselines
The naive reference point is the generator with no retrieval. MedKP reports that direct inference with ChatGLM3-6B on MedDG reaches only 12.41 entity Macro-F1, with a GPT-4-judged hallucination score of 2.60. We rerun this with our prompts so the number is ours, not borrowed.
The strongest existing medical system is MedKP. It reports 31.41 entity Macro-F1 on MedDG, a hallucination score of 1.03, and a consistency score of 6.10. It is the right competitor because it already combines knowledge-graph triples with explicit clinical-action tracking on the same backbone. We reproduce it on the same splits (14,864/2,000/1,000), the same LoRA budget, and the same GPT-4 judge prompt. Beating it means higher entity Macro-F1 and a lower hallucination score on the full test set. The decisive comparison is on the negation-and-revision slice defined below, where we expect a margin well outside seed variance across three runs.
On OpenDialKG the strongest competitor is SURGE, which reports 57.63 KQA F1 against 50.60 for an all-knowledge baseline. We run its released configuration with the same generator size we use.
The most dangerous baseline is conceptual rather than published: an LLM rewrites the dialogue history into a standalone question, which then drives KG²RAG unchanged. No reported result was found on Lacuna for KG²RAG on MedDG or OpenDialKG, so we run it ourselves. It gets the same graph, passage index, top-k budget, and tuning budget, which is a grid over expansion depth and k matched to ours.
Two other references round out the comparison. A long-context baseline concatenates the full history with the top passages from dense retrieval, up to the same token budget. A RA-Rec-style baseline turns a JSON state into a dense query without graph expansion.
Ablations isolate the key ingredient. Keeping the graph but replacing status labels with an unlabeled entity set tests whether polarity, not structure, drives any gain. Removing hard pruning of denied paths, removing the discrimination term ($\gamma = 0$), and disabling the incremental cache each isolate one further component.
Why not just…?
Why not just rewrite the conversation into a standalone query and run graph RAG? This is the real threat. A capable rewriter can write "abdominal pain without fever", and if the retriever honored that, our mechanism would add little. The weak point is the retriever: dense similarity between "without fever" and fever-related passages remains high, and graph expansion from a seed passage about fever reintroduces the denied entity two hops later. We settle this empirically with the rewrite-plus-KG²RAG baseline under the same budget. If it matches us on the negation slice, the contribution reduces to "rewrite well", and we would report that.
Why not just stuff the whole conversation and the documents into a long context? U-NIAH reports that retrieval beats pure long-context processing for 7B/8B models, with an 82.58% win-rate, and that hallucinations rise sharply at extreme noise ratios. Our generator is 6B, so we expect stuffing to lose. We still run it at a matched token budget, because a stronger long-context model could close the gap on short consultations.
Why not just use MedKP's triples and skip passage retrieval? MedKP already reduces hallucination substantially. Triples, however, cannot carry guideline-level conditions such as "if no fever, consider X". Graph vs. Sequence also found that human evaluators preferred text-grounded responses in 60–84% of cases, even though graphs generalize better to unseen topics. Our design uses the graph to select and the text to say. The comparison of MedKP against our system with the passage layer removed shows whether passages earn their cost.
Proposed Experiments
The first decisive check is a counterfactual status flip. For a sample of MedDG test dialogues, we take one affirmed symptom and change the patient's utterance so that it is denied, with all other content held fixed. A status-respecting system should change its retrieved evidence and its predicted entities. For every system we measure the contradiction rate: the fraction of retrieved passages and of generated replies that presuppose the denied entity, judged by GPT-4 against the edited transcript and spot-checked by hand.
The second check is a natural slice. We select MedDG and OpenDialKG test turns whose state, as given by our MIEACL-trained tracker, contains at least one denied or superseded anchor. On that slice we report entity Macro-F1, KQA F1, and hallucination score. On it we expect our method to beat both MedKP and rewrite-plus-KG²RAG. If we see no gain there, the idea fails, regardless of averages over the full set.
The third check is retrieval noise: the fraction of retrieved facts that are irrelevant to or contradicted by the gold state. We track it across turn depth to see whether status-aware pruning keeps noise from growing as conversations lengthen, which is the failure U-NIAH warns about.
We also report per-turn latency with and without the incremental cache. Finally, we propagate tracker error by rerunning all comparisons with gold MIEACL-style statuses versus predicted ones. This tells us how much of the gain survives an imperfect tracker; DMIE's 82.54% macro-F1 suggests it will be noticeably imperfect.
References
- Knowledge Graph-Guided Retrieval Augmented Generation
- Knowledge-Consistent Dialogue Generation with Knowledge Graphs
- MedKP: Medical Dialogue with Knowledge Enhancement and Clinical Pathway Encoding
- Dialogue Medical Information Extraction with Medical-Item Graph and Dialogue-Status Enriched Representation
- U-NIAH: Unified RAG and LLM Evaluation for Long Context Needle-in-a-Haystack
- MedDG: A Large-scale Medical Consultation Dataset for Building Medical Dialogue System
- Retrieval-Augmented Conversational Recommendation with Prompt-based Semi-Structured Natural Language State Tracking
- Diverse Retrieval-Augmented In-Context Learning for Dialogue State Tracking
- Graph vs. Sequence: An Empirical Study on Knowledge Forms for Knowledge-Grounded Dialogue