2025/05/18 by Hanlin Zhu, Zhu, Hanlin, Shibo Hao +9 · 7 voices · 28 citations
Computer Science · #Advanced Graph Neural Networks #Multimodal Machine Learning Applications #Topic Modeling #cs.LG
paper · pdf · doi:10.48550/arxiv.2505.12514
openalex publication_date 2025/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Large Language Models (LLMs) have demonstrated remarkable performance in many applications, including challenging reasoning problems via chain-of-thoughts (CoTs) techniques that generate ``thinking tokens'' before answering the questions. While existing theoretical works demonstrate that CoTs with discrete tokens boost the capability of LLMs, recent work on continuous CoTs lacks a theoretical understanding of why it outperforms discrete counterparts in various reasoning tasks such as directed graph reachability, a fundamental graph reasoning problem that includes many practical domain applications as special cases. In this paper, we prove that a two-layer transformer with D steps of continuous CoTs can solve the directed graph reachability problem, where D is the diameter of the graph, while the best known result of constant-depth transformers with discrete CoTs requires O(n2) decoding steps where n is the number of vertices (D