Research map / Large language models / Reasoning and chain of thought

Clustering as Reasoning: A $k$-Means Interpretation of Chain-of-Thought Graph Learning

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Long CoT dynamics and efficiency · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes KCoT, a graph chain-of-thought framework that interprets iterative LLM reasoning as k-means assignment/update steps, using a Semantic Discriminating Prompt and a Condition-Net to fuse structural and reasoning-induced neighbors over TAGs.

Problem

Graph CoT methods for text-attributed graphs use disjoint LLM and GNN pipelines and lack a principled, interpretable account of how reasoning steps optimize node representations.

Approach

Reframes graph CoT as clustering: a Transformer block can implement soft k-means assignment, so prompts that explicitly do "assignment" (filter neighbors) and "update" (summarize centroid) steps drive iterative refinement; a Condition-Net turns the textual thoughts into a modulation matrix for a frozen GCN encoder.

Key results

• KCoT reaches 79.25% node classification accuracy on ogbn-Arxiv under the Single Focus protocol, versus 76.66% for the strongest baseline LLAGA-HO.
• KCoT achieves 90.63% on Cora node classification and 88.45% on Cora link prediction (Single Focus), exceeding LLAGA-HO's 89.22% and 86.82%.
• Ablation: removing the Semantic Discriminating Prompt drops Products node classification from 86.39% to 82.35%; removing CoT (t=1) drops Cora node classification to 89.12%.

Surprising findings

• Performance peaks at t=2 thought steps and declines for more steps, which the authors attribute to k-means-like overfitting to outliers and GNN over-smoothing.
• Removing the structural neighbors input yields only a small drop on Products link prediction relative to some other ablations, and the w/o-Prompt variant is not uniformly worst across all settings.

Limitations

• The Transformer-to-k-means equivalence is a construction under specific assumptions (key-dependent bias, fixed centers), not a property of trained LLMs.
• The misalignment contraction theorem rests on assumptions the authors describe as supported only by visualization rather than proven.
• Evaluated only on four datasets with a frozen GCN encoder and a single LLM backbone for the main results.

Experimental setup

Datasets: Cora Pubmed ogbn-Arxiv ogbn-Products

Benchmarks: Cora Pubmed ogbn-Arxiv ogbn-Products

Metrics: accuracy p-value (t-test)

Baselines: GCN GraphSAGE GAT SGC SAGN NodeFormer Vicuna-7B GraphGPT LLAGA-ND LLAGA-HO

Builds on: LLaGA GraphGPT GCN BERT

Closest papers by meaning

• Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Properties (NeurIPS 2025 · similarity 0.90)
• Enhancing Chain of Thought Prompting in Large Language Models via Reasoning Patterns (AAAI 2025 · similarity 0.89)
• CDW-CoT: Clustered Distance-Weighted Chain-of-Thoughts Reasoning (AAAI 2025 · similarity 0.89)
• Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.89)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought (NeurIPS 2025 · similarity 0.89)
• SCOUT: Teaching Pre-trained Language Models to Enhance Reasoning via Flow Chain-of-Thought (NeurIPS 2025 · similarity 0.89)