Skip to content

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

🕒 Published (v1): 2025-11-13 07:49 UTC · Source: Arxiv · Venue: AAAI · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GraphIF is a training-free, plug-and-play framework that models multi-turn dialogues as directed relation graphs and uses graph-structured prompts to improve LLM instruction following across turns. It decomposes relation extraction into iterative agent-based action identification and execution phases, then converts the resulting graph into natural-language constraint prompts that rewrite initial LLM responses. Across five backbone models on two long-dialogue benchmarks, GraphIF achieves 7–52% gains over instruction-tuned baselines on all four evaluation metrics.

Problem

Instruction-tuned LLMs treat each response in a multi-turn dialogue as an isolated generation step, so they fail to satisfy long-distance or global constraints established in earlier turns (e.g., "all responses must end with X" set in turn 1 is forgotten by turn 15). Existing memory-enhanced approaches (MemoryBank, MemoChat) rely on vector-similarity retrieval or topic indexing, which cannot capture structured inter-turn relational dependencies. Incremental fine-tuning is costly and generalizes poorly.

Method

GraphIF operates in three stages at inference time, with no parameter updates:

  1. Agent-Based Relation Extraction: Given current instruction \(I_t\) and dialogue history \(H_t\), an LLM agent iterates between Action Identification (selecting the next relation type from a predefined set: Global Constraint, Context-Anchored, Modify, Summary, New Topic, Done) and Action Execution (locating the specific historical turns satisfying that relation). A dynamic notebook \(N = \{a_{t,s} \to E_{t,s}\}\) accumulates extracted mappings across iterations, building a directed relation graph \(G = (V, E, R)\) where nodes are dialogue turns and labeled directed edges encode inter-turn constraints.

  2. Relation Graph Prompt Generation: Each edge in \(G\) is verbalized into a natural-language prompt \(P_g\) that states the relation type, the constraint it implies for the current response, and the relevant historical dialogue content.

  3. Initial Response Rewrite: The LLM generates a baseline response \(\text{RES}_\text{initial} = \text{LLM}([H_t, I_t])\), then a rewrite step \(\text{RES}_t = \text{Rewrite}(\text{RES}_\text{initial}, P_g)\) uses the graph prompt to enforce all identified constraints.

Key Contributions

  • Training-free, plug-and-play framework requiring no model fine-tuning or architectural changes.
  • Agent-based iterative relation extraction with action-triggered mechanisms, outperforming single-pass LLM extraction.
  • Five coarse-grained, extensible relation types that cover the full semantic space of inter-turn dependencies.
  • Two new evaluation datasets (MT-Eval*, StructFlowBench*) with >20 turns per dialogue and multiple inter-turn relations per instance, constructed from prior benchmarks.

Results

  • GraphIF achieves 7–52% absolute improvement across all four metrics (CSR, ISR, DRFR, WCSR) relative to LLM-only baselines on MT-Eval* and StructFlowBench*.
  • Largest gains on ISR (strictest metric, all constraints must be satisfied per turn): >20 percentage-point improvement in most settings (e.g., Llama-3.1-8B-Instruct: 27.51% → 80.35% on MT-Eval*; Qwen2.5-7B: 51.30% → 76.96%).
  • MemoryBank and MemoChat show negligible gains or regression versus LLM-only across all five backbone models.
  • Consistent gains across model scales: Qwen2.5-3B ISR 9.56% → 46.09%; Qwen2.5-14B ISR 75.65% → 82.17% on MT-Eval*.
  • Ablation: removing the agent module (one-shot extraction) drops ISR from 76.96% to 21.74% (Qwen2.5-7B, MT-Eval*); removing graph prompt (content-only) drops ISR to 63.48%.
  • Strongest gains on global constraint satisfaction on StructFlowBench*, where instruction-tuned LLMs show up to 40% performance drops.

Limitations

  • Evaluation datasets are small (MT-Eval*: 10 samples Ă— 23 turns; StructFlowBench*: 32 samples Ă— 24 turns), limiting statistical confidence.
  • Predefined relation taxonomy is hand-crafted; novel constraint types require manual extension of the action set.
  • Iterative agent-based relation extraction adds inference latency (number of LLM calls proportional to relation count per turn); latency analysis is deferred to the appendix without full quantification in the main text.
  • Relies on GPT-4o as the judge, introducing potential evaluation bias.
  • Not evaluated on open-ended, unstructured dialogues—benchmarks are constructed to contain explicit inter-turn constraints, which may not reflect all real-world distributions.

Relevance to Agentic AI / LLM Agents

GraphIF directly instantiates an agentic loop—alternating action identification and execution—for a structured sub-task (relation extraction), demonstrating that agent-style decomposition generalizes beyond task completion to meta-cognitive dialogue management. The work is particularly relevant to agent architectures that maintain stateful context over long interaction horizons, where forgetting early instructions is a known failure mode. The graph-prompt rewriting pattern (generate-then-refine using structured intermediate representations) aligns with tool-augmented and reflection-based agent paradigms (e.g., ReAct, Plan-and-Act). It also points to a broader principle: explicit symbolic structure (graphs) can compensate for LLMs' distributional forgetting in multi-step agentic tasks without retraining.