Step-resolved data attribution for looped transformers Georgios Kaissis, David Mildenberger, Juan Felipe Gomez, Martin J. Menten, Eleni Triantafillou Abstract We study how individual training examples shape the internal computation of looped transformers, where a shared block is applied for τ \tau recurrent iterations to enable latent reasoning. Existing training-data influence estimators such as TracIn yield a single scalar score that aggregates over all loop iterations, obscuring when during the recurrent computation a training example matters. We introduce Step-Decomposed Influence (SDI) , which decomposes TracIn into a length- τ \tau influence trajectory by unrolling the recurrent computation graph and attributing influence to specific loop iterations. To make SDI practical at transformer scale, we propose a TensorSketch implementation that never materialises per-example gradients. Experiments on looped GPT-style models and algorithmic reasoning tasks show that SDI scales excellently, matches full-gradient baselines with low error and supports a broad range of data attribution and interpretability tasks with per-step insights into the latent reasoning process. † † affiliationnotice: Equal contribution 1 Introduction The capability of Large Language Models (LLMs) to perform complex reasoning has become a central focus of current machine learning research. This shift is driven by the observation that allocating additional compute at test-time—often realised through Chain-of-Thought (CoT) prompting—can substantially improve performance on benchmarks requiring multi-step logic, mathematics, and algorithmic execution ( 18 ; 30 ) . However, standard CoT relies on explicit, discrete token generation, which introduces significant computational overhead and expressive limitations. Generating intermediate tokens in natural language is costly and often includes many tokens that contribute little to advancing the underlying reasoning state (e.g., formatting tokens or connective words), consuming both compute and context window budget ( 10 ) . More fundamentally, requiring intermediate computation to be communicated through a discrete natural-language channel can be a low-bandwidth constraint relative to the model’s continuous hidden representations, which may be a more suitable substrate for high-dimensional intermediate computation ( 22 ) . To overcome these limitations, recent work has pivoted toward latent reasoning , where the model performs intermediate computations in a high-bandwidth continuous space rather than a discrete token space ( 41 ; 35 ) . Among the architectures facilitating this paradigm, the looped (also called weight-tied or depth-recurrent ) transformer has emerged as a particularly promising candidate ( 37 ; 19 ) . A looped transformer operates by applying a shared block of parameters recursively over its own activations (and possibly input embeddings) for a fixed or dynamic number of iterations; e.g., at a loop horizon \tau=8 , the same transformer block is applied eight times to the residual stream before producing final logits. This architectural design decouples the parameter count from the computational depth axis: a looped transformer can maintain a small memory footprint while allocating dynamic compute budgets to harder instances by simply looping more times ( 14 ; 3 ) . The efficacy of this approach has been demonstrated across domains, from algorithmic tasks ( 38 ) to large-scale architectures like Ouro and RecurrentGemma ( 42 ; 8 ) , as well as specialised reasoning architectures like Tiny Recursive Models ( 27 ) and Universal Reasoning Models ( 17 ) . Why step-resolved data attribution? Despite their growing prominence, the internal dynamics of looped transformers remain underexplored. While it is known that looping improves performance, understanding how latent states ( “thoughts” ) evolve across loop iterations and how specific training data influences this evolution is an open challenge. Traditional data attribution methods, such as Influence Functions ( 29 ) or TracIn ( 33 ) , treat the model as a static function mapping input to output. While these estimators can be applied to looped architectures, their output is a single scalar influence score that aggregates over all applications of a shared block, and therefore does not localise influence to specific loop iterations. To thus rigorously interpret looped models, we require a granular view that apportions credit to the specific computational steps they perform. In looped transformers, the loop horizon \tau is a test-time compute knob : increasing \tau changes the amount of internal computation without changing the parameter set or the number of generated tokens. In this regime, practitioners may be interested not only in which training examples matter, but when they matter during the recurrent computation. A single scalar influence score cannot reveal whether an example primarily supports early iterations (e.g., parsing/grounding) versus late iterations (e.g., iterative refinement), nor whether positive and negative effects cancel across steps. Step-resolved attribution on the other hand can enable e.g., (i) calibrating test-time compute by identifying the “influence horizon” where training data ceases to impact latent state evolution, removing the need for expensive hyperparameter retraining; (ii) detecting signal cancellation , where a near-zero aggregate scalar score masks significant but opposing effects at early versus late iterations; and (iii) depth-targeted data curation , allowing practitioners to filter for examples that specifically drive iterative refinement rather than early input processing. In this work, we introduce Step-Decomposed Influence (SDI) , a novel framework for interpreting looped transformers via unrolled data attribution. By generalising the TracIn estimator ( 33 ) to the recurrent setting, we decompose the scalar influence of a training point into a trajectory of influences across loop iterations. We provide a reference implementation of the SDI framework at https://github.com/gkaissis/step-decomposed-influence-oss . Contributions Our specific contributions are as follows: • Step-Decomposed Influence (SDI): We formalise the attribution of training data to internal recurrent steps of weight-tied models. We prove a conservation identity showing that SDI losslessly decomposes standard TracIn, bridging the gap between static influence scores and dynamic latent computation. • Streaming TensorSketch with Tighter Bounds: We address the memory bottleneck of gradient-based attribution via a streaming sketch-during-backprop algorithm that avoids materialising per-example gradients. Theoretically, we derive tight variance bounds for TensorSketch on outer-product sums that are strictly tighter than prior art, ensuring unbiased, low-variance estimation at transformer scale. • Applications to Latent Reasoning: We demonstrate SDI’s utility across three distinct regimes: recovering finite-state automata circuits in parity tasks, linking test-time compute scaling to late-stage influence in Sudoku, and revealing implicit geometric growth of influence in a looped 330M parameter LLM (Nanochat), suggesting that looped transformers spontaneously learn to represent their own progress through the recurrence. 2 Background In this section we give a brief overview of looped transformer models and how they are trained for language modelling tasks. We also overview the TracIn estimator ( 33 ) and its application for computing the influence of training examples on predictions of the model. Looped transformers The parameters \mathbf{w} of a looped transformer are partitioned into three functional blocks: a read-in block \mathbf{w}_{\text{in}} , a recurrent body \mathbf{w}_{\text{body}} , and a read-out block \mathbf{w}_{\text{out}} . Given an input sequence \mathbf{x} , the read-in block maps sequences to an embedding \mathbf{h}_{0}=E(\mathbf{x};\mathbf{w}_{\text{in}}) . This embedding has shape \mathbb{R}^{L\times d} for sequence length L and hidden size d . The body block then iteratively refines the embedding for \tau steps by looping over activations: \mathbf{h}_{t}=F(\mathbf{h}_{t-1},\mathbf{e}_{\text{inj}};\mathbf{w}_{\text{body}}) for t\in\{1,\dots,\tau\} . We will often refer to \tau as the depth dimension and t as a “step” . To stabilise training across steps, looped transformers often employ input injection, represented above as the dependence on \mathbf{e}_{\text{inj}} ( 5 ) . This input injection can be additive as in 14 , concatenative as in 18 or null. The read-out block maps the final activation \mathbf{h}_{\tau} to logits y=R(\mathbf{h}_{\tau};\mathbf{w}_{\text{out}}) , and standard cross-entropy loss is used to train the looped model. It is common for looped models to be trained with randomised depths ( 18 ) (sampling \tau from a probability distribution) or with input-dependent \tau ( 14 ) to encourage robustness to changing \tau , as is often the case at inference-time to optimize test-time compute. TracIn To quantify the effect of training data on model predictions, we build upon the TracIn estimator ( 33 ) . TracIn approximates the influence of a train example z on an example z^{\prime} by summing the dot product of their loss gradients over saved checkpoints \mathcal{W}{=}\{\mathbf{w}_{k}\}_{k=1}^{K} . Letting \ell be the loss function (e.g., cross-entropy); the TracIn estimator is given by: \operatorname{TracIn}_{\mathbf{w}}(z,z^{\prime})=\sum_{k=1}^{K}\eta_{k}\nabla_{\mathbf{w}}\ell(\mathbf{w}_{k};z)\cdot\nabla_{\mathbf{w}}\ell(\mathbf{w}_{k};z^{\prime}). (1) Here \eta_{k} denotes the learning rate associated with checkpoint \mathbf{w}_{k} . Note that while the gradient with respect to matrix parameters is a matrix, TracIn flattens all gradients into vectors to compute the dot product. Intuitively, for fixed z^{\prime} , training examples z with \operatorname{TracIn}(z,z^{\prime}){>}0 reduce the loss on z^{\prime} along the training trajectory, while z with \operatorname{TracIn}(z,z^{\prime}){<}0 increase the loss on z^{\prime} . Interpreting \operatorname{TracIn}(z,z^{\prime}) as the “influence” of train example z on example z^{\prime} , we follow 16 ; 15 and distinguish between self-influence ( z=z^{\prime} ), a proxy for memorisation during training, and cross-influence ( z{\neq}z^{\prime} ), which captures how training on z relates to generalisation on a held out example z^{\prime} . Our work exploits the recurrent structure of \mathbf{w}_{\text{body}} to decompose the TracIn gradients and therefore the estimator across steps, which we outline in the next section. For a discussion on why we chose TracIn as our influence proxy over other approaches such as Influence Functions, see Appendix A . 3 Step-Decomposed Influence We wish to apply and build on the TracIn estimator introduced in Section 2 to looped transformers. A naïve application of Equation 1 would use the total gradient \nabla_{\mathbf{w}_{\text{body}}}\ell , which unrolls into the sum the contribution of the gradients across steps. Using this for TracIn obscures whether a training example z influences z^{\prime} in early vs. late loop steps. To resolve this, we introduce Step-Decomposed Influence (SDI) , which turns a single scalar influence score into a step-resolved influence trajectory . This enables analyses that are not accessible from scalar influence estimators, such as localising which training examples affect early vs. late loop steps and identifying where additional steps yield diminishing returns. Gradients as a sum over steps: Let \ell(\mathbf{w};z) denote the loss of a model with parameters \mathbf{w} at an example z ; we omit explicit dependence on (\mathbf{w};z) when unambiguous. Recall that the per-step activations are given by \mathbf{h}_{t}=F(\mathbf{h}_{t-1},\mathbf{e}_{\text{inj}};\mathbf{w}_{\text{body}}) for t\in\{1,\dots,\tau\} . The dependence of \mathbf{h}_{t} on \mathbf{w}_{\text{body}} and on \mathbf{h}_{t-1} , which also depends on \mathbf{w}_{\text{body}} , turns the total derivative of the loss with respect to \mathbf{w}_{\text{body}} into a sum of Vector-Jacobian Products. Proposition 1 . For a looped transformer with \tau steps and sequence length L , let \mathbf{h}_{t,j}\in\mathbb{R}^{d} denote the hidden state of the j -th token at step t . The total derivative of the loss with respect to \mathbf{w}_{\text{body}} can be unrolled into a sum over \tau steps and L tokens: \displaystyle\phi_{t}=\sum_{j=1}^{L}\frac{\mathrm{d}\ell}{\mathrm{d}\mathbf{h}_{t,j}}\frac{\partial\mathbf{h}_{t,j}}{\partial\mathbf{w}_{\text{body}}},\quad\frac{\mathrm{d}\ell}{\mathrm{d}\mathbf{w}_{\text{body}}}=\sum_{t=1}^{\tau}\phi_{t} (2) Where \frac{\mathrm{d}\ell}{\mathrm{d}\mathbf{h}_{t,j}}\in\mathbb{R}^{d} is the gradient at step t and token j computed via backpropogation through time (BPTT), and \frac{\partial\mathbf{h}_{t,j}}{\partial\mathbf{w}_{\text{body}}}\in\mathbb{R}^{d\times\lvert\mathbf{w}_{\text{body}}\rvert} is the Jacobian of the function F with respect to the parameters \mathbf{w}_{\text{body}} , while holding the input state \mathbf{h}_{t-1} and input injection \mathbf{e}_{\text{inj}} constant. Moreover, if \mathbf{w}_{\text{body}} is a concatenation of a matrix \mathbf{W} and a vector \mathbf{b} , and in F they appear only through a tokenwise linear map of the form \mathbf{c}_{t,j}=\mathbf{W}\>\mathbf{a}_{t,j}+\mathbf{b} where \mathbf{a}_{t}=f(\mathbf{h}_{t-1}) is the forward activation, then \phi_{t} simplifies to sums of outer products for \mathbf{W} and to sums of vectors for \mathbf{b} : \displaystyle\delta_{t,j} \displaystyle=\frac{\mathrm{d}\ell}{\mathrm{\mathrm{d}}\mathbf{c}_{t,j}} (3) \displaystyle\phi_{t}^{\mathbf{W}}=\sum_{j=1}^{L}\delta_{t,j}\>\otimes \displaystyle\>\mathbf{a}_{t,j},\quad\phi_{t}^{\mathbf{b}}=\sum_{j=1}^{L}\delta_{t,j}. (4) Let \mathbf{W}\in\mathbb{R}^{d_{\text{out}}\times d_{\text{in}}} , then \delta_{t,j}\in\mathbb{R}^{d_{\text{out}}},\mathbf{a}_{t,j}\in\mathbb{R}^{d_{\text{in}}} . Moreover \phi_{t}^{\mathbf{W}}\in\mathbb{R}^{d_{\text{out}}\times d_{\text{in}}},\phi_{t}^{\mathbf{b}}\in\mathbb{R}^{d_{\text{out}}} , and \phi_{t}=(\phi_{t}^{\mathbf{W}},\phi_{t}^{\mathbf{b}}) with \lvert\mathbf{w}_{\text{body}}\rvert=d_{\text{out}}d_{\text{in}}+d_{\text{in}} . If F instead contains many modules each with matrix-valued and vector-valued parameters of the same form (e.g. F is a GPT-2 small model), then we apply the above analysis individually to each matrix and vector parameter, and concatenate to form \phi_{t} . Proof. By definition of the total derivative. ∎ Step-Decomposed Influence (SDI) Recall that TracIn estimates the influence of a training example z on an example z^{\prime} by summing gradient dot products over checkpoints (cf. Equation 1 ). SDI refines this by localising the contribution to a specific step t . Concretely, define the step-localised influence \mathcal{I}_{t}(z,z^{\prime})\coloneqq\sum_{k=1}^{K}\eta_{k}\nabla_{\mathbf{w}_{\text{body}}}\ell(\mathbf{w}_{k};z)\cdot\phi_{t}(\mathbf{w}_{k};z^{\prime}). (5) As a direct consequence of Proposition 1 , this step-localized cross influence losslessly decomposes TracIn across steps: \operatorname{TracIn}_{\mathbf{w}_{\text{body}}}(z,z^{\prime})=\sum_{t=1}^{\tau}\mathcal{I}_{t}(z,z^{\prime}), (6) We are now ready to formally define SDI. Definition 1 ( Step-Decomposed Influence (SDI) ) . Given checkpoints \mathcal{W}{=}\{\mathbf{w}_{k}\}_{k=1}^{K} and learning rates \{\eta_{k}\}_{k=1}^{K} , the SDI trajectory of a training example z on a test example z^{\prime} through the step trajectory is the length- \tau vector \mathrm{SDI}(z,z^{\prime}){\coloneqq}\left(\mathcal{I}_{t}(z,z^{\prime})\right)_{t=1}^{\tau}. (7) SDI is generally asymmetric in z and z^{\prime} . Our default choice decomposes the test-side recurrence and answers: How much did training on z (across all its training-time loop steps) influence loop step t of the computation on z^{\prime} ? Other decompositions are possible, depending on whether one wants to attribute effects on test-time steps (as above) or causes from training-time steps . For example, a training-step decomposition can be defined as \widehat{\mathcal{I}}_{t}(z,z^{\prime})\coloneqq\sum_{k=1}^{K}\eta_{k}\,\phi_{t}(z;\mathbf{w}_{k})\cdot\nabla_{\mathbf{w}_{\textnormal{body}}}\ell(\mathbf{w}_{k};z^{\prime}). (8) More granularly, one can form a stepwise influence matrix \mathcal{I}_{s,t}(z,z^{\prime})\coloneqq\sum_{k=1}^{K}\eta_{k}\,\phi_{s}(z;\mathbf{w}_{k})\cdot\phi_{t}(z^{\prime};\mathbf{w}_{k}). (9) This matrix view makes the “train-time step” vs. “test-time step” distinction explicit. Sketch-during-backprop Computing and storing the full-dimensional vectors \phi_{t}(\mathbf{w}_{k};z^{\prime})\in\mathbb{R}^{|\mathbf{w}_{\textnormal{body}}|} for every step, checkpoint and example is prohibitively expensive. Prior TracIn implementations typically follow a project-after-the-fact pipeline: first compute and store full per-example gradients, then apply a random projection to reduce dimensionality ( 33 ; 23 ) . As per-example gradients are never materialized in standard training pipelines (the sums in Proposition 1 and batch reduction of the loss are done in parallel in backwards-mode automatic differentiation), this approach retains the peak memory and runtime burden of per-example gradient materialisation. In contrast, SDI uses a sketch-during-backprop pipeline: we compute projected/sketched features on the fly and never instantiate the full per-example gradients . This efficient implementation is one of our core contributions that unlocks computing SDI and TracIn at transformer scale and can also be used more broadly whenever on-the-fly compressed per-example gradients are required. We rely on two sketching primitives: for a vector \mathbf{x}{\in}\mathbb{R}^{d} , CountSketch ( 9 ) defines a linear map \mathsf{CS}:\mathbb{R}^{d}\to\mathbb{R}^{m} using a hash h:[d]\to[m] and signs s:[d]\to\{\pm 1\} : (\mathsf{CS}(x))_{j}{\coloneqq}\sum_{i:\,h(i)=j}s(i)\,\mathbf{x}_{i}. This is a sparse random projection that preserves inner products in expectation while requiring only \mathcal{O}(d) computation to apply. \mathsf{CS} applies to vectors, and can therefore be used to sketch gradients of vector parameters such as biases \mathbf{b} in Proposition 1 or affine parameters in normalisation layers. The dominant parameters in transformer blocks, however, are matrix weights (e.g., the linear maps in attention and MLPs), whose per-example gradients factor as sums of outer products of backpropagated signals \delta_{t,j} and activations \mathbf{a}_{t,j} as shown in Proposition 1 . TensorSketch builds off of \mathsf{CS} and provides an efficient sketch for such outer products by convolving the CountSketch of the two vectors ( 32 ) . Formally, for \mathbf{u}\in\mathbb{R}^{d_{\textnormal{out}}} and \mathbf{v}\in\mathbb{R}^{d_{\textnormal{in}}} , TensorSketch defines a map \mathsf{TS}:\mathbb{R}^{d_{\textnormal{out}}}\times\mathbb{R}^{d_{\textnormal{in}}}\to\mathbb{R}^{m} such that \mathsf{TS}(\mathbf{u},\mathbf{v}) is a CountSketch of the tensor product \mathbf{u}\otimes\mathbf{v} computed in \mathcal{O}(d_{\textnormal{out}}+d_{\textnormal{in}}+m\log m) time. Since TensorSketch is linear, it can applied to sums of outer products like gradients from matrix parameters. See Appendix B for a more detailed explanation of CountSketch and TensorSketch. In our implementation, we apply \mathsf{CS} / \mathsf{TS} independently (meaning the underlying hashes are sampled independently) at each parameter tensor then concatenate to obtain a sketch of the full per-example gradient. Formally, let \mathcal{S}_{m}(\cdot) denote the block concatenation of independent \mathsf{CS} / \mathsf{TS} maps, each with output dimension m , applied per parameter tensor (vector parameters via \mathsf{CS} , matrix parameters via \mathsf{TS} ), producing a single global sketched vector. Note that if some gradient \mathbf{g} contains \alpha total parameter gradients, then S_{m} outputs an \alpha\>m -dimensional vector. Since \mathsf{CS} and \mathsf{TS} are linear, so is \mathcal{S} . We denote sketched vectors by \widetilde{\mathbf{u}}\coloneqq\mathcal{S}(\mathbf{u}) and estimate SDI in the sketched space: \widetilde{\mathcal{I}}_{t}(z,z^{\prime}){\coloneqq}\sum_{k=1}^{K}\eta_{k}\;\widetilde{\nabla_{\mathbf{w}_{\textnormal{body}}}\ell(\mathbf{w}_{k};z)}\cdot\widetilde{\phi_{t}(\mathbf{w}_{k};z^{\prime})}. (10) By linearity of \mathcal{S} and Equation 2 , we have that: \widetilde{\nabla_{\mathbf{w}_{\textnormal{body}}}\ell(\mathbf{w}_{k};z)}=\sum_{t=1}^{\tau}\widetilde{\phi_{t}(\mathbf{w}_{k};z^{\prime})}. (11) Since \mathsf{TS} is a function that acts directly on the vectors that form the outer product, and not the outer product itself, our approach computes these sketches directly during backpropagation using intermediate signals ( “hooks” ) similar to the approach in 40 . Recall that the hidden step states are given by \mathbf{h}_{t}=F(\mathbf{h}_{t-1},\mathbf{e}_{\text{inj}};\mathbf{w}_{\text{body}}) for t\in\{1,\dots,\tau\} . For each step t , token L , and matrix parameter in F , SDI applies TensorSketch to the cached forward activation \mathbf{a}_{t,j} and the backpropagation signal \delta_{t,j} . It then sums the sketched outer products over tokens j to form \tilde{\phi}_{t} before concatenating sketches across parameter tensors to form a single global feature vector per example and step. Algorithm 1 summarises the approach. From a systems perspective, the sketches require \Theta(B\tau m) extra storage per parameter-tensor for storing \widetilde{\phi}_{1:B,t} for batch size B , horizon \tau , and sketch dimension m . Note that materializing the full per-example \phi_{1:B,t} would scale as \Theta(B\tau|\mathbf{w}_{\textnormal{body}}|) . In our 135.1M-parameter GPT-2 experiment, |\mathbf{w}_{\textnormal{body}}| is on the order of 100M, whereas m=2048 with 48 parameter tensors, therefore SDI is \sim 1,000\times less memory intensive. Computationally, our procedure introduces only an additive overhead to standard BPTT—dominated by the FFT-based TensorSketch updates and scaling linearly in the number of per-step module invocations (hence in B\tau ) and as m\log m in the sketch dimension—but it is incurred inline during the same backward pass. Empirically, this overhead is small at transformer scale as seen in the experimental section. Algorithm 1 1: Checkpoint \mathbf{w} ; batch Z=\{z_{i}\}_{i=1}^{B} ; loop horizon \tau ; sketch dim. m ; per-parameter sketch maps \{\mathsf{CS},\mathsf{TS}\} ;sequence length L ; recurrent function F 2: \widetilde{\phi}_{1:B,t}\leftarrow[\,] for all t=1,\dots,\tau 3: Attach hooks to F to cache forward inputs \mathbf{a}_{t,j} and read backward signals \delta_{t,j} 4: Run one forward pass 5: for each step t during backward pass do 6: for each matrix/vector parameter W,b in F do 7: \widetilde{\nabla_{W}}\ell=\sum_{j=1}^{L}\mathsf{TS}(\delta_{t,j},a_{t,j}) 8: \widetilde{\nabla_{b}}\ell=\sum_{j=1}^{L}\mathsf{CS}(\delta_{t,j}) 9: Append (\widetilde{\nabla_{W}}\ell,\widetilde{\nabla_{b}}\ell) to \widetilde{\phi}_{1:B,t} 10: end for 11: end for 12: \widetilde{\mathbf{g}}_{1:B}\leftarrow\sum_{t=1}^{\tau}\widetilde{\phi}_{1:B,t} (cf. Equation 11 ) 13: return Sketched per-example gradients \widetilde{\mathbf{g}}_{1:B}\in\mathbb{R}^{B\times m} and sketched step-resolved gradients \{\widetilde{\phi}_{1:B,t}\}_{t=1}^{\tau} . Error bounds Our sketched SDI estimator is unbiased and has variance that scales as \mathcal{O}(1/m) in the sketch dimension m , corresponding to a typical estimation error that scales as \mathcal{O}(\nicefrac{{1}}{{\sqrt{m}}}) . We show this by specialising and tightening the TensorSketch variance bound of 32 : Lemma 1 . Fix examples z,z^{\prime} , their SDI estimates \mathcal{I}_{t},\widetilde{\mathcal{I}}_{t} and checkpoints \mathcal{W}=\{\mathbf{w}_{k}\}_{k=1}^{K} . For each k , define the training-gradient vector \mathbf{g}_{k}\coloneqq\nabla_{\mathbf{w}_{\textnormal{body}}}\ell(\mathbf{w}_{k};z), and for each t{\in}\{1,\dots,\tau\} define the test-step vector \mathbf{p}_{k,t}\coloneqq\phi_{t}(\mathbf{w}_{k};z^{\prime}). Let \mathcal{S} be the sketch map described above with sketch dimension parameter m , which we assume is even. Define the full and sketched dot products \iota_{k,t}\coloneqq\mathbf{g}_{k}\cdot\mathbf{p}_{k,t} and \widetilde{\iota}_{k,t}\coloneqq\widetilde{\mathbf{g}_{k}}\cdot\widetilde{\mathbf{p}_{k,t}}. Then, \mathbb{E}\big[\widetilde{\iota}_{k,t}\big]=\iota_{k,t} and \operatorname{Var}\left(\widetilde{\iota}_{k,t}\right){\leq}(\nicefrac{{4}}{{m^{2}}}+\nicefrac{{6}}{{m}})\,\|\mathbf{g}_{k}\|_{2}^{2}\,\|\mathbf{p}_{k,t}\|_{2}^{2}. Consequently, for each step t , \mathbb{E}\left[\left(\widetilde{\mathcal{I}}_{t}{-}\mathcal{I}_{t}\right)^{2}\right]{\leq}\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\left(\sum_{k=1}^{K}\eta_{k}\|\mathbf{g}_{k}\|_{2}\|\mathbf{p}_{k,t}\|_{2}\right)^{2}. (12) Proof. See Appendix C . ∎ We remark that the (\nicefrac{{4}}{{m^{2}}}+\nicefrac{{6}}{{m}}) factor above comes from our novel bound of \operatorname{Var}\left(\widetilde{\iota}_{k,t}\right) and is strictly tighter than the \nicefrac{{8}}{{m}} factor derived in 32 . Moreover, our bound cannot be improved in general: there exists gradients \mathbf{g}_{k},\mathbf{p}_{k,t} such that the bound on \operatorname{Var}\left(\widetilde{\iota}_{k,t}\right) is tight. See Lemma 4 in the Appendix for the proof. Lemma 1 highlights the key scaling behaviour we need for SDI: the sketch error decays as m grows and has no explicit dependence on the parameter dimension |\mathbf{w}_{\textnormal{body}}| . 4 Experiments Scalability and Correctness We first empirically validate that SDI is practical for larger-scale looped transformers. For this purpose, we instantiate a looped 135.1 M-parameter GPT ( 34 ; 28 ) with loop horizon \tau{=}32 . This yields an effective depth of 132 blocks and is FLOP-equivalent to a 1 B-parameter model at sequence length 128 , and all computations are in 32 -bit floating point precision. Our TensorSketch SDI implementation matches the full stepwise-gradient baseline with low distortion while substantially reducing GPU memory consumption and negligible runtime overhead: On a single 48GB NVidia RTX A6000 GPU, our implementation translates into an order-of-magnitude increase in feasible batch size ( 4{\to}40 at m{=}2048 ). Fidelity improves predictably with sketch dimension: at m{=}2048 (used throughout the rest of the experimental section), relative SDI and TracIn errors are 0.0388\pm 0.0030 and 0.0220\pm 0.0052 (average \pm standard deviation over 10 independent trials). Moreover, m exhibits the expected \nicefrac{{1}}{{\sqrt{m}}} scaling (log–log slope: -0.489 , see Appendix Figure 4 ). Conservation holds to numerical precision: the direct sketch of the full gradient matches the sum of per-step sketches up to \approx 10^{-7} absolute error. Critically, our sketched SDI estimator adds little runtime overhead: at batch size 40 , computing SDI adds only 2.55\pm 0.002 s (10 trials) per weight checkpoint compared to an inference-only forward pass. Taken together, these results show that SDI is a scalable tool that can be deployed on LLM-scale looped transformers even on modest hardware. SDI as a MechInterp hypothesis generator Mechanistic Interpretability (MechInterp) attempts to explain model behaviour in terms of internal algorithmic mechanisms ( circuits ( 13 ) ) rather than input/output attribution. We next demonstrate the synergy between data attribution and MechInterp by leveraging SDI to uncover and validate a finite-state circuit inside a looped transformer trained on the parity task. Following 14 , we train a causal looped transformer with a single weight-tied decoder block and additive input injection. Further model details can be found Appendix D . For a sequence with n random bits, the model loops \tau{=}n+2 times, but we read out and compute the loss on the hidden state captured at loop iteration n . We train with a length curriculum that increases the maximum number of digits from 2 to 21 during training, and evaluate on length- 40 out-of-distribution inputs where the trained model achieves 100\% accuracy. To probe the latent computation, we compute SDI trajectories for the loop-body parameters and demonstrate SDI on a “probe” input (0101\dots) of length 40 . As shown in Figure 1 A, SDI exhibits a sawtooth-like oscillation with apparent period 4 , a final peak at step n after which it drops to zero (since later loop iterations are causally unused and shown only for demonstration). In parallel, we track the model’s forward dynamics via the logit margin at the answer token across loop iterations, which displays the same period- 4 structure with sharp margin increases lagging SDI peaks by one iteration ( Figure 1 A). These step-resolved signatures suggest that the answer-token hidden state is cycling among a small number of discrete latent states. Figure 1 : SDI as a mechanistic discovery tool We train a looped transformer on parity and apply SDI to an alternating probe (0101\dots) . (A) SDI and Logit Margin at the answer token across loop iterations t ; light gray guides indicate the SDI peak phase (period 4 ) and the dotted gray line at t{=}40 marks the model’s readout step. (B) PCA phase portrait of the answer-token hidden state across loop iterations, coloured by a k{=}4 discretization, revealing a four-state limit cycle. We validate this hypothesis by explicitly unrolling the recurrent computation on the probe and recording the answer-token hidden state \mathbf{h}_{t} after each loop iteration. We find strong recurrence at period 4 with \mathbb{E}\cos(\mathbf{h}_{t},\mathbf{h}_{t+4}){\approx}0.95 and a clear 4 -state cycle in PCA space ( Figure 1 B). Discretising \{\mathbf{h}_{t}\} by k -means with k{=}4 yields an almost-deterministic transition graph with a single dominant cycle except for an initial transient self-loop: \widehat{P}{=}\begin{pNiceMatrix} , where \widehat{P}_{ij} is the empirical probability of transitioning from state i to j at the next loop iteration ( Figure 1 B). Finally, we turn this circuit hypothesis into a proxy by replacing the model’s linear readout by a discrete state assignment (nearest k -means centroid at the readout step) followed by a state-to-parity lookup table learned on a small calibration set of alternating inputs. This proxy achieves 100\% accuracy on held-out alternating inputs across a wide range of lengths, including lengths beyond the training curriculum, and it remains highly predictive on the actual length- 40 test set performance of the model ( {\approx}93\% accuracy without refitting the discretisation). In summary, SDI provides a visual, step-resolved signature of latent periodic computation that guides a concrete mechanistic analysis and yields an interpretable proxy circuit. Taken together with the results of 14 , these findings indicate that looped transformer latent reasoning can implement discrete, length-generalisable finite-state algorithms for specific types of problems and inputs. Scaling laws of loop compute A central promise of looped transformers is test-time compute scaling in activation space: at inference, one can allocate additional compute by unrolling the shared block for more recurrent iterations, without changing the input/output token length (in contrast to token-space test-time scaling). We study this regime on the Sudoku dataset from 36 . Following the approaches of 38 ; 30 , we train a looped transformer with bidirectional attention, a single weight-tied decoder block and no input injection with a Poisson log-normal distribution over loop horizons with mean \tau{=}32 (clipped at 1{\leq}\tau{\leq}64 ), and evaluate the trained model at fixed test-time loop budgets between 4 and 64 . Further model details can be found Appendix D . As shown in Figure 2 A, harder puzzles are substantially more compute-sensitive: reducing loops sharply degrades accuracy, while increasing loops yields gains up to about \tau{\approx}64 before saturating. To connect these accuracy scaling curves to the latent computation, we compute SDI and summarise the per-step magnitude of stepwise SDI scores as an SDI energy curve. Figure 2 B shows that hard instances maintain higher SDI energy deeper into the recurrence (slower decay—note the logarithmic y -axis scaling), indicating that later recurrent steps remain relevant when additional loop compute yields the largest gains . In this sense, SDI complements accuracy-based scaling curves by characterising where/how long along the recurrent computation additional test-time compute remains salient. Figure 2 : Scaling laws of loop compute on SATNet Sudoku. (A) Test board accuracy (a board is correct iff all blank cells are correct) versus the number of test-time loops, stratified by puzzle difficulty (binned by the number of initial missing cells; more missing implies harder). Harder puzzles are substantially more compute-sensitive: reducing loops sharply degrades accuracy, while increasing loops yields gains up to about the training-mean depth \tau{\approx}32 (dotted line) before saturating; we include {>}32 loops to show the plateau. (B) SDI energy across loop steps (median and IQR across puzzles in each difficulty bin), where SDI energy at step t is the sum of absolute stepwise SDI scores across training points. Harder puzzles maintain higher SDI energy deeper into the recurrence (slower decay), mirroring their larger marginal gains from additional loop compute. (Step-resolved) influence across difficulty An advantage of algorithmic reasoning datasets is that they offer a precise notion of instance difficulty while avoiding the long-tail heterogeneity of natural text corpora ( 16 ; 15 ) . For Sudoku, difficulty is the number of missing cells, yet all examples share a bounded, highly regular support (a fixed 9{\times}9 grid with the same local constraints), making this a clean testbed to study memorisation and influence without confounding from rare lexical patterns. Using (TracIn) self-influence as a proxy for memorisation as proposed by 15 , we find that harder training puzzles are systematically more memorised : self-influence increases moderately with the number of blanks (Spearman \rho{=}0.428 , p{<}0.001 ), and hard training puzzles (missing \geq 45 ) have roughly 2\times larger median self-influence than easy ones (missing \leq 42 ; Table 1 ). This mirrors the observations of 15 on natural data that harder examples tend to be memorised more, but interestingly, here the effect arises despite the absence of a long-tail support shift, suggesting an optimisation-driven bias tied to instance difficulty rather than rarity. We next use SDI to examine how memorisation relates to generalisation (cross-influence) and when influence acts in the recurrent computation. Define the cross-influence mass of a training puzzle z as C(z){=}\sum_{z^{\prime}\in\mathcal{D}_{\mathrm{test}}}|\operatorname{TracIn}(z,z^{\prime})| . We find C(z) increases moderately with training difficulty (Spearman \rho{=}0.500 , p{<}0.001 ) and very strongly with self-influence ( \rho{=}0.919 , p{<}0.001 ); in particular, in this run we find no examples in the bottom quartile of self-influence that lie in the top quartile of C(z) , indicating that the most broadly cross-influential Sudoku puzzles are also the most memorised. Finally, SDI reveals a step-resolved signature of this coupling: decomposing the test-side SDI energy ( Figure 2 B) by training difficulty shows that hard training puzzles not only account for a larger share of |\operatorname{TracIn}| mass, but also place significantly more SDI energy in late loop iterations (steps 17 – 32 of \tau{=}32 ; Table 1 ). Intuitively, hard puzzles are more memorised and help harder test puzzles more. This influence is exerted for longer throughout the loop. We view these results as closely related to the findings of 4 in (non-transformer) classification NNs, who establish that harder examples are correctly predicted in deeper layers of the model and that these deeper layers (in our depth-recurrent transformers: later loop steps) are responsible for memorisation. Table 1 : Influence, memorisation, and SDI timing on Sudoku. Easy train : missing {\leq}42 ; Hard train : missing {\geq}45 . On test bins ( 46 – 47 blanks = easy test; 49 – 50 blanks = hard test), Share is the mean fraction of per-test |\operatorname{TracIn}| mass attributable to the given training group. SDI late mass is the mean fraction of SDI energy in late steps t{\geq}17 (of \tau{=}32 ). p -values are Welch (train-train) or paired (train-test) t-tests and p{<}0.001 for all results in the table. Easy train Hard train Self TracIn (median [IQR]) 0.225 [0.155, 0.367] 0.451 [0.303, 0.787] Cross mass C(z) (median [IQR]) 3.07 [2.60, 3.82] 4.43 [3.77, 5.80] On easy test puzzles (46–47 blanks): Share of |\operatorname{TracIn}| mass 28.9% 37.7% SDI late mass (steps 17–32) 24.0% 24.9% On hard test puzzles (49–50 blanks): Share of |\operatorname{TracIn}| mass 27.9% 38.9% SDI late mass (steps 17–32) 24.3% 25.3% Nanochat Finally, we present a case study on recursive Nanochat , a 328.3 M-parameter GPT-style chat model, retrofitting looped computation into Nanochat ( 28 ) as in 30 . Details on the model training can be found Appendix D . In brief, the model is trained on a mixture of datasets (including reasoning datasets like GSM8K, ARC-Easy and ARC-Challenge and general language datasets like SmolTalk and SpellingBee) over three stages: pretraining, mid-training and supervised fine-tuning with truncated BPTT ( k{=}4 ) and training loop steps sampled from a a Poisson log-normal distribution with mean 4 . We focus on GSM8K (train/test) as a reasoning dataset and evaluate SDI using various test-time recurrence counts \tau\in\{2,\dots,16\} with sketch dimension m{=}2048 on the full answer. Importantly, we recompute SDI without truncation i.e., with full BPTT through all \tau loop steps. For all training stages that include GSM8K, influence is allocated almost exclusively to late loop steps: SDI increases nearly exponentially with t with the last step alone usually contributing \geq 50\% of the total influence. Figure 3 shows the normalised cumulative signed SDI sum per step t for GSM8K exemplarily in the supervised fine-tuning stage. Interestingly, the model seems to build up the entirety of its total influence within these last loop steps, independently of how many loop steps it is actually allowed to take. These results lead us to the hypothesis that the model implicitly encodes a “loop step counter” in the latent state: SDI reveals that—even without an explicit step embedding—the transformer seems able to represent progress through the loop because the model “knows what the four last loop steps are” . This finding is corroborated by the task-specific performance on GSM8K plateauing for all test-time \tau>4 . We regard a deeper investigation of this phenomenon as a promising direction for future work. Figure 3 : Geometric influence growth across the loop horizon. Signed SDI share per step t for several analysis horizons \tau in mid-training stage, recomputed with full BPTT through the recurrence from GSM8K train to GSM8K test. Removing truncation reveals a smooth, approximately geometric increase of stepwise influence with depth. 5 Discussion and future work We have presented Step-Decomposed Influence (SDI), a framework that transforms data attribution from a scalar score into a temporal trajectory. By unrolling the gradient dynamics of looped transformers, SDI reveals not just which data points contribute to model performance, but when their influence manifests during the latent reasoning process. Limitations TracIn admits the cleanest interpretation under (stochastic) gradient descent, where checkpoint weights \eta_{k} directly reflect the learning-rate schedule. In modern training pipelines, the loop-body parameters may instead be updated by momentum, adaptive preconditioning, or optimizer-specific transformations. In such settings, our estimator should be viewed as a TracIn-style gradient-similarity influence computed along the training trajectory rather than a faithful approximation to an influence function derived from a specific optimization dynamics. A promising direction is to incorporate optimizer geometry more explicitly, e.g., by defining a preconditioned inner product. Moreover, SDI is defined with respect to a particular unrolling of the computation graph and an analysis horizon \tau . When training uses randomized loop counts, adaptive halting, or truncated BPTT, step indices are not always comparable across examples, and truncation can systematically remove long-range credit assignment (early-step SDI is identically zero by construction). While we can recompute SDI with full BPTT for analysis (as in our Nanochat case study), scaling full-horizon SDI to very long recurrences remains expensive. Addressing this may require improved systems techniques, e.g., more aggressive activation recomputation/checkpointing or hardware scaling. Future Work Like TracIn, SDI measures gradient alignment along a training trajectory; it does not on its own certify that removing or reweighting an example will change behaviour in a specific way, nor does it disentangle confounds such as shared features across many examples. Moreover, although sketching removes the need to materialize per-example gradients, computing dense train \times test influence matrices is still costly at very large |\mathcal{D}_{\mathrm{train}}| . A natural next step is to treat the sketched per-example (and per-step) vectors as an indexable embedding space: one can build approximate nearest-neighbour retrieval over \widetilde{\nabla\ell(\cdot)} to find the most influential candidates for each query, and then refine SDI on a small retrieved set, enabling scalable workflows such as depth-targeted data curation and debugging. Another promising direction is extending SDI beyond supervised next-token losses to modern alignment pipelines. For RLHF-style preference optimization, one could compute step-resolved influence of preference pairs on downstream behaviours, revealing whether alignment data primarily shapes early “instruction following” dynamics or late “reasoning/refinement” steps, and identifying training examples that disproportionately affect late-step computation where subtle failures often emerge. Similarly, in RL settings with verifiable rewards, SDI could help localize which trajectories and reward signals drive improvements at specific recurrent steps and diagnose step-local reward hacking. Finally, SDI suggests new ways to use the recurrence: step-energy curves and influence horizons could be turned into instance-wise stopping criteria or training-time regularisers that encourage useful computation to persist deeper into the loop, directly connecting interpretability signals to test-time compute allocation and model design. Impact Statement We introduce theoretical and practical tools for data attribution in looped transformers, bridging the gap between static influence scores and dynamic latent reasoning. While we acknowledge that precise influence estimation could theoretically be exploited to identify vulnerabilities for targeted data poisoning or to manipulate specific reasoning steps, we anticipate that these methods will be critical for improving model safety and transparency. By enabling practitioners to audit internal computations and trace the origins of model behaviours to specific training examples, our framework facilitates model debugging and dataset curation, ultimately supporting the development of more reliable and accountable AI reasoning systems. Appendix A Extended Related Work Looped transformers The concept of reusing transformer layers to increase computational depth without increasing parameters dates back to the Universal Transformer ( 11 ) . Recent work has demonstrated that looped transformers can act as programmable computers capable of executing iterative algorithms ( 19 ) and are superior at learning algorithms compared to standard transformers ( 37 ) . 35 further bridge the gap to reasoning, arguing that looped models implicitly simulate Chain-of-Thought in continuous space while 20 study formal properties of their learning dynamics. Scaling properties of these models have been investigated by 42 and 14 , who show that loop-based architectures scale favourably for length generalisation in algorithmic tasks. Recent architectures such as Ouro ( 42 ) and RecurrentGemma ( 8 ) have successfully scaled these principles to LLM benchmarks. Our work complements this literature by providing the first (to our knowledge) step-resolved training-data influence estimator for weight-tied looped transformers, decomposing data influence across recurrent computation iterations rather than producing a scalar score aggregated over loop steps. Stepwise attribution in recurrent models A broad literature studies stepwise attribution in recurrent non-transformer models, typically explaining a prediction by assigning importance to input timesteps (or tokens) rather than to internal recurrent computation iterations; examples include additive decompositions such as REAT ( 12 ) and perturbation-based explainers such as TimeSHAP ( 6 ) . Other work adapts training-data influence techniques to sequential settings, e.g., blockwise deletion for temporally correlated sequences ( 2 ) or influence for sequence tagging segments ( 25 ) . These methods are complementary to SDI: we focus on weight-tied looped transformers and decompose training-example influence across the model’s internal loop iterations, yielding a time-resolved influence trajectory over latent computation steps. Latent reasoning Moving reasoning from explicit tokens to latent space is a rapidly growing frontier ( 41 ; 10 ) . Approaches like Coconut ( 22 ) train models to reason in continuous latent space, while others explore specialised architectures for recursive reasoning, such as block-recurrent dynamics in vision ( 24 ) , Tiny Recursive Models ( 27 ) and the very recent Universal Reasoning Model ( 17 ) that explicitly cites the recurrent design, inherited from Universal Transformers, as a key to SOTA results on very challenging reasoning benchmarks. 18 and 30 demonstrate that recurrent depth is a key enabler for scaling test-time compute. The recent work of 7 studies the question of “which reasoning steps matter?” in reasoning models, but limits itself to models that reason in token space. On the other hand, the opacity of latent space in latent reasoning models remains a significant hurdle; our work attempts to bridge the gap by linking discrete latent computational steps back to the training data. Data attribution Understanding model behaviour by identifying influential training examples is a fundamental goal of interpretability. The recent survey by 21 highlights the utility of data attribution methods for debugging and data curation, while the seminal works of 16 ; 15 have linked data attribution (and specifically influence estimation) to generalisation properties of deep neural networks. Classic approaches for influence estimation rely on Influence Functions ( 29 ) , which estimate the effect of upweighting a training point via the Hessian. However, for modern deep networks and LLM-scale models, explicitly forming or inverting the Hessian is typically computationally prohibitive; practical influence-function implementations therefore rely on approximations. Gradient-based attribution methods, such as TracIn ( 33 ) , approximate influence by tracing the dot product of gradients throughout training, a technique that has been theoretically connected to influence-function-style quantities under specific assumptions on the optimisation dynamics ( 39 ) . We rely on TracIn over Influence Functions for two reasons: (1) Influence Functions typically assume a converged model whereas TracIn operates on the optimisation trajectory, allowing us to attribute behaviour to specific training dynamics captured at any intermediate checkpoint; (2) TracIn admits a clean linear decomposition over the recurrent computation as shown below, directly enabling the unrolled attribution of SDI, while it is unclear how to derive a similarly interpretable decomposition for curvature-based influence estimates involving the inverse Hessian across recurrent steps. Our work is complementary to current interpretability work that attributes model behaviour to internal computation at varying granularities (e.g., layer-wise, or circuit-level mechanisms ( 13 ) ) but these analyses typically assume a feedforward depth axis with untied parameters. In weight-tied looped transformers, repeated reuse of the same parameters collapses this axis, motivating attribution methods that explicitly resolve influence across recurrent iterations of a shared computation. Sketching and CountSketch/TensorSketch Randomised sketching methods provide structured, memory-efficient alternatives to dense random projections for approximately preserving inner products. In particular, CountSketch constructs sparse random linear maps that preserve dot products in expectation while being computationally cheap ( 9 ) . TensorSketch extends this idea to tensor products, enabling fast sketching of outer products via FFT-based convolution ( 31 ; 32 ) . Its core utility is the compression of sums of outer products without explicitly forming the high-dimensional tensors. We exploit this in SDI by observing that per-example gradients of transformer linear weights factor as outer products of activations and backpropagated signals; TensorSketch therefore allows us to compute per-example and per-step SDI features directly during backpropagation, avoiding materialisation of full per-example gradients. This is a key innovation over previous applications of TracIn that used dense ( 33 ) or sparse ( 23 ) Johnson Lindenstrauss (JL) projections ( 26 ; 1 ) . We elaborate on CountSketch and TensorSketch in the next subsection. Appendix B Overview of CountSketch and TensorSketch CountSketch was introduced in the context of estimating the frequency of items in a data stream, and TensorSketch in the context of approximating polynomial kernels in high dimensions. In this work, we instead use these techniques to compute SDI estimates. As a result, we use only a small subset of the results from the seminal papers of 31 ; 32 . We provide an overview of the relevant results in this section, starting with some notation: Notation Bolded lowercase letters such as \mathbf{u} denote vectors and bolded uppercase letters such as \mathbf{U} denote matrices. Let [n]=\{1,\ldots,n\} , \mathbf{u}\otimes\mathbf{v}=\mathbf{u}\mathbf{v}^{\top} denote the outer product of \mathbf{u} with \mathbf{v} , and \langle\mathbf{u},\mathbf{v}\rangle=\mathbf{u}^{\top}\mathbf{v} denote the vector inner product. The inner product between two matrices is the Frobenius inner product \langle\mathbf{U},\mathbf{V}\rangle=\text{tr}(\mathbf{U}^{\top}\mathbf{V}) . Note that the Frobenius inner product is the same as flattening the matrices into 2 vectors, then computing the vector inner product. In the main body, we flattened all matrices into vectors, and used the notation \mathbf{u}\cdot\mathbf{v} denote the inner product for both vectors and matrices. In this Appendix, we keep the shapes of the matrices (we do not flatten), and use the notation \langle\cdot,\cdot\rangle to denote the inner product for both vectors and matrices. Let \circ denote the Hadamard product so that \mathbf{Y}=\mathbf{U}\circ\mathbf{V} means \mathbf{Y}_{ij}=\mathbf{U}_{ij}\mathbf{V}_{ij} . Now, we introduce the concept of k -wise independence, which is needed for reasoning about the randomness in hash functions: Definition 2 . A family \mathcal{H} of functions f:[d]\rightarrow[m] is k-wise independent if for any set of integers \{i_{1},\ldots,i_{k}\}\subseteq[d] , and a random f\in\mathcal{H} , the vector of hash values \{f(i_{1}),\ldots,f(i_{k})\} is uniform in [m]^{k} . B.1 CountSketch Definition 3 ( 32 ) . Given h:[d]\rightarrow[m] sampled from a 2-wise independent family, and s:[d]\rightarrow\{-1,1\} sampled from a 4-wise independent family, a CountSketch \mathsf{CS} of a vector \mathbf{x}\in\mathbb{R}^{d} (often denoted \tilde{\mathbf{x}} and referred to as the sketch of \mathbf{x} ) is defined as the linear map \displaystyle\mathsf{CS}(\mathbf{x})_{j} \displaystyle=\sum_{\begin{subarray}{c}i\in[d]:h(i)=j\end{subarray}}s(i)\mathbf{x}_{i} \displaystyle=\sum_{\begin{subarray}{c}i\in[d]\end{subarray}}\mathds{1}[h(i)=j]s(i)\mathbf{x}_{i} In our settings, m\sum_{\begin{subarray}{c}\mathbf{u},\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}\mathds{1}[H(\mathbf{u})=\alpha]S(\mathbf{u})\mathbf{X}_{\mathbf{u}}\>\mathds{1}[H(\mathbf{v})=\alpha]S(\mathbf{v})\mathbf{Y}_{\mathbf{v}} \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u},\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\left(\sum_{\alpha\in[m]}\mathds{1}[H(\mathbf{u})=\alpha]\mathds{1}[H(\mathbf{v})=\alpha]\right) \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u},\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\>\mathds{1}[H(\mathbf{u})=H(\mathbf{v})] \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u},\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}} \displaystyle=\langle\mathbf{X},\mathbf{Y}\rangle+\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}} Since s_{1} and s_{2} are 2-wise independent, their product S . This means S(\mathbf{u})S(\mathbf{v}) (if \mathbf{u}\neq\mathbf{v} ) is the product of two independent Rademacher random variables, which has mean 0 in expectation. Therefore \mathbb{E}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle]=\langle\mathbf{X},\mathbf{Y}\rangle . Now, for the variance. We write: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\mathbb{E}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle^{2}]-\langle\mathbf{X},\mathbf{Y}\rangle^{2}. (13) We expand \langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle^{2} to: \displaystyle\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle^{2} \displaystyle=\left(\langle\mathbf{X},\mathbf{Y}\rangle+\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\right)^{2} \displaystyle=\langle\mathbf{X},\mathbf{Y}\rangle^{2}+2\langle\mathbf{X},\mathbf{Y}\rangle\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}}+\left(\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\right)^{2}. (14) The first term of Equation 14 is a constant and cancels the same term in Equation 13 . The second term disappears when we take the expectation due to the 2-wise independence of S . The third term is non-zero since the 2-wise independence of S introduces correlations. We are left with: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\mathbb{E}\left[\left(\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\right)^{2}\right] \displaystyle=\mathbb{E}\left[\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\\ \mathbf{u^{\prime}}\neq\mathbf{v^{\prime}}\in[d]\times[d^{\prime}]\end{subarray}}S(\mathbf{u})S(\mathbf{v})S(\mathbf{u}^{\prime})S(\mathbf{v}^{\prime})\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{X}_{\mathbf{u^{\prime}}}\mathbf{Y}_{\mathbf{v^{\prime}}}\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\mathbf{\xi}_{\mathbf{u}^{\prime},\mathbf{v}^{\prime}}\right] \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\\ \mathbf{u^{\prime}}\neq\mathbf{v^{\prime}}\in[d]\times[d^{\prime}]\end{subarray}}\mathbb{E}\left[S(\mathbf{u})S(\mathbf{v})S(\mathbf{u}^{\prime})S(\mathbf{v}^{\prime})\right]\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{X}_{\mathbf{u^{\prime}}}\mathbf{Y}_{\mathbf{v^{\prime}}}\mathbb{E}\left[\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\mathbf{\xi}_{\mathbf{u}^{\prime},\mathbf{v}^{\prime}}\right] (15) Where we used the linearity of expectation and the fact that randomness of S is independent of the randomness of H to split the expectation into two. Evaluating the expectation Equation 15 is non-trivial and will take multiple pages of work. We begin by splitting the expectation over S into three expectations over s_{1},s_{2} and H (recall that s_{1},s_{2} are independent from one other and 4-wise independent, and H is independent of s_{1},s_{2} and 2-wise independent). The full expression for the sum is (in the unrolled indices) is: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\sum_{\begin{subarray}{c}i,i^{\prime},k,k^{\prime}\in[d]\\ j,j^{\prime},\ell,\ell^{\prime}\in[d^{\prime}]\end{subarray}}\mathbb{E}[s_{1}(i)s_{1}(k)s_{1}(i^{\prime})s_{1}(k^{\prime})]\mathbb{E}[s_{2}(j)s_{2}(\ell)s_{2}(j^{\prime})s_{2}(\ell^{\prime})] (16) \displaystyle\cdot\mathds{1}[i\neq k\text{ or }j\neq\ell)]\mathds{1}[i^{\prime}\neq k^{\prime}\text{ or }j^{\prime}\neq\ell^{\prime})]\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{i^{\prime}j^{\prime},k^{\prime}\ell^{\prime}}\right] \displaystyle\cdot\mathbf{X}_{ij}\mathbf{Y}_{k\ell}\mathbf{X}_{i^{\prime}j^{\prime}}\mathbf{Y}_{k^{\prime}\ell^{\prime}} where \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{i^{\prime}j^{\prime},k^{\prime}\ell^{\prime}}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,\ell)\text{ and }(H(i^{\prime},j^{\prime})=H(k^{\prime},\ell^{\prime})] Note that the s_{1},s_{2} expectations can only be 0 or 1 . Therefore, in order to determine what this sum evaluates to, we will first identify the indices where the expectations over s_{1},s_{2} are non-zero. Then, we will determine if the indicator functions rule out any of those indices. Then, we will find what the \xi expectations equal under the remaining indices, then we will do the sums over the tensors \mathbf{X},\mathbf{Y} . In order for a term to contribute to the sum, both of the s_{1},s_{2} expectations must be 1. Lets focus on the expectation over s_{1} . The only way for this to be non-zero is if the 4 indices are all equal or if the 4 indices form 2 equal pairs. This is because if three indices are equal then we have \mathbb{E}[s(i)^{3}s(j)]=\mathbb{E}[s(i)^{3}]\mathbb{E}[s(j)]=0 . The same thing happens if the 4 indices are not the same. For one expectation, this means we have the following cases: \displaystyle\mathbb{E}[s_{1}(i)s_{1}(k)s_{1}(i^{\prime})s_{1}(k^{\prime})] \displaystyle=\begin{cases}1\quad\text{if }i=k\text{ and }k^{\prime}=i^{\prime}\\ 1\quad\text{if }i=i^{\prime}\neq k=k^{\prime}\\ 1\quad\text{if }i=k^{\prime}\neq k=i^{\prime}\\ 0\quad\text{otherwise}\end{cases} Note that the first case jointly covers when i=k\neq k^{\prime}=i^{\prime} and i=k=k^{\prime}=i^{\prime} . We have the same 3 cases for the other expectation, which leads to nine total cases for when the total expectation is 1 : \displaystyle\mathbb{E}[s_{2}(j)s_{2}(\ell)s_{2}(j^{\prime})s_{2}(\ell^{\prime})] \displaystyle=\begin{cases}1\quad\text{if }j=\ell\text{ and }\ell^{\prime}=j^{\prime}\\ 1\quad\text{if }j=j^{\prime}\neq\ell=\ell^{\prime}\\ 1\quad\text{if }j=\ell^{\prime}\neq\ell=j^{\prime}\\ 0\quad\text{otherwise}\end{cases} Lets go through each of the 9 cases individually. The order we go in will appear random upon a first reading, but as the math proceeds it will become clear why we go in the order we do. In each case, we will first evaluate what the \xi expectation simplifies to, then we will do the sum over the tensors \mathbf{X},\mathbf{Y} , which we will also write into matrix notation. The following summation identities will be useful: \displaystyle\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}A_{ijk\ell} \displaystyle=\sum_{\begin{subarray}{c}i,k\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}A_{ijk\ell}-\sum_{\begin{subarray}{c}i\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}A_{iji\ell}-\sum_{\begin{subarray}{c}i,k\in[d]\\ j\in[d^{\prime}]\end{subarray}}A_{ijkj}+\sum_{\begin{subarray}{c}i\in[d]\\ j\in[d^{\prime}]\end{subarray}}A_{ijij} (17) \displaystyle\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}A_{ijk\ell} \displaystyle=\sum_{\begin{subarray}{c}i,k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}A_{ijk\ell}-\sum_{\begin{subarray}{c}i\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}A_{iji\ell} (18) The following matrix equalities will also be useful: \displaystyle(\mathbf{X}\mathbf{Y})_{ij}=\sum_{k}\mathbf{X}_{ik}\mathbf{Y}_{kj}\quad(\mathbf{X}^{T}\mathbf{Y})_{ij}=\sum_{k}\mathbf{X}_{ki}\mathbf{Y}_{kj}\quad(\mathbf{X}\mathbf{Y}^{T})_{ij} \displaystyle=\sum_{k}\mathbf{X}_{ik}\mathbf{Y}_{jk}. We begin with the 9 cases: 0: (i=k\text{ and }k^{\prime}=i^{\prime}) and (j=\ell\text{ and }\ell^{\prime}=j^{\prime}) . While this case makes the expectation 1 , terms with this indices in the sum Equation 16 are zero due to the indicator functions, so this case can be discarded. 1: (i=k\text{ and }k^{\prime}=i^{\prime}) and (j=j^{\prime}\neq\ell=\ell^{\prime}) . We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,i\ell}\mathbf{\xi}_{i^{\prime}j,i^{\prime}\ell}\right] \displaystyle=\text{Pr}[(H(i,j)=H(i,\ell)\text{ and }(H(i^{\prime},j)=H(i^{\prime},\ell)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle\equiv h_{1}(i)+h_{2}(\ell)\quad(\text{mod }m) (19) \displaystyle h_{1}(i^{\prime})+h_{2}(j) \displaystyle\equiv h_{1}(i^{\prime})+h_{2}(\ell)\quad(\text{mod }m). (20) where here we use \equiv to denote equality under the modulo operation. Remember that we are interested in the probability that both events Equation 19 and Equation 20 occur. Subtracting like terms, we have that the events simplify to: \displaystyle h_{2}(j)-h_{2}(\ell)\equiv 0\quad(\text{mod }m) Since h_{2} is 2-wise independent and j\neq\ell , h_{2}(j),h_{2}(\ell) can be treated as two independent uniform random variables in [m] , and therefore h_{2}(j)-h_{2}(\ell)\text{ mod }m is a uniform random variable in \{0,1,\ldots,m-1\} . Therefore the probability that it equals 0 is simply 1/m , and the expectation over \xi is: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,i\ell}\mathbf{\xi}_{i^{\prime}j,i^{\prime}\ell}\right] \displaystyle=\frac{1}{m} With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . The sum becomes: \displaystyle T_{1} \displaystyle=\sum_{\begin{subarray}{c}i,i^{\prime}\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{i\ell}\mathbf{X}_{i^{\prime}j}\mathbf{Y}_{i^{\prime}\ell} \displaystyle=\sum_{j\neq\ell}\left(\sum_{i\in[d]}\mathbf{X}_{ij}\mathbf{Y}_{i\ell}\right)\left(\sum_{i^{\prime}\in[d]}\mathbf{X}_{i^{\prime}j}\mathbf{Y}_{i^{\prime}\ell}\right) \displaystyle=\sum_{j\neq\ell}(\mathbf{X}^{T}\mathbf{Y})_{j\ell}(\mathbf{X}^{T}\mathbf{Y})_{j\ell} \displaystyle=\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}-\sum_{j\in[d^{\prime}]}(\mathbf{X}^{T}\mathbf{Y})_{jj}(\mathbf{X}^{T}\mathbf{Y})_{jj} \displaystyle=\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}-\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2} Note that the actual contribution to the sum is \frac{1}{m}T_{1} . We exclude the 1/m term in the derivation above for notational clarity, and also because in the upcoming cases, the same T_{1} term appears although the value of the \xi expectation is different. 2: (i=k^{\prime}\neq k=i^{\prime}) and (j=j^{\prime}\neq\ell=\ell^{\prime}) Similar to T_{1} , here the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{kj,i\ell}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,\ell)\text{ and }(H(k,j)=H(i,\ell)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle\equiv h_{1}(k)+h_{2}(\ell)\quad(\text{mod }m) \displaystyle h_{1}(k)+h_{2}(j) \displaystyle\equiv h_{1}(i)+h_{2}(\ell)\quad(\text{mod }m). We can rearrange the events as: \displaystyle h_{1}(i)-h_{1}(k) \displaystyle\equiv-(h_{2}(j)-h_{2}(\ell))\quad(\text{mod }m) \displaystyle h_{1}(i)-h_{1}(k) \displaystyle\equiv h_{2}(j)-h_{2}(\ell)\quad(\text{mod }m). Since h_{1},h_{2} are independent, the event A=h_{1}(i)-h_{1}(k)\text{ mod }m is independent of B=h_{2}(j)-h_{2}(\ell)\text{ mod }m . Moreover, A,B are uniform random variables in \{0,1,2,\ldots,m-1\} . Our equations of interest simplify to: \displaystyle A+B \displaystyle\equiv 0\quad(\text{mod }m) \displaystyle A-B \displaystyle\equiv 0\quad(\text{mod }m) Note that A+B\in\{0,\ldots,2m-2\} , therefore the only way for A+B\equiv 0(\text{ mod }m) is for A+B=\{0,m\} . Similarly, A-B\in\{-(m-1),\ldots,m-1\} , therefore the only way for A-B\equiv 0(\text{ mod }m) is for A-B=0 . Therefore, our probability simplifies to: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{kj,i\ell}\right] \displaystyle=\text{Pr}[A=B=0\text{ or }A=B=\frac{m}{2}] \displaystyle=\frac{1}{m^{2}}+\frac{\mathds{1}[m\text{ is even}]}{m^{2}}. The awkward indicator term occurs because if m is odd, then m/2 is not an integer, therefore A,B cannot take on that value and the expectation is 1/m^{2} . If m is even then they can and the expectation is 2/m^{2} . Since m is almost always even and a power of 2 for optimization purposes, we will assume the probability is 2/m^{2} . With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . Using the summation identity in Equation 18 , the sum can be written as T_{1} minus an extra off-diagonal like sum: \displaystyle T_{2} \displaystyle=\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{k\ell}\mathbf{X}_{kj}\mathbf{Y}_{i\ell} (21) \displaystyle=\text{\lx@cref{creftype\lx@tilde refnum}{T2i}}+\sum_{\begin{subarray}{c}i\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{i\ell}^{2}-\sum_{\begin{subarray}{c}i\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{i\ell}^{2} \displaystyle=T_{1}-\sum_{\begin{subarray}{c}i\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{i\ell}^{2} \displaystyle=T_{1}-\sum_{\begin{subarray}{c}i\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{i\ell}^{2}+\sum_{\begin{subarray}{c}i\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{ij}^{2} \displaystyle=T_{1}-\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))+\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle Note that the actual contribution to the sum is \frac{2}{m^{2}}T_{2} . 3: (i=i^{\prime}\neq k=k^{\prime}) and (j=\ell\text{ and }\ell^{\prime}=j^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,kj}\mathbf{\xi}_{ij^{\prime},kj^{\prime}}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,j)\text{ and }(H(i,j^{\prime})=H(k,j^{\prime})] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle\equiv h_{1}(k)+h_{2}(j)\quad(\text{mod m}) \displaystyle h_{1}(i)+h_{2}(j^{\prime}) \displaystyle\equiv h_{1}(k)+h_{2}(j^{\prime})\quad(\text{mod m}). Subtracting like terms, we have that the events simplify to: \displaystyle h_{1}(i)-h_{1}(k)\equiv 0\quad(\text{mod }m) The argument from here is identical to T_{1} but with different indices: since h_{1} is 2-wise independent and i\neq k , h_{1}(i),h_{1}(k) can be treated as two independent uniform random variables in [m] , and therefore h_{1}(i)-h_{1}(k)\text{ mod }m is a uniform random variable in \{0,1,\ldots,m-1\} . Therefore the probability that it equals 0 is simply 1/m , and the expectation over \xi is: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,kj}\mathbf{\xi}_{ij^{\prime},kj^{\prime}}\right] \displaystyle=\frac{1}{m}. With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . The sum is a partner to T_{1} since the arithmetic is identical but with different indices: \displaystyle T_{3} \displaystyle=\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j,j^{\prime}\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{kj}\mathbf{X}_{ij^{\prime}}\mathbf{Y}_{kj^{\prime}} \displaystyle=\sum_{i\neq k}\left(\sum_{j\in[d^{\prime}]}\mathbf{X}_{ij}\mathbf{Y}_{kj}\right)\left(\sum_{j^{\prime}\in[d^{\prime}]}\mathbf{X}_{ij^{\prime}}\mathbf{Y}_{kj^{\prime}}\right) \displaystyle=\sum_{i\neq k}(\mathbf{X}\mathbf{Y}^{T})_{ik}(\mathbf{X}\mathbf{Y}^{T})_{ik} \displaystyle=\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}-\sum_{i\in[d]}(\mathbf{X}\mathbf{Y}^{T})_{ii}(\mathbf{X}\mathbf{Y}^{T})_{ii} \displaystyle=\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}-\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2} Note that the actual contribution to the sum is \frac{1}{m}T_{3} . 4: (i=i^{\prime}\neq k=k^{\prime}) and (j=\ell^{\prime}\neq\ell=j^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{i\ell,kj}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,\ell)\text{ and }(H(i,\ell)=H(k,j)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle=h_{1}(k)+h_{2}(\ell)\quad\text{ mod }m \displaystyle h_{1}(i)+h_{2}(\ell) \displaystyle=h_{1}(k)+h_{2}(j)\quad\text{ mod }m. Moving terms around, we have that the events simplify to: \displaystyle h_{1}(i)-h_{1}(k) \displaystyle\equiv-(h_{2}(j)-h_{2}(\ell))\quad\text{ mod }m \displaystyle h_{1}(i)-h_{1}(k) \displaystyle\equiv h_{2}(j)-h_{2}(\ell)\quad\text{ mod }m. The events are identical to those analysed in Case 2. Therefore we have: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{i\ell,kj}\right] \displaystyle=\frac{2}{m^{2}} With the assumption that m is even. With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . This sum is a partner to T_{2} in that just like how T_{2} could be written as T_{1} minus an off-diagonal like sum, so can T_{4} be written as T_{3} minus an off-diagonal like sum using the summation identity in Equation 18 : \displaystyle T_{4} \displaystyle=\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq j^{\prime}\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{kj^{\prime}}\mathbf{X}_{ij^{\prime}}\mathbf{Y}_{kj} (22) \displaystyle=\lx@cref{creftype\lx@tilde refnum}{T4i}+\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{kj}^{2}-\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{kj}^{2} \displaystyle=T_{3}-\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{kj}^{2} \displaystyle=T_{3}-\sum_{\begin{subarray}{c}i,k\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{kj}^{2}+\sum_{\begin{subarray}{c}i\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{ij}^{2} \displaystyle=T_{3}-\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y}))+\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle Note that the actual contribution to the sum is \frac{2}{m^{2}}T_{4} . 5: (i=k\text{ and }k^{\prime}=i^{\prime}) and (j=\ell^{\prime}\neq\ell=j^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,i\ell}\mathbf{\xi}_{i^{\prime}\ell,i^{\prime}j}\right] \displaystyle=\text{Pr}[(H(i,j)=H(i,\ell)\text{ and }(H(i^{\prime},\ell)=H(i^{\prime},j)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle\equiv h_{1}(i)+h_{2}(\ell)\quad(\text{mod m}) \displaystyle h_{1}(i^{\prime})+h_{2}(\ell) \displaystyle\equiv h_{1}(i^{\prime})+h_{2}(j)\quad(\text{mod m}). Moving terms around, we have that the events simplify to: \displaystyle h_{2}(j)-h_{2}(\ell)\equiv 0\quad(\text{mod }m) This event is identical to the one in Case 1, and the expectation over \xi is: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,i\ell}\mathbf{\xi}_{i^{\prime}\ell,i^{\prime}j}\right] \displaystyle=\frac{1}{m}. With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . This sum is another partner to T_{1} in that the arithmetic is identical: \displaystyle T_{5} \displaystyle=\sum_{\begin{subarray}{c}i,i^{\prime}\in[d]\\ j\neq j^{\prime}\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{ij^{\prime}}\mathbf{X}_{i^{\prime}j^{\prime}}\mathbf{Y}_{i^{\prime}j} \displaystyle=\sum_{j\neq j^{\prime}\in[d^{\prime}]}\left(\sum_{i\in[d]}\mathbf{X}_{ij}\mathbf{Y}_{ij^{\prime}}\right)\left(\sum_{i^{\prime}\in[d]}\mathbf{X}_{i^{\prime}j^{\prime}}\mathbf{Y}_{i^{\prime}j}\right) \displaystyle=\sum_{j\neq j^{\prime}\in[d^{\prime}]}(\mathbf{X}^{T}\mathbf{Y})_{jj^{\prime}}(\mathbf{X}^{T}\mathbf{Y})_{j^{\prime}j} \displaystyle=\sum_{j,j^{\prime}\in[d^{\prime}]}(\mathbf{X}^{T}\mathbf{Y})_{jj^{\prime}}(\mathbf{X}^{T}\mathbf{Y})_{j^{\prime}j}-\sum_{j\in[d^{\prime}]}(\mathbf{X}^{T}\mathbf{Y})_{jj}(\mathbf{X}^{T}\mathbf{Y})_{jj} \displaystyle=\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})-\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2} Note that the actual contribution to the sum is \frac{1}{m}T_{5} . Note also that the diagonal term here is identical to the one in T_{1} . 6: (31) (i=k^{\prime}\neq k=i^{\prime}) and (j=\ell\text{ and }\ell^{\prime}=j^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,kj}\mathbf{\xi}_{kj^{\prime},ij^{\prime}}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,j)\text{ and }(H(k,j^{\prime})=H(i,j^{\prime})] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle=h_{1}(k)+h_{2}(j)\quad(\text{mod }m) \displaystyle h_{1}(k)+h_{2}(j^{\prime}) \displaystyle=h_{1}(i)+h_{2}(j^{\prime})\quad(\text{mod }m). Subtracting like terms, we have that the events simplify to: \displaystyle h_{1}(i)-h_{1}(k)\equiv 0\quad(\text{mod }m) This event is identical to the one in Case 3, and the expectation over \xi is therefore: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,kj}\mathbf{\xi}_{kj^{\prime},ij^{\prime}}\right] \displaystyle=\frac{1}{m} With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . This sum is another partner to T_{1} in that the arithmetic is identical: \displaystyle T_{6} \displaystyle=\sum_{\begin{subarray}{c}i\neq i^{\prime}\in[d]\\ j,j^{\prime}\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{i^{\prime}j}\mathbf{X}_{i^{\prime}j^{\prime}}\mathbf{Y}_{ij^{\prime}} \displaystyle=\sum_{i\neq i^{\prime}\in[d]}\left(\sum_{j\in[d^{\prime}]}\mathbf{X}_{ij}\mathbf{Y}_{i^{\prime}j}\right)\left(\sum_{j^{\prime}\in[d^{\prime}]}\mathbf{X}_{i^{\prime}j^{\prime}}\mathbf{Y}_{ij^{\prime}}\right) \displaystyle=\sum_{i\neq i^{\prime}\in[d]}(\mathbf{X}\mathbf{Y}^{T})_{ii^{\prime}}(\mathbf{X}\mathbf{Y}^{T})_{i^{\prime}i} \displaystyle=\sum_{i,i\in[d]}(\mathbf{X}\mathbf{Y}^{T})_{ii^{\prime}}(\mathbf{X}\mathbf{Y}^{T})_{i^{\prime}i}-\sum_{i\in[d]}(\mathbf{X}\mathbf{Y}^{T})_{ii}(\mathbf{X}\mathbf{Y}^{T})_{ii} \displaystyle=\text{tr}((\mathbf{X}\mathbf{Y}^{T})^{2})-\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2} \displaystyle=\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})-\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2} Where at the end, the cyclic property of the trace (\text{tr}(PQ)=\text{tr}(QP)) and the invariance of the trace under transposes (\text{tr}(P)=\text{tr}(P^{T})) was used to turn the trace into the same one in T_{5} . Note that the actual contribution to the sum is \frac{1}{m}T_{6} . Note also that the diagonal term here is identical to the one in T_{3} . 7: (i=i^{\prime}\neq k=k^{\prime}) and (j=j^{\prime}\neq\ell=\ell^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{ij,k\ell}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,\ell)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle=h_{1}(k)+h_{2}(\ell)\quad(\text{mod }m) Moving terms around, we have that the event simplifies to: \displaystyle h_{1}(i)-h_{1}(k)\equiv h_{2}(\ell)-h_{2}(j)\quad(\text{mod }m) Letting A=h_{1}(i)-h_{1}(k)\text{ mod }m and B=h_{2}(\ell)-h_{2}(j)\text{ mod }m , we have that by the 2-wise independence of h_{1},h_{2} , that A,B are uniform random variables in \{0,1,\ldots,m-1\} . Therefore, the probability that A=B is simply 1/m . And therefore: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,kj}\mathbf{\xi}_{kj^{\prime},ij^{\prime}}\right] \displaystyle=\frac{1}{m} With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . The arithmetic for simplifying this sum has no previous analogue. The summation identity Equation 17 was used to split the sum into 4 terms. Note that the two terms that appear with a minus sign are the same as the ones that appear in T_{2} and T_{4} . \displaystyle T_{7} \displaystyle=\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{k\ell}\mathbf{X}_{ij}\mathbf{Y}_{k\ell} \displaystyle=\sum_{\begin{subarray}{c}i,k\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}(\mathbf{X}_{ij})^{2}(\mathbf{Y}_{k\ell})^{2}-\sum_{\begin{subarray}{c}i\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}(\mathbf{X}_{ij})^{2}(\mathbf{Y}_{i\ell})^{2}-\sum_{\begin{subarray}{c}i,k\in[d]\\ j\in[d^{\prime}]\end{subarray}}(\mathbf{X}_{ij})^{2}(\mathbf{Y}_{kj})^{2}+\sum_{\begin{subarray}{c}i\in[d]\\ j\in[d^{\prime}]\end{subarray}}(\mathbf{X}_{ij})^{2}(\mathbf{Y}_{ij})^{2} \displaystyle=\left\|\mathbf{X}\right\|_{F}^{2}\left\|\mathbf{Y}\right\|_{F}^{2}-\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))-\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y}))+\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle Note that the actual contribution to the sum is \frac{1}{m}T_{7} . 8: (i=k^{\prime}\neq k=i^{\prime}) and (j=\ell^{\prime}\neq\ell=j^{\prime}) We begin by noting that the expectation over \xi is the same for all elements in the sum: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,k\ell}\mathbf{\xi}_{k\ell,ij}\right] \displaystyle=\text{Pr}[(H(i,j)=H(k,\ell)] Expanding out the events in the probability, we have: \displaystyle h_{1}(i)+h_{2}(j) \displaystyle\equiv h_{1}(k)+h_{2}(\ell)\quad(\text{mod m}) This event is identical to the one in Case 7, and the expectation over \xi is: \displaystyle\mathbb{E}\left[\mathbf{\xi}_{ij,i\ell}\mathbf{\xi}_{i^{\prime}\ell,i^{\prime}j}\right] \displaystyle=\frac{1}{m}. With the \xi expectation handled, we move on to the sum over the tensors \mathbf{X},\mathbf{Y} . The arithmetic in this sum is identical to T_{7} . Note that the two terms with a minus sign that appear here are the same as in T_{1} and T_{3} . Note also that the final Hadamard term also appears in T_{2},T_{4}, and T_{7} . \displaystyle T_{8} \displaystyle=\sum_{\begin{subarray}{c}i\neq k\in[d]\\ j\neq\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{k\ell}\mathbf{X}_{k\ell}\mathbf{Y}_{ij} \displaystyle=\sum_{\begin{subarray}{c}i,k\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{ij}\mathbf{X}_{k\ell}\mathbf{Y}_{k\ell}-\sum_{\begin{subarray}{c}i\in[d]\\ j,\ell\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{ij}\mathbf{X}_{i\ell}\mathbf{Y}_{i\ell}-\sum_{\begin{subarray}{c}i,k\in[d]\\ j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}\mathbf{Y}_{ij}\mathbf{X}_{kj}\mathbf{Y}_{kj}+\sum_{\begin{subarray}{c}i\in[d]\\ j\in[d^{\prime}]\end{subarray}}(\mathbf{X}_{ij})^{2}(\mathbf{Y}_{ij})^{2} \displaystyle=\langle\mathbf{X},\mathbf{Y}\rangle^{2}-\left\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\right\|_{2}^{2}-\left\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\right\|_{2}^{2}+\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle Note that the actual contribution to the sum is \frac{1}{m}T_{8} . With all the cases handled, we now group the positive terms with a 2/m^{2} in front to get: \displaystyle P_{1} \displaystyle=\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}+\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}+2\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle and the negative terms to get: \displaystyle N_{1} \displaystyle=\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2}+\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2}+\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))+\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y})) We do the same with the 1/m terms: \displaystyle P_{2} \displaystyle=\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}+\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}+2\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})+\langle\mathbf{X},\mathbf{Y}\rangle^{2}+\left\|\mathbf{X}\right\|_{F}^{2}\left\|\mathbf{Y}\right\|_{F}^{2}+2\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle \displaystyle=P_{1}+2\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})+\langle\mathbf{X},\mathbf{Y}\rangle^{2}+\left\|\mathbf{X}\right\|_{F}^{2}\left\|\mathbf{Y}\right\|_{F}^{2} and negative terms to get: \displaystyle N_{2} \displaystyle=3\left[\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2}+\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2}\right]+\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))+\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y})) \displaystyle=N_{1}+2\left[\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2}+\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2}\right] This means that: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\\ \mathbf{u^{\prime}}\neq\mathbf{v^{\prime}}\in[d]\times[d^{\prime}]\end{subarray}}\mathbb{E}\left[S(\mathbf{u})S(\mathbf{v})S(\mathbf{u}^{\prime})S(\mathbf{v}^{\prime})\right]\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{X}_{\mathbf{u^{\prime}}}\mathbf{Y}_{\mathbf{v^{\prime}}}\mathbb{E}\left[\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\mathbf{\xi}_{\mathbf{u}^{\prime},\mathbf{v}^{\prime}}\right] \displaystyle=\frac{2}{m^{2}}(P_{1}-N_{1})+\frac{1}{m}(P_{2}-N_{2}). (23) This concludes the first part of the proof, which was evaluating Equation 16 in closed form. To upper-bound the variance, it is tempting to drop the negative terms and just upper bound P_{1},P_{2} with Cauchy-Schwartz, but a tighter bound can be achieved by noting that the term with a factor of 2 in P_{1} is \leq the trace terms in N_{1} . Using that ( \sum_{j}a_{j})(\sum_{\ell}b_{\ell})\geq\sum_{j}a_{j}b_{j} : \displaystyle\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T})) \displaystyle=\sum_{i\in[d]}\left(\sum_{j\in[d^{\prime}]}\mathbf{X}_{ij}^{2}\right)\left(\sum_{\ell\in[d^{\prime}]}\mathbf{Y}_{i\ell}^{2}\right) \displaystyle\geq\sum_{\begin{subarray}{c}i\in[d],j\in[d^{\prime}]\end{subarray}}\mathbf{X}_{ij}^{2}\mathbf{Y}_{ij}^{2} \displaystyle=\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle The same argument yields that \text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y}))\geq\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle , therefore we have: \displaystyle 2\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle\leq\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))+\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y})). Therefore, in order to upper bound the variance, the term 2\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\right\rangle can be dropped in P_{1} and P_{2} . We can drop all the remaining terms in N_{1},N_{2} as well. We are left with: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\sum_{\begin{subarray}{c}\mathbf{u}\neq\mathbf{v}\in[d]\times[d^{\prime}]\\ \mathbf{u^{\prime}}\neq\mathbf{v^{\prime}}\in[d]\times[d^{\prime}]\end{subarray}}\mathbb{E}\left[S(\mathbf{u})S(\mathbf{v})S(\mathbf{u}^{\prime})S(\mathbf{v}^{\prime})\right]\mathbf{X}_{\mathbf{u}}\mathbf{Y}_{\mathbf{v}}\mathbf{X}_{\mathbf{u^{\prime}}}\mathbf{Y}_{\mathbf{v^{\prime}}}\mathbb{E}\left[\mathbf{\xi}_{\mathbf{u},\mathbf{v}}\mathbf{\xi}_{\mathbf{u}^{\prime},\mathbf{v}^{\prime}}\right] \displaystyle=\frac{2}{m^{2}}(P_{1}-N_{1})+\frac{1}{m}(P_{2}-N_{2}) \displaystyle\leq\frac{2}{m^{2}}\left(\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}+\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}\right) \displaystyle+\frac{1}{m}\left(\left\|\mathbf{X}^{T}\mathbf{Y}\right\|_{F}^{2}+\left\|\mathbf{X}\mathbf{Y}^{T}\right\|_{F}^{2}+2\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})+\langle\mathbf{X},\mathbf{Y}\rangle^{2}+\left\|\mathbf{X}\right\|_{F}^{2}\left\|\mathbf{Y}\right\|_{F}^{2}\right). By the submultiplicative property of the Frobenius norm \displaystyle\|\mathbf{X}^{T}\mathbf{Y}\|_{F}^{2}\leq\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2},\quad\|\mathbf{X}\mathbf{Y}^{T}\|_{F}^{2}\leq\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2}. and by Cauchy-Schwartz (and noting that \text{tr}(A^{2})=\langle A,A^{\top}\rangle then using the above bound): \displaystyle\langle\mathbf{X},\mathbf{Y}\rangle^{2}\leq\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2},\quad\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})\leq\|\mathbf{X}^{T}\mathbf{Y}\|_{F}^{2}\leq\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2} We are left with: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle\leq\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2}. (24) We remark that this bound is strictly tighter than the 32 bound of \nicefrac{{8}}{{m}}\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2} for sketch dimension m\geq 2 . As the sketch dimension m goes to infinity, our bound is 33.\bar{3}\% tighter. At sketch dimensions above 400 , the improvement is already above 33\% . Moreover, our bound is tight. The proof is relatively straightforward, in that we give an example for which the bound is saturated. Let \mathbf{x}=\mathbf{y}=\frac{1}{\sqrt{d}}\mathbf{1}_{d} , where \mathbf{1}_{d} is the d -dimensional vector of ones. Let \mathbf{x}^{\prime}=\mathbf{y}^{\prime}=\frac{1}{\sqrt{d^{\prime}}}\mathbf{1}_{d^{\prime}} . Now, define \mathbf{X}=\mathbf{x}\otimes\mathbf{x}^{\prime}=\frac{1}{\sqrt{dd^{\prime}}}\mathbf{1}_{d\times d^{\prime}} , and \mathbf{Y}=\mathbf{y}\otimes\mathbf{y}^{\prime}=\frac{1}{\sqrt{dd^{\prime}}}\mathbf{1}_{d\times d^{\prime}} , where \otimes denotes the Kronecker product or outer product. This implies \displaystyle\|\mathbf{X}^{T}\mathbf{Y}\|_{F}^{2}=\|\mathbf{X}\mathbf{Y}^{T}\|_{F}^{2}=\langle\mathbf{X},\mathbf{Y}\rangle^{2} \displaystyle=\text{tr}((\mathbf{X}^{T}\mathbf{Y})^{2})=\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2}=1 \displaystyle\|\text{diag}(\mathbf{X}^{T}\mathbf{Y})\|_{2}^{2}=\text{tr}((\mathbf{X}^{T}\mathbf{X})\circ(\mathbf{Y}^{T}\mathbf{Y}))=\frac{1}{d^{\prime}}, \displaystyle\quad\|\text{diag}(\mathbf{X}\mathbf{Y}^{T})\|_{2}^{2}=\text{tr}((\mathbf{X}\mathbf{X}^{T})\circ(\mathbf{Y}\mathbf{Y}^{T}))=\frac{1}{d} \displaystyle\left\langle\mathbf{X}\circ\mathbf{X},\mathbf{Y}\circ\mathbf{Y}\right\rangle \displaystyle=\frac{1}{dd^{\prime}} This means \displaystyle P_{1}=2+\frac{2}{dd^{\prime}},\quad \displaystyle N_{1}=\frac{2}{d^{\prime}}+\frac{2}{d} \displaystyle P_{2}=6+\frac{2}{dd^{\prime}},\quad \displaystyle N_{2}=\frac{4}{d^{\prime}}+\frac{4}{d} and therefore, using Equation 23 we have that the variance equals: \displaystyle\operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle] \displaystyle=\frac{2}{m^{2}}(P_{1}-N_{1})+\frac{1}{m}(P_{2}-N_{2}) \displaystyle=\frac{4}{m^{2}}\left(1+\frac{1}{dd^{\prime}}-\frac{1}{d^{\prime}}-\frac{1}{d}\right)+\frac{1}{m}\left(6+\frac{2}{dd^{\prime}}-\frac{4}{d^{\prime}}-\frac{4}{d}\right) Therefore, in the limit as d,d^{\prime}\rightarrow\infty , we have that \operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle]=\frac{4}{m^{2}}+\frac{6}{m} , which is equal to the bound in Equation 24 since \|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2}=1 . ∎ Appendix C Proof of Lemma 1 Here, we prove Lemma 1 . This proof assumes familiarity with CountSketch and TensorSketch. See Appendix B for a self-contained overview of all required background. See 1 Proof. First, a remark on notation. In the main body we used \mathbf{u}\cdot\mathbf{v} to denote the dot product, while in the proof below we use \langle\mathbf{u},\mathbf{v}\rangle . This is done for notational clarity. Second, in Appendix B we use \mathbf{X}_{ij} to denote the i-th row and j-th column of the matrix \mathbf{X} , and \mathbf{x}_{i} to denote the i-th element of a vector \mathbf{x} . The proof below does not use this notation, instead \mathbf{x}_{i} refers to the i-th vector in a sequence of vectors, and same for \mathbf{X}_{i} . The proof for this lemma follows the following logic: 1. CountSketch is unbiased and has a controlled error. Formally, CountSketch with embedding dimension m , when applied to any two vectors (\mathbf{x},\mathbf{y}) of the same shape, yields random embeddings (\tilde{\mathbf{x}},\tilde{\mathbf{y}}) with the property that \mathbb{E}[\langle\tilde{\mathbf{x}},\tilde{\mathbf{y}}\rangle]=\langle\mathbf{x},\mathbf{y}\rangle and \operatorname{Var}[\langle\tilde{\mathbf{x}},\tilde{\mathbf{y}}\rangle]\leq 2/m\|\mathbf{x}\|_{2}^{2}\|\mathbf{y}\|_{2}^{2} . 2. TensorSketch is unbiased and has a controlled error. Formally, TensorSketch with embedding dimension m , when applied to any two matrices that are sums of outer products (\mathbf{X},\mathbf{Y}) of the same shape, yields random embeddings (\tilde{\mathbf{X}},\tilde{\mathbf{Y}}) with the property that \mathbb{E}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle]=\langle\mathbf{X},\mathbf{Y}\rangle and \operatorname{Var}[\langle\tilde{\mathbf{X}},\tilde{\mathbf{Y}}\rangle]\leq(2/m^{2}+6/m)\|\mathbf{X}\|_{F}^{2}\|\mathbf{Y}\|_{F}^{2} . 3. The global sketch map \mathcal{S} , which flattens and concatenates sketched gradients across parameter tensors, preserves unbaisedness and bounded variance. 4. Summing over checkpoints preserves unbiasedness and bounded variance. Item 1 and Item 2 follow from the results in Appendix B . Item 3 follows from linearity of expectation and variance when the sketched gradients are independent across parameter tensors. Concretely, suppose the training-gradient vector \mathbf{g}_{k} is a concatenation of \alpha vector-valued parameter gradients (which we denote by \mathbf{x} ) and \beta matrix-valued parameter gradients (which we denote by \mathbf{X} ) and WLOG is of the form \mathbf{g}_{k}^{\top}=(\mathbf{x}_{1}^{\top},\mathbf{x}_{2}^{\top},\ldots\mathbf{x}_{\alpha},\mathbf{X}_{1}^{\top},\mathbf{X}_{2}^{\top}\ldots\mathbf{X}_{\beta}^{\top}) . By this, we mean that we concatenate all the vector-valued gradients first, and then flatten the matrix-valued parameter gradients and concatenate them to the end. Note here that \mathbf{x}_{1} denotes the first vector in the concatenation \mathbf{g}_{k} , and not to the first element of the vector \mathbf{x} . Since the sketch map \mathcal{S} independently sketches parameter-level gradients to vectors of dimension m , let \mathsf{CS}_{1},\ldots,\mathsf{CS}_{\alpha} denote the \alpha independent CountSketches (where by independent, we mean the underlying hashes are sampled independently), and \mathsf{TS}_{1},\ldots,\mathsf{TS}_{\beta} denote the \beta independent TensorSketches. Formally, \mathsf{TS} as defined in the main body acts on two vectors \mathbf{u},\mathbf{v} and sketches the outer product \mathbf{u}\otimes\mathbf{v} . However, below we abuse notation slightly and write \mathsf{TS}(\mathbf{X}) with the understanding that \mathbf{X} is a sum of outer products (since it is a matrix-parameter gradient, see Proposition 1 for details) and \mathsf{TS} is linear. The sketched training-gradient vector can be written as \displaystyle\tilde{\mathbf{g}}_{k}=\mathcal{S}(\mathbf{g}_{k}) \displaystyle=(\mathsf{CS}_{1}(\mathbf{x}_{1}),\mathsf{CS}_{2}(\mathbf{x}_{2})^{\top},\ldots\mathsf{CS}_{\alpha}(\mathbf{x}_{\alpha})^{\top},\mathsf{TS}_{1}(\mathbf{X}_{1})^{\top},\mathsf{TS}_{2}(\mathbf{X}_{2})^{\top},\ldots\mathsf{TS}^{\top}_{\beta}(\mathbf{X}_{\beta})) \displaystyle=(\tilde{\mathbf{x}}^{\top}_{1},\tilde{\mathbf{x}}_{2}^{\top},\ldots\tilde{\mathbf{x}}_{\alpha}^{\top},\tilde{\mathbf{X}}_{1}^{\top},\tilde{\mathbf{X}}_{2}^{\top},\ldots\tilde{\mathbf{X}}_{\beta}^{\top})\in\mathbb{R}^{(\alpha+\beta)m}. We assume the same structure for the test-step vector \mathbf{p}_{k,t} : \displaystyle\tilde{\mathbf{p}}_{k,t}=\mathcal{S}(\mathbf{p}_{k,t}) \displaystyle=(\mathsf{CS}_{1}(\mathbf{y}_{1}),\mathsf{CS}_{2}(\mathbf{y}_{2})^{\top},\ldots\mathsf{CS}_{\alpha}(\mathbf{y}_{\alpha})^{\top},\mathsf{TS}_{1}(\mathbf{Y}_{1})^{\top},\mathsf{TS}_{2}(\mathbf{Y}_{2})^{\top},\ldots\mathsf{TS}^{\top}_{\beta}(\mathbf{Y}_{\beta})) \displaystyle=(\tilde{\mathbf{y}}^{\top}_{1},\tilde{\mathbf{y}}_{2}^{\top},\ldots\tilde{\mathbf{y}}_{\alpha}^{\top},\tilde{\mathbf{Y}}_{1}^{\top},\tilde{\mathbf{Y}}_{2}^{\top},\ldots\tilde{\mathbf{Y}}_{\beta}^{\top})\in\mathbb{R}^{(\alpha+\beta)m} We now compute the full and sketched dot products \iota_{k,t}\coloneqq\langle\mathbf{g}_{k},\mathbf{p}_{k,t}\rangle and \widetilde{\iota}_{k,t}\coloneqq\langle\widetilde{\mathbf{g}_{k}},\widetilde{\mathbf{p}_{k,t}}\rangle . \displaystyle\iota_{k,t} \displaystyle=\langle\mathbf{g}_{k},\mathbf{p}_{k,t}\rangle \displaystyle\widetilde{\iota}_{k,t} \displaystyle=\langle\widetilde{\mathbf{g}_{k}},\widetilde{\mathbf{p}_{k,t}}\rangle \displaystyle=\sum_{i=1}^{\alpha}\left\langle\mathsf{CS}_{i}(\mathbf{x}_{i}),\mathsf{CS}_{i}(\mathbf{y}_{i})\right\rangle+\sum_{j=1}^{\beta}\langle\mathsf{TS}_{j}(\mathbf{X}_{j}),\mathsf{TS}_{j}(\mathbf{Y}_{j})\rangle We observe that the inner product decomposes to the inner products of the respective sketches. Due to linearity of expectation, this means: \displaystyle\mathbb{E}[\widetilde{\iota}_{k,t}] \displaystyle=\sum_{i=1}^{\alpha}\mathbb{E}[\left\langle\mathsf{CS}_{i}(\mathbf{x}_{i}),\mathsf{CS}_{i}(\mathbf{y}_{i})\right\rangle]+\sum_{j=1}^{\beta}\mathbb{E}[\langle\mathsf{TS}_{j}(\mathbf{X}_{j}),\mathsf{TS}_{j}(\mathbf{Y}_{j})\rangle] Note that the randomness inside each expectation is over that respective CountSketch or TensorSketch. We can therefore use the fact that each CountSketch and TensorSketch is unbiased to conclude: \displaystyle\mathbb{E}[\widetilde{\iota}_{k,t}] \displaystyle=\sum_{i=1}^{\alpha}\left\langle\mathbf{x}_{i},\mathbf{y}_{i}\right\rangle+\sum_{j=1}^{\beta}\langle\mathbf{X}_{j},\mathbf{Y}_{j}\rangle \displaystyle=\langle\mathbf{g}_{k},\mathbf{p}_{k,t}\rangle=\iota_{k,t} Moreover, since each CountSketch/TensorSketch is independent, this means the variance of the sum is the sum of the variances: \displaystyle\operatorname{Var}[\widetilde{\iota}_{k,t}] \displaystyle=\sum_{i=1}^{\alpha}\operatorname{Var}[\left\langle\mathsf{CS}_{i}(\mathbf{x}_{i}),\mathsf{CS}_{i}(\mathbf{y}_{i})\right\rangle]+\sum_{j=1}^{\beta}\operatorname{Var}[\langle\mathsf{TS}_{j}(\mathbf{X}_{j}),\mathsf{TS}_{j}(\mathbf{Y}_{j})\rangle]. (25) We can therefore use the variance bound for CountSketch from 32 (restated in Lemma 2 ) and the novel variance bound for TensorSketch derived in Lemma 4 2 2 2 The bound in Lemma 4 does not assume \mathbf{X},\mathbf{Y} are sums of outer products, and applies more generally to TensorSketchs of any two matrices. to upper bound the variance: \displaystyle\operatorname{Var}[\widetilde{\iota}_{k,t}] \displaystyle\leq\frac{2}{m}\sum_{i=1}^{\alpha}\|\mathbf{x}_{i}\|_{2}^{2}\|\mathbf{y}_{i}\|_{2}^{2}+\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\sum_{j=1}^{\beta}\|\mathbf{X}_{j}\|_{F}^{2}\|\mathbf{Y}_{j}\|_{F}^{2} \displaystyle=\sum_{i=1}^{\alpha}\frac{2}{m_{i}^{\mathsf{CS}}}\|\mathbf{x}_{i}\|_{2}^{2}\|\mathbf{y}_{i}\|_{2}^{2}+\sum_{j=1}^{\beta}\left(\frac{4}{m_{j}^{2}}+\frac{6}{m_{j}}\right)\|\mathbf{X}_{j}\|_{F}^{2}\|\mathbf{Y}_{j}\|_{F}^{2} \displaystyle\leq\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\left(\sum_{i=1}^{\alpha}\|\mathbf{x}_{i}\|_{2}^{2}\|\mathbf{y}_{i}\|_{2}^{2}+\sum_{j=1}^{\beta}\|\mathbf{X}_{i}\|_{F}^{2}\|\mathbf{Y}_{j}\|_{F}^{2}\right) \displaystyle\leq\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\|\mathbf{g}_{k}\|_{2}^{2}\|\mathbf{p}_{k,t}\|_{2}^{2} Where we used 2/m<4/m^{2}+6/m and \sum_{i}a_{i}b_{i}\leq(\sum_{i}a_{i})(\sum_{j}b_{j}) to upper bound the variance. Note that this bound in tight in that we have equality when there are no vector-valued parameters ( \alpha=0 ), there is one matrix-valued parameter ( \beta=1 ), and \mathbf{g}_{k},\mathbf{p}_{k,t} are outer products of parallel unit-RMS norm vectors as described in Lemma 4 . Now for Item 4 . We have that: \displaystyle\mathcal{I}_{t}(z,z^{\prime}) \displaystyle=\sum_{k=1}^{K}\eta_{k}\iota_{k,t} \displaystyle\widetilde{\mathcal{I}}_{t}(z,z^{\prime}) \displaystyle=\sum_{k=1}^{K}\eta_{k}\widetilde{\iota}_{k,t} By linearity of expectation and unbiasedness, \mathbb{E}[\widetilde{\mathcal{I}}_{t}(z,z^{\prime})]=\mathcal{I}_{t}(z,z^{\prime}) . Therefore: \displaystyle\mathbb{E}[\left(\widetilde{\mathcal{I}}_{t}(z,z^{\prime})-\mathcal{I}_{t}(z,z^{\prime})\right)^{2}] \displaystyle=\operatorname{Var}(\widetilde{\mathcal{I}}_{t}(z,z^{\prime})) Note that we use the same sketches for every checkpoint k , which means the sketched gradients across checkpoints are correlated. In contrast to Equation 25 , here the variance of the sum is not the sum of the variances. Instead, we include the covariance terms, and use Cauchy-Schwarz to upper bound the covariances: \displaystyle\mathbb{E}[\left(\widetilde{\mathcal{I}}_{t}(z,z^{\prime})-\mathcal{I}_{t}(z,z^{\prime})\right)^{2}] \displaystyle=\operatorname{Var}(\widetilde{\mathcal{I}}_{t}(z,z^{\prime})) \displaystyle=\sum_{k=1}^{K}\eta_{k}^{2}\operatorname{Var}(\widetilde{\iota}_{k,t})+\sum_{i\neq j\in[K]}\eta_{i}\eta_{j}\operatorname{Cov}(\widetilde{\iota}_{i,t},\>\>\widetilde{\iota}_{j,t}) \displaystyle\leq\sum_{k=1}^{K}\eta_{k}^{2}\operatorname{Var}(\widetilde{\iota}_{k,t})+\sum_{i\neq j\in[K]}\eta_{i}\eta_{j}\sqrt{\operatorname{Var}(\widetilde{\iota}_{i,t})\operatorname{Var}(\widetilde{\iota}_{j,t})} \displaystyle\leq\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\sum_{k=1}^{K}\eta_{k}^{2}\|\mathbf{g}_{k}\|_{2}^{2}\|\mathbf{p}_{k,t}\|_{2}^{2} \displaystyle+\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\sum_{i\neq j\in[K]}\eta_{i}\eta_{j}\|\mathbf{g}_{i}\|_{2}\|\mathbf{p}_{i,t}\|_{2}\|\mathbf{g}_{j}\|_{2}\|\mathbf{p}_{j,t}\|_{2} \displaystyle=\left(\frac{4}{m^{2}}+\frac{6}{m}\right)\left(\sum_{k=1}^{K}\eta_{k}\|\mathbf{g}_{k}\|_{2}\|\mathbf{p}_{k,t}\|_{2}\right)^{2} ∎ Appendix D Further experimental details D.1 Experimental details: scalability and correctness We validate the scalability, fidelity, and systems overhead of SDI. All runs use PyTorch in full float32 precision and full backpropagation through the unrolled recurrence (no truncation). Model We instantiate a looped GPT-style model (from the nanochat GPT implementation ( 28 ) ) with sequence length T{=}128 and loop horizon \tau{=}32 recurrent iterations. The architecture follows a prelude–recurrent core–coda pattern with 2 prelude blocks, a recurrent core consisting of a stack of 4 transformer blocks applied \tau times, and 2 coda blocks, giving an effective depth of 2+4\tau+2=132 blocks. We set bptt_k=None to enforce full BPTT through all \tau iterations. Unless otherwise stated, SDI targets the loop-body parameters corresponding to the recurrent core plus the injection adapter. Data and loss Because this benchmark evaluates sketch fidelity and systems overhead (not generalisation), we use synthetic random token sequences. For each trial we sample idx and targets uniformly at random from the model vocabulary to form a batch of shape (B,T) . We compute a per-example loss vector by requesting per-token cross-entropy losses (no reduction) and averaging over tokens, yielding \ell_{i}\in\mathbb{R} for each example i\in\{1,\dots,B\} . Baselines and estimators We compare: (i) Full Gradient TracIn/SDI, which materializes full per-example stepwise gradients, and (ii) Projected TracIn/SDI, which computes stepwise features during backprop using TensorSketch/CountSketch without instantiating full per-example gradients as described above. For the projected estimator, we sweep sketch dimension m\in\{256,512,1024,2048,4096,8192\} (default), and average results over 10 independent sketch seeds. For a fixed batch, we treat the batch as both the “train” and “query” sets and compute SDI producing an SDI tensor in \mathbb{R}^{B\times B\times\tau} ; the corresponding TracIn matrix is obtained by summing over steps. Fidelity metrics For SDI and TracIn, we report relative Frobenius error: \|\widehat{\mathrm{SDI}}-\mathrm{SDI}\|_{F}/\|\mathrm{SDI}\|_{F} and \|\widehat{\mathrm{TracIn}}-\mathrm{TracIn}\|_{F}/\|\mathrm{TracIn}\|_{F} , where the unprojected full-gradient result is treated as ground truth. We also fit a log–log slope of mean SDI error versus m to verify the expected \mathcal{O}(m^{-1/2}) scaling, the result of which is shown in Figure 4 . As expected, the relative scales as \mathcal{O}(\nicefrac{{1}}{{\sqrt{m}}}) . Figure 4 : Empirical error scaling w.r.t sketch dimension m . Average and standard deviation over 10 trials. Conservation check To empirically verify sketched conservation, we select representative loop-body matrix parameters and compare: (1) a direct TensorSketch applied to the summed full matrix gradient \sum_{t=1}^{\tau}\phi_{t} , versus (2) the sum of the per-step sketched gradients \sum_{t=1}^{\tau}\widetilde{\phi}_{t} produced by ProjectedTracInSDI . We report the maximum absolute discrepancy and relative \ell_{2} discrepancy. Memory and runtime On CUDA (NVidia RTX A6000), we quantify the maximum feasible batch size under each method via an out-of-memory search (batch sizes starting at 4 , increasing in steps of 4 ). We additionally measure (i) the overhead of projected featurization relative to a plain backward pass on the same batch, and (ii) the added wall-clock time per checkpoint relative to an inference-only forward pass, where per-checkpoint SDI time is defined as one projected featurization plus SDI/TracIn reductions on that batch. D.2 Experimental details: SDI as a mechanistic interpretability hypothesis generator (parity) Task and sequence format Parity examples are token sequences over a vocabulary of size 6 . Inputs are bit strings (tokens 0/1 ) of variable length n , followed by an “=” token (token 2 ) and padding (token 3 ) to a fixed sequence length T{=}n{+}2 . Labels place the parity bit (0/1) at the “=” position; non-answer positions are masked out of the loss via a per-token mask. The model receives an additional per-example integer batch_nums equal to the number of digits n ; in our implementation batch_nums is 1-indexed and indicates the loop iteration at which the model state is read out. The methodology here is identical to 14 . Model and recurrence We use a LoopedTransformer as described in the parity task experiments of 14 with a linear read-in map ( linear_embedding=True ), embedding width d_{\text{model}}{=}256 , one decoder block ( n_layer=1 ) and 64 attention heads. The model executes exactly T recurrent iterations, with additive input injection at every iteration. The model captures (and later decodes) the state at iteration batch_nums and ignores later iterations. Thus, for an n -bit parity instance, the model loops for \tau=T=n+2 iterations but uses the hidden state from iteration n for prediction; stepwise influence beyond the readout step is therefore zero. Subsampled train/test sets for influence To make SDI computation lightweight while preserving coverage over difficulty (sequence length), we subsample: (i) 512 training examples, constructed as 128 from each tercile of the training length distribution plus an additional 128 examples at length exactly 20 , and (ii) 384 test examples sampled from the held-out test set (all length 40 in this setup). We also create two special alternating probes (0101\ldots) and (1010\ldots) of length 40 (with T{=}42 total tokens) for the probe experiment in the main body. SDI computation We compute SDI/TracIn on the loop-body parameters using Projected TracIn/SDI with sketch dimension m{=}2048 and per-example masked cross-entropy loss. We aggregate across all checkpoints; checkpoint weights \eta_{k} are taken from the optimizer nominal learning rate. We compute: (i) train \to test SDI/TracIn, (ii) train \to train SDI/TracIn for self-influence (diagonal), and (iii) train \to special SDI trajectories for the alternating probes. Mechanistic readouts For a fixed alternating probe, we form a summed SDI profile by aggregating across training points: \mathrm{SDI}_{\Sigma}(t)\coloneqq\sum_{z\in\mathcal{D}_{\mathrm{train}}}\mathrm{SDI}(z,\text{probe})_{t} . In parallel, we explicitly unroll the recurrent computation for all T{=}42 iterations and record: (i) the answer-position hidden state h_{t} after each loop iteration, and (ii) the logit margin between the true parity class and the incorrect class at each iteration. We quantify periodic structure by (a) autocorrelation of the margin curve and (b) cosine similarity \cos(h_{t},h_{t+4}) . We then compute a 2D PCA embedding of \{h_{t}\}_{t=1}^{T} and cluster the trajectory with k -means ( k{=}4 ) to obtain a discrete state sequence and an empirical transition matrix (row-normalized). Proxy circuit evaluation To turn the discrete-state hypothesis into an interpretable proxy, we learn a cluster \to parity lookup table from a small calibration set of alternating sequences (256 examples with random length in [2,40] ). We evaluate this proxy on a larger alternating evaluation set (1024 examples), including an in-distribution split (length \leq 20 ) and an out-of-distribution split (length >20 ). To diagnose when the proxy applies beyond the alternating family, we also report a selective proxy accuracy by thresholding the k -means distance to the nearest centroid, using the 95th percentile distance on the alternating calibration set as the “on-manifold” threshold. D.3 Experimental details: scaling laws of loop compute (Sudoku) Dataset and difficulty We use the SATNet Sudoku tensors from 36 , each of shape (10{,}000,9,9,9) . We define puzzle difficulty as the number of missing cells (“blanks”), computed as the number of grid positions whose 9-way input vector is all zeros. Train/test split (non-IID by difficulty) We sort puzzles by missing-cell count and assign the easiest 80\% to train and the hardest 20\% to test, then shuffle each split with the same seed. All loop-scaling evaluations in this section are performed on the full hard test split . Model and training-time loop sampling We instantiate a looped transformer taking inspiration from 38 using non-causal/bidirectional attention with learned positional embeddings with d_{\text{model}}{=}128 , 1 decoder block, 4 attention heads, and a recurrent loop horizon with training mean 32 . Training samples the number of loops per batch from a Poisson log-normal distribution (clipped to 1\leq r\leq 64 ) as described in 30 ; 18 . Board accuracy and evaluation across loop budgets Given model logits of shape (B,81,9) , we predict a board by \arg\max over the last dimension. A board is counted correct iff all originally blank cells are predicted correctly: \texttt{board\_correct}=\bigl((\hat{y}=y)\ \lor\ \neg\texttt{blank\_mask}\bigr)\ \texttt{all over cells}. We evaluate board accuracy at multiple test-time loop budgets by re-running the same checkpoint with an overridden loop count. SDI energy curves To relate compute scaling to data influence, we compute SDI on a fixed analysis horizon (default \tau{=}32 ) and summarize stepwise magnitude as an “energy” curve. We define per-test-example SDI energy e_{j}(t)\;=\;\sum_{i\in\text{sampled train}}\left|\mathrm{SDI}(z_{i},z^{\prime}_{j})_{t}\right|. We then aggregate e_{j}(t) across test examples within each difficulty bin and plot the median and IQR versus t on a log-scaled y -axis. (Panel A uses the full hard test split for accuracy; Panel B uses the SDI computation subset described below.) Difficulty bins For visualization, we bin test puzzles by missing-cell counts. The plotting script uses an “auto” binning heuristic that produces three approximately equally sized bins for the common hard-split support {46,47,48,49,50}: (46–47), (48), and (49–50). D.4 Experimental details: step-resolved influence across Sudoku difficulty SDI artifacts and sampled subsets We recreate the same non-IID easy/hard split as in training (easy 80% train, hard 20% test by missing cells), then subsample fixed-size subsets from each split: 512 training puzzles and 512 test puzzles. Sampling is stratified by missing-cell count, allocating samples as uniformly as possible across the missing-count strata subject to each stratum’s capacity. We compute influence on a fixed analysis horizon \tau{=}32 using Projected TracIn/SDI with sketch dimension m{=}2048 targeting the recurrent block parameters. Loss and evaluation unit For each Sudoku puzzle, the per-example loss is the mean cross-entropy over blank cells only (cells that are missing in the input), matching the standard “solve the blanks” evaluation. All influence quantities treat an example as a full Sudoku board (81-way token sequence). Self-influence and cross-influence From the train \to train TracIn matrix, we define self-influence for each training puzzle z as the diagonal entry \mathrm{TracIn}(z,z) . From the train \to test TracIn matrix, we define the cross-influence mass of a training puzzle C(z)\;=\;\sum_{z^{\prime}\in\mathcal{D}_{\mathrm{test}}}\bigl|\mathrm{TracIn}(z,z^{\prime})\bigr|. We report correlations of these quantities with training difficulty (missing-cell count) and with each other. Train/test difficulty groups We define easy train as missing \leq 42 and hard train as missing \geq 45 (leaving 43–44 as a middle band), and we evaluate on two test difficulty bins: (46–47 missing) as “easy test” and (49–50 missing) as “hard test”. These groupings are applied within the sampled train/test subsets. Share of |\mathrm{TracIn}| mass by training group. For a fixed test puzzle z^{\prime} , let M(z^{\prime})=\sum_{z}|\mathrm{TracIn}(z,z^{\prime})| be its total absolute influence mass over the sampled training set. For a training group G , define its share on z^{\prime} as \mathrm{Share}_{G}(z^{\prime})\;=\;\frac{\sum_{z\in G}|\mathrm{TracIn}(z,z^{\prime})|}{M(z^{\prime})}. We report the mean of \mathrm{Share}_{G}(z^{\prime}) over test puzzles within each test difficulty bin. Step-resolved SDI timing (SDI energy and late mass) Given the SDI tensor \mathrm{SDI}(z,z^{\prime})\in\mathbb{R}^{\tau} , we define per-test SDI energy curves by summing absolute SDI across training points: e_{G,z^{\prime}}(t)\;=\;\sum_{z\in G}\left|\mathrm{SDI}(z,z^{\prime})_{t}\right|. To summarise when influence acts, we normalise per test example to a distribution p_{G,z^{\prime}}(t)=e_{G,z^{\prime}}(t)/\sum_{s=1}^{\tau}e_{G,z^{\prime}}(s) and compute timing statistics. In particular, we define “late” steps as t\geq 17 (i.e., indices \geq 16 in 0-based indexing) and report the SDI late mass \mathrm{LateMass}_{G}(z^{\prime})\;=\;\sum_{t=17}^{\tau}p_{G,z^{\prime}}(t), averaged over test puzzles in each difficulty bin. We also compute auxiliary timing summaries (e.g., centre of mass and CDF crossing steps) and validate the conservation identity \mathrm{TracIn}(z,z^{\prime})=\sum_{t=1}^{\tau}\mathrm{SDI}(z,z^{\prime})_{t} numerically (maximum absolute discrepancy). Statistical tests We use Spearman rank correlation for monotone association claims, and Welch two-sample t -tests (and paired t -tests where appropriate for per-test paired shares) to report p -values for group comparisons. Statistical significance is set at p<0.05 . D.5 Experimental details: recursive nanochat Model and recurrence We analyze a 328.3 M-parameter recursive GPT-style chat model ( 28 ) with a prelude–recurrent core–coda decomposition and an input injection adapter. The model has 2 prelude blocks, a recurrent core consisting of a stack of 4 transformer blocks reused across r recurrent iterations, and 2 coda blocks; for fixed r , the effective depth is 2+4r+2 . Training uses truncated BPTT with k{=}4 , implemented by detaching the recurrent state for iterations earlier than the last k . Training stages and TracIn checkpoints We follow the standard nanochat pipeline (pretraining, mid-training and supervised fine-tuning). During the GSM8K-containing stages (mid-training and supervised fine-tuning), we periodically save TracIn checkpoints along with optimizer learning-rate metadata and aggregate influence across all available checkpoints in each stage ( 82/71 checkpoints, respectively). Checkpoint weights \eta_{k} are taken from the recorded learning rates. Train sources and query set For mid training and supervised fine-tuning, we study cross-influence from GSM8K training into GSM8K test loss. We construct fixed tokenized sample sets by uniformly sampling 1024 conversations, truncating each rendered conversation to at most 2048 tokens. The mid training sources are SmølTalk, MMLU, GSM8K, Identity, Simple Spelling, and SpellingBee. The supervised fine-tuning training sources are ARC-Easy, ARC-Challenge, GSM8K, SmølTalk, Identity, Simple Spelling, and SpellingBee. Losses All losses are per-example means of the token-level cross-entropy over valid (unmasked) targets. For mid training examples, we use next-token loss over all tokens in the conversation. For sft training examples, we use an assistant-only mask (matching the sft training objective). SDI computation We compute Projected TracIn/SDI targeting the recurrent core and injection adapter parameters, with sketch dimension m{=}2048 , evaluating fixed recurrence counts r\in\{2,\dots,16\} . By default, SDI uses the checkpoint’s truncated-BPTT setting; when r>k , only the last k loop steps contribute nonzero SDI and earlier steps are zero by construction.