Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
Authors: Yanna Ding, Songtao Lu, Yingdong Lu, Tomasz Nowicki, Jianxi Gao
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Specifically, we (1) provide the closed-form expression of the global minimizer (in an enlarged parameter space) for a single-layer linear self-attention (LSA) model; (2) prove that recovering transformer parameters that realize the optimal solution is NP-hard in general, revealing a fundamental limitation of onelayer LSA in representing structured dynamical functions; and (3) supply a novel interpretation of a multilayer LSA as performing preconditioned gradient descent to optimize multiple objectives beyond the square loss. These theoretical results are numerically validated using simplified transformers. |
| Researcher Affiliation | Collaboration | Yanna Ding1 , Songtao Lu2 , Yingdong Lu3, Tomasz Nowicki3, Jianxi Gao1 1 Department of Computer Science, Rensselaer Polytechnic Institute 2 Department of Computer Science and Engineering, The Chinese University of Hong Kong 3 IBM Research |
| Pseudocode | No | The paper does not contain any clearly labeled pseudocode or algorithm blocks. It primarily uses mathematical notation and descriptive text to explain methodologies. |
| Open Source Code | Yes | Our code is available at https://github.com/dingyanna/ICL-Markov-Dynamics |
| Open Datasets | No | For data, we construct each prompt with n + 1 = 101 sequences, where each sequence represents a binary Markov chain of length d+1... To generate data, we use the process described in Section B.1. |
| Dataset Splits | Yes | For data, we construct each prompt with n + 1 = 101 sequences, where each sequence represents a binary Markov chain of length d+1. The first n sequences serve as in-context examples, and the final sequence xn+1 is a query with its last token yn+1 masked. The prediction task is to infer yn+1 based on the shared temporal dynamics among chains. |
| Hardware Specification | Yes | The experiments are conducted on an NVIDIA A40 GPU. |
| Software Dependencies | No | The paper mentions using Adam optimizer but does not specify any software libraries or frameworks with version numbers (e.g., Python, PyTorch, TensorFlow versions). |
| Experiment Setup | Yes | The LSA model is trained using the Adam optimizer for 1000 iterations with a learning rate of 0.01, minimizing the mean squared error between predicted and true labels... The models are optimized by Adam over 50K epochs with learning rate 0.0001. |