Cover Image

Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Yehudai, Gilad, Sanford, Clayton, Bechler-Speicher, Maya, Fischer, Orr, Gilad-Bachrach, Ran, Globerson, Amir
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Artificial Intelligence Computation and Language
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Interpretable and Effective Graph Neural Additive Networks
by: Bechler-Speicher, Maya, et al.
Published: (2024)

TREE-G: Decision Trees Contesting Graph Neural Networks
by: Bechler-Speicher, Maya, et al.
Published: (2022)

Graph Neural Networks Use Graphs When They Shouldn't
by: Bechler-Speicher, Maya, et al.
Published: (2023)

On the Utilization of Unique Node Identifiers in Graph Neural Networks
by: Bechler-Speicher, Maya, et al.
Published: (2024)

Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
by: Bechler-Speicher, Maya, et al.
Published: (2026)

Towards Invariance to Node Identifiers in Graph Neural Networks
by: Bechler-Speicher, Maya, et al.
Published: (2025)

Compositional Reasoning with Transformers, RNNs, and Chain of Thought
by: Yehudai, Gilad, et al.
Published: (2025)

When Can Transformers Count to n?
by: Yehudai, Gilad, et al.
Published: (2024)

Graph Mixing Additive Networks
by: Bechler-Speicher, Maya, et al.
Published: (2025)

Cayley Graph Propagation
by: Wilson, JJ, et al.
Published: (2024)

Mixture of Universal Experts: Scaling Virtual Width via Depth-Width Transformation
by: Chen, Yilong, et al.
Published: (2026)

Understanding Transformer Reasoning Capabilities via Graph Algorithms
by: Sanford, Clayton, et al.
Published: (2024)

Logarithmic Width Suffices for Robust Memorization
by: Egosi, Amitsour, et al.
Published: (2025)

A Graph Meta-Network for Learning on Kolmogorov-Arnold Networks
by: Bar-Shalom, Guy, et al.
Published: (2026)

Improving Engagement and Efficacy of mHealth Micro-Interventions for Stress Coping: an In-The-Wild Study
by: Yehuda, Chaya Ben, et al.
Published: (2024)

Improving LLM Final Representations with Inter-Layer Geometry
by: Ulanovski, Tom, et al.
Published: (2026)

SuperMAN: Interpretable and Expressive Networks over Temporally Sparse Heterogeneous Data
by: Bechler-Speicher, Maya, et al.
Published: (2025)

Billion-Scale Graph Foundation Models
by: Bechler-Speicher, Maya, et al.
Published: (2026)

A General Recipe for Contractive Graph Neural Networks -- Technical Report
by: Bechler-Speicher, Maya, et al.
Published: (2024)

Meta Reinforcement Learning with Finite Training Tasks -- a Density Estimation Approach
by: Rimon, Zohar, et al.
Published: (2022)

Controllable User Simulation
by: Tennenholtz, Guy, et al.
Published: (2026)

Markov flow policy -- deep MC
by: Soffair, Nitsan, et al.
Published: (2024)

ASRJam: Human-Friendly AI Speech Jamming to Prevent Automated Phone Scams
by: Grabovski, Freddie, et al.
Published: (2025)

Are You Human? An Adversarial Benchmark to Expose LLMs
by: Gressel, Gilad, et al.
Published: (2024)

Loop, Think, & Generalize: Implicit Reasoning in Recurrent-Depth Transformers
by: Kohli, Harsh, et al.
Published: (2026)

GDS Agent for Graph Algorithmic Reasoning
by: Shi, Borun, et al.
Published: (2025)

When LLMs are Unfit Use FastFit: Fast and Effective Text Classification with Many Classes
by: Yehudai, Asaf, et al.
Published: (2024)

Geometric Factual Recall in Transformers
by: Ravfogel, Shauli, et al.
Published: (2026)

The Dual-Stream Transformer: Channelized Architecture for Interpretable Language Modeling
by: Kerce, J. Clayton, et al.
Published: (2026)

Tighter Bounds on the Information Bottleneck with Application to Deep Learning
by: Weingarten, Nir, et al.
Published: (2024)

Latent Reasoning with Supervised Thinking States
by: Amos, Ido, et al.
Published: (2026)

Reconstructing Training Data From Real World Models Trained with Transfer Learning
by: Oz, Yakir, et al.
Published: (2024)

MoGU: Mixture-of-Gaussians with Uncertainty-based Gating for Time Series Forecasting
by: Aviv, Gilad, et al.
Published: (2025)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
by: Huang, Zekai, et al.
Published: (2025)

A Nurse is Blue and Elephant is Rugby: Cross Domain Alignment in Large Language Models Reveal Human-like Patterns
by: Yehudai, Asaf, et al.
Published: (2024)

Large Language and Reasoning Models are Shallow Disjunctive Reasoners
by: Khalid, Irtaza, et al.
Published: (2025)

On the Reconstruction of Training Data from Group Invariant Networks
by: Elbaz, Ran, et al.
Published: (2024)

Latent Chain-of-Thought? Decoding the Depth-Recurrent Transformer
by: Lu, Wenquan, et al.
Published: (2025)

Do LLMs have Consistent Values?
by: Rozen, Naama, et al.
Published: (2024)

Multi-Task GRPO: Reliable LLM Reasoning Across Tasks
by: Ramesh, Shyam Sundhar, et al.
Published: (2026)