GraphIF: Enhancing Multi-Turn Instruction Following for Large Language Models with Relation Graph Prompt

AI summary

Overview

Research area: Natural Language Processing, specifically multi-turn instruction following and dialogue systems for large language models.

Technical level: Intermediate (familiarity with LLMs, prompting, and instruction-following evaluation is helpful but not required).

Scope: This paper introduces GraphIF, a training-free, plug-and-play framework that represents multi-turn dialogues as directed relation graphs and converts those graphs into natural language prompts to refine LLM responses so they satisfy constraints spread across many dialogue turns.

What This Paper Is About

Large language models often forget or ignore instructions given several turns earlier in a conversation, such as a rule that every reply must end with a specific phrase. Existing fixes either fine-tune models on large multi-turn dialogue datasets or add memory modules, but the authors argue both approaches treat each response as an isolated task and never explicitly model the relationships between turns. GraphIF tackles this by extracting those inter-turn relations as a labeled directed graph, turning the graph into a natural language prompt, and rewriting the model's first-draft answer using that prompt.

Key Contributions

1. A training-free, plug-and-play framework. GraphIF explicitly models inter-turn relations through graph structures and generates graph prompts to refine initial LLM responses, requiring no parameter updates and no architectural changes to the backbone model.

2. An agent-based relation extraction module. Because direct extraction of inter-turn relations is difficult, especially for long-distance constraints, the module iteratively alternates between an Action Identification phase and an Action Execution phase, using a dynamic notebook to maintain relation mappings and avoid redundant extraction, progressively constructing the dialogue relation graph.

3. Two modules that turn relations into better responses. A Relation Graph Prompt Generation module converts structured graph information into natural language prompts that articulate inter-turn relations and their constraints, and an Initial Response Rewrite module uses those prompts to refine the LLM's initial output.

4. Two new long multi-turn evaluation datasets. Because existing multi-turn instruction-following datasets have short dialogues and oversimplified inter-turn relations, the authors build MT-Eval* (10 samples of 23 turns each, 230 total dialogues, 4 relation types) and StructFlowBench* (32 samples of 24 turns each, 768 total dialogues, 7 relation types), each dialogue featuring multiple inter-turn relations.

Main Findings

• Consistent, large gains across all four metrics. Integrating GraphIF into instruction-tuned LLMs improves performance across all multi-turn instruction-following metrics, with reported gains ranging from 7% to 52%. The largest effect is on Instruction Satisfaction Rate (ISR), the strictest metric, which scores only when a response satisfies all constraints in a turn; GraphIF improves ISR by over 20%.

• Concrete numbers on the strongest baselines. For Qwen2.5-7B-Instruct on MT-Eval*, scores move from 80.22 CSR / 51.30 ISR / 79.70 DRFR / 79.57 WCSR (LLM-only) to 91.30 / 76.96 / 91.06 / 90.72 with GraphIF. On StructFlowBench*, the same model goes from 70.70 / 23.02 / 71.22 / 67.07 to 89.46 / 69.25 / 89.47 / 88.60. For Llama-3.1-8B-Instruct on MT-Eval*, LLM-only scores of 67.03 / 27.51 / 67.88 / 64.22 rise to 91.27 / 80.35 / 90.87 / 92.58.

• Memory-based baselines do not help. MemoryBank and MemoChat show negligible gains or actively hurt performance compared to vanilla instruction-tuned LLMs. For example, Qwen2.5-7B-Instruct with MemoChat on MT-Eval* drops to 59.42 / 16.52 / 58.79 / 56.35, well below the LLM-only baseline. The authors attribute this to coarse-grained summarization with naive vector-similarity retrieval (MemoryBank) and topic indexing that misses macro-level dialogue structure (MemoChat).

• Global constraints are the hardest case. Instruction-tuned LLMs struggle particularly with global constraints, showing performance drops of up to 40%, while GraphIF achieves its most notable improvements on that constraint type and maintains or improves performance across all constraint types. GraphIF also improves performance on current-instruction constraints, meaning rewritten responses address immediate user requirements while remaining consistent with historical ones.

• Gains hold across model scales. On MT-Eval*, Qwen2.5-3B-Instruct goes from 59.42 / 9.56 / 59.09 / 56.99 to 75.43 / 46.09 / 75.45 / 75.51, and Qwen2.5-14B-Instruct from 90.22 / 75.65 / 90.00 / 92.61 to 93.62 / 82.17 / 93.48 / 95.71.

• Both modules are necessary. Ablations show that replacing the iterative agent with one-time LLM relation extraction and removing semantic relation explanations from the prompt both degrade results. On MT-Eval* with Qwen2.5-7B-Instruct, GraphIF scores 91.30 / 76.96 / 91.06 / 90.72, versus 67.17 / 21.74 / 66.52 / 63.48 without the Relation Extraction Agent and 85.80 / 63.48 / 85.45 / 84.14 without the Graph Prompt.

• Case study shows error correction in action. For Llama-3.1-8B-Instruct, the instruction "List them in the order they appear in the story" requires reordering entities from turn 8 by their appearance in the story from turn 2. The initial response has ordering confusion; GraphIF identifies the Context-Anchored relation between the current instruction and turns 2 and 8, and the graph prompt guides the model to the correct ordering.

Methodology in Plain English

GraphIF treats a conversation as a graph where every node is one dialogue turn (the user instruction plus the model's response) and every labeled directed edge records a relationship between turns.

The process has three stages. First, an agent-based relation extraction module looks at the current instruction and the dialogue history and repeatedly asks the LLM two questions in alternation: which relation applies next (Action Identification, drawn from a fixed action set), and which historical turns satisfy it (Action Execution). A notebook records what has already been found, so the agent does not repeat itself, and the process stops when the agent selects a Done action. The relations are Identify_Global_Constraint (the instruction becomes a rule for all later replies, with newer rules overriding conflicting older ones), Identify_Context_Anchored (the instruction depends on specific earlier content), Identify_Modify (the instruction refines or extends earlier content), Identify_Summary (the instruction asks for a summary of specific earlier turns), New_Topic (the instruction starts an unrelated topic, with a topic pointer tracking which topic is active), and Done.

Second, the Relation Graph Prompt Generation module flattens each extracted relation into readable natural language: the relation's definition, how it connects to the current instruction and what constraint the response must satisfy, and the content of the connected turns.

Third, the Initial Response Rewrite module first gets a baseline answer by simply concatenating dialogue history and the current instruction, then asks the LLM to compare that draft against the graph prompt, identify unsatisfied constraints, and rewrite the answer accordingly.

The authors evaluate five instruction-tuned backbones (Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct, Hermes-3-Llama-3.1-8B, Llama-3.1-Storm-8B, Llama-3.1-Tulu-3.1-8B), plus Qwen2.5-3B-Instruct and Qwen2.5-14B-Instruct for scale analysis, on MT-Eval* and StructFlowBench*, using four metrics (CSR, ISR, DRFR, WCSR) judged by GPT-4o with human verification. Generation used temperature 0.7, top_p 0.8, and top_k 20; each configuration was run three times and averaged; experiments ran on 4 A800-80GB GPUs.

Why This Matters

Impact on research: The paper opens a direction the authors state was previously unexplored: using graph structures to enhance multi-turn instruction following. It argues that the bottleneck is not data volume but the absence of explicit modeling of cross-turn relations, and it offers a training-free alternative to dataset collection or fine-tuning, along with two longer, lexically richer evaluation sets that expose weaknesses in current instruction-tuned LLMs.

Real-world applications:

• Conversational assistants and customer-support agents that must honor standing rules (for example, always closing with a particular phrase, or never using commas) across entire sessions.
• Multi-step assistants that build on earlier outputs, such as rewriting a document section that was produced many turns earlier.
• Long-session tutoring or analytical chat where a later question depends on a specific earlier explanation or dataset passage.
• Agentic workflows with long-horizon, persistent constraints where retraining a model per deployment is impractical.

Industry relevance: Because GraphIF requires no retraining and no architectural changes, it can be layered onto an existing instruction-tuned model already in deployment. The reported consistency of gains from 3B to 14B parameters suggests the approach is deployable at different cost points, though the multi-step extraction-and-rewrite pipeline introduces additional LLM calls whose latency implications the paper addresses in its appendix (specific latency figures are not reported in the content provided here).

Future Directions

• Extending the relation set. The authors state their relation set is designed to be extensible rather than exhaustive, so future work can add new relations, provided each comes with a precise semantic explanation for the LLM.
• Reducing inference overhead. GraphIF adds relation extraction, prompt generation, and rewriting steps on top of a baseline LLM call; the appendix analyzes latency efficiency, but further work could streamline or cache the graph construction.
• Combining graph signals with training. Since GraphIF is training-free by design, a natural question is whether the extracted relation graphs could also inform fine-tuning objectives rather than only prompt-time rewriting.
• Scaling to longer and more varied dialogues. The evaluation covers dialogues of 23 and 24 turns across 4 and 7 relation types; testing on substantially longer conversations, other public benchmarks such as the recently released MultiChallenge mentioned in the appendix, and additional backbone models would test generalizability.

Target Audience

Researchers working on dialogue systems, instruction following, and graph-augmented generation; engineers building production conversational assistants who need better long-context constraint adherence without retraining; and evaluation-focused practitioners interested in the MT-Eval* and StructFlowBench* construction methodology and the four constraint-oriented metrics.

Authors’ abstract

Multi-turn instruction following is essential for building intelligent conversational systems that can consistently adhere to instructions across dialogue turns. However, existing approaches to enhancing multi-turn instruction following primarily rely on collecting or generating large-scale multi-turn dialogue datasets to fine-tune large language models (LLMs), which treat each response generation as an isolated task and fail to explicitly incorporate multi-turn instruction following into the optimization objectives. As a result, instruction-tuned LLMs often struggle with complex long-distance constraints. In multi-turn dialogues, relational constraints across turns can be naturally modeled as labeled directed edges, making graph structures particularly suitable for modeling multi-turn instruction following. Despite this potential, leveraging graph structures to enhance the multi-turn instruction following capabilities of LLMs remains unexplored. To bridge this gap, we propose GraphIF, a plug-and-play framework that models multi-turn dialogues as directed relation graphs and leverages graph prompts to enhance the instruction following capabilities of LLMs. GraphIF comprises three key components: (1) an agent-based relation extraction module that captures inter-turn semantic relations via action-triggered mechanisms to construct structured graphs; (2) a relation graph prompt generation module that converts structured graph information into natural language prompts; and (3) a response rewriting module that refines initial LLM outputs using the generated graph prompts. Extensive experiments on two long multi-turn dialogue datasets demonstrate that GraphIF can be seamlessly integrated into instruction-tuned LLMs and leads to significant improvements across all four multi-turn instruction-following evaluation metrics.