Cover Image

Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ye, Qilin, Fu, Deqing, Jia, Robin, Sharan, Vatsal
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Transformers Learn to Achieve Second-Order Convergence Rates for In-Context Linear Regression
by: Fu, Deqing, et al.
Published: (2023)

Pre-trained Large Language Models Use Fourier Features to Compute Addition
by: Zhou, Tianyi, et al.
Published: (2024)

Convergent Evolution: How Different Language Models Learn Similar Number Representations
by: Fu, Deqing, et al.
Published: (2026)

FoNE: Precise Single-Token Number Embeddings via Fourier Features
by: Zhou, Tianyi, et al.
Published: (2025)

Transformers Learn Low Sensitivity Functions: Investigations and Implications
by: Vasudeva, Bhavya, et al.
Published: (2024)

Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data
by: Ran-Milo, Yuval, et al.
Published: (2026)

Textual Steering Vectors Can Improve Visual Understanding in Multimodal Large Language Models
by: Gan, Woody Haosheng, et al.
Published: (2025)

Limitations on Accurate, Trusted, Human-level Reasoning
by: Panigrahy, Rina, et al.
Published: (2025)

Improved Bounds for Swap Multicalibration and Swap Omniprediction
by: Luo, Haipeng, et al.
Published: (2025)

Optimal Multiclass U-Calibration Error and Beyond
by: Luo, Haipeng, et al.
Published: (2024)

On the Inherent Privacy of Zeroth Order Projected Gradient Descent
by: Gupta, Devansh, et al.
Published: (2025)

Sample Amplification: Increasing Dataset Size even when Learning is Impossible
by: Axelrod, Brian, et al.
Published: (2019)

How Muon's Spectral Design Benefits Generalization: A Study on Imbalanced Data
by: Vasudeva, Bhavya, et al.
Published: (2025)

Proper Learnability and the Role of Unlabeled Data
by: Asilis, Julian, et al.
Published: (2025)

Understanding Contextual Recall in Transformers: How Finetuning Enables In-Context Reasoning over Pretraining Knowledge
by: Vasudeva, Bhavya, et al.
Published: (2026)

Efficient Swap Multicalibration of Elicitable Properties
by: Hu, Lunjia, et al.
Published: (2025)

Stability and Multigroup Fairness in Ranking with Uncertain Predictions
by: Devic, Siddartha, et al.
Published: (2024)

When is Multicalibration Post-Processing Necessary?
by: Hansen, Dutch, et al.
Published: (2024)

Regularization and Optimal Multiclass Learning
by: Asilis, Julian, et al.
Published: (2023)

Provably Reliable Classifier Guidance via Cross-Entropy Control
by: Sahu, Sharan, et al.
Published: (2026)

Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
by: Vaswani, Sharan, et al.
Published: (2025)

A Spectral View of Adversarially Robust Features
by: Garg, Shivam, et al.
Published: (2018)

A Graph-Enhanced Deep-Reinforcement Learning Framework for the Aircraft Landing Problem
by: Maru, Vatsal
Published: (2025)

Simultaneous Swap Regret Minimization via KL-Calibration
by: Luo, Haipeng, et al.
Published: (2025)

Discovering Data Structures: Nearest Neighbor Search and Beyond
by: Salemohamed, Omar, et al.
Published: (2024)

Auditability and the Landscape of Distance to Multicalibration
by: Derhake, Nathan, et al.
Published: (2025)

Unlabeled Data Can Provably Enhance In-Context Learning of Transformers
by: Liu, Renpu, et al.
Published: (2026)

On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization
by: Sahu, Sharan, et al.
Published: (2026)

Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms
by: Lazzati, Filippo, et al.
Published: (2024)

The Rich and the Simple: On the Implicit Bias of Adam and SGD
by: Vasudeva, Bhavya, et al.
Published: (2025)

Latent Concept Disentanglement in Transformer-based Language Models
by: Hong, Guan Zhe, et al.
Published: (2025)

Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization
by: Sahu, Sharan, et al.
Published: (2026)

Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot
by: Wang, Zixuan, et al.
Published: (2024)

Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees
by: Du, Ally Yalei, et al.
Published: (2025)

Eidetic Learning: an Efficient and Provable Solution to Catastrophic Forgetting
by: Dronen, Nicholas, et al.
Published: (2025)

Provable Training for Graph Contrastive Learning
by: Yu, Yue, et al.
Published: (2023)

Traffic-Aware Optimal Taxi Placement Using Graph Neural Network-Based Reinforcement Learning
by: Khetarpaul, Sonia, et al.
Published: (2026)

Provable In-Context Learning of Nonlinear Regression with Transformers
by: Li, Hongbo, et al.
Published: (2025)

Transformers Provably Learn to Internalize Chain-of-Thought
by: Huang, Yixiao, et al.
Published: (2026)

Formal Algorithms for Model Efficiency
by: Tyagi, Naman, et al.
Published: (2025)