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..
Towards Understanding Transformers in Learning Random Walks
Authors: Wei Shi, Yuan Cao
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We theoretically demonstrate that, after training with gradient descent, a one-layer transformer model can achieve optimal accuracy in predicting random walks... Experiments are conducted to support our theoretical findings. ... Figure 4 and Figure 5 illustrate the results of the experiment for p = 0.5 and p = 1 respectively: Figure 4(a) and Figure 5(a) present the prediction accuracy; Figure 4(b) and Figure 5(b) visualize the value matrix V (T ) after 50 iterations; Figure 4(c) and Figure 5(c) display the attention scores attached to each token after 50 iterations. |
| Researcher Affiliation | Academia | Wei Shi School of Computing and Data Science The University of Hong Kong EMAIL Yuan Cao School of Computing and Data Science The University of Hong Kong EMAIL |
| Pseudocode | No | The paper describes the model (equations 2.1, 2.2, 2.3) and training algorithm (gradient descent) textually and mathematically. It does not contain a structured pseudocode block or a clearly labeled algorithm block with step-by-step instructions for the model or training process. |
| Open Source Code | No | 5. Open access to data and code. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: Experiments in this paper are on synthetic data and are relatively simple. The purpose is mainly to back up our theory. |
| Open Datasets | No | We study random walks on circles. Specifically, consider K nodes (possible locations) that are arranged on a circle so that each node has two neighbors... 1. Draw s1 Unif([K]). 2. For i = 2, . . . , N, sample either si = si 1 + 1 K with probability p or si = si 1 1 K with probability 1 p. 3. Set xi = esi, i [N 1], and y = s N. ... For both tasks, we generate 1000 sequences to train the model. |
| Dataset Splits | Yes | The prediction accuracy is calculated based on 1000 test data. For both tasks, we generate 1000 sequences to train the model. ... Both experiments are conducted on 1024 training data and 1024 test data. |
| Hardware Specification | No | 8. Experiments compute resources. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The experiments in this paper are very simple and are mainly to verify our theory. There is no need to specify compute resources. |
| Software Dependencies | No | The paper does not explicitly mention specific software components or libraries with their version numbers that are crucial for replicating the experiments. |
| Experiment Setup | Yes | We consider gradient descent with zero initialization V (0) = 0K K, W (0) = 0(K+M) (K+M) to train the model. The update rule for the parameter matrices W , V are as follows: W (t+1) = W (t) η W L(θ(t)), V (t+1) = V (t) η V L(θ(t)), (2.3), where η > 0 is the learning rate and t 0 is the iteration number. ... In this case, we set the length of the positional embedding M = 1000, the initialization V (0) = 0K K, W (0) = 0(K+M) (K+M), and the learning rate η = 1. The constant ϵ in the log-loss is set as ϵ = 0.1. ... Random initialization. In this case, we set the length of the positional embedding M = 1000, the initialization V (0) ij , W (0) ij N(0, σ2) with σ = 0.01, and the learning rate η = 0.01. The constant ϵ in the log-loss is set as ϵ = 0.1. |