Sampling the free uniform spanning forest from IID labels

Source and verification

This article explains family 231 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

A uniform spanning forest is defined by a global limit. Family 231 claims that its free version can nevertheless be sampled from independent vertex labels by one measurable rule that respects every graph isomorphism. The rule is not asserted to inspect only finitely many labels.

🏷️ Preliminaries: free forests and equivariant sampling

A spanning tree of a finite connected graph contains every vertex and has no cycles. Choose such a tree uniformly. On an infinite locally finite connected graph, take finite connected exhaustions without identifying boundary vertices. The weak limit of these tree laws is the free uniform spanning forest (FUSF). Its components need not form one tree.

The wired construction identifies the exterior boundary before taking a limit and can give a different forest. A sampling procedure for the wired forest therefore does not settle the free case.

Attach independent uniform labels $U_v\in [0,1]$ to all vertices. A factor-of-IID rule determines each edge indicator measurably from the labelled graph. Equivariance means that relabelling the graph by an isomorphism relabels the output forest in the same way. A root-free rule cannot choose a distinguished starting vertex as external input.

Measurability permits dependence on infinitely many labels. A finitary factor, whose output at an edge is determined by an almost surely finite neighborhood, is a stronger property.

🏷️ The claimed graphwise sampling theorem

One rule for the free forest

The manuscript claims one Borel, root-independent, equivariant rule $\Phi (G,U,e)\in \{0,1\}$ such that, on every infinite connected locally finite simple unweighted graph,

$$\{e:\Phi (G,U,e)=1\}$$

has the FUSF law. No bounded-degree or amenability assumption is imposed. (OpenAI, 2026)

The paper also applies its sampling method to invariant strongly Rayleigh laws, a class of negatively dependent binary processes, including suitable determinantal processes. Those extensions concern specified translation actions. The present exposition concentrates on the graphwise forest theorem rather than the surrounding group-action theory.

A determinantal law is recognizable from its finite inclusion probabilities: for a kernel $K$, the probability that a finite edge set $A$ is included is $\det K_A$. This is one useful description of forest correlations, but a formula for probabilities is not yet an equivariant sample.

🏷️ A finite response identity

Give a finite spanning tree the weight $\exp ({\sum }_e{h}_e{X}_e)$, where $X_e$ is its edge indicator. Differentiating the normalized finite sum gives

$$\frac{\partial \mathbb{E}{X}_e}{\partial h_f}=\mathrm{Cov}(X_e,X_f).$$

Spanning-tree indicators have nonpositive off-diagonal covariances. Also ${\sum }_f{X}_f=|V|-1$ is deterministic, so the covariance row sums to zero. Writing $p_e=\mathbb{E}{X}_e$, these two facts imply

$$\begin{array}{rl}\sum _f\left|\frac{\partial p_e}{\partial h_f}\right|& =2\mathrm{Var}(X_e)\\ & =2p_e(1-p_e)\le \frac{1}{2}.\end{array}$$

The last bound is independent of graph size and of the external weights. It supplies uniform control of how one edge responds when all log weights change by a bounded amount.

Passing this estimate to infinite-volume conditional laws is a substantive part of the source. A finite identity does not alone construct a compatible drift for all infinitely many coordinates.

🏷️ Gaussian observations and independent innovations

Imagine first sampling the desired forest $X$, then observing every edge through independent Brownian noise:

$$Y_e(t)=t{X}_e+B_e(t).$$

Let $b_e(t,Y)$ be the posterior mean of $X_e$ given the observations. Subtracting its integrated drift gives independent Brownian innovations

$$W_e(t)=Y_e(t)-{\int }_0^t{b}_e(s,Y(s))ds.$$

This is initially a description using an already sampled forest. To turn it into a sampler, the proof must recover $Y$ from $W$. The response bound makes the deterministic integral equation

$$Z_e(t)=w_e(t)+{\int }_0^t{b}_e(s,Z(s))ds$$

uniquely solvable by a measurable iteration. Feeding independent Brownian paths into this decoder reproduces the observation law. Then $Y_e(n)/n\to X_e$ almost surely, since Brownian motion divided by time tends to zero.

The countable Brownian field is not uniformly bounded across all edges. The argument controls bounded differences between iterates rather than assuming the input lies in a bounded-coordinate space.

🏷️ Equivariance and the scope of the construction

Intrinsic edge-centered neighborhoods make the conditional laws and decoder independent of a chosen root. Independent vertex labels provide independent Brownian edge inputs by allocating disjoint random coordinates. The proof must implement this allocation measurably and compatibly with graph isomorphisms.

This construction preserves dependence on a single IID input throughout the infinite-volume passage. Merely taking weak limits of finite equivariant samplers would not suffice: a weak limit of factor laws need not itself be a factor of the same kind. The manuscript claims a Borel factor, not a finite expected coding radius or a practical finite-time sampling algorithm.

🏷️ Key steps and proof outlines

The proof turns a uniform bound on finite covariance rows into an inverse for an infinite observation process. The order of limits, the norm used for inversion, and the allocation of independent edge noise are all essential. The following outlines the arguments in “Weighted trees and a canonical response field,” “A deterministic inverse and a Brownian sampler,” and “One Borel graph rule” (OpenAI, 2026).

Why the response has a negative square

Temporarily orient a finite graph’s edges, delete one incidence row, and denote its remaining edge columns by $a_e$. For conductances $c_e=e^{h_e}$, its reduced Laplacian is $L={\sum }_e{c}_e{a}_e{a}_e^{\mathsf{T}}$. Cauchy–Binet gives

$$\det L=\sum _{T\text{ spanning tree}}\prod _{e\in T}{c}_e.$$

Indeed, an edge set with a cycle has dependent columns; an acyclic set of $|V|-1$ edges is a tree, and successive leaf removal shows its incidence determinant has absolute value one. Differentiating this identity gives $p_e=c_e{a}_e^{\mathsf{T}}{L}^{-1}{a}_e$. Differentiating again, using the derivative of a matrix inverse, gives for $e\ne f$

$$\mathrm{Cov}(X_e,X_f)=-c_e{c}_f(a_e^{\mathsf{T}}{L}^{-1}{a}_f{)}^2.$$

This proves the sign needed in the covariance-row computation above. Integrating that row bound along a segment of external fields proves the $1/2$ Lipschitz estimate at arbitrary positive conductances, including near very uneven weights.

Two spatial limits construct an everywhere-defined drift

The free exhaustion limit itself follows from projections. If $C_H$ is the space spanned by finite cycle flows in a finite subgraph $H$, the tree inclusion kernel, extended by zero, is $Q_H-P_{C_H}$; here $Q_H$ projects onto edges of $H$. Along an exhaustion, $Q_H\to I$ and $P_{C_H}\to P_C$ strongly, where $C$ is the closed span of all finite cycle flows of the infinite graph. The latter convergence follows from

$$\Vert P_{C_m}x-P_{C_n}x{\Vert }^2=\Vert P_{C_m}x{\Vert }^2-\Vert P_{C_n}x{\Vert }^2(m\ge n).$$

The norms increase and are bounded, so the projections are Cauchy. Finite inclusion probabilities are principal determinants of the kernel. Their limits, followed by inclusion–exclusion, give all cylinder probabilities and the exhaustion-independent forest law $\nu$.

For a finite observation set $S$, define

$$b_{e,S}(t,y)=\frac{\int x_e\exp ({\sum }_{f\in S}(y_f-t/2)x_f)d\nu (x)}{\int \exp ({\sum }_{f\in S}(y_f-t/2)x_f)d\nu (x)}.$$

Hold $S$ fixed while taking the free tree limit: numerator and denominator are bounded cylinder functions, the denominator has a strictly positive lower bound for fixed fields, and the finite response estimate passes to their ratio. Only then exhaust observations using the intrinsic edge-centered sets $S_n(e)$ and define $b_e={\mathrm{limsup}}_n{b}_{e,S_n(e)}$. An outer limit need not exist on arbitrary fields. The limsup is Borel, lies in $[0,1]$, and retains the response estimate for every bounded difference $y-y^{\prime }$. This avoids inventing an infinite partition function or using an infinite forest’s nonexistent fixed total edge count.

Innovations are jointly independent Brownian motions

In the reference model $Y_i(t)=t{X}_i+B_i(t)$, the finite observation likelihood is exactly the exponential in the preceding ratio, because $X_i^2=X_i$. The bridge $Y_i(s)-(s/t)Y_i(t)$ contains only Brownian noise and is independent of the endpoints and $X$. Thus endpoints suffice for the posterior. Increasing finite observation sets and bounded martingale convergence identify $b_i(t,Y(t))$ with the full posterior at each fixed time.

Subtract the integrated posterior to obtain $\hat{W}$. Bounded Fubini proves that each increment has conditional mean zero; it does not require one exceptional set valid for every real time. To identify the joint law, take a finitely supported vector $\theta$. On an interval of length $h$, the increment $D={\sum }_i{\theta }_i\Delta {\hat{W}}_i$ is a Gaussian Brownian increment plus a correction bounded by $h{\sum }_i|{\theta }_i|$. Its conditional variance is $h{\sum }_i{\theta }_i^2+O_{\theta }(h^{3/2})$, and its third absolute moment is $O_{\theta }(h^{3/2})$. Taylor expansion yields

$$\left|\mathbb{E}(e^{iD}\mid {\mathcal{H}}_u)-e^{-h{\sum }_i{\theta }_i^2/2}\right|\le C_{\theta }{h}^{3/2}.$$

Subdivide a fixed interval into $N$ pieces. Successive conditioning accumulates error at most $N{C}_{\theta }{h}^{3/2}\to 0$. The limiting conditional characteristic function proves both the Gaussian vector law and independence from the observation past. This is stronger than verifying individual Brownian marginals.

A factorial bound solves the decoder for every input

Start Picard iteration at $Z^0=w$ and integrate the drift to define $Z^{k+1}$. Boundedness gives the initial difference at most $t$; the response estimate with $L=1/2$ then gives inductively

$$\underset{i}{\sup }|Z_i^{k+1}(t)-Z_i^k(t)|\le \frac{L^k{t}^{k+1}}{(k+1)!}.$$

Summing this bound proves uniform convergence of differences over all coordinates on every finite time interval. The input paths themselves may be unbounded across coordinates and need no shared modulus of continuity. The Lipschitz estimate passes the limit through the integrals. Applying the same factorial estimate to any other solution proves uniqueness. Parameter integration and rational-time evaluation prove that each iterate and its limit are Borel; the iteration also preserves causality and relabeling symmetry.

In the reference coupling, $Y$ solves this equation driven by $\hat{W}$, so deterministic uniqueness gives $Y=Z(\hat{W})$. Therefore fresh independent Brownian input has the same complete decoded path law. Gaussian tails and Borel–Cantelli give $B_i(n)/n\to 0$ simultaneously on the countable edge set. The Borel readout $1\{{\mathrm{limsup}}_n{Z}_i(n)/n>1/2\}$ consequently has the entire forest law, not merely the correct edge marginals.

flowchart TD
  A[Finite weighted-tree response] --> B[Canonical posterior drift]
  B --> C[Unique Borel decoder]
  D[Reference forest plus observation noise] --> E[Independent innovations]
  E --> C
  C --> F[Integer-time slopes recover the forest law]
  G[Fresh IID vertex labels] --> H[Independent edge Brownian paths]
  H --> C

Independent edge noise without choosing a root

Split each vertex label into an independent key and a private sequence of uniforms. Orient an edge toward its larger-key endpoint; if the smaller endpoint is $u$, use the private uniform indexed by the larger endpoint’s rank among $u$‘s neighbors. Distinct edges select distinct private coordinates. Conditional on all keys, those coordinates remain independent uniforms. Local finiteness makes every rank finite.

A fixed Borel uniform-to-Brownian map supplies the edge paths. Key collisions receive a globally equivariant default and have probability zero on each fixed countable graph. Finite neighbor listings, edge-centered balls, scalar integration, and prescribed countable limits are all Borel on varying labeled graphs. This last check makes the construction one graphwise rule, rather than a separate measurable sampler chosen for each graph.

See Also

• Family 236 uses the same observation vocabulary but a different argument to recover spins from innovations at a critical threshold.
• Family 211 studies spanning-tree-weighted maps, where the graph itself is random.

🏷️ Manuscripts and verification scope

• The free uniform spanning forest is a factor of IID — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope page describes the graphwise free-forest factor and selected invariant negatively dependent and determinantal extensions. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The free uniform spanning forest is a factor of IID.