CoEvoT: Co-Evolving Chain-of-Thought Prompting for Graph-LLM Reasoning
This work addresses the challenge of distribution shift in graph learning by enabling step-wise, state-aware evidence refinement for LLM-based graph reasoning, offering a novel approach to improve label-efficient prediction.
CoEvoT introduces a co-evolving Chain-of-Thought prompting framework for graph-LLM reasoning that iteratively refines graph tokens and reasoning steps in a closed loop, outperforming state-of-the-art baselines across eight datasets.
Graph learning under distribution shift presents a persistent challenge, where models adapt to new graphs with limited or even no supervision. Recent graph--LLM approaches move toward label-efficient prediction by linearizing graphs into prompts and using large language models (LLMs) as predictors, and can adopt Chain-of-Thought (CoT) prompting to exploit LLM's multi-step reasoning capability. However, existing CoT-based graph--LLM methods generate intermediate thoughts while conditioning on fixed graph tokens, limiting step-wise refinement of structural cues. In this paper, we propose CoEvoT, a simple yet effective co-evolving CoT prompting framework for graph--LLM reasoning. CoEvoT couples text-to-graph token rewriting and graph-to-text reasoning guidance in a closed loop: each intermediate textual thought is used to update the graph token evidence state via a lightweight condition network, and the updated tokens are fed back into the next-step instruction to guide subsequent LLM reasoning. This enables step-wise, state-aware evidence refinement, rather than reasoning over a fixed graph snapshot. Extensive experiments on eight datasets demonstrate that CoEvoT consistently outperforms state-of-the-art baselines.