REVIEW 3 cited by
Understanding Transformer Reasoning Capabilities via Graph Algorithms
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.
Forward citations
Cited by 3 Pith papers
-
Learning Compositional Functions with Transformers from Easy-to-Hard Data
A transformer with O(log k) layers provably learns the k-fold permutation composition task in poly(N,k) samples with curriculum or mixed easy-to-hard data, despite an SQ lower bound requiring N^{Omega(k)} samples on h...
-
Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
In a metastable Markov model of reasoning, search and RL improve hitting times by boosting rare hard edges, and distilling clusters into a meta-chain preserves escape dynamics.
-
Are Large Language Models Good Temporal Graph Learners?
TGTalker prompts LLMs with the most recent edges and neighbor history of a temporal graph, achieving link prediction accuracy competitive with specialized temporal graph neural networks on five real-world datasets.
Discussion (0). Continue with ORCID to comment.