arXiv CSopen access

A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning Jason Gaitonde1 , Frederic Koehler2 , Elchanan Mossel3 , Joonhyung Shin2 , and Allan Sly4 1

Duke University University of Chicago 3 Massachusetts Institute of Technology 4 Princeton University

arXiv:2605.13687v1 [cs.LG] 13 May 2026

May 14, 2026

Abstract We introduce a family of synthetic languages with hierarchical structure — generated by a broadcast process on trees — for which the role of context length and reasoning in autoregressive generation can be analyzed precisely. At the heart of our analytic approach is an exact k-gram ansatz in place of transformers with context length k, a substitution we then validate empirically. Using this ansatz we derive explicit asymptotic predictions for distributional statistics of the sequences produced by a trained model, instantiated in two settings. For the Ising broadcast process (a soft-constrained language), we prove that the variance of the generated sum scales log-linearly in the context depth and its kurtosis converges to that of a Gaussian — both deviating from the true language for any sublinear context. For the coloring broadcast process (a hard-constrained language) in the freezing regime, bounded-context autoregression produces sequences that, with high probability, are inconsistent with any valid coloring of the underlying tree. Together these results imply an Ω(n) lower bound on the context length required to faithfully sample length-n sequences. In contrast, we prove that an autoregressive reasoning model with only Θ(log n) working memory can sample exactly from the true language — an exponential improvement. We confirm both the lower-bound predictions and the reasoning-based upper bound empirically with transformers trained on the synthetic language; the trained models track our asymptotic predictions quantitatively across a wide range of context sizes.

Introduction

The size of an autoregressive language model’s context window is one of the central design parameters in modern LLMs. Larger contexts allow more long-range dependencies to be captured (Vaswani et al., 2017), are essential for the reasoning/chain-of-thought paradigm (Xiong et al., 2024; Guo et al., 2025; Jaech et al., 2024), and empirically obey scaling laws relating context size to predictive loss (Kaplan et al., 2020; Hoffmann et al., 2022). They are also expensive: the quadratic cost of attention in the context length has driven substantial research into scaling contexts up (Dao et al., 2022; Liu et al., 2025; Katharopoulos et al., 2020; Wang et al., 2020). Despite this centrality, a sharp theoretical understanding of what context length buys — 1

and when reasoning can substitute for it — has remained elusive. A core obstacle is the difficulty of formulating quantitative distributional questions about generated text when the underlying language distribution is unknown. A hierarchical language with tractable statistics. In this work we study a class of synthetic languages for which the underlying distribution is both known exactly and admits a clean asymptotic analysis. The language is generated by a broadcast process on a d-ary tree: a root token is sampled from a prior and then propagated downward through a noisy channel until it reaches the dh leaves, which form the observed sequence. Variants of this model have a long history in probability and statistical physics, and have recently been used as a substrate for theoretical questions about deep learning (Mossel, 2016; Cagnetta et al., 2024; Tomasini and Wyart, 2024; Ren et al., 2026). Crucially, the model is not merely a “formal language” (i.e., a set of valid strings) but a probability distribution over strings, which is what generative pretraining actually targets via maximum likelihood. The hierarchical structure also reflects a long tradition in linguistics and NLP that treats language as compositional and multiscale (Chomsky, 1957; Jurafsky and Martin, 2026; Elman, 1990; Ebeling and Neiman, 1995; Yang et al., 2016): parse trees, semantic dependencies, and discourse structure all impose correlations across widely separated length scales. We emphasize that tree-structured representations of language are ubiquitous. Hierarchical sentence diagrams appear in 19th-century pedagogical grammars (Reed and Kellogg, 1877), and immediate constituent analysis (Bloomfield, 1933; Wells, 1947) formalized the view that sentences decompose recursively into nested constituents. Chomsky (1957) and Tesnière (1959) both represented sentences using hierarchical tree structures, and compositional semantics assigns meaning to a sentence by recursively combining the meanings of its subtrees (Montague, 1970). NLP inherited this perspective, from probabilistic context-free grammars (Jurafsky and Martin, 2026) and treebank-based parsing (Marcus et al., 1993) to tree-structured neural networks (Socher et al., 2013; Tai et al., 2015). The broadcast model can be viewed as a probabilistic generative process on such a tree, with the latent internal nodes playing the role of unobserved syntactic or semantic structure. The broadcast model on trees. Let Td,h denote the d-ary tree of height h, and let Σ be a finite set of tokens. The (d, h, κ, ν)-broadcast process samples a token at each node of the tree as follows: the root is drawn from a prior ν over Σ, and each non-root node, given the value at its parent, is sampled independently according to a transition kernel κ on Σ. The language is defined as the joint distribution over the dh leaf h tokens, viewed as a distribution on Σd . See Section 2 for full details. In this paper we focus on two instantiations of this model: the Ising broadcast process, where Σ = {±1} and κ copies the parent with probability ρ and re-randomizes otherwise, modeling soft global correlations; and the coloring broadcast process, where Σ = [q] and κ samples a uniformly random color for each child which differs from its parent. The latter models hard logical constraints analogous to those in code or formal mathematics. In either case, internal nodes can be interpreted as latent high-level topics or syntactic structure that constrains the observed tokens at the leaves. For our experiments, the leaf sequence is tokenized with hierarchical punctuation marks delimiting subtrees at each level — analogous to how natural language uses commas, periods, and paragraph breaks to mark structure at different scales — so that a bounded-context model can locate itself within the hierarchy. See Section 4 for details. Our theoretical results, which concern the marginal distribution over leaf values,

P (a) log( n1 Var( Xr )) versus the log context size.

(b) Kurtosis of

Xr versus the log context size.

P Figure 1: Variance and kurtosis of the sum of leaf spins Xr for the Ising broadcast process with d = 3, h = 8, and ρ = 0.9, computed for different models and context sizes. The thin horizontal lines (grey) indicate the log variance and kurtosis of the ground truth language, and the thin vertical line indicates the context size which encompasses the entire tree (i.e., w = h). The “Non-reasoning” (blue) and “Reasoning” (orange) curves are both trained transformers: the latter model uses additional intermediate tokens in its generation. The “Simulated” (green) curves are generated using the exact autoregressive broadcast process in Theorem 2.2. The “Asymptotics” (red) lines are computed from Theorems 3.1 and 3.2, which hold when the context depth and the tree height have large gap (h − w → ∞), with w → ∞. See also Section 4.1. are unaffected by this tokenization choice. Our analysis: quantitative predictions for trained transformers via a k-gram ansatz. Our key technical idea is to analyze, in place of a transformer with context length k, the optimal autoregressive process that depends only on the previous k tokens. We refer to this as the k-gram ansatz. While k-gram models with large k are well known to be statistically and computationally intractable in general (Shannon, 1948; Jurafsky and Martin, 2026), in our hierarchical model the distribution of k-gram is tractable, and we use it to derive explicit scaling laws for distributional statistics of the generated sequence. We then show experimentally that transformers trained on the same synthetic language closely match these predictions: the variance, kurtosis, and validity-rate curves of the trained models track our asymptotic theory across a wide range of context sizes.

1.1

Summary of our results

We now describe our main theoretical contributions, which fall into two parts: lower bounds showing that bounded-context autoregression is observably inconsistent with the true language, and an upper bound showing that logarithmic-memory reasoning suffices to generate from it exactly.

Figure 2: The plot of “valid rate” versus log context size for d = 4, h = 6, and q = 3. The sequence of dh colors generated by a model is valid if there is a d-ary tree with height h with proper q-coloring such that the leaves have the colors as given in the sequence. The valid rate is defined by the proportion of valid sequences as we generate the sequence multiple times. The thin horizontal lines indicate perfect generation (rate equals 1) and completely inconsistent generation (rate equals 0). The “Asymptotics” line is identical to inconsistent generation as per Theorem 3.3. The vertical line and the other three models are as discussed in Figure 1. See also Section 4.2. Lower bounds: scaling laws and Gaussianity for Ising. Our lower bounds concern an autoregressive variant of the broadcast process (Theorem 2.2) in which each subtree of size dw is generated using only the previous dw tokens. For the Ising broadcast process above the Kesten–Stigum threshold dρ2 > 1, we prove that the normalized variance of the generated sum of tokens scales log-linearly in the context depth w, and that its kurtosis converges to that of a Gaussian (Theorems 3.1 and 3.2). Both effects imply that the global coherence of the generated language is polynomially smaller than that of the true language unless w is within O(1) of h, and both are matched quantitatively by transformers trained on the synthetic language (Figure 1). Lower bounds: inconsistent generation for coloring. For the coloring broadcast process in the freezing regime — where the branching factor d is sufficiently large compared to the number of colors q — we prove that any bounded-context autoregressive model produces, with high probability, sequences that are inconsistent with any proper coloring of Td,h (Theorem 3.3). This is a qualitatively different failure mode from the Ising case: not statistical decoherence but outright invalidity, analogous to code in which individual functions compile but the program as a whole does not. We confirm this prediction empirically (Figure 2). Upper bound: logarithmic reasoning suffices. In contrast to these lower bounds, we prove that an autoregressive reasoning model — one equipped with a working memory of O(h log d) = O(log n) bits that can be read from and written to during generation — can sample exactly from the true (d, h, κ, ν)-language

(Theorem 3.4). This is an exponential improvement over what is achievable without reasoning: our lower bounds show that any non-reasoning model needs Ω(n) context to even approximately match simple global statistics, while Θ(log n) reasoning bits suffice to sample exactly. Trained transformers equipped with reasoning traces match the true language empirically across all our settings, with context windows orders of magnitude smaller than the language length.

1.2

Related Work

Hierarchical language models. A fundamental question in the theory of deep learning is understanding why depth is necessary, that is, identifying natural data distributions for which deep architectures provably outperform shallow ones. Mossel (2016) proposed to study hierarchical generative models based on broadcast on trees with the goal of representing data such as images or languages. Mossel observed that efficient algorithms for reconstructing such models follow from known results on phylogenetic reconstruction and established a separation in the semi-supervised setting below the Kesten-Stigum bound. Follow up results established low-degree hardness in the same regime (Koehler and Mossel, 2022; Huang and Mossel, 2024, 2025). More recent work in physics (Cagnetta et al., 2024; Tomasini and Wyart, 2024) analyzed variants of this model and demonstrate that both gradient descent and diffusion-based methods experimentally learn their model in the easy regime (i.e. above the Kesten-Stigum bound). Ren et al. (2026) prove that, under mild conditions, a deep convolutional network with gradient descent-based methods and layerwise training can efficiently learn this class. Formal languages and the representational power of transformers. A number of recent works have studied the representational power of the transformer architecture from the perspective of formal languages and worst-case complexity theory. See, e.g., Pérez et al. (2021); Barceló et al. (2023); Chiang et al. (2023); Chen et al. (2025); Merrill and Sabharwal (2023b). For example, Merrill and Sabharwal (2023b) showed that log-precision transformers are contained within the class T C 0 of bounded-depth circuits, while Pérez et al. (2021); Merrill and Sabharwal (2023a); Feng et al. (2023) show that transformers with the ability to generate intermediate states, i.e. with reasoning/CoT, are Turing complete. So from the perspective of worst-case complexity theory (and assuming standard conjectures, c.f., Chen et al. (2025)), reasoning/CoT are known to be crucial to allow transformers to represent many languages. In fact, once CoT is introduced, even relatively simple models like linear next-token-predictors become Turing complete (Malach, 2023). The aforementioned results are largely existential, i.e., investigate the representational ability of transformers. However, existence alone does not imply that standard training methods, or indeed that any method, can efficiently learn such a model from examples. Conjecturally hard examples like the problem of learning sparse parities with noise (Blum et al., 2003) show that learning even quite easy-to-represent concepts from data can be cryptographically hard (see related discussion in Malach (2023)). In contrast, for the hierarchical languages we study, we can experimentally demonstrate that the behavior of realistic transformer architectures, trained via next-token-prediction in the usual way, exhibits close agreement with our theoretical predictions. Learning-theoretic perspectives on reasoning/CoT. The recent works of Malach (2023); Joshi et al. (2025) study the effect of CoT on the computational and statistical tractability of learning. One important finding is that the inclusion of short reasoning traces (of O(log n) length for an input of length n) in the 5

training data can allow autoregressive models to learn functions like parities with noise which are cryptographically hard when the reasoning traces are omitted. The benefit of reasoning in our model is similar, in that a O(log n) length reasoning trace enables learning both theoretically and experimentally, but the underlying mechanism is statistical rather than computational. Without the reasoning trace, we show that the transformer with sublinear context windows progressively loses information about the past, which causes it to incorrectly generate the language. This in turn is driven by the hierarchical structure of our language, where information naturally flows over different length scales, which is absent from constructions like sparse parities. Other related work. As discussed in the introduction, the computational challenge caused by the quadratic time-complexity of the attention mechanism, and the importance of being able to attend to large contexts, are considered to be extremely important considerations in the design and use of SoTA language models. Our reasoning example partially fits into the paradigm of context compression/compaction. See Anthropic (2025) for discussion of the fundamental importance of context management in Claude Code and other applications. Our k-gram ansatz is partially motivated by a theoretical work of Sharan et al. (2018), which showed some positive results for modeling languages with bounded mutual information over large length scales using simple k-gram models. Practical k-gram models are restricted to relatively short contexts since their state space grows exponentially with the length of their memory; however, we might hope that transformers with sublinear windows on natural languages may be able to learn good approximations to the corresponding (intractible) k-gram model. As a reminder, k-gram models themselves date back to the early mathematical studies of natural language by Shannon (1948) — see, e.g., Jurafsky and Martin (2026) for more background.

1.3

Organization

In Section 2 we define the ground truth generative model in full detail. In Section 3 we formally state our main theoretical results, leaving the detailed proofs to the appendices. In Section 4 we confirm our theoretical predictions with experiments on transformers trained on the synthetic language.

Broadcast Process as a Hierarchical Language Model

Formally, our hierarchical model of language follows the “broadcast process on trees": Definition 2.1 (Broadcast Model). Let Td,h denote the d-ary tree of depth h and let Σ denote a finite set of tokens. We index the non-root nodes of Td,h by writing a node r at level ℓ as r ∈ [d]ℓ . Given a probability transition kernel κ on Σ — called the broadcast channel — and the initial prior ν on the root, the (d, h, κ, ν)broadcast process on Td,h is generated as follows: 1. Sample the root value X∅ ∼ ν. 2. Given the values at a layer ℓ ≤ h − 1, independently sample Xr for r ∈ [d]ℓ+1 according to the law µr (σ) = κ(Xr[1:ℓ] , σ) ,

σ ∈ Σ.

We write XL ∈ Σd for the sequence of tokens at the leaves. The (d, h, κ, ν)-language is defined by the h law of XL , which is a distribution on Σd . When ν is omitted, it is the stationary distribution. We will study two particular broadcast processes: first, the Ising broadcast process is defined by the state space Σ = {−1, +1} and the broadcast channel   1+ρ if σ = σ ′ , 2 κ(σ, σ ′ ) = 1−ρ  otherwise 2

for a correlation parameter ρ ∈ [0, 1], and the Rademacher prior ν. In particular, a child copies its parent’s state with probability ρ and re-randomizes with probability 1 − ρ. We also consider the coloring broadcast process with state space Σ = [q] and broadcast channel  0 if σ = σ ′ , κ(σ, σ ′ ) =  1 otherwise q−1

for a fixed constant q ≥ 2 representing the number of colors, and the uniform prior ν on Σ. Here, a child randomly picks a color not chosen by its parent. This process was studied extensively in probability and statistical physics starting with Kesten and Stigum (1966a); Higuchi (1977); Spitzer (1975), further background can be found in Evans et al. (2000); Mossel (2004); Mézard and Montanari (2006); Mossel (2022). Our main theoretical results will compare the statistics of the broadcast process with a Markovian version that has sublinear length to generate new subtrees: Definition 2.2 (Autoregressive Broadcast Process). Given parameters d, h, κ as in Theorem 2.1, the (d, h, κ)h autoregressive broadcast process with context depth w ≤ h is the stochastic process X L ∈ Σd generated as follows: w

1. Sample Y1 ∈ Σd from the marginal of the (d, h, κ)-broadcast process on (any) subtree of size dw . 2. For r = 2, . . . , dh−w , sample Yr by sampling first hr ∈ {1, . . . , h − w} independently from the distribution of heights between subtrees of depth w in Td,h and then sampling Yr from the (d, h, κ)broadcast process conditioned on Yr−1 and with these subtrees having least common ancestor in Td,h at height exactly hr . h

The final sample is XL = (Y1 , . . . , Ydh−w ) ∈ Σd . The autoregressive broadcast produces a sample XL by sampling on subtrees of Td,h of size dw one at a time. In each generation step, the autoregressive process conditions just on the previous subtree to produce the next subtree. The conditional distribution of this next subtree is simulated from the original broadcast process by averaging over the conditional distribution of adjacent subtrees in the original process, taken over the random height of the least common ancestor which governs the signal between these subtrees. In other words, the generation step samples adjacent subtrees according to the law of the broadcast process for a random pair of adjacent subtrees in Td,h . Note that this process is slightly different from the vanilla token-by-token auto-regressive process, because it is more mathematically elegant to analyze a process where you generate one depth w sub-tree at a time. We expect the same results hold for generating one token at a time (which is how we run the experiments), at the cost of a more complicated proof. 7

Theoretical results

Our main technical results concern the power of autoregressive models where they are only allowed to regress on the limited number of the most recent outputs. We consider models that, given an empty prompt or the leaves of a d-ary tree with height w, output the leaves of a (random) d-ary tree with height w, where w is the context depth as in Theorem 2.2. This corresponds to a transition kernel (conditional distribution function) w w p(· | −) : Σd ∪ {∅} → P(Σd ) w

where P(Σd ) is the set of probability measures on Σd ; this is equivalent to considering models with Θ(dw log |Σ|) bits of context. Running this model dh−w times autoregressively, starting with the initial h prompt ∅, samples a sequence in Σd , and our goal is to compare the distribution of this generated sequence to the ground truth (d, h, κ)-language. For simple autoregressive models without reasoning, we consider that the generative model is trained on data generated in the following way: 1. Sample a (d, h, κ)-language XL of Td,h . 2. Sample a subtree index i uniformly at random from [dh−w ] = {1, 2, · · · , dh−w }. 3. If i ≥ 2, then the input is the leaves Yi−1 of the (i − 1)th subtree of Td,h , and the output is the leaves Yi of the ith subtree of Td,h . If i = 1, then the input is an empty prompt. Since the model can only look at the subtree of height w each step, this is equivalent to training on the (d, h, κ)-autoregressive broadcast process, and the optimal model will exactly generate the (d, h, κ)autoregressive broadcast process. Thus, it suffices to compare the full broadcast process (Theorem 2.1) to its Markovian autoregressive variant (Theorem 2.2). A natural question is how the global statistics of the autoregressively generated sequence scale with the context length w as the language length dh grows. This section answers this question for the Ising and coloring broadcast processes (Sections 3.1 and 3.2), and shows that an exponentially smaller amount of reasoning memory suffices to recover the true distribution exactly (Section 3.3). Appendices. Proofs of theorems for Section 3.1 are deferred to Section D, for Section 3.2 to Section E, and for Section 3.3 to Section F.

3.1

Ising Broadcast Process

For the Ising broadcast process, a natural statistic is the variance of the sum of tokens normalized by dh/2 , which measures the global alignment of the language. For the true (non-autoregressive) language, the sum of tokens is well-understood: above the Kesten–Stigum threshold dρ2 > 1, this statistic becomes correlated with the latent root token even as h → ∞ (Kesten and Stigum, 1966b), see also Janson and Mossel (2004), and the normalized variance becomes exponentially large in the height h (see (2)). The following theorem shows that the autoregressive variant exhibits a sharply different behavior in this regime.

Theorem 3.1. Consider the Ising broadcast process on Td,h with dρ2 > 1. For a given context depth h 0 ≤ w ≤ h, let XL ∈ {±1}d denote a sample from the autoregressive process on the leaves with context length dw . Then if w → ∞ and h − w → ∞, the (log-) normalized variance satisfies:    dh X   log d−h · Var  (XL )i  = w log(dρ2 ) + log(Ad,ρ (2)) + o(1), (1) i=1

where Ad,ρ (2) is an explicit constant depending only on d, ρ. h

By contrast, when XL ∈ {±1}d is a sample from the true Ising broadcast process (i.e. w = h),    h d X   log d−h · Var  (XL )i  = h log(dρ2 ) + log(Cd,ρ (2)) + o(1),

(2)

i=1

where Cd,ρ (2) ≤ Ad,ρ (2) is an explicit constant depending only on d, ρ.1 Theorem 3.1 has two implications. First, while the autoregressive process produces tokens with the correct local marginals by definition, its global coherence is polynomially smaller than the true language’s unless a linear fraction of the language is used as context (w = h − O(1)). In the context of natural language, this can be thought of as failing to produce a strong unified signal — for example, generating a long, ambiguous answer to a yes/no question rather than committing to a direction. Second, the prediction is precisely quantitative: the log-variance is linear in w with slope log(dρ2 ), which our experiments on trained transformers confirm closely (Figure 1a). This decoherence has a further observable consequence. By computing higher moments of the autoregressive process via the theory of broadcast processes, we obtain the following result: Theorem 3.2. Consider the Ising broadcast process on Td,h with dρ2 > 1. For a given context depth h 0 ≤ w ≤ h, let XL ∈ {±1}d denote a sample from the autoregressive process on the leaves with context P length dw . If w → ∞ and h − w → ∞, then the excess kurtosis of i (XL )i satisfies: 4 Pdh   h E (X ) d L i i=1 X (3) Kurt  (XL )i  − 3 := 2 2 − 3 = o(1) . Pdh i=1 E i=1 (XL )i Recall that the kurtosis of Gaussian random variables is precisely 3. Intuitively, Theorem 3.2 says that bounded-context autoregression in this hierarchical language causes information decay rapid enough for central-limit-type behavior to emerge: the generated sum behaves like a sum of approximately independent contributions from each subtree, even though the true language has heavy-tailed multiscale dependencies.Our experiments again confirm this prediction (Figure 1b).

3.2

Coloring Broadcast Process

The previous results quantify the behavior of bounded-context autoregression in a soft-constrained language: every sequence has positive probability under the true language, and the generated sequences differ from 1

The different constant terms reflect that when w is very close to h, there are finite-size corrections to the asymptotics.

it statistically rather than logically. Many real applications of language models involve hard-constrained languages, where logical or syntactic rules exclude entire classes of sequences — code, formal mathematics, structured data, and so on. The coloring broadcast process serves as a clean abstraction of this setting: by construction, valid sequences correspond exactly to leaf labelings extending to a proper coloring of the underlying tree. A central phenomenon in the theory of colorings on trees is freezing (e.g. Mossel and Peres (2003); Semerjian (2008); Sly (2009)): when d is sufficiently large relative to q, the leaves of a subtree contain enough information to typically fix all of the internal labels, including the root. We demonstrate that freezing has stark consequences for autoregressive generation. Theorem 3.3. Consider the autoregressive coloring broadcast process with q colors on Td,h with any context depth w < h satisfying d > q(log(q)+log log(q)+1+oq (1)). Then with probability 1−oq (1), the sampling of the leaves in the autoregressive coloring process is inconsistent with any proper coloring of Td,h . The interpretation is that with bounded context, the autoregressive process samples each subtree consistently with itself but cannot maintain global consistency across subtrees, as freezing-determined “commitments” made at the leaves of one subtree generically conflict with those of another. In the natural-language analogy: each subtree corresponds to a coherent local fragment, but the overall sequence has no globally valid parse. The empirical counterpart in Figure 2 shows that trained transformers in this regime almost never produce a valid sequence, while reasoning-equipped models almost always do.

3.3

Autoregressive Models with Reasoning

We model a reasoning-equipped autoregressive model as the ordinary autoregressive model augmented with an additional working memory — a finite set M of memory states that the model may freely read from or write to between generation steps, and whose contents are not part of the final output. The model is then a transition kernel (conditional distribution function) w

p(· | −) : (Σd ∪ {∅}) × M → P(Σd × M) .

(4)

The size of the memory log |M| is the relevant “reasoning budget,” analogous to the length of a chain-ofthought trace in real LLMs. The next theorem shows that a logarithmic budget is sufficient to sample the true language exactly, even with arbitrarily small context. Theorem 3.4. For any 0 ≤ w ≤ h, |M| = (d|Σ|)O(h−w) suffices to sample from the exact (d, h, κ)language. In particular, there is an autoregressive reasoning model with context size O(h log(d|Σ|)) that samples from the ground truth language (when w = 0 is chosen). This result is agnostic to the broadcast channel κ. The intuition is that the memory only needs to carry information about the path from the root to the current generation position in the tree — specifically, the labels of the O(h) ancestors and recent siblings needed to sample the next subtree from the true conditional distribution. This is O(h log d|Σ|) = O(log n) bits of state, exponentially smaller than the Ω(n) context required by a non-reasoning model. Connecting back to practice, this offers a clean theoretical analogue to the context-compression phenomenon studied in modern LLMs (Anthropic, 2025): a small, well-chosen working memory can substitute for a much larger context window, provided the underlying distribution has compressible hierarchical structure. 10

+ + +

+ +

-++ --- +++ -+- -++ +++ --- --- ++-++1---1+++2-+-1-++1+++2---1---1++Figure 3: An example of the tokenization of the leaves of a ternary tree with height 3.

Empirical Results

We corroborate our theory by empirically demonstrating the scaling law for the two broadcast processes: the sum of leaves for the Ising model, and the success rate of root reconstruction for the coloring model. We use nanochat by Karpathy (2025) as our base model and train on the dataset synthetically generated from our hierarchical language described in Section 2. Then we evaluate the empirical distribution of the output generated by the autoregressive sampling of the pre-trained model. Our codes for experiments are available in https://github.com/joonhyungshin/nanocontext. See Section G for the detailed experiment setup. Punctuation. A notable detail in the tokenization step of our language is the introduction of punctuation marks. Recall that our hierarchical language is a sequence of the dh leaves of a d-ary tree with height h, with latent internal nodes that affect the leaves in its subtree. We insert a punctuation mark every d values in the sequence, effectively telling the model that “a certain subtree has concluded, and a new subtree begins.” We use different punctuation tokens for different height of the subtrees, analogous to natural language documents which have different indicators at different levels (commas, periods, line breaks, etc.). Including the punctuation marks, we use dh−1 (d + 1) − 1 many tokens to tokenize a d-ary tree with height h. See Figure 3 for an illustrative example. Autoregressive training. Recall that in our theoretical results in Section 3, we considered restrictive models that samples a subtree given the previous subtree. To evaluate under a more practical scenario, we do not follow this restriction in our experiments. Instead, we do the usual autoregressive training: the training samples are “chunks” C of the leaves of length k equal to the prescribed context size, and train the model to predict C[2 : k + 1] given C[1 : k]. During the inference, the model autoregressively outputs a token one at a time, where the current output is fed back as the most recent token of the input and the oldest token is truncated in case the number of tokens exceeds k. Here, the punctuation marks described in the previous paragraph play a vital role, since it tells the model what part of the subtree it is currently generating or being trained on. Reasoning models. We train the reasoning model from scratch in a supervised fashion, by manually inserting the desired memory states periodically in the training data. For instance, suppose that we aim at a

reasoning model p(· | −) as in (4) capable of exact sampling. We generate a sequence L0 , M0 , L1 , M1 , . . . , Ldh−w , Mdh−w where (Li+1 , Mi+1 ) are sampled from p(· | Li , Mi ) autoregressively, tokenize the sequence, randomly sample a chunk of length k, and feed it as a training sample. To inform the model wrapper that part of the output is the memory state and not the actual leaves, we prepend and append special memory tokens to mark the beginning and the end of the memory section.

4.1

Ising Broadcast Process

P We collect the dh spins autoregressively outputted by the models and compute their sum Xr . We repeat P this at least 1,000 times and visualize distributional properties of Xr . To compare with the theory results in Section 3.1, we estimate the log-normalized variances as predicted in by (1) in Theorem 3.1, as well as the excess kurtosis as in (3) as predicted in Theorem 3.2. We run the experiments with correlation ρ = 0.9 on ternary trees (d = 3) of height h = 8, so we are above the Kesten–Stigum threshold (dρ2 = 2.43 > 1). We train reasoning models with context sizes 26 , 27 , · · · , 211 and non-reasoning models with context sizes 24 , 25 , · · · , 211 . The results are summarized in Figure 1. The “Simulated” curve is computed using the true autoregressive broadcast process, with context depth w defined in Theorem 2.2. For the non-reasoning models, as context size decreases, the variance and the kurtosis deviate from the ground truth and converge to our asymptotic prediction as w shrinks. In contrast, for reasoning models the variance and kurtosis are close to the ground truth even at context size 26 = 64 ≪ dh = 6561.

4.2

Coloring Broadcast Process

In the q-coloring model, we collect the dh colors from the model output, and attempt to find a d-ary tree with height h with proper q-coloring such that the colors of the leaves are those generated by the model. We repeat this at least 1000 times and count the number of successful reconstruction attempts to estimate the success rate. We run the experiments with quaternary trees (d = 4) of height h = 6 on q = 3 colors, lying in the frozen regime. Context sizes are as in the Ising case. As shown in Figure 2, non-reasoning models with small context size almost never generate a sequence of valid colors, while the reasoning models almost always generate a valid sequence.

Limitations

A key advantage of our hierarchical model of language is to enable clean theory and empirical validation. It would be interesting to study both theoretically and empirically similar phenomena in natural languages. For our theoretical results, we leverage the geometry of regular trees to obtain precise quantitative predictions. Extending this theory to more general language or correlation structures is an interesting future direction.

Acknowledgments J.G. and E.M were partially supported by Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826 and by NSF award NSF DMS-2031883. We thank Yonatan Belinkov, Tatsunori Hashimoto, and Matus Telgarsky for interesting discussions.

References Anthropic. Effective context engineering for ai agents, 2025. URL https://www.anthropic.com/ engineering/effective-context-engineering-for-ai-agents. Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. Logical languages accepted by transformer encoders with hard attention. arXiv preprint arXiv:2310.03817, 2023. P. M. Bleher, J. Ruiz, and V. A. Zagrebnov. On the purity of the limiting gibbs state for the ising model on the bethe lattice. Journal of Statistical Physics, 79(1):473–482, 1995. doi: 10.1007/BF02179399. URL https://doi.org/10.1007/BF02179399. Leonard Bloomfield. Language. Henry Holt and Company, New York, 1933. Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506–519, 2003. Francesco Cagnetta, Leonardo Petrini, Umberto M Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Physical Review X, 14(3): 031001, 2024. Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2631–2653. IEEE, 2025. David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, pages 5544–5562. PMLR, 2023. Noam Chomsky. Syntactic Structures. Mouton, The Hague, 1957. Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006. ISBN 978-0471-24195-9. URL http://www.elementsofinformationtheory.com/. Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in neural information processing systems, 35:16344–16359, 2022. Werner Ebeling and Alexander Neiman. Long-range correlations between letters and sentences in texts. Physica A: Statistical Mechanics and its Applications, 215(3):233–241, 1995. Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2):179–211, 1990.

William Evans, Claire Kenyon, Yuval Peres, and Leonard J Schulman. Broadcasting on trees and the ising model. Annals of Applied Probability, pages 410–433, 2000. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36:70757–70798, 2023. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-r1 incentivizes reasoning in llms through reinforcement learning. Nature, 645(8081):633–638, 2025. Y. Higuchi. Remarks on the limiting Gibbs states on a (d + 1)-tree. Publ. Res. Inst. Math. Sci., 13(2): 335–348, 1977. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, DDL Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 10, 2022. Han Huang and Elchanan Mossel. Low degree hardness for broadcasting on trees. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, pages 32137–32218, 2024. URL https: //openreview.net/forum?id=3iOefhez5e. Han Huang and Elchanan Mossel. Polynomial low degree hardness for broadcasting on trees (extended abstract). In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2856–2857. PMLR, 30 Jun–04 Jul 2025. URL https://proceedings.mlr.press/v291/huang25a.html. Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024. S. Janson and E. Mossel. Robust reconstruction on trees is determined by the second eigenvalue. Ann. Probab., 32:2630–2649, 2004. URL http://front.math.ucdavis.edu/0406.5447. Keller Jordan, Jeremy Bernstein, Brendan Rappazzo, @fernbear.bsky.social, Boza Vlado, You Jiacheng, Franz Cesista, Braden Koszarsky, and @Grad62304977. modded-nanogpt: Speedrunning the nanogpt baseline, 2024a. URL https://github.com/KellerJordan/modded-nanogpt. Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024b. URL https:// kellerjordan.github.io/posts/muon/. Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. A theory of learning with autoregressive chain of thought. arXiv preprint arXiv:2503.07932, 2025. Daniel Jurafsky and James H Martin. Speech and language processing: An introduction to natural language processing, computational linguistics, and speech recognition, 2026.

Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. Andrej Karpathy. nanochat: The best chatgpt that $100 can buy, 2025. URL https://github.com/ karpathy/nanochat. Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156–5165. PMLR, 2020. H. Kesten and B. P. Stigum. Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Statist., 37:1463–1481, 1966a. H. Kesten and B. P. Stigum. Additional Limit Theorems for Indecomposable Multidimensional GaltonWatson Processes. The Annals of Mathematical Statistics, 37(6):1463 – 1481, 1966b. doi: 10.1214/aoms/ 1177699139. URL https://doi.org/10.1214/aoms/1177699139. Frederic Koehler and Elchanan Mossel. Reconstruction on trees and low-degree polynomials. Advances in Neural Information Processing Systems, 35:18942–18954, 2022. Aixin Liu, Aoxue Mei, Bangcai Lin, Bing Xue, Bingxuan Wang, Bingzheng Xu, Bochao Wu, Bowei Zhang, Chaofan Lin, Chen Dong, et al. Deepseek-v3. 2: Pushing the frontier of open large language models. arXiv preprint arXiv:2512.02556, 2025. Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv:2309.06979, 2023.

arXiv preprint

Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330, 1993. William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023a. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531–545, 2023b. M. Mézard and A. Montanari. Reconstruction on trees and the spin glass transition. Journal of Statistical Physics, 124:1317–1350, 2006. Richard Montague. Universal grammar. Theoria, 36(3):373–398, 1970. E. Mossel. Survey: Information flow on trees. In J. Nešetřil and P. Winkler, editors, Graphs, Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science, pages 155–170. 2004. URL http://front.math.ucdavis.edu/0406.5446. Elchanan Mossel. Deep learning and hierarchal generative models. arXiv preprint arXiv:1612.09057, 2016. Elchanan Mossel. Probabilistic view of voting, paradoxes, and manipulation. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 59(3):297–330, 2022. 15

Elchanan Mossel and Yuval Peres. Information flow on trees. The Annals of Applied Probability, 13(3): 817–844, 2003. ISSN 10505164. URL http://www.jstor.org/stable/1193228. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35, 2021. Alonzo Reed and Brainerd Kellogg. Higher Lessons in English: A Work on English Grammar and Composition. Clark and Maynard, New York, 1877. Yunwei Ren, Yatin Dandi, Florent Krzakala, and Jason D Lee. Provable learning of random hierarchy models and hierarchical shallow-to-deep chaining. arXiv preprint arXiv:2601.19756, 2026. Guilhem Semerjian. On the freezing of variables in random constraint satisfaction problems. Journal of Statistical Physics, 130(2):251–293, 2008. doi: 10.1007/s10955-007-9417-7. URL https://doi. org/10.1007/s10955-007-9417-7. Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27 (3):379–423, 1948. Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant. Prediction with a short memory. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1074–1087, 2018. Allan Sly. Reconstruction of random colourings. Communications in Mathematical Physics, 288 (3):943–961, 2009. doi: 10.1007/s00220-009-0783-7. URL https://doi.org/10.1007/ s00220-009-0783-7. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1631–1642, 2013. F. Spitzer. Markov random fields on an infinite tree. Ann. Probability, 3(3):387–398, 1975. Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics (ACL), pages 1556–1566, 2015. Lucien Tesnière. Éléments de syntaxe structurale. Klincksieck, Paris, 1959. Umberto Tomasini and Matthieu Wyart. How deep networks learn sparse and hierarchical data: the sparse random hierarchy model. arXiv preprint arXiv:2404.10727, 2024. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017. Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768, 2020. 16

Rulon S. Wells. Immediate constituents. Language, 23(2):81–117, 1947. Wenhan Xiong, Jingyu Liu, Igor Molybog, Hejia Zhang, Prajjwal Bhargava, Rui Hou, Louis Martin, Rashi Rungta, Karthik Abinav Sankararaman, Barlas Oguz, et al. Effective long-context scaling of foundation models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4643–4663, 2024. Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hierarchical attention networks for document classification. In Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies, pages 1480– 1489, 2016. Daniel Zwillinger and Stephen Kokoska. CRC standard probability and statistics tables and formulae. Crc Press, 1999.

Overview of the Appendix

For our theoretical results, we introduce the relevant background from Markov chains and the theory of broadcast processes in Section B. In Section C, we carry out the asymptotic calculations for the ground truth Ising language using recursive arguments from the hierarchical structure. We build on this in Section D to make our theoretical predictions for autoregressive generation in the Ising (soft-constrained) version of our language. In Section E we prove that for the coloring (hard-constrained) version of our language, shortcontext models without reasoning will typically produce invalid trees, building on the freezing phenomenon in this model. In Section F, we complete the proof of the positive theoretical result for the reasoning model. In Section G we give more details about the setup for our simulations with transformer models. In Section H, we state and prove some lemmas for asymptotic series calculations which are used in the proofs of our main results.

Further Preliminaries

B.1

Markov Chains

In many of our arguments, we will use the information-theoretic characterization of Markov chains (see e.g. Cover and Thomas (2006)). Formally, a sequence of random variables A1 , A2 , . . . , An forms a Markov chain, denoted A1 → A2 → . . . → An , if for each k, conditioned on Ak , the random variables (A1 , . . . , Ak−1 ) and (Ak+1 , . . . , An ) are conditionally independent. In other words, the future and past of a Markov chain are conditionally independent given the present. An well-known equivalent definition is that the conditional distribution of Ak given A1 , . . . , Ak−1 is the same as the conditional distribution of Ak given just Ak−1 .

It will be convenient to track several induced Markov chains in the autoregressive Ising process as in Theorem 2.2 later on. We have the following highly convenient closed form for their cross-correlations for any Markov chain on marginally uniform spins: Lemma B.1. Let A1 → . . . → An denote any Markov chain with each Ai ∈ {±1} marginally uniform. Let αi = E[Ai Ai+1 ]. Then n−1 Y E[A1 An ] = αi i=1

Proof. This immediately follows by induction using the Markov property: the claim is trivially true for n = 2 and for general n, E[A1 An ] = E[E[A1 An |An−1 ]] = E[E[A1 |An−1 ]E[An |An−1 ]] = αn−1 E[An−1 E[A1 |An−1 ]] = αn−1 E[E[A1 An−1 |An−1 ]] = αn−1 E[A1 An−1 ], so we can conclude by induction. The second line follows by conditional independence in any Markov chain, while the rest is basic properties of binary random variables and conditional expectation.

B.2

Broadcast Processes

In this section, we record simple calculations for d-ary trees as well as relevant background on broadcasting processes that will be important in our arguments. B.2.1

d-ary Trees

For our computations, we will require the following distribution of least common ancestor heights in Td,h . Proposition B.2. In Td,h , for any leaf node ℓ, the number of leaves in Td,h whose least common ancestor with ℓ is at distance k is 1 for k = 0 and (dk − dk−1 ) for 1 ≤ k ≤ h. Proof. This is immediate from the fact that all leaves at distance k > 0 from ℓ are precisely the leaves belonging to the same subtree as ℓ of size dk but that do not belong to the same subtree of r of size dk−1 . We will also need the following simple computation on the height of least common ancestors of a random adjacent pair of leaves (ℓ, ℓ + 1) where ℓ is uniform on [d]h \ {(d, . . . , d)}. Recall that under our encoding of the leaves, this excluded vertex is simply the rightmost vertex of Td,h . Proposition B.3. Let Dh denote the (random) height of the least common ancestor of a random pair of adjacent leaves (ℓ, ℓ+1) sampled uniformly in Td,h . Then as h → ∞, the law of Dh converges in distribution to Geom(1/d), a geometric random variable with success probability 1/d. In particular, for any fixed ρ ∈ [0, 1), αh := Es∼Dh [ρ2s ] → α∗ := Es∼Geom(1/d) [ρ2s ] < 1. 18

Proof. Under our encoding of the tree, the least common ancestor of a pair (ℓ, ℓ + 1) ∈ ([d]h )2 is precisely the last component of ℓ ∈ [d]h \ {(d, . . . , d)} that is not equal to d since then there is no carryover. We can couple the sampling of ℓ uniform on [d]h \ {(d, . . . , d)} with a uniform sample on [d]h up to error 1/dh from sampling ℓ = (d, . . . , d). As h → ∞, this probability of failure tends to 0, and moreover, the index of the last component that is not equal to d converges to Geom(1/d) since each component then is equal to d with probability 1/d independently across coordinates. B.2.2

Ising Broadcast

Consider the Ising broadcast process on Td,h with correlation parameter ρ as in Theorem 2.1. We will view d, ρ as fixed while h → ∞. For our later computations to compute moments of the autoregressive Ising broadcast, we will need to define: qh := qh (d, ρ) = E[E[X|Y ]2 ] where (X, Y ) is the root and leaves, respectively, of a sample from the broadcast process on Td,h with correlation ρ. In other words, this is the (squared) expected reconstruction advantage on average over the sampling of the leaves. A fundamental fact from the theory of Ising broadcast processes is that when dρ2 < 1, then qh → 0 as h → ∞ while above the Kesten-Stigum bound, the reconstruction probability stays bounded away from 0: Theorem B.4 (Kesten-Stigum Bound (Kesten and Stigum (1966b)), see e.g. Bleher et al. (1995)). Consider the Ising broadcast process on Td,h with correlation parameter ρ and uniform prior on the root. Then if dρ2 > 1 is fixed, it holds that lim qh = q ∗ > 0 h→∞

for an absolute constant q ∗ = q ∗ (d, ρ). Proof. First, note that the limit exists because qh is monotone non-increasing in h. This is because the broadcast process can be written as a Markov chain X → Y 1 → Y 2 → . . . → Y h, where Y j is the vector of spins at level j of the d-ary tree. In particular, the process for t ≥ 1 defined by E[X|Y t ] forms a backwards martingale. In particular, the L2 -norms are decreasing since qt+1 = E[E[X|Y t+1 ]2 ] = E[E[E[X|Y t ]|Y t+1 ]2 ] ≤ E[E[E[X|Y t ]2 |Yt+1 ]] = E[E[X|Y t ]2 ] = qt , by Cauchy-Schwarz and the tower law. Therefore, qh → q ∗ for some q ∗ ≥ 0 by nonnegativity. To see that q ∗ is in fact strictly positive when above the Kesten-Stigum bound, it is well-known (see e.g. Bleher et al. (1995)) that when dρ2 > 1, the following reconstruction problem is solvable (Mossel and Peres (2003)): h lim dT V (Y1h , Y−1 ) > 0, (5) h→∞

h denote the distributions of the leaves of the Ising broadcast process of depth h conditioned where Y1h , Y−1 on the root X being +1 and −1, respectively. By definition of total variation distance, X 1 h )= | Pr(Y h |X = 1) − Pr(Y h |X = −1)| dT V (Y1h , Y−1 2 h Y h ∈{±1}d

Pr(Y h )| Pr(X = 1|Y h ) − Pr(X = −1|Y h )|

Y h ∈{±1}dh

h i = EY h |E[X|Y h |] √ ≤ qh . The second equality is Bayes’ rule to rewrite the total variation distance in terms of the expected magnetization of the root given the leaves, and the final step is Cauchy-Schwarz. Since the total variation distance stays bounded away from zero above the KS bound by (5), the same therefore holds true for qh and hence the limiting value q ∗ . B.2.3

Coloring Broadcast

A well-known fact for the coloring broadcast process is the onset of freezing: if the branching factor d of Td,h is sufficiently large compared to the number of colors q, then with high probability over the sampling of the process, the posterior distribution of the root given the leaves is fixed to a unique color. We will require the following quantitative version by Sly (2009) that was implicit in earlier work of Mossel and Peres (2003) as well as Semerjian (2008): Theorem B.5 (Freezing, Lemma 7 of Sly (2009)). Consider the coloring broadcast process on Td,h with q colors. Then if the branching factor d satisfies d ≥ q(log(q) + log log(q) + oq (1)), h

then if XL ∈ [q]d denotes the colors of the leaves, then with probability at least 1 − 1/ log(q) over XL : Law(X∅ |XL ) = δi , where i ∼ [q] is a marginally uniform color.

Moments of the Ising Language

In this section, we compute important statistics of the Ising broadcast process so as to compare with the statistics of the autoregressive version that uses bounded context windows in generation. In particular, we will compute various moments of these processes that will be used for the proof of Theorem 3.1 and Theorem 3.2.

C.1

Moments of the Broadcast Process

Throughout this section, we will consider the Ising broadcast process with correlation parameter ρ satisfying dρ2 = λ > 1; we will view d and ρ as fixed. We remark that a well-known equivalent description of the 20

broadcast process is that with probability ρ, an internal vertex copies its sign in Σ to a child, while with probability 1 − ρ, it broadcasts a uniformly random sign. To set up various recurrences, we will compute the following moments:    k

 X   Md,ρ,h (k) := E  Xi  X∅ = +1  , i∈[d]h

where Xi for i ∈ [d]h are the nodes at level h of the broadcast process and X∅ is the value of the root. While our focus will eventually k = 2, 4, this more general definition will enable us to recurse using the tree structure, and so here we will treat h as a general variable in the recursion. Note that Md,ρ,h (k) for k even is the same as the unconditional expectation by symmetry. We will find that these moments are equal to (dρ)kh up to an explicit multiplicative constant depending only on d, ρ, but not h. The first two moments are well-known and elementary: Proposition C.1. Let XL be sampled from the (d, h)-Ising broadcast process with fixed correlation ρ satisfying dρ2 = λ > 1. Then Md,ρ,h (1) = (dρ)h Md,ρ,h (2) = dh + dh · (1 − 1/d) ·

h X (dρ2 )ℓ . ℓ=1

In particular, Md,ρ,h (2) = (1 − o(1)) · Cd,ρ (2) · (dρ)2h , where Cd,ρ (2) := (1 − 1/d) ·

dρ2 . dρ2 − 1

Proof. The first moment is trivial from linearity of expectation. Each Xr for r ∈ [d]h has the same marginal distribution by symmetry, and has conditional expectation +1 when the path of length h from the root has no re-randomizations, while is otherwise mean zero. This means E[Xr |X∅ = +1] = ρh , and so Md,ρ,h (1) = dh · ρh = (dρ)h . For the second moment, we can argue as follows:    2

ℓ,ℓ′ =1

ℓ=1

d d d X X X  X   2LCA(ℓ,ℓ′ ) h   ′ Xℓ   = E[Xℓ Xℓ ] = ρ =d · Md,ρ,h (2) = E  ρ2LCA(1,ℓ) ℓ∈[d]h

where LCA(·, ·) denotes the height of the least common ancestor of the leaves. Here, we use the fact that Xℓ and Xℓ′ have nontrivial correlation if and only if the signal from their least common ancestor propagates 21

′

to both of them, which occurs with probability ρ2LCA(ℓ,ℓ ) by independence in the broadcasting along edges. The last equality is by symmetry of the tree. To evaluate this sum, Theorem B.2 shows that h

d X

ρ2LCA(1,ℓ) = 1 +

ℓ=1

h X

ρ2k · (dk − dk−1 ) = 1 + (1 − 1/d) ·

k=1

h X

ρ2k · dk ,

k=1

and the claim follows for Md,ρ,h (2). The final statement follows by noting that h X d · (1 − 1/d) · (dρ2 )ℓ = dh · (1 − 1/d) · (dρ2 ) · h

ℓ=1

! (dρ2 )h − 1 dρ2 − 1 ! dρ2 = (1 − o(1)) · (1 − 1/d) · · (dρ)2h . dρ2 − 1

Since dρ2 > 1 is fixed, this term asymptotically dominates dh as h → ∞. We now compute the higher moments we need using a recursive argument based on the lower depths and moments. Proposition C.2. Let XL be sampled from the (d, h)-broadcast process with fixed correlation ρ satisfying dρ2 = λ > 1. Then Md,ρ,h (3) = (1 − o(1)) · Cd,ρ (3) · (dρ)3h , where 1 Cd,ρ (3) := · (dρ)2 − 1

! (d − 1)2 dρ2 2 3· · + (dρ) · (1 − 1/d)(1 − 2/d) d (dρ2 − 1)

Proof. Let us write Z1 , . . . , Zd as the d subtree sums of the children of the root node in the broadcast process. We then have:   3 X   Md,ρ,h (3) = E  Zi  Xr = +1 i∈[d]

= dρMd,ρ,h−1 (3) + 3d(d − 1)ρMd,ρ,h−1 (2) · Md,ρ,h−1 (1) + d(d − 1)(d − 2)ρ3 (Md,ρ,h−1 (1))3 = dρMd,ρ,h−1 (3) + 3(d − 1)Md,ρ,h−1 (2) · (dρ)h + (1 − 1/d)(1 − 2/d)(dρ)3h To see where these terms come from, note that: 1. The first term corresponds to choosing the same subtree each time. In this case, with probability ρ, the root of the subtree remains the same as the root of the full tree and we get the same quantity of the subtree one level below. If this does not occur, then the root of the subtree is rerandomized and the expectation is zero by symmetry since we are computing an odd moment. 2. The second term corresponds to the different ways of choosing two subtrees, one of them twice. There are d · (d − 1) choices for them (where the first choice is taken twice), and given this choice, there are three permutations. The square term is precisely Md,ρ,h−1 (2), while for the linear term, it again becomes mean zero with probability 1 − ρ independently, else corresponds to the subtree sum conditioned on the subtree root remaining 1. This has expectation (dρ)h−1 . 22

3. Finally, all three indices are different, and we may freely permute them to give d(d − 1)(d − 2) options. Conditioned on the root, each retains the signal with probability ρ independently, and given they all do, the corresponding means are Md,ρ,h−1 (1) = (dρ)h−1 . When any of these events fails, the expectation simply becomes zero. The second equality then comes from plugging in Theorem C.1 for the first moments. Iterating this recurrence, we use Theorem C.1 to obtain: Md,ρ,h (3) = (dρ)h + 3(d − 1)(dρ)h

h−1 X

Md,ρ,ℓ (2) + (1 − 1/d)(1 − 2/d)

ℓ=0 h

ℓ=0

= (dρ) + 3(d − 1)(dρ) (Cd,ρ (2) − o(1))

h−1 X

h X (dρ) + (1 − 1/d)(1 − 2/d)(dρ) (dρ)2ℓ 2ℓ

ℓ=0

= (dρ)h + (1 − o(1)) · 3 · (d − 1) · Cd,ρ (2) · (dρ)h + (1 − 1/d)(1 − 2/d)(dρ)h = 1 − o(1) ·

h−1 X (dρ)3h−2ℓ

ℓ=1

(dρ)2h − 1 (dρ)2 − 1

(dρ)2h+2 − (dρ)2 (dρ)2 − 1

1 2 · 3 · (d − 1) · C (2) + (dρ) · (1 − 1/d)(1 − 2/d) · (dρ)3h d,ρ (dρ)2 − 1

:= (1 − o(1)) · Cd,ρ (3) · (dρ)3h P In the second line, we use the elementary fact that if x > 1 is fixed, then the nearly geometric sum hi=0 (1− h+1 o(1))xi = (1 − o(1)) x x−1−1 since this sum is dominated by the largest elements which have prefactors tending to 1. The stated formula for Cd,ρ (3) follows by substituting the value of Cd,ρ (2). Finally, we can compute the fourth moment using the previous results: Proposition C.3. Let XL be sampled from the (d, h)-broadcast process with fixed correlation ρ satisfying dρ2 = λ > 1. Then Md,ρ,h (4) = (1 − o(1)) · Cd,ρ (4) · (dρ)4h , where 4(d − 1)ρ2 Cd,ρ (3) + 3(d − 1)(Cd,ρ (2))2 + 6(d − 1)(d − 2)ρ2 Cd,ρ (2) + (d − 1)(d − 2)(d − 3)ρ4 Cd,ρ (4) := (d3 ρ4 ) − 1 Proof. As in the previous computation, we again have   4 X   Md,ρ,h (4) = E  Zi  Xr = +1 i∈[d]

= dMd,ρ,h−1 (4) + 4d(d − 1)ρ2 Md,ρ,h−1 (3) · Md,ρ,h−1 (1) + 3d(d − 1)(Md,ρ,h−1 (2))2 + 6d(d − 1)(d − 2)ρ2 Md,ρ,h−1 (2) · (Md,ρ,h−1 (1))2 + d(d − 1)(d − 2)(d − 3)ρ4 (Md,ρ,h−1 (1))4

The interpretation of each of the terms is similar, grouping by the possible exponents of the at most four distinct indices. One can verify that the coefficients indeed sum to d4 . We pick up a ρ factor for each term that corresponds to an odd moment of a subtree since the root copies the signal with this probability, or else the odd moment is zero by symmetry. Unwinding this recurrence by expanding Md,ρ,h−1 (4), then expanding Md,ρ,h−2 (4), and so on, we find that Md,ρ,h (4) = dh + 4(d − 1)ρ2

h−1 X

dh−ℓ Md,ρ,ℓ (3)Md,ρ,ℓ (1) + 3(d − 1)

ℓ=0

h−1 X

dh−ℓ (Md,ρ,ℓ (2))2

ℓ=0

+ 6(d − 1)(d − 2)ρ2

h−1 X

dh−ℓ Md,ρ,ℓ (2) · (Md,ρ,ℓ (1))2

ℓ=0

+ (d − 1)(d − 2)(d − 3)ρ4

h−1 X

dh−ℓ (Md,ρ,ℓ (1))4

ℓ=0

and simplifying yields that Md,ρ,h (4) equals h

d + (1 − o(1)) · 4 · d (d − 1)ρ Cd,ρ (3)

h−1 X

−ℓ

4ℓ

d (dρ) + (1 − o(1))3d (d − 1)(Cd,ρ (2))

ℓ=0

+ (1 − o(1))6dh (d − 1)(d − 2)ρ2 Cd,ρ (2)

h−1 X

d−ℓ (dρ)4ℓ + dh (d − 1)(d − 2)(d − 3)ρ4

ℓ=0

h−1 X

d−ℓ (dρ)4ℓ

ℓ=0 h−1 X

d−ℓ (dρ)4ℓ

ℓ=0

= (1 − o(1)) · d · 4(d − 1)ρ2 Cd,ρ (3) + 3(d − 1)(Cd,ρ (2))2 + 6(d − 1)(d − 2)ρ2 Cd,ρ (2) + (d − 1)(d − 2)(d − 3)ρ4 ·

(d3 ρ4 )h − 1 (d3 ρ4 ) − 1

= (1 − o(1)) · (dρ)4h · 4(d − 1)ρ2 Cd,ρ (3) + 3(d − 1)(Cd,ρ (2))2 + 6(d − 1)(d − 2)ρ2 Cd,ρ (2) + (d − 1)(d − 2)(d − 3)ρ4 (d3 ρ4 ) − 1 | {z } :=Cd,ρ (4)

as claimed.

Moments of the Autoregressive Ising Process

In this section, we complete the proof of Theorem 3.1 and Theorem 3.2. To do this, we use the results of the previous section to compute moments for the autoregressive Ising process as defined in Theorem 2.2. The main difference is that the cross-correlations will decay much faster even when above the Kesten-Stigum bound, so that the moments add up almost independently. Recall that to generate the leaves of a new subtree Yi of size dw in the autoregressive process given Yi−1 , we sample the height hi from the law of heights of adjacent subtrees at depth h − w in Td,h and then sample Yi from the conditional law on (Yi−1 , Yi ) from the broadcast process when these subtrees have least common ancestor at height hi . This distribution over heights was considered in Theorem B.3. 24

′

Define α = αh−w = E[ρ2h ], where h′ is sampled from the random height distribution Dh−w of adjacent subtrees at depth h−w. By Theorem B.3, we know that α → α∗ as defined there as h−w → ∞. Throughout the following results, we similarly define dw X Zi := (Yi )ℓ ℓ=1

for the sum of the leaves in the ith generated subtree of size dw .

D.1

Equivalent Markov Chains

For our computations, we will use the following equivalent description of the AR process from the ith subtree leaves Yi to the i + jth subtree leaves Yi+j . Because Yi is marginally a sample from the normal broadcast process, we can equivalently sample this process via the following Markov chain: ′ ′ Yi → Xi → Xi+1 → Yi+1 → Xi+1 → Xi+2 → Yi+2 → . . . → Yi+j−1 → Xi+j−1 → Xi+j → Yi+j , (6)

where Xℓ is the root of the ℓth subtree; note that the actual AR process is only the restriction to the Yℓ part. ′ for ℓ ≥ 1, we sample the posterior of the root of the corresponding To sample Xi as well as each Xi+ℓ subtree given the leaves in the previous step of the Markov chain (i.e. Yi and Yi+ℓ , respectively). The ′ → Xi+ℓ+1 for j ≥ 1 is obtained by sampling the height hi+ℓ of transition Xi → Xi+1 as well as each Xi+ℓ the LCA of the subtrees and then rerandomizing the spin except with probability ρ2hi+ℓ . Taken on average ′ X over hi+ℓ ∼ Dh−w , this means that the probability of not rerandomizing is precisely E[Xi+ℓ i+ℓ+1 ] = α, ∗ 2 which we know converges to α as h − w → ∞ by Theorem B.3.

D.2

Preliminary Calculations

In the remaining computations, we will leverage the following highly convenient fact: for a pair of random variables (X1 , X2 ) ∈ {±1}2 that are marginally uniform, if E[X1 X2 ] = γ ≥ 0, then one can equivalently sample them by sampling X1 uniformly and then setting X2 = X1 with probability γ and otherwise setting X2 to be a uniform bit. We will refer to this latter event, which occurs with 1 − γ probability, as rerandomizing. Next, we will calculate the correlations of the root values of the generated subtrees in the autoregressive process as expressed in the equivalent Markov chain given in (6). Lemma D.1. Fix any i ≥ 1 and let j ≥ 1. Then for the Markov chain given in (6), E[Xi Xi+j ] = α(αqw )j−1 . Proof. If j = 1, then by the Markov representation in (6), we have: Yi → Xi → Xi+1 → Yi+1 2

Note that the difference in the first step of this Markov chain comes from the fact that conditioned on hi , the marginal on (Yi , Yi+1 ) is the same as an honest sample from the broadcast process from a root that connects to the root of each subtree at distance hi in each branch; in other words, we need not sample Xi′ since conditioned on Yi , it has the same law as Xi itself so we may rewrite in this way.

is a Markov chain, and in particular, the probability that there is no rerandomization from Xi → Xi+1 is α. Since these bits are marginally uniform, this means E[Xi Xi+1 ] = α. For j > 1, observe that we can consider the restriction in (6) to the Markov chain on subtree root spins in {±1} given by Xi → Xi+1 → Xi+2 → . . . → Xi+j . Since these spins are binary and marginally uniform, Theorem B.1 implies that E[Xi Xi+j ] =

j Y

αk ,

k=1

where αk = E[Xi+k−1 Xi+k ]. Therefore, it suffices for us to compute αk for k ≥ 2 since we already know α1 = α. To do this, observe that we again have the restriction to a Markov chain on {±1} with uniform marginals: ′ Xi+k−1 → Xi+k−1 → Xi+k ,

where by the above discussion, ′ Xi+k ] = E[ρ2hi+k−1 ] = α E[Xi+k−1

since this comes only from the sampling of the random height hi+k and then rerandomizing except with probability ρ2hi+k between the roots of these adjacent subtrees. By Theorem B.1, it therefore suffices to compute ′ E[Xi+k−1 Xi+k−1 ] ′ . To from the AR process, which we can write as the induced Markov chain Xi+k−1 → Yi+k−1 → Xi+k−1 ′ do this, observe that conditional on Yi+k−1 , Xi+k−1 and Xi+k−1 are independent posterior samples of the subtree root value X given these leaves, and so ′ ′ |Yi+k−1 ]] ] = E[E[Xi+k−1 Xi+k−1 E[Xi+k−1 Xi+k−1

= E[E[Xi+k−1 |Yi+k−1 ]2 ] = qw . Putting these two steps together, Theorem B.1 therefore implies that for k > 1, αk = E[Xi+k−1 Xi+k ] = α · qw , which completes the proof. We now use this explicit expression for the correlations of root spins in the AR process to calculate the correlations of subtree sums by leveraging conditional independencies once we condition on these spins: Lemma D.2. In the autoregressive broadcast process, for any i, j ≥ 1, it holds that E[Yi Yi+j ] = Md,ρ,w (1)2 · α · (α · qw )j−1 . 26

Proof. We have that Zi → Xi → Xi+j → Zi+j is a Markov chain. Since E[Xi Xi+j ] = α · (α · qw )j−1 by Theorem D.1, the probability that the transition Xi → Xi+j does not rerandomize is precisely α · (α · qw )j−1 ; moreover, note that this event is independent of the actual value of Xi by symmetry and therefore also Zi since the process is a Markov chain. If E is the event that this rerandomization event occurs, then by the tower law E[Zi Zi+j |E] = E[Zi E[Zi+j |E, Yi ]|E] = 0 since the subtree root Xi+j is then a uniform root bit conditioned on Yi and E. On the other hand, when E does not occur, we know that Xi = Xi+j . Then E[Zi Zj |E c ] = E[Zi Zj |Xi = Xj ] = Xi2 (Md,ρ,w (1))2 = (Md,ρ,w (1))2 , since in this case, the Markov property implies Yi , Yi+j are conditionally independent samples from the broadcast process but with common root value Xi . The claim then follows by the law of total probability as E[Zi Zi+j ] = Pr(E) · 0 + Pr(E c ) · (Md,ρ (1))2 = Md,ρ (1)2 · α · (α · qw )j−1 .

We now compute the higher cross-moments that will be needed for calculating the fourth moment of the autoregressive process. The first bound is trivial: Lemma D.3. In the AR process, for any i, it holds that E[Zi2 ] = Md,w,ρ (2) E[Zi4 ] = Md,w,ρ (4) Proof. This is trivial since Yi has the same distribution as the usual broadcast process of depth w. Lemma D.4. In the AR process, for any i < j < k, it holds that E[Zi2 Zj Zk ] = α · (αqw )k−j−1 Md,ρ,w (2) · Md,ρ,w (1)2 . Similarly, it holds that E[Zi Zj Zk2 ] = α · (αqw )k−j−1 Md,ρ,w (2) · Md,ρ,w (1)2 Proof. We claim that conditioned on Zi2 , (Yj , Yk ) has the same law as in the AR process without any further conditioning. Indeed, note that conditioning on Yi2 does not change the distribution of the root Xi by symmetry since the square makes the sum independent of the root value. This implies that the rest of the Markov chain has identical conditional distribution to the original Markov chain. Therefore, E[Zi2 Zj Zk ] = E[Zi2 ]E[Zj Zk ], and so, we may conclude by Theorem D.2 and the fact that Yi itself is simply a sample from the broadcast process with depth w. An analogous argument holds for the second expectation since similarly, the distribution of Zk2 is independent of (Yi , Yj ) by symmetry after squaring. 27

Lemma D.5. In the AR process, for any i < j < k < ℓ, it holds that E[Zi Zj Zk Zℓ ] = α2 · (αqw )(ℓ−k)+(j−i)−2 · Md,ρ,w (1)4 . Proof. Note that the restriction of the AR process Yi → Yj → Xj′ → Yk → Yℓ . remains a Markov chain. To compute the expectation, we first condition on Xj′ to obtain E[E[Zi Zj |Xj′ ]E[Zk Zℓ |Xj′ ]], where we use the Markov property to decompose the conditionally independent parts as the subtree sums are functions of the corresponding leaves. However, observe that by symmetry, both expectations are independent of the value of Xj′ since as in the proof of Theorem D.2, the expectation is zero except on the event that there is no rerandomization. This is independent of the spin Xj′ by symmetry. In particular, we find that E[Zi Zj Zk Zℓ ] = E[Zi Zj ]E[Zk Zℓ ], and we conclude by Theorem D.2. Lemma D.6. In the AR process, for any i < j < k, it holds that 0 ≤ E[Zi Zj2 Zk ] ≤ α2 · (αqw )(k−j)+(j−i)−2 · Md,ρ,w (1)2 · Md,ρ,w (2). Proof. We again have a Markov chain Yi → Xi → Xj → Yj → Xj′ → Xk → Yk . We claim that conditional on Yj , the probability there is no rerandomization between Xi and Xk is α2 · (αqw )(k−j)+(j−i)−2 · E[Xj |Yj ]2 . Indeed, the conditional probability that there is no randomization between Xi → Xj and from Xj′ → Xk is precisely α2 · (αqw )(k−j)+(j−i)−2 by Theorem D.1 since these events are independent of the actual value of Yj by the Markov property and spin symmetry. Moreover, the probability that there is no randomization between Xj and Xj′ given Yj is E[Xj |Yj ]2 by the argument of Theorem D.1. If we let E denote the event that there is rerandomization between Xi and Xk , then similar computations to before imply E[Zi Zj2 Zk ] = E[E[Zi Zj2 Zk |Yj ]] = E[Zj2 E[Zi Zk |Yj ]] = Md,ρ,w (1)2 · E[Zj2 Pr(E c |Zj )] = α2 · (αqw )(k−j)+(j−i)−2 · Md,ρ,w (1)2 · E[Zj2 E[Xj |Yj ]2 ] ≤ α2 · (αqw )(k−j)+(j−i)−2 · Md,ρ,w (1)2 · Md,ρ,w (2). In the last step, we use the trivial fact that Xj ∈ {−1, 1} to pull out the factor. Note that this computation implies that the expectation is nonnegative since it admits a square representation. 28

Lemma D.7. In the AR process, for any i < j, it holds that E[Zi2 Zj2 ] = Md,w,ρ (2)2 . Proof. We again have a Markov chain Yi → Xi → Xj → Yj . Conditioned on (Xi , Xj ), Yi and Yj are conditionally independent, and moreover, the law of (Zi2 , Zj2 ) is independent of (Xi , Xj ) by symmetry since the subtree sums get squared and thus do not depend on the root values. The claim follows. Lemma D.8. In the AR process, for any i < j, it holds that E[Zi3 Zj ] = E[Zi Zj3 ] = α · (α · qw )j−i−1 · Md,ρ,w (3) · Md,ρ,w (1). Proof. We again have a Markov chain Yi → Xi → Xj → Yj . By similar reasoning to Theorem D.2, let E denote the event that there is a rerandomization from Xi → Xj . By Theorem D.1, the complementary event E c has probability α · (α · qw )j−i−1 even conditioned on Xi . We again know that the conditional expectation of Zj given E occurs and given Yi is zero, and moreover, E[Zi3 Zj |E c , Xi ] = Xi2 · Md,ρ,w (3) · Md,ρ,w (1) = Md,ρ,w (3) · Md,ρ,w (1), since on this event, the roots are identical and then one can apply conditional independence conditioned on having the same root. The claim again follows.

D.3

Variance and Fourth Moments

At this point, we can use the cross-correlations computed in the previous section to compute the variance of the sum in the autoregressive process: Proposition D.9. Let XL be sampled from the (d, h)-Ising autoregressive broadcast process with fixed correlation ρ satisfying dρ2 > 1 with w → ∞ and h − w → ∞. Then     h−w dh dX X 2α∗ Var  (XL )i  = Var  Zi  = dh−w Md,w (2) + (1 − o(1)) · · (dρ)2w · dh−w 1 − α∗ q ∗ i=1

i=1

= (1 − o(1)) · Ad,ρ (2) · (dρ)2w · dh−w where

Ad,ρ (2) :=

Cd,ρ (2) +

Proof. We can directly compute:   h−w h−w h−w dX dX dX   Var Zi = E[Zi Zj ] = E[Zi2 ] + 2 i=1

i,j=1

i=1

2α∗ 1 − α∗ q ∗

X 1≤i<j≤dh−w

E[Zi Zj ]

h−w

Md,w (2) + 2(dρ)

·α

dh−w X−1

(dh−w − ℓ)(α · qw )ℓ

ℓ=0

In the third equality, we sum over distances between pairs and use Theorem D.2. To obtain the final asymptotics, note that since we are above the Kesten-Stigum bound (dρ2 > 1), Theorem B.4 implies that qw → q ∗ ∈ (0, 1] as w → ∞ and we further have α → α∗ ∈ (0, 1) since h − w → ∞ by Theorem B.3. We can therefore apply dominated convergence and standard geometric identities/bounds to deduce 2w

2(dρ)

·α

dh−w X−1

(dh−w − ℓ)(α · qw )ℓ = (1 − o(1)) ·

ℓ=0

2α∗ · (dρ)2w · dh−w . 1 − α∗ q ∗

Theorem C.1 shows that as w → ∞, since dρ2 > 1, Md,w (2) = (1 − o(1)) · Cd,ρ (2) · (dρ)2w , so we obtain the stated claim. We thus obtain Theorem 3.1: Theorem D.10 (Theorem 3.1, restated). Consider the Ising broadcast process on Td,h with dρ2 > 1. For a h given context depth 0 ≤ w ≤ h, let XL ∈ {±1}d denote a sample from the autoregressive process on the leaves with context length dw . Then if w → ∞ and h − w → ∞, the (log-) normalized variance satisfies:    dh X 1  log  h Var  (XL )i  = w log(dρ2 ) + log(Ad,ρ (2)) + o(1). (7) d i=1 h

By contrast, when XL ∈ {±1}d is a sample from the true Ising broadcast process (i.e. w = h),    h d X 1  log  h Var  (XL )i  = h log(dρ2 ) + log(Cd,ρ (2)) + o(1). d i=1

Proof. The first identity for the autoregressive process is obtained by taking the logarithm in Theorem D.9. The second identity for the true language was already obtained in Theorem C.1. We can now compute the fourth moment, which will imply Theorem 3.2: Proposition D.11. Let XL be sampled from the (d, h)-Ising autoregressive broadcast process with fixed correlation ρ satisfying dρ2 > 1 and context depth w ≤ h. Then if h − w, w → ∞,  4  h−w dX   E  Zi   = (1 − o(1)) · Ad,ρ (4) · d2(h−w) · (dρ)4w , i=1

where

2α∗ Ad,ρ (4) = 3 · Cd,ρ (2) + 1 − α∗ q ∗

= 3 · Ad,ρ (2)2 .

Proof. We expand by the indices in order by counting the types of terms:  4  h−w dX X   E  Zi   = dh−w · E[Z14 ] + 6E[Zi2 Zj2 ] + 4E[Zi3 Zj ] + 4E[Zj3 Zi ] i=1

1≤i<j≤dh−w

+ 12

E[Zi2 Zj Zk ] + E[Zi Zj2 Zk ] + E[Zi Zj Zk2 ]

1≤i<j<k≤dh−w

+ 24

E[Zi Zj Zk Zℓ ]

1≤i<j<k<ℓ≤dh−w

= dh−w · Md,w (4) +

6Md,w (2)2 + 8Md,w (3) · Md,w (1) · α(α · qw )j−i−1

1≤i<j≤dh−w

+ 12(Md,w (2))(Md,w (1))2 · α

(α · qw )k−j−1 + (α · qw )j−i−1

1≤i<j<k≤dh−w

+ 12

E[Zi Zj2 Zk ]

1≤i<j<k≤dh−w

+ 24(Md,w (1))4 α2

(α · qw )(ℓ−k)+(j−i)−2 .

1≤i<j<k<ℓ≤dh−w

Here, we applied Theorem D.3, Theorem D.8, Theorem D.4, and Theorem D.5 to express all terms exactly in terms of α, qw except for the Zi Zj2 Zk terms. We will momentarily show that this extra term is of asymptotically of lower order. For any sequence βw → β < 1 as s → ∞, we have the following identities:

j−i−1 βw = (1 − o(1)) ·

1≤i<j≤dh−w

1 · dh−w 1−β

1 · d2(h−w) 1 − β 1≤i<j<k≤dh−w 2 X 1 1 (ℓ−k−1)+(j−i−1) βw = (1 − o(1)) · · · d2(h−w) . 2 1 − β h−w X

k−j−1 βw + β j−i−1 = (1 − o(1)) ·

1≤i<j<k<ℓ≤d

These first approximate identity is easy to see directly by counting the number of possibilities for j − i = s for each s and using dominated convergence, while the other two are from Theorem H.2 and Theorem H.3. Recalling that for a = 2, 3, 4 and w → ∞, we have Md,ρ,w (a) = (1 − o(1)) · Cd,ρ (a) · (dρ)aw by Theorem C.1, Theorem C.2, and Theorem C.3, the dominant order terms are those of order d2(h−w) · (dρ)4w . Plugging in the above identities with βw = αw qw → α∗ q ∗ < 1 and keeping just these highest-order terms, we deduce that  4  h−w 2 ! dX ∗ ∗ α α   E  Yi   = (1 − o(1)) · 3Cd,ρ (2)2 + 12Cd,ρ (2) · + 12 · d2(h−w) · (dρ)4w 1 − α∗ q ∗ 1 − α∗ q ∗ i=1

= (1 − o(1)) · 3 · Ad,ρ (2)2 · d2(h−w) · (dρ)4w , 31

as claimed. It remains to confirm that the final term indeed satisfies X E[Zi Zj2 Zk ] = O dh−w · (dρ)4w 1≤i<j<k≤dh−w

so that it is indeed asymptotically negligible as w, h − w → ∞. To do this, Theorem D.6 provides the bounds 0 ≤ E[Zi Zj2 Zk ] ≤ α2 · (αqw )(k−j)+(j−i)−2 · Md,ρ,w (1)2 · Md,ρ,w (2). Since qw → q ∗ > 0 as we are above the Kesten-Stigum bound by Theorem B.4 and also 0 < α∗ q ∗ < 1, Theorem H.1 shows that the sum over all tuples 1 ≤ i < j < k ≤ dh−w is O(dh−w ) · Md,ρ,w (1)2 · Md,ρ,w (2) = O(dh−w ·(dρ)4w ) as w, h−w → ∞, confirming this term is indeed lower-order as claimed. We immediately deduce Theorem 3.2: Theorem D.12 (Theorem 3.2, restate). Consider the Ising broadcast process on Td,h with dρ2 > 1. For a h given context depth 0 ≤ w ≤ h, let XL ∈ {±1}d denote a sample from the autoregressive process on the P leaves with context length dw . Then if w → ∞ and h − w → ∞, the excess kurtosis of i (XL )i satisfies: 4 Pdh   E dh i=1 (XL )i X   Kurt (XL )i − 3 := 2 2 − 3 = o(1) . Pdh i=1 E i=1 (XL )i Proof. Simply combine the second moment of the autoregressive process in Theorem D.9 and the fourth moment in Theorem D.11.

Inconsistent Colorings Above Freezing

We now turn to establishing that an autoregressive broadcast process for the coloring process will fail to produce a consistent coloring of the full d-ary tree. By this, we mean that with high probability over the sampling of the autoregressive process, there is no proper coloring of the entire tree Td,h that can be extended from the color of the sampled leaves. In fact, we will show that this holds even just to go up a single level of the tree. To prove this, we require the following simple observation on the posterior distribution of a child of the root given any prior distribution on any other child: Lemma E.1. Consider the coloring broadcast process with q colors on Td,h . Let X∅ denote the color of the root of the tree and let X1 , . . . , Xd denote the colors of the children. Then given any distribution ν on the first child X1 , the posterior distribution on X2 is lower bounded by (q − 2)/(q − 1)2 for all colors. Proof. It suffices to show that the claim is true conditioned on any value of X1 . Given the color of X1 ∈ [q], the posterior distribution on X∅ is simply uniform on [q] \ {X1 }. Conditioned on any of these valid colors, the posterior distribution on X2 simply becomes uniform on [q] \ {X∅ }. It is easy then to see that for any i ∈ [q], and initial choice of X1 , there are q − 2 choices of X∅ such the posterior probability Xi = i is 1/(q − 1). Since each of these q − 2 choices for X∅ has probability at least 1/(q − 1) given X1 , the claim follows. 32

We can now put this simple observation with the onset of freezing: Theorem E.2 (Theorem 3.3, restated). Consider the autoregressive coloring broadcast process with q colors on Td,h with any context depth w < h such that d > q(log(q)+log log(q)+1+oq (1)). Then with probability 1 − oq (1), the sampling of the leaves in the autoregressive coloring process is inconsistent with any proper coloring of Td,h . Proof. Consider an internal vertex v at depth h − w − 1 ≥ 0. We will show that in the autoregressive coloring process for this range of parameters, it holds with 1 − oq (1) probability over the sampling of the d subtrees of size dw that there is no valid color for vertex v. Label the children of v by 1, . . . , d at level h − w. In the autoregressive sampling, we sample the subtree of i + 1 of size dw given the colors of the subtree of i. It is clear that marginally, the subtree of vertex 1 is a sample from the true coloring broadcast process of the d-ary tree at depth w, which can be obtained by sampling the color X1 uniformly and then running the broadcast process for this root value. We will consider the following equivalent description of the sampling process: to sample the (i + 1)th subtree given the value of the leaves of the ith subtree, we obtain the posterior distribution on Xi , which implies the posterior on Xi+1 , which is then broadcast to the leaves in the coloring process. By Theorem B.5, it follows that in this sampling process that X1 is frozen to a uniformly random color i1 ∈ [q] given the colors of its leaves with probability at least 1 − 1/ log(q). More generally, using Theorem B.5 again and symmetry, the posterior of each Xi given the leaves of the ith subtree is again frozen to the actual value Xi given the colors of the leaves with probability at least 1 − 1/ log(q), and by Theorem E.1, it further holds that each color Xi has probability at least (q − 2)/(q − 1)2 of being any i ∈ [q] for any conditioning of the previous subtree (which has an induced posterior ν on Xi−1 ). We now claim that with 1 − oq (1) probability, this implies that there is no valid color for vertex v that can be consistent with the colors of the d sampled subtrees of this process. Indeed, this event is implied by the event that for each color i ∈ [q], there exists some Xj in this process that is frozen to color i ∈ [q] by the corresponding leaves of the subtree. By a standard coupon collector argument, Pr ∃i ∈ [q] : i valid for v given leaves q−2 d ≤ q 1 − (1 − 1/ log(q)) (q − 1)2 d(1 − 1/ log(q)) 2 ≤ q exp −(1 − O(1/q )) · q ≤ q exp −(1 − O(1/q 2 )) · (log(q) + log log(q) + 1 + oq (1))(1 − 1/ log(q)) ≤ q exp(−(1 − O(1/q 2 ))(log(q) + log log(q) − oq (1))) =

1 + oq (1) , log(q)

as claimed. Remark E.1. It appears unlikely that one can go below the freezing threshold and still obtain the same inconsistent colorings. The reason is simply because this bound is tight for freezing, and as soon as one is below it, the probability of freezing decays doubly exponentially in the height of the tree. This can be most easily seen when d = q − 1, in which case the probability a parent at depth h − 1 is frozen is on the order 33

of e−q . Following the recursion, this causes the probability of a node at depth h − w being inconsistent with the leaves to be exp(−Θ(q w )), so it is actually doubly exponentially small in the depth. This can only be offset by the number of vertices for very small context depths w to obtain an internal node that has no valid colors.

Exponential Advantage of Reasoning

In this section, we give a proof of Theorem 3.4. We design an even simpler model where p(· | −) conditions only on the current memory state. Set M = (Σh−w ∪ {∅}) × [d]h−w . The Σh−w ∪ {∅} component encodes the values along the path from the root of the entire tree to the root of the current subtree, and the [d]h−w component encodes the index of the next subtree. We start with an initial memory state (∅, (1, · · · , 1)). Let M = (P, r) be the current memory state, and we describe a procedure that samples the next leaves Y ′ and the next memory state M ′ = (P ′ , r′ ). The idea is to mimic the depth-first search of the tree defining the (d, h, κ)-language. 1. We first sample, if not already observed, the values along the path defined by r in the current (d, h, κ)broadcast process. • If r = (1, · · · , 1), then we recursively sample through the broadcast channel κ X∅ , X(1) , X(1,1) , · · · , Xr . That is, X∅ is sampled from the stationary distribution of κ, and Xr[1:ℓ+1] is sampled from κ(Xr[1:ℓ] , ·) for each ℓ = 0, 1, · · · , h − w − 1. • Otherwise, let j be the largest integer such that rj > 1. By the induction hypothesis which will be ensured later, the jth component of P equals the already observed Xr[1:j−1] (X∅ if j = 1). Starting from this, we recursively sample through the broadcast channel κ Xr[1:j] , Xr[1:j+1] , · · · , Xr . 2. Now we have access to the values X∅ , · · · , Xr . We sample a (d, w, κ, δXr )-language and set Y ′ to be the sampled leaves. This is the broadcast process on Td,w where the root has a fixed value Xr . Then we set P ′ = (X∅ , · · · , Xr[1:h−w−1] ) . 3. Let k be the largest integer such that rk < d. We set r′ = (r1 , · · · , rk + 1, 1, · · · , 1) . If such an integer does not exist, the sampling has finished and we reset to r′ = (1, · · · , 1). As noted before, this can be understood as the depth-first sampling of a broadcast process and thus samples the correct language by construction.

Experiment Details

G.1

Tokenization

We elaborate on a tokenization procedure of our synthetic language based on the broadcast model on d-ary trees, as described in Theorem 2.1. The first step is to tokenize the states in Σ. Since the two broadcast processes we consider have discrete state spaces, we can simply use them as tokens. In addition, we insert “punctuation” tokens to encode the information of the least common ancestor of the two adjacent nodes. In other words, we use the token set T = Σ ⊔ P where P = {p1 , p2 , · · · , ph−1 } is the set of punctuation tokens. Before we mathematically define the tokenization procedure, we refer the reader to Figure 3 for a quick illustration on how we tokenize an Ising broadcast model. The tokenization of Td,h with leaves Xr for r ∈ [d]h is a sequence τ1 , τ2 , · · · , τL of length L = dh−1 (d + 1) − 1. The mth token τm is determined by the following. We write m = r0 + (d + 1)

h−1 X (ri − 1)di−1 i=1

where ri ∈ [d] for 1 ≤ i ≤ h − 1 and 0 ≤ r0 ≤ d. Note that there is a unique such expansion. Now τm is given by:  X (rh−1 ,··· ,r0 ) if r0 ≥ 1, τm = pζ(m) if r0 = 0 where ζ(m) = max{i ∈ Z+ : rj = 1 for all 1 ≤ j < i} .

G.2

Training Without Reasoning

We describe a procedure of preparing a training set to train a simple autoregressive model. Namely, given the context length k, we explain how the pair of an input sequence x and an output sequence y is sampled. The model is trained using the usual cross entropy loss. For efficient training, we add an additional “context refresh” token ∅ to the token set T̃ = T ∪ {∅}. This can also be understood as the “beginning of sequence” token. Now we sample x, y ∈ T̃ k with the following algorithm. (1)

(1)

(2)

1. Sample an infinite sequence of independent broadcast processes: Td,h with leaves Xr , Td,h with (2)

leaves Xr , and so on. 2. Tokenize the processes which gives the sequences (1)

(1)

(2)

(τ1 , · · · , τL ), (τ1 , · · · , τL ), · · · . 3. Join them with the context refresh token, giving an infinite sequence (1)

(1)

(2)

(3)

(τ̃1 , τ̃2 , · · · ) = (τ1 , · · · , τL , ∅, τ1 , · · · , τL , ∅, τ1 , · · · ) . 35

4. Sample a random index ι ∼ Uniform({1, · · · , L + 1}) and obtain a consecutive subsequence τ̃ι , τ̃ι+1 , · · · , τ̃ι+k . (1)

In particular, τ̃ι = τι

if ι ≤ L and τ̃ι = ∅ otherwise.

5. Now set x = (τ̃ι , · · · , τ̃ι+k−1 ) ,

y = (τ̃ι+1 , · · · , τ̃ι+k ) .

For each backpropagation, a fresh pair of (x, y) is sampled from this procedure. This resembles the way the pre-training of large language models is usually done on large corpuses. In practice, the sequence (τ̃1 , · · · , ) and the index ι are not randomly sampled for each training step, but often ι is just taken sequentially from a fixed sequence. In our experiments, however, the differences between the two approaches were insignificant. The inference (sampling) step of the trained model is straightforward: we “prompt” the model with the context refresh token ∅, sample the next token conditioned on the previous k tokens, repeating L times.

G.3

Training With Reasoning

As briefly noted in Section 4, the reasoning models are trained by inserting the “memory tokens” inbetween value tokens in the training set. Before we elaborate on this, it is helpful to describe the inference step, i.e., design a model “wrapper” that hides the memory tokens and outputs the value tokens in T . We first choose positive integers ℓv and ℓm such that 2ℓm + ℓv − 1 is at most the context size k. We want the model to retain a memory of size ℓm and output a sequence of ℓv value tokens (including punctuation tokens) each step. To be specific, we want the model to perform the following sampling step: given its current memory state represented by ℓm memory tokens, output ℓv value tokens and ℓm memory tokens representing the next memory state. This is why we require 2ℓm + ℓv ≤ k + 1. We repeat this until the model has outputted L tokens. Markov chain of memory states. The proof of Theorem 3.4 in Section F describes a way to design the memory state using the path from the root to the current position. The conditional distribution function constructed in the proof can be understood as the transition kernel of a Markov chain of memory states, where each transition from one state to another outputs a subtree of height w. Our first step is to build a similar Markov chain so that it outputs a token one at a time. This requires a bit of extension since the model must be able to output a punctuation token. We set the memory states as the alternating sequences of values and indices of the form σ1 , r1 , σ2 , r2 , · · · , σh−h0 , rh−h0 (8) where σi ∈ Σ, ri ∈ [d], and 0 ≤ h0 ≤ h. This in particular means that the model has sampled (X∅ , Xr1 , X(r1 ,r2 ) , · · · , X(r1 ,··· ,rh−h0 −1 ) ) = (σ1 , · · · , σh−h0 ) . The state transition is defined as follows, depending on the value of h0 . • The case h0 = 0 is further divided into the following two.

– If rh < d, then the model samples and outputs X(r1 ,··· ,rh +1) from X(r1 ,··· ,rh−1 ) = σh through the broadcast channel κ. The next state is a sequence σ1 , r1 , σ2 , r2 , · · · , σh , rh + 1 of the same length 2h. – If rh = d, then the model computes the largest index j < h such that rj < d. If no such j exists (i.e., ri = d for all i), then the model outputs a context refresh token ∅ and jumps to the state ∅. Otherwise, the model outputs a punctuation token ph−j and jumps to the state σ1 , r1 , · · · , σj , rj which is a sequence of length 2j. • If 0 < h0 < h, our construction guarantees rh−h0 < d. The model recursively samples X(r1 ,··· ,rh−h0 +1) , X(r1 ,··· ,rh−h0 +1,1) , · · · , X(r1 ,··· ,rh−h0 +1,1,··· ,1) from X(r1 ,··· ,rh−h0 −1 ) = σh−h0 through κ, where the subscript of the last element has h0 ones. The model outputs X(r1 ,··· ,rh−h0 +1,1,··· ,1) and jumps to the state σ1 , r1 , · · · , σh−h0 , rh−h0 + 1, X(r1 ,··· ,rh−h0 +1) , 1, · · · , X(r1 ,··· ,rh−h0 +1,1,··· ,1) , 1 where the subscript of the penultimate element has h0 − 1 ones. • The case h0 = h corresponds to the initial and final state ∅. The model samples X∅ , X1 , X(1,1) , · · · , X(1,··· ,1) from a fresh tree, outputs the last value whose subscript has h ones, and jump to the state X∅ , 1, · · · , X(1,··· ,1) , 1 where the subscript of the penultimate element has h − 1 ones. Similar to the the argument in Section F, dh−1 (d + 1) − 1 state transitions starting from the initial memory state ∅ outputs the correct language distribution, including the punctuation marks. Tokenization of the memory states. token set

Tokenizing the memory states (8) is straightforward. We use the Tm = Σ ⊔ [d] ⊔ {∅} ⊔ {s, e}

where ∅ is the optional “padding” token, which allows us to tokenize the memory states in a fixed length 2h as σ1 , r1 , · · · , σh−h0 , rh−h0 , ∅, ∅, · · · , ∅, ∅ using 2(h − h0 ) padding tokens. To prevent the model from confusing the memory state tokens with the output tokens, one might also choose to use different set of tokens for Σ and ∅. As discussed in Section 4, we also enclose the memory tokens with the additional “memory start token” s and “memory end token” e. Recall that we want the model to generate ℓm memory tokens every ℓv output value tokens. Following the above tokenization of the memory states, we need ℓm = 2 + 2h tokens. As a consequence, we require that 1 ≤ ℓv ≤ k − 2h − 1. 37

Constructing training sequences. If the values of all of the nodes (including the internal nodes) of a tree Td,h are given, then the Markov chain described in the previous paragraph becomes deterministic. In other words, it gives a unique sequence of memory states ∅ = M0 , M1 , · · · , ML , ML+1 = ∅ . Now each training sequence is generated from the following procedure. (1)

(2)

1. Sample an infinite sequence of independent broadcast processes Td,h , Td,h and the corresponding (i)

sequences of memory states: for each Td,h we write (i)

(i)

∅ = M0 , M1 , · · · , ML+1 = ∅ for its sequence of memory states. 2. Following the same process in Section G.2 we obtain the sequence (1)

(1)

(2)

(3)

(τ̃1 , τ̃2 , · · · ) = (τ1 , · · · , τL , ∅, τ1 , · · · , τL , ∅, τ1 , · · · ) . 3. Sample a random index ι ∼ Uniform({1, · · · , L + 1}) and consider the infinite sequence τ̃ι , τ̃ι+1 , · · · . 4. We insert ℓm = 2 + 2h tokens right before each of the tokens τ̃ι , τ̃ι+ℓv , τ̃ι+2ℓv , · · · . The memory tokens to insert before τ̃s are determined by the following. If s − 1 = (L + 1)i + j for integers i and (i+1) 0 ≤ j ≤ L, we insert the tokenization of Mj . 5. Take the first k + 1 tokens from the new token sequence. Set x and y to be the first k and the last k tokens from the chosen subsequence. Note that x is an alternating sequence of ℓm memory tokens and ℓv output value tokens. Thus, the model learns to predict the next tokens given the first ℓm memory tokens, and to maintain its memory state every ℓv outputs.

G.4

Computing Resources and Reproducibility

Model hyperparameters. Our base model nanochat, in its default configuration, automatically chooses its own model hyperparameters given the desired number of transformer layers and the context size. We use 10 transformer layers for all of our experiments which is slightly larger than our maximum tree height 8. The weights of a model occupy less than 200 megabytes of disk storage. Training iterations. We configure to train 215 = 32768 tokens in one mini-batch and 219 = 524288 tokens in one iteration. For instance, if the context size is 210 = 1024, then 25 = 32 training sequences (x, y) are processed in one optimizer step and one training iteration always consists of 24 = 16 optimizer steps. We run 3,000 to 10,000 training iterations depending on the model we train.

Optimizer. The optimizer we use is a combination of a modified Adam by Jordan et al. (2024a) and Muon by Jordan et al. (2024b). This is taken from the optimizer of the original nanochat by Karpathy (2025) without modification. Computation. We note that nanochat is powerful but lightweight enough to reach a GPT-2 grade capability for natural language in around 2 hours training on 8xH100 GPU node. Due to the simplicity of our synthetic language, all of the pre-training runs in our experiments take a few hours even with 2 A100 GPUs, which makes them easily reproducible. Approximately, 1,000 training iterations take about 1 hour of 2 A100 GPUs. Context size for “Simulated” data points. We note that for the “Simulated” data points in Figures 1 and 2, the context size is defined to be dw−1 (d + 1), instead of dw , because we properly take the punctuation marks into account. Estimating variance and kurtosis. Given the i.i.d. samples, these are computed using the standard sample variance and sample excess kurtosis formulae commonly available in scientific computing packages (see, e.g., Zwillinger and Kokoska (1999)).

Auxiliary Results

Lemma H.1. Let αn ∈ [0, 1) be a sequence that converges to some α∗ < 1. Then X

αnk−i = (1 − o(1))

1≤i<j<k≤n

α∗ 1 − α∗

2 · n.

Proof. Let s := k − i and note that s ranges from 2 to n − 2 under our index convention. For convenience, we will write α instead of αn below. Then by an elementary counting argument, X

n−2 X

αk−i =

(n − s)(s − 1)αs ,

s=2

1≤i<j<k≤n

since there are (n − s) valid i < k pairs with this difference, and for each such pair, there are exactly s − 1 valid indices j for any such pair. We deduce that X

1≤i<j<k≤n

k−i

n−2 X

α (s − 1) −

s=2

n−2 X

s(s − 1)αs .

s=2

By the dominated convergence theorem (to be precise, αn < α′ < 1 for all sufficiently large n by the convergence assumption and the geometric series is bounded), the first sum converges with lim

n→∞

n−2 X s=2

2 ∞ X α∗ ∗ s α (s − 1) = (s − 1)(α ) = , 1 − α∗ s

s=2

and similarly the second sum converges to a constant by standard bounds on geometric moments. 39

Lemma H.2. Let αn ∈ [0, 1) be a sequence that converges to some α∗ < 1. Then X

αnk−j = (1 − o(1)) ·

1≤i<j<k≤n

α ∗ n2 2(1 − α∗ )

. Proof. We again will write α in place of αn . By a similar combinatorial argument, we may write   n−1 n−1 X X n−s−1 X 1X  αk−j = (n − s)(n − s − 1)αs , i αs = 2 1≤i<j<k≤n

s=1

i=1

since there are (n − s) valid j < k pairs with difference s, and one may take all possible indices i that are at most j for each such pair leading to the inner sum. We can further simplify as n−1

n−1

s=1

1 1X 1X s (n − s)(n − s − 1)α = (1 − s/n)(1 − s/n − 1/n)αs . n2 2 2 We may now take limits as n → ∞. We can again apply dominated convergence using the convergence of αn → α∗ , and so the limit of this sum is precisely ∞

α∗ 1X ∗ s (α ) = , 2 2(1 − α∗ ) s=1

which gives the desired conclusion. Lemma H.3. Let αn ∈ [0, 1) be a sequence that converges to some α∗ < 1. Then 2 X 1 α∗ (ℓ−k)+(j−i) αn = (1 − o(1)) · · · n2 2 1 − α∗ 1≤i<j<k<ℓ≤n

. Proof. We first find a simpler combinatorial way to count the relevant indices. Let r = ℓ − k ≥ 1, s = j − i ≥ 1, and t = k − j ≥ 1. This gives a natural bijection from the indices 1 ≤ i < j < k < ℓ ≤ n to the set of indices 1 ≤ i, s, r, t ≤ n satisfying i + s + r + t ≤ n. Moreover, for any fixed s, r, t satisfying s + r + t ≤ n − 1, there are exactly n − r − s − t valid choices for i that can admit these gaps. In particular, we may write X X α(ℓ−k)+(j−i) = αs+r i,s,t,r:i+s+t+r≤n

1≤i<j<k<ℓ≤n

αs+r (n − s − t − r).

s,t,r:s+t+r≤n−1

If we define u := r + s, then there are u − 1 valid choices of r, s that yield any possible u, and so the sum becomes:   n−u−1 X X X (u − 1)αu (n − u − t) = (u − 1)αu  (n − u − t) u,t:2≤u≤n−2,t+u≤n−1

2≤u≤n−2

t=1

(u − 1)αu

2≤u≤n−2

(n − u)(n − u − 1) . 2

At this point, we can expand in n to find that n−2

(ℓ−k)+(j−i)

n2 X = (u − 1)αu + O(n), 2 u=2

1≤i<j<k<ℓ≤n

where we may use standard geometric bounds for the lower order contributions in n. For this dominant geometric term, we can again apply dominated convergence in the same way as before to find that lim

n→∞

n−2 X

(u − 1)α =

u=2

α∗ 1 − α∗

2 .

Record · ID 180671 · SHA-256 2a210def7b3fe718
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.