Introduction
Games generate unbounded worlds from seeded noise. A terrain height is a hash of its coordinates and a seed, so any region can be computed on its own and in any order, and machines that share the seed make the same world. When every small window of a map must come from a designer’s example, worlds are made by search instead. Wave Function Collapse (Gumin, [21 ] ) fills a canvas in a data-dependent order and restarts when the constraints run into a contradiction. Model synthesis (Merrell, [44 ] ) modifies a valid model one overlapping block at a time, so that a contradiction costs one block, and block solvers built on it (Boris the Brave, [10 ] ; Kleineberg [35 ] ) give random access by re-solving blocks over a fixed periodic background, which they keep where a block cannot be solved. Where validity fixes a row’s place, as in a brick wall, their worlds keep the background’s rows. Learned generators with random access, such as InfiniteDiffusion for terrain (Goslin, [19 ] ), carry no hard constraint.
We study random access through locality: each cell is a fixed function of the randomness near it, which may include coins shared along whole rows or on blocks that meet its neighborhood (§ 2 ). A cellular automaton run for a fixed number of rounds is local in this sense, and so is a diffusion sampler whose convolutional denoiser draws fresh noise at every step. A generator may also read its position modulo a fixed period; one that reads its position with no period, or randomness at unboundedly many scales, can also give random access but lies outside this model. We ask what a local generator must be given, whatever its architecture, to make worlds whose every window comes from one example (Figure 1 ).
Figure 1. Worlds from one example. Each column shows a public example and the central 64 × 64 64 \times64 64 × 64 256 × 256 256 \times256 256 × 256 § 6 ), both mended, with the share of forbidden windows on the whole canvas. On the first five examples validity carries a quantity over any distance, an invariant along rows or a phase. Independent coins leave forbidden windows on all five; given the quantity, the method leaves none, and on Fabric and RedMaze its world is the tiled example. Cave carries no such quantity, and both rules are valid on it.
A brick wall shows what independent coins, which give each cell randomness of its own, cannot do (Figure 2 ). No window of the example lets a mortar row step up or end, so a row’s place among the mortar lines is a quantity that validity carries along the whole row. A local generator on independent coins decides it at distant cells of a row independently, and wherever they disagree a forbidden window lies between them. Bergmann et al. [5 ] observed the same of textures: a generator on independent noise with a limited receptive field cannot align distant regions. For any quantity that validity carries along an axis and the statistics make vary, a generator of radius r r r 1 / r 1/r 1/ r § 3 ). This holds even where one repeated color satisfies every constraint, so that the constraints alone are solvable in constant time [11 ] . The order cannot be improved: the min-coin copy, which copies the example over regions drawn from the coins, stays within a constant factor of the bound, and a rule learned on independent coins leaves forbidden windows at about the copy’s rate (Figure 3 ).
Figure 2. The row type on Wall, a row’s place relative to the horizontal mortar lines, which validity keeps constant along every row. (a) The example and the row type of each of its rows. (b) The rule on independent coins after repair and mending, each cell tinted by the row type of the window centered on it: the type changes along rows, and the forbidden windows sit where it changes. (c) The method, given row types drawn from the seed, at the same coin seed: every row keeps its type, and no window is forbidden. (d) A mending instance with no completion (Appendix § 20 .§ 1 ): of the cells freed around a forbidden window (hatched), two frozen patches on one row carry row types that validity cannot join, a witness (Appendix § 13 .11).
Figure 3. The min-coin copy’s share of forbidden windows before mending against its radius r r r q r q_r q r 1 / r 1/r 1/ r r = 32 r=32 r = 32 § 8.5 from noise alone and diamonds the same model given the certificate’s input, at its radius r = 300 r=300 r = 300
The example alone shows whether the theorems apply. A search over the overlap graphs of the example’s locally valid patches finds quantities that validity carries, and we call an example with one certified (§ 6 ). We call a generator valid on an example when, after mending, a local re-solve around each forbidden window, at most one window in a thousand stays forbidden on each canvas. On 21 public examples, which we call resistant, a rule learned on independent coins stays far from valid. The search certifies 13 of them and none of the others. Where mending fails on a certified example, at the radii we examined, the re-solve mostly holds a witness, two frozen patches whose values of the quantity no valid filling can join (Figure 2 (d)), and the min-coin copy, mended the same way, is valid on no certified example at radii up to 128 (§ 8.1 ).
A shared input escapes the bound, and random access allows one. An invariant along rows is supplied as row types drawn band by band from the seed with the example’s own transitions, and a phase as the coordinates modulo its period, both at bounded work per cell (§ 6 ). Coins shared on blocks of bounded length help only as a larger radius would, unless the generator ties the quantity to their grid (Proposition 1). The position alone also escapes the bound but gives one world, the example tiled from absolute coordinates. A generator free of forbidden windows, at any depth, can vary the quantity between worlds only through randomness shared along whole lines (Theorem 3). Where the example’s rows glue, a condition decided by a finite computation on the example, that is also enough: a generator that reads only its band’s coin and its position leaves no forbidden window for any value of the coins (Theorem 4).
The rows glue on seven of the eight examples with a row invariant, all but 3Bricks. These are the examples where the copier, which fills the sampled rows with stretches of the example’s rows, exists and leaves no forbidden window (§ 6 ). With the copier, or a lookup of the example at the coordinates modulo the period, the input carries validity by itself, without learning or mending, on ten of the twelve certified examples that receive one.
A learned local generator can use the input as well. A small neural cellular automaton (Mordvintsev et al., [47 ] ), learned from the single example and given this input, is valid after mending on the same ten certified examples, all but 3Bricks and SmileCity. On the octaves of seeded noise alone, which share coins along whole rows as well as on blocks, it is valid on five of the twelve, and on independent coins on none. On the nine certified examples where it is valid on all eight canvases, no canvas keeps a forbidden window, while no generator on independent coins with the same statistics could be free of them, at any depth on most of these examples and at the radius of the whole pipeline on the rest (§ 8.2 ). A convolutional diffusion model given the input is valid on eight of the twelve, five of them without copying the example (§ 8.5 ).
Outside the corpus on which we built the procedure, the automaton is valid on all five examples we held out, two of them only with the input. On 27 examples taken from other implementations of Wave Function Collapse and related generators, the search again certifies only examples that resist independent coins, and the automaton, given the input where a certificate exists and the octaves elsewhere, is valid on 21 of them, against 18 on the octaves alone (§ 8.2 ).
Where a copier exists, learning is not what makes the worlds valid or new. The automaton composes its rows instead of copying them, and on Wall its canvases lie where Theorem 2 excludes the law of every generator on independent coins (Figure 6 ), but a block solver that re-solves the copier’s canvases does the same without learning (§ 8.3 ). Learning adds something of its own where nothing is certified, as the prior from which a mender starts. From a rule learned on the octaves, one mender makes 34 of the 39 uncertified examples valid, more than from any prior without learning that we gave it, though a block solver started from the tiled example needs no prior and is valid there by construction.
Figure 6. Wall and SimpleWall against the bounds. Each point is one canvas mended within radius 24, at the total variation δ \delta δ 3 × 3 3 \times3 3 × 3 ϵ \epsilon ϵ r = 804 r = 804 r = 804 δ = κ f \delta= \kappa_f δ = κ f δ \delta δ
With the octaves where nothing is certified and the input elsewhere, the automaton, which we call the method, is valid on 45 of the 52 public examples. Most of that validity comes with the mender, which rewrites a median of 18% of the cells where the method ends valid. Regions mended separately agree once each carries a margin as wide as a mending change can travel, so the method keeps random access (§ 8.4 ).
Our contributions are the lower bound, its counterpart at any depth and a construction that attains its order (§ 3 ); a necessary condition on what a local generator free of forbidden windows must share to vary the quantity between worlds, and a sufficient one decided on the example; the certificate and the input built from it, which keeps random access (§ 6 ); and a measured account of what a learned rule adds to that input (§ 8 ). Appendix M gives, for most experiments, the outcome we expected before the run beside the outcome observed.
Setting
A world is a coloring x : Z 2 → [ C ] x : \mathbb{Z}^{2} \to[C] x : Z 2 → [ C ] C C C N × N N \times N N × N x x x K K K K ⊆ [ C ] N × N K \subseteq[C]^{N \times N} K ⊆ [ C ] N × N K K K forbidden . As in Wave Function Collapse’s overlapping model (Gumin, [21 ] ), K K K f f f window statistics , so the plane tiled with the example is K K K f f f f f f N = 3 N = 3 N = 3 § 7 ), a weaker demand than K K K
Coins are uniform numbers hashed from the seed and the coordinates, shared over blocks as in seeded noise. A scale pair a = ( i , j ) a = (i, j) a = ( i , j ) i , j ∈ { 0 , 1 , 2 , … } ∪ { ∞ } i, j \in\{0, 1, 2, \ldots\} \cup\{\infty\} i , j ∈ { 0 , 1 , 2 , … } ∪ { ∞ } v = ( x , y ) v = (x, y) v = ( x , y ) v a = ( ⌊ x / 2 i ⌋ , ⌊ y / 2 j ⌋ ) v^{a} = (\lfloor x/2^{i} \rfloor, \lfloor y/2^{j} \rfloor) v a = (⌊ x / 2 i ⌋ , ⌊ y / 2 j ⌋) 2 i × 2 j 2^{i} \times2^{j} 2 i × 2 j ∞ \infty ∞ A A A w w w a ∈ A a \in A a ∈ A ω a , w \omega_{a,w} ω a , w v v v ω ( v ) = ( ω a , v a ) a ∈ A \omega(v) = (\omega_{a,v^{a}})_{a\in A} ω ( v ) = ( ω a , v a ) a ∈ A
Definition 1 (random-access generator). A random-access generator of radius r r r A A A X X X X v = g ( ( ω ( v + u ) ) ∥ u ∥ ∞ ≤ r ) X_v = g((\omega(v + u))_{\lVert u\rVert_\infty\le r}) X v = g (( ω ( v + u ) ) ∥ u ∥ ∞ ≤ r ) g g g g g g v m o d p v \bmod p v mod p v v v p p p ω ( v ) \omega(v) ω ( v ) v v v
Definition 2 (generator on independent coins). When A = { ( 0 , 0 ) } A = \{(0,0)\} A = {( 0 , 0 )} ( ω v ) v ∈ Z 2 (\omega_v)_{v\in\mathbb{Z}^{2}} ( ω v ) v ∈ Z 2 X v = g ( ( ω v + u ) ∥ u ∥ ∞ ≤ r ) X_v = g((\omega_{v+u})_{\lVert u\rVert_\infty\le r}) X v = g (( ω v + u ) ∥ u ∥ ∞ ≤ r ) X v X_v X v ℓ ∞ \ell_\infty ℓ ∞ r r r v v v [28 , 20 , 6 ] ).
A random-access generator is local : any region follows from the coins within distance r r r § 6 , row types drawn band by band from the seed and the coordinates modulo a period, fit the general form, and so does the mended output, with a reach , beyond which no coin changes a cell’s color, in place of the radius (Appendix § 12 ).
Limits of local generators
When validity carries a quantity along an axis and the example’s statistics make it vary, no local generator on independent coins is both free of forbidden windows and faithful to the statistics, at any depth; at radius r r r 1 / r 1/r 1/ r
Quantities carried by validity. A P × P P \times P P × P P ≥ N P \ge N P ≥ N locally valid if all its N × N N \times N N × N K K K V P V_P V P e e e overlap graph G P , e G_{P,e} G P , e V P V_P V P a a a b b b b b b e e e transported quantity is a map φ \varphi φ V P V_P V P σ \sigma σ φ ( b ) = σ ( φ ( a ) ) \varphi(b) = \sigma(\varphi(a)) φ ( b ) = σ ( φ ( a )) invariant , φ \varphi φ σ \sigma σ e e e row type (Figure 2 ). For a phase , σ \sigma σ d d d d ≥ 2 d \ge2 d ≥ 2 full labeling gives each locally valid patch its weak component c c c d c d_c d c c c c § 13 .§ 1 ). A one-way quantity , the strongly connected component of G P , e G_{P,e} G P , e
Theorem 1 (a floor from a transported quantity). Let g g g r r r X X X φ \varphi φ e e e P P P p s p_s p s P × P P \times P P × P X X X φ = s \varphi= s φ = s ε \varepsilon ε X X X
ε ≥ 1 − max s p s ( 2 r + P + 1 ) ( P − N + 1 ) 2 . \varepsilon\ge\frac{1-\max_s p_s}{(2r+P+1)(P-N+1)^2}. ε ≥ ( 2 r + P + 1 ) ( P − N + 1 ) 2 1 − max s p s . The theorem binds every such generator, whatever its architecture or training, among them the learned rule of § 7 on each cell’s own coins alone, the independent-coin rule . Patches 2 r + P 2r+P 2 r + P e e e φ \varphi φ σ \sigma σ max s p s \max_s p_s max s p s § 13 .§ 2 ).
Defects against fidelity. The bound vanishes only if φ \varphi φ P = N P=N P = N δ \delta δ f f f p s ≤ f ( φ = s ) + δ p_s \le f(\varphi=s)+\delta p s ≤ f ( φ = s ) + δ
ε ( 2 r + N + 1 ) + δ ≥ κ f , κ f = 1 − max s f ( φ = s ) . (1) \varepsilon(2r+N+1)+\delta\ge\kappa_f,\qquad\kappa_f=1-\max_s f(\varphi=s). \tag*{(1)} ε ( 2 r + N + 1 ) + δ ≥ κ f , κ f = 1 − s max f ( φ = s ) . (1) For any P P P κ ( δ ) \kappa(\delta) κ ( δ ) φ \varphi φ V P V_P V P N × N N \times N N × N δ \delta δ f f f κ ( 0 ) = κ f \kappa(0)=\kappa_f κ ( 0 ) = κ f κ ( δ ) ≥ κ f − δ \kappa(\delta)\ge\kappa_f-\delta κ ( δ ) ≥ κ f − δ ({xref}Appendix B.5`).
Rare changes. A quantity that the example lets change, but rarely, still sets a floor at finite radius. Let J ⊂ K J \subset K J ⊂ K θ = f ( J ) \theta=f(J) θ = f ( J ) φ \varphi φ e e e P = N P=N P = N K ∖ J K \setminus J K ∖ J K K K σ \sigma σ J J J
Corollary 1 (rare changes). Let g g g r r r ε \varepsilon ε δ \delta δ f f f κ J = 1 − max s f ( { w ∈ K ∖ J : φ ( w ) = s } ) \kappa_J=1-\max_s f(\{w\in K\setminus J:\varphi(w)=s\}) κ J = 1 − max s f ({ w ∈ K ∖ J : φ ( w ) = s })
( ε + δ + θ ) ( 2 r + N + 1 ) ≥ κ J . (\varepsilon+\delta+\theta)(2r+N+1)\ge\kappa_J. ( ε + δ + θ ) ( 2 r + N + 1 ) ≥ κ J . The proof runs Theorem 1 on K ∖ J K\setminus J K ∖ J K K K J J J § 13 .§ 6 ); when J J J (1) . A generator with ε = δ = 0 \varepsilon=\delta=0 ε = δ = 0 2 r + N + 1 ≥ κ J / θ 2r+N+1\ge\kappa_J/\theta 2 r + N + 1 ≥ κ J / θ θ \theta θ 1 / θ 1/\theta 1/ θ
Unbounded radius
A factor of i.i.d. coins is X = F ( ω ) X=F(\omega) X = F ( ω ) F F F Z 2 \mathbb{Z}^2 Z 2
Theorem 2 (no generator driven by independent coins). Let X X X K K K φ \varphi φ e e e § 13 or, for a one-way quantity, under the labeling by strongly connected components. Then almost surely φ \varphi φ κ ( δ ) > 0 \kappa(\delta)>0 κ ( δ ) > 0 X X X δ \delta δ f f f P = N P=N P = N f f f κ f \kappa_f κ f
Its proof uses ergodicity in place of a radius, which makes the value that a line free of forbidden windows carries almost surely one constant (Appendix § 13 ).
Corollary 2 (convolutional diffusion samplers). Let X X X X X X K K K κ ( δ ) > 0 \kappa(\delta)>0 κ ( δ ) > 0 X X X δ \delta δ f f f P = N P=N P = N f f f κ f \kappa_f κ f
Run without padding, the sampler commutes with every translation, so its output is a factor of i.i.d. coins and Theorem 2 applies; zero padding would let it read its position (Xu et al., 2021).
Local algorithms. A K K K [11 ] ). Some such labelings admit generators on independent coins whose defects fall exponentially in the radius, while on agreement constraints such as checkerboards none does better than order 1 / r 1/r 1/ r § 13 , after Brandt et al. [11 ] and Grebík & Rozhoň [20 ] ). Both theorems rest on classical arguments for factors of i.i.d. processes and add a trade between defects, fidelity and radius that binds even constraints a constant coloring satisfies.
Coins shared on blocks. The octaves of seeded noise share coins over blocks, which both theorems exclude.
Proposition 1 (coins shared on blocks). Let X X X X v X_v X v r r r v v v ℓ \ell ℓ e e e 2 r + ℓ 2r+\ell 2 r + ℓ 2 r 2r 2 r ε \varepsilon ε p s p_s p s K K K f f f
the example with wrap-around, copying the tiled example on every block of an ℓ × ℓ \ell\times\ell ℓ × ℓ ε ≤ 2 ( N − 1 ) / ℓ \varepsilon\le2(N-1)/\ell ε ≤ 2 ( N − 1 ) / ℓ 2 ( N − 1 ) / ℓ 2(N-1)/\ell 2 ( N − 1 ) / ℓ f f f T T T e e e X v X_v X v d c d_c d c T T T T T T ℓ \ell ℓ § 13 .§ 9 ).
A coin shared over a length ℓ \ell ℓ e e e ℓ / 2 \ell/2 ℓ /2
The floor’s order is attained. The min-coin copy copies the example as (b) does, over regions drawn from independent coins: every cell v v v [ 0 , 1 ] [0,1] [ 0 , 1 ] t v t_v t v Y Y Y m v m_v m v r r r v v v X v = Y ( v − m v + t m v ) X_v = Y(v-m_v+t_{m_v}) X v = Y ( v − m v + t m v ) m v m_v m v
Proposition 2 (the floor’s order is attained). Let N ≥ 2 N \ge2 N ≥ 2 K K K f f f § 2 . For every radius r ≥ N r \ge N r ≥ N min-coin copy is a generator on independent coins of radius r r r ε \varepsilon ε δ \delta δ f f f
ε ≤ q r , δ ≤ q r , where \varepsilon\le q_r,\qquad\delta\le q_r,\qquad\text{where} ε ≤ q r , δ ≤ q r , where q r = 1 − ( 2 r + 2 − N 2 r + N ) 2 < 4 ( N − 1 ) 2 r + N . q_r = 1-\left(\frac{2r+2-N}{2r+N}\right)^2 < \frac{4(N-1)}{2r+N}. q r = 1 − ( 2 r + N 2 r + 2 − N ) 2 < 2 r + N 4 ( N − 1 ) . Here q r q_r q r § 13 .§ 10 ). Inequality (1) sets the copy, whose statistics lie within q r q_r q r f f f ( κ f − q r ) / ( 2 r + N + 1 ) (\kappa_f-q_r)/(2r+N+1) ( κ f − q r ) / ( 2 r + N + 1 ) 4 ( N − 1 ) < κ f ( 2 r + N ) 4(N-1)<\kappa_f(2r+N) 4 ( N − 1 ) < κ f ( 2 r + N ) 4 ( N − 1 ) / κ f 4(N-1)/\kappa_f 4 ( N − 1 ) / κ f 1 / r 1/r 1/ r Figure 3 the copy sits at up to about 170 times the floor on the certified examples with a transported quantity (Appendix § 20 .§ 2 ), and the independent-coin rule lies within a factor of two of the copy at its own radius on all twelve of them. The diffusion model from noise lies far above the copy at its own radius, so its radius alone does not explain its rate (Appendix § 22 ).
What a generator must share
For a generator in the general form of Definition 1 and an axis direction e e e e e e G e \mathcal{G}_e G e e e e e e e Λ \Lambda Λ p p p T T T e e e
Theorem 3 (what a generator free of forbidden windows must share). Let X X X p p p Λ \Lambda Λ φ \varphi φ e e e X X X K K K φ \varphi φ G e \mathcal{G}_e G e e e e T T T φ \varphi φ X X X r r r G e \mathcal{G}_e G e e e e 2 r 2r 2 r § 14 .§ 2 ).
Part (a) is Theorem 2 run given G e \mathcal{G}_e G e T e Te T e [4 ] . Part (b) is Theorem 1 run given G e \mathcal{G}_e G e § 14 ).
Without coins shared along e e e T T T T T T § 14 ). Functions of the coordinates, such as the example tiled from absolute coordinates, satisfy (a) but repeat one world. For the layout of the quantity to differ between worlds, a generator free of forbidden windows therefore needs an input shared along the quantity’s direction that, with the position, fixes the quantity at every cell: for an invariant, values shared along whole lines; for a phase, a period T T T § 6 draws an allowed sequence of row types band by band from the seed, which a rule on coins shared along whole rows would have to do itself (Appendix § 13 .12).
The same transport limits editing a valid world. If two K K K e e e
Finding the quantity and supplying it
The example alone shows what a local generator must be given: a search of its locally valid patches finds the quantity that validity carries, before anything is trained, and its kind names an input that supplies it and keeps random access.
The search. For each axis direction e e e G P , e G_{P,e} G P , e P P P N N N § 13 .13). It reports an invariant when two weak components hold patches of the example, a phase when a weak component c c c d c ≥ 2 d_c \ge2 d c ≥ 2 κ ( 0 ) > 0 \kappa(0) > 0 κ ( 0 ) > 0 certificate : it proves a floor for every generator on independent coins whose statistics lie within δ \delta δ ({xref}Section 3), and an example with one is *certified*. The search is one-sided: an uncertified example may have a floor that a larger patch or another kind of quantity would reveal, and a certified one a second quantity, as SmileCity does ({xref}Appendix J`).
The input. The kind of the example’s first certificate, under a fixed tie-break (Appendix § 15 ), decides what the rule reads besides the octaves:
an invariant: the type of each line along its axis, from the row-type sampler;
a phase of period d d d d d d
a one-way quantity or an invariant along a diagonal, which have no input of their own, or no certificate at all: the octaves alone.
The row-type sampler. Along rows, where every certified invariant of the corpus runs, the type of row y y y P P P y − ⌊ P / 2 ⌋ y-\lfloor P/2\rfloor y − ⌊ P /2 ⌋ L L L L L L anchor , and draws the other states from the example’s transition frequencies, conditioned on returning to the anchor at the band’s end, so the anchor falls on the same rows in every world, a constraint that an offset hashed from the seed would lift (§ 10 ). The draw reads only the seed and the band’s index, so the state of any row costs work bounded by L L L § 15 ).
When the row types are enough. On most examples with a row invariant, the row types and the position are enough to vary the quantity between worlds with no forbidden window. Call a sequence of L + P − 1 L+P-1 L + P − 1 realization of the types drawn for a band if all its windows lie in K K K P P P § 14 .§ 6 ). The example’s rows glue if there is a strip Z Z Z P − 1 P-1 P − 1 Z Z Z
Theorem 4 (when the row types are enough). Let the example carry an invariant along rows, with the row-type sampler drawing bands of L ≥ P − 1 L \ge P-1 L ≥ P − 1 P ≤ 5 P \le5 P ≤ 5 Z Z Z L L L Z Z Z K K K
Two consecutive bands both carry Z Z Z § 14 ). The copier, which also fills each band with stretches of the example’s rows, chains its offsets toward the next band’s in place of a fixed strip, so it is valid by construction, not by the theorem (§ 8.2 ). Gluing is decided by a finite computation on the example (Appendix § 14 .§ 7 ). The rows glue on every example with a row invariant but 3Bricks, and these are the examples where the copier exists; on them the computation came after the copier’s results and explains them. On the three held-out walls it came first, and there too the rows glue and the copier leaves no forbidden window.
The phase channels. For a phase of period d d d x m o d d x \bmod d x mod d y m o d d y \bmod d y mod d
The octaves. Besides its own coins, every cell reads coins of every scale pair ( i , j ) (i,j) ( i , j ) i , j ∈ { 0 , 2 , 3 , 4 , ∞ } i,j \in\{0,2,3,4,\infty\} i , j ∈ { 0 , 2 , 3 , 4 , ∞ } ( 0 , 0 ) (0,0) ( 0 , 0 ) T = 16 T=16 T = 16
The failures of five certified examples, 3Bricks, Fabric, Skyline, Skyline2 and Wall, shaped parts of this procedure (Appendix § 15 ); the other certified examples test it within the corpus, the held-out ones as it stood when they ran, and those from other implementations as it stands (§ 8.2 ).
Generators and protocol
The tiled example is valid and has the example’s window statistics exactly, so validity and fidelity alone cannot show that a generator does anything. We compare the learned generators with generators that show what copying and mending achieve without learning (Table 1 ), and measure copying and variation by normalized agreement with the tiled example, repetition of its patches and aligned variation between seeds, except where every valid world is a translate of the tiling (Appendix § 17 .§ 3 ).
Table 1. The generators without learning that the text names (Appendix § 17 .§ 2 defines every generator). All but the block reference and Wave Function Collapse are random access, after mending too by the margin of § 8.4 . Shifted replay, the block reference, the random-access block solver and Wave Function Collapse skip the mender.
The learned automaton. The method’s rule is a neural cellular automaton (Mordvintsev et al. [47 ] ) learned from the single example (Figure 4 ): a radius-one update run without padding for 32 rounds, so a local generator of radius 32 on the input of § 6 . Training asks every round for allowed windows with the example’s frequencies, and a variation term penalizes agreement between two runs that differ only in their fine coins, against the shortcut of Proposition 1(b); rules trained without it do not copy either (Appendix § 23 .§ 8 ). Then four repair rounds recolor cells under forbidden windows with coins hashed from the seed and
Figure 4. The method. (1) The certificate decides the input: row types drawn band by band for an invariant along rows (dashed: a band boundary; orange: the anchor), the coordinates modulo d d d d d d
the position (Appendix § 16 ). The octave rule is the same construction on the octaves alone; the independent-coin rule, which reads no shared coins and so cannot take that shortcut, was trained before we added the variation term and has none.
The diffusion model. A convolutional diffusion model is trained on each example by Gaussian diffusion on the one-hot colors ((Ho et al., 2020)), with the standard loss and no term for forbidden windows. It samples with one step of its unpadded denoiser at each of 50 noise levels, under noise hashed from the seed, step and coordinates, so a cell depends on independent noise within 300 cells. It is trained from two training seeds, from noise alone on the certified examples and on controls, and with the input of § 6 , without the octaves, wherever a certificate names one (Appendix § 22 ).
Mending. Mending re-solves what repair leaves in two passes over a lattice of 48 × 48 blocks fixed in absolute coordinates. It frees the cells around each defect, out to the mending radius 24, and re-solves them with Wave Function Collapse’s propagation, cluster by cluster where a block’s defects cannot be completed together (Appendix § 16 .§ 3 ). It thus rewrites part of the output prior , the generator it starts from (§ 8.3 ). No coin farther than 804 cells from a cell can change its mended color, the reach of the whole pipeline: the rule’s radius with its repair rounds, plus the 760 cells that a mending change can travel.
Protocol. Validity is judged on three 256 × 256 256 \times256 256 × 256 development seeds . A robustness test adds five canvases on the robustness seeds , and a last test three on fresh seeds that no decision used; the rules counted are trained from training seed 0 (Table 4 ). The examples fall into three classes by what mending within radius 8, without cluster completion, makes of the independent-coin rule on one canvas: it leaves at most one window in a thousand forbidden on the mendable examples, at most one in a hundred on the partial ones, and more on the resistant ones, which resist independent coins. Every certified example lies far from these boundaries, with at least 0.024 of its windows forbidden.
Table 4. The comparisons and their protocols. Each mending radius comes with blocks of twice the radius. Canvases are 256 × 256 256 \times256 256 × 256 § 16 .§ 3 ; the mender without it leaves a block unchanged when it cannot complete all of its defects together.
Results
Independent coins fail where the certificate finds a quantity
The certificate picks out the examples on which independent coins fail. It certifies 13 of the 21 examples that resist independent coins (§ 7 , Table 8 ) and none of the 31 others (Figure 5 ). Against the 21 examples that independent coins mend, leaving out the partial ones, a one-sided Fisher exact test gives p = 8 ⋅ 10 − 6 p = 8 \cdot10^{-6} p = 8 ⋅ 1 0 − 6 § 19 ). On examples from other implementations, which played no part in designing the search, it again certifies only examples that resist (§ 8.2 ).
Figure 5. Every public example after mending: the share of forbidden windows on the worst of three canvases for the independent-coin rule (square), the octave rule (pentagon) and the method (circle); on Town and the uncertified examples the method is the octave rule, and only its circle is drawn. The dotted line marks validity, one forbidden window in a thousand; exact zeros sit below the break in the axis. The lower row gives the share of the method’s cells that mending rewrites, and the dashed line its median over the examples the method makes valid. The examples are grouped by class (§ 7 ) and ordered within each by the independent-coin rule; names in bold carry a certificate.
Table 8. The certificate on the certified public examples and on Chess and Stripes, two controls whose only valid colorings are the two phases of a period-two pattern (Appendix § 17 .§ 6 ). Rows with an invariant or a phase use the full labeling of § 3 ; Town’s row uses its one-way quantity, whose constant is κ f = 1 − ∑ s → t f s f t \kappa_f = 1 - \sum_{s\to t} f_s f_t κ f = 1 − ∑ s → t f s f t t t t s s s κ ( δ ) \kappa(\delta) κ ( δ ) 1 − ∑ s → t p s p t 1 - \sum_{s\to t} p_s p_t 1 − ∑ s → t p s p t § 13 .§ 7 ). Columns: the kind of quantity, its direction, the patch size P P P d d d k × m k\times m k × m k k k m m m κ ( δ ) \kappa(\delta) κ ( δ ) δ = 0 \delta= 0 δ = 0 δ = 0.05 \delta= 0.05 δ = 0.05 δ \delta δ 1024 2 1024^2 102 4 2 L 1 L_1 L 1
caption:
Once mended, the rule on independent coins is valid on most uncertified examples, and on none certified one at any mending radius we tried (Appendix § 20 .§ 3 ). The theorems explain this failure without forcing it at our threshold: mending gives a generator on independent coins the pipeline’s reach as its radius (Proposition 1(a)), and at that reach the floor for a generator with the example’s statistics lies below the threshold on every certified example (Appendix § 13 .§ 11 ).
The failure is not peculiar to learning. The min-coin copy, which attains the floor’s order, is valid after mending on none of the certified examples at radii up to 128, while at radius 64 it is already valid on 19 examples that do not resist (Appendix § 20 .§ 2 ). On Wall it is still invalid at radius 512, and if its rate kept falling as 1 / r 1/r 1/ r
Sampled from noise alone, the diffusion model fails on every certified example but also on most of the uncertified controls that the independent-coin rule makes valid, so at its training budget it cannot test the certificate’s selectivity (Table 16 ).
Table 16. The diffusion model of Section 5 by input and class of example: the number of examples (n n n
Mending stalls on the certified examples for the reason the theorems give. At the radii we examined, most instances it cannot complete hold a witness, two frozen patches on one line whose values of the quantity no valid filling can join (Figure 2 (d), Table 10 ).
Table 10. Witnesses on every certified example and on the resistant examples without a certificate. The instances are those of Appendix § 20 .§ 6 decided unsolvable at ρ = 4 \rho= 4 ρ = 4 Table 14 . Columns: the unsolvable instances; those the solver refutes before any search; the share with a witness, overall, per radius and among the instances the solver had to search; and the solvable instances searched, none of which holds a witness, as none can. Without a certificate the labeling of patches of size 3 has one value, so no witness can exist there, and the shares are those of the labeling of patches of size 4 along rows or columns.
Table 10. Witnesses on every certified example and on the resistant examples without a certificate. The instances are those of Appendix I.4 decided unsolvable at ρ = 4 \rho= 4 ρ = 4
The eight resistant examples without a certificate show no quantity carried along a line. They stay uncertified when the search widens to larger patches, knight-move directions and tall strips (Appendix § 18 ). In the worlds of Wave Function Collapse, a global solver, the dependence between 3×3 windows persists to 64 cells along the quantity’s direction on every certified example but Skyline2, and along no direction on the eight without one (Appendix § 18 .§ 1 ). Whatever constrains them is not a quantity carried along a line, at least not one visible at the patch sizes and distances we measured.
Local generators given the certificate's input
The input often carries validity by itself, on ten of the twelve certified examples that receive one. The copier, which exists where the rows glue (§ 6 ), leaves no forbidden window on any of its seven examples even before mending (Table 21 ). Where the example is one period of its phase, as on Fabric, RedMaze and SimpleMaze, reading it at the coordinates the phase channels give yields the tiled example; on SmileCity, whose example spans several periods, it does not (Appendix § 21 ).
Table 21. Fillers of the row types on the eight examples with a row invariant: the copier (none exists on 3Bricks), the re-solved copier, which re-solves the copier’s canvas block by block, the method’s own rule and the Metropolis filler on the row types after 256 sweeps, all mended within radius 24. Valid means valid on all three canvases. The share of forbidden windows is that of the canvas the mender receives, the median over the canvases; the other columns give the range over the canvases of the share of cells mending changes, of rows equal to a row of the example up to a horizontal shift, of 16 × 16 16 \times16 16 × 16 3 × 3 3 \times3 3 × 3
Given the input, the method is valid on 11 of the 13 certified examples, all of which defeat the rule on independent coins (Figure 5 ). The octaves, which include coins shared along whole rows, already give six of them; the input adds six, Wall among them, and loses 3Bricks. On Fabric, by Proposition 1(c), every rule on the octaves that matches the example’s statistics has a floor above the threshold before mending, though not after (Appendix § 13 .§ 11 ), while given the phase channels the rule leaves nothing to mend. With the octaves where nothing is certified, the method is valid on 45 of the 52 public examples, against 28 for the rule on independent coins.
On most of the certified examples the theorems set the method’s worlds beyond the reach of independent coins. On nine certified examples no canvas of the method keeps a forbidden window (Table 9 , Figure 6 ). On Wall and five others the program of § 3 stays positive at the canvases’ largest distance from the example’s statistics, so no generator on independent coins free of forbidden windows comes as close at any depth (Theorem 2); on Fabric, RedMaze and SimpleMaze the method’s world is the tiled example, which no such generator reaches in any case. On the other three the statistics lie too far for Theorem 2. There Theorem 1 still requires a generator on independent coins whose most common row type is no more common than in the method’s worlds to leave at least four forbidden windows per canvas in expectation, but at the pipeline’s reach it forces each one only somewhere along a stretch longer than a canvas is wide, so a clean canvas is weak evidence there.
Table 9. The method’s worlds against the theorems on the certified examples, in the order of Table 8 , on the eight canvases of the development and robustness seeds (on Wall also the fresh seeds), mended within radius 24. Columns: the kind of quantity and its patch size P P P δ \delta δ 3 × 3 3 \times3 3 × 3 § 13 .§ 7 at the largest δ \delta δ δ ∗ \delta^* δ ∗ δ \delta δ δ \delta δ max s p s \max_s p_s max s p s r = 804 r = 804 r = 804 § 13 .§ 2 .
caption:
The method holds up on examples that shaped nothing in the procedure. It is valid on every certified example whose failures played no part in designing it (§ 6 ) but
SmileCity, and on all five examples we drew or transposed for the test: three walls, two of them transposed so that their invariant runs along columns, and two mazes, one certified. On transposed Wall and on the certified maze the octaves alone fail (Appendix § 19 ). It leaves 3Bricks and SmileCity invalid: on SmileCity the rule mixes two lattices of faces along the rows, which no finite patch certifies (Appendix § 21 ), and on 3Bricks one of its three canvases stays just above the threshold (Appendix § 23 .§ 11 ).
Examples that we neither drew nor tuned against test the procedure from further outside. We ran it unchanged on 27 example images from eight other open-source implementations of Wave Function Collapse and related generators (Appendix § 19 ), and the method is valid on 21 of them, more than the octave rule or independent coins (Table 19 ). The certified examples carry the difference: the method is valid on all four that receive an input and the octave rule on one, though on three of them, each one period of a pattern, the method’s world is the tiled example. Where nothing is certified the method is the octave rule, which does about as well there as tiles of the example shifted block by block under the same mender.
Table 19. The examples from other implementations (Appendix H), grouped by repository. Certificate and input: what the search finds and what the procedure then gives the rule. Class: the independent-coin rule’s class from mending at radius ρ \rho ρ
What a learned rule adds
What does a learned rule add to an input that already carries validity? Where a copier exists, the input alone makes the worlds valid, and a block solver without learning, run on the copier’s canvases, makes them new as well. The copier is valid on all seven examples where it exists (§ 8.2 ) but copies: every row of its canvases is a row of the example up to a horizontal shift (Table 21 ). The rule composes its rows instead: on Wall none of the rows inside its courses is a row of the example (Table 22 ), and on every example with a row invariant none of its 16 × 16 patches that hold no forbidden window before mending occurs in the tiled example (Table 23 ). The composition is therefore the rule’s own, and on Flowers, MoreFlowers and Skyline, where mending touches almost every patch, the mender’s as well.
Table 22. Bricks, joints and copies on Wall. Each entry is the range over a generator’s canvases (256 × 256, mended within radius 24 where the generator is mended; the method on the development and fresh seeds, the others on the development seeds). Forbidden windows are a rate; joints are a share of course cells; the total variation counts all forbidden windows as one outcome, and the next column is the share of it forced by the shortage of windows with a joint. The octave rule and the independent-coin rule are not valid on Wall.
The rule’s composition before mending on the examples with a row invariant, counted after the run. Before mending, after the rule’s repair rounds: the share of the rule’s 16 × 16 16 \times16 16 × 16 16 × 16 16 \times16 16 × 16 Table 9 .
Table 23.
A block solver without learning composes as well once it starts from the copier’s canvases. The re-solved copier re-solves every block of such a canvas in two passes on the random-access block solver’s lattice. It starts from a canvas without forbidden windows, and each re-solve keeps every window it touches allowed and always has a completion, the block’s current content, so it leaves no forbidden window on any seed. As in the rule’s worlds, none of its rows with more than one color is a row of the example, and its statistics lie closer to the example’s than the rule’s on all but Platformer (Table 21 ).
The layout of rows is the sampler’s, which draws a new sequence of row types from each seed. Every filler that reads it follows it, while the block solvers run from the tiled example keep the tiling’s sequence on every seed, since a block re-solved under frozen surroundings cannot change a row’s type (Appendix § 23 .§ 7 ). On Wall none of the method’s canvases has the tiling’s sequence and no two agree up to a shift; only the rows around the band anchors share their type on every canvas (Figure 10 ). The method’s normalized agreement with the tiling is 0.09, where an i.i.d. draw scores zero and the tiling one, against 0.67 for the random-access block solver (Table 24 ).
Variation between seeds and copying of the tiling on Wall. Aligned variation is the share of cells that differ between two canvases of one generator after the relative translation that makes it smallest, and normalized agreement is the share of cells equal to the best translation of the tiled example, scaled to be 0 for an i.i.d. draw and 1 for a translate of the tiling (Appendix § 17 .§ 3 ). The method and the two copiers are measured on the three canvases of the development seeds, mended within radius 24, and the block solvers and shifted replay on eight canvases, at the coin seeds of Table 37 . The copier’s aligned variation was not measured.
Table 24.
Figure 10. The layout of rows on Wall. Each strip gives the types of 96 of the 256 rows of one canvas, read downward, drawn left to right in the colors of Figure 2 and shifted to align best with the tiled example, the top strip, whose sequence both block solvers keep. The lower strips are the sequences that the row-type sampler draws on six of the method’s canvases, those of the development and fresh seeds, and that both copiers follow. A tick marks each row whose type differs from the aligned tiling.
On Wall the rule’s statistics lie farther from the example’s than either copier’s, mostly because its bricks run longer (Table 22 ). A sampler written by hand composes less well: the Metropolis filler, which composes on the row types and reads far beyond the rule’s radius, is valid on four of the examples with a row invariant, and the rule on seven (Appendix § 23 .§ 6 ).
Learning adds something of its own where nothing is certified, as the prior from which one mender starts. From the octave rule the mender makes 34 of the 39 uncertified examples valid, and from any prior without learning that we gave it no more than 23, the count of block-shifted tiles (Appendices § 23 .§ 3 and § 20 .§ 2 ). On the examples from other implementations the octave rule leads block-shifted tiles where nothing is certified only by a single example (§ 8.2 ). The block solvers need no prior and are valid on the uncertified examples by construction, and where the octave rule is valid at mending radius 8, mostly on uncertified examples, the random-access block solver varies about as much as the rule and keeps a little more of the tiling’s layout (Appendix § 23 .§ 7 ).
Most of the rule’s validity comes with the mender. Before mending the method is valid on 4 of the 52 examples, City, Fabric, RedMaze and SimpleMaze. On the examples it makes valid, mending rewrites a median of 18% of the cells (Figure 5 ), and almost every rewritten cell would make a window forbidden if its old color returned (Appendix § 23 .§ 1 ).
Random access after mending
Mending keeps random access once each chunk carries a margin as wide as a mending change can travel, at most 760 cells. Every input channel is a function of the seed and the coordinates, so chunks agree before mending, and the mender seeds every solve by the seed, its block’s absolute coordinates and the cluster’s index (Appendix § 16 .§ 3 ). A narrower margin sufficed on every canvas we tested: at 256 cells each agrees cell for cell with its separately mended chunks (Appendix § 23 .§ 9 ). On twelve canvases 2048 cells wide, whose edge lies beyond a mending change’s reach of the chunk, so that the chunk sees the values of the unbounded world, the agreement holds at each margin we tried, from 256 to 760 cells. At 256 cells a chunk of 256 2 256^2 25 6 2
A mender of longer reach makes more examples valid, at a wider margin. Mending within radius 48 instead of 24 widens the guaranteed margin from 760 to 1528 cells and adds Skew1 and ScaledMaze, valid on all eight canvases and without copying, for 47 of the 52 public examples. A mender close to a global solver also makes Mountains and SmileCity valid, with window statistics about 2.1 times as far from the example’s, and still leaves Lake and Link2 invalid (Appendix L.8).
A diffusion model given the input
Does the input help a learned generator of another kind? It does for the convolutional diffusion model of Section 5.
From noise alone, where Theorem 1 binds it at its radius and Corollary 2 at any number of steps, the model is valid on none of the twelve certified examples that receive an input (Section 6.1). Given the input, it is valid after mending on eight of them at both training seeds. It follows the input: on all twelve the quantity switches value along its direction at least ten times less often than from noise alone, and on Wall its share of forbidden windows before mending falls from 0.22 to 0.012, near the method’s.
Where the model is valid and its worlds can differ from the tiling, it does not copy. On Fabric, RedMaze and SimpleMaze, whose valid worlds are essentially translates of the tiling (Appendix F.3), its world is the tiled example, as the method’s is. On the other five it makes valid, few of its 16 × 16 patches occur in the tiled example and none of its rows with more than one color is a row of the example, while every row of the copier’s canvases is (Table 16). It falls short of the method only on Skyline and Skyline2, where it leaves about five times as many forbidden windows before mending as the method and stays invalid after mending (Appendix K).
Related work
Constrained content. Wave Function Collapse [21 ] and model synthesis [44 , 45 ] are read as constraint solving [33 ] and extended with a hierarchy [49 ] or with learned constraints or orders of collapse [7 , 67 ] , and neural cellular automata enforce the constraints with a mixed-integer program [68 ] , all by global search; our generators are local.
Random access. Non-parametric texture synthesis [15 ] is sequential. Wang tiles [12 , 65 , 36 ] , by-example noise [23 ] and parallel synthesis [38 ] compute any part of an unbounded texture on its own, and InfinityGAN [39 ] and InfiniteDiffusion [19 ] learn random access without hard constraints. Constrained worlds are grown in the order of exploration [34 ] or re-solved block by block [10 , 35 ] , after model synthesis [44 ] , over a known-good background that Boris the Brave [10 ] makes optional at the cost of its fallback for failed blocks. Here an input named by the example lets local generators meet the constraint.
Local computation. The K K K [40 ] . Classifications of locally checkable labelings on grids (Brandt et al., 2017; Grebík & Rozhoň [20 ] ; Berlow et al. [6 ] ) and local mending (Balliu et al. [3 ] ) describe what rules of bounded radius with coins can satisfy (after Luby [42 ] ; Jeavons et al. [30 ] ). Balliu et al. [4 ] separate shared from private randomness with grids on which every row must output one bit: with private coins and too few rounds to see a whole row, its nodes can agree only by fixing the bit by their vertical position, while with shared randomness each node reads the shared bit at its row. Theorem 3 finds this dichotomy for every quantity that validity carries along an axis, at any depth, with the example’s statistics in place of their adversarial input. Finitary codings (Holroyd et al. [28 ] ; Spinka [62 ] ) let the radius be random but almost surely finite, and finitely dependent colorings (Holroyd & Liggett [27 ] ) ask only for independence at a distance. Local computation algorithms (Rubinfeld et al. [57 ] ), local access to huge random objects (Goldreich et al. [18 ] ; Biswas et al. [9 ] ) and perfect sampling of infinite Gibbs measures (Anand & Jerrum [1 ] ) answer local queries about one consistent sample. Height functions and tiling groups (Conway & Lagarias [13 ] ; Thurston [63 ] ) carry quantities like ours along paths and give criteria for whether a region can be tiled; we find ours by searching the example. These concern satisfiability or a given measure, not an example’s statistics.
Local samplers. Short-range denoisers can miss long-range structure (Montanari [46 ] , § 8 ): a local denoiser succeeds once its radius exceeds the data’s Markov length by a logarithmic factor, and fails where that length diverges (Hu et al. (2025)). Trained denoisers are local in practice (Niedoba et al. [50 ] ; Lukoianov et al. [43 ] ), and by locality and equivariance convolutional diffusion models sample locally consistent mosaics of training patches (Kamb & Ganguli [32 ] ). By Corollary 2, such a sampler, run on the whole plane from independent noise, cannot be both free of forbidden windows and faithful where validity carries a quantity that the statistics make vary. Sampling can need far more rounds than constructing: a uniform independent set needs rounds of the order of the diameter on some graphs, though the empty set is one (Feng et al. [16 ] ). Gibbs measures have related limits (van den Berg & Steif [64 ] ), and for diffusion models, generating scale by scale eases the sampling of long-range structure (Guth et al. [22 ] ).
Shared inputs. Seeded noise sums octaves of interpolated gradients hashed on integer lattices (Perlin [54 , 55 ] ; Lagae et al. [37 ] ), and our octaves are such noise without interpolation. Learned generators of unbounded images draw multiscale randomness too (Skorokhodov et al. [60 ] ; Henzler et al. [24 ] ). Bergmann et al. [5 ] observed that a texture generator on independent noise with a limited receptive field (Jetchev et al. [31 ] ) is a mixing process that cannot align distant regions, and gave theirs a global channel and periodic channels with a random phase, which for a phase is the input Theorem 3 asks for. Under a hard constraint we bound the defects that independent noise costs, find in the example which shared input a generator needs, and show that a generator free of forbidden windows can vary the quantity between worlds only through randomness shared along the axis. The row-type sampler combines the recursive method of random generation (Nijenhuis & Wilf [51 ] ; Flajolet et al. [17 ] ) with counter-based random numbers (Salmon et al. [58 ] ), and the certificate sets the period of our phase channels and the sampler’s automaton.
Learning from one image. Neural cellular automata learn update rules from one target (Mordvintsev et al. [47 ] ; Niklasson et al. [52 ] ) or generate levels under quality-diversity search (Earle et al. [14 ] , SinGAN (Shaham et al., [59 ] and TOAD-GAN (Awiszus et al., [2 ] ) learn from one image or level, and a diffusion sampler with a closed-form patch denoiser needs no training (Qiu et al. [56 ] ). Run for a fixed number of steps on coins indexed by position, a texture automaton is a local generator with random access, as ours is, but none of these works holds its output to a hard constraint.
Limitations
We built the certificate search, the inputs and the training recipe on the public examples, and widened the search after its first count (§ 8.1 ), so the counts on them show agreement on the corpus the procedure was built on rather than a test on new examples. Even the certified examples whose failures shaped none of it test it only within that corpus, and on most of them the octave rule alone is valid as well. The tests from outside it are the five examples we drew or transposed, where the input decides the outcome on two, and the 27 examples from other implementations, where it decides the outcome only on GbLattice, GbTriangles and GbZigzag, each one period of a pattern and all from one repository (§ 8.2 ).
The certificate is one-sided: an uncertified example may carry a quantity that the search does not cover, and a certified example may carry a second quantity that no input of the procedure fixes, as SmileCity does (§ 6 ). The worlds of a global solver show no persistent dependence on the resistant examples without a certificate, but that test can miss a quantity, as it misses the quantity behind Skyline2’s (Appendix § 18 .§ 1 ). Theorem 4 needs the example’s rows to glue, which they do not on 3Bricks; whether other rows realize its row types there, and which condition is necessary as well as sufficient, is open (Appendix § 14 ). The procedure has no input for a one-way quantity or for an invariant along a diagonal, so on Town and on GbDiamond the method is the octave rule, and every certified invariant in the corpus runs along rows, so only the transposed walls test the procedure along columns (§ 8.2 ).
The phase channels fix the layout to the coordinates, so on Fabric and the mazes every coin seed we drew gives the same canvas, though worlds with their statistics leave a seed little to choose beyond the translate (Appendix § 17 .§ 3 ). An offset hashed from the seed, a coin shared over the plane and so allowed by Theorem 3, would let the seed place the phase or the anchor rows of the row-type sampler and keep random access; we did not train with one. Mending rewrites cells with Wave Function Collapse’s completions, and we have not divided the credit for validity between the rule and the mender on each example (§ 8.3 ). A mender of longer reach adds valid examples only at a wider margin, and on Lake and Link2 none that we ran gives valid worlds (§ 8.4 ). Validity allows up to one forbidden window in a thousand on each canvas, a threshold we chose; Figure 5 shows the examples on which no canvas keeps one.
Each count rests on one training run per example and on three canvases. Trained from two more seeds, the method stays valid at both on ten of the eleven certified examples it makes valid at the first, and at each new seed the octave rule is valid on slightly fewer examples than at the first (Table 18 ). Judged on eight canvases instead of three, the method is no longer valid on Skyline2 and Town (Appendix § 23 .§ 1 ). At the reach of the whole pipeline, clean canvases set the method apart from generators on independent coins only weakly (§ 8.2 ). The diffusion model ran at one training budget (Appendix § 22 ). We ran one window size, N = 3 N = 3 N = 3 § 17 .§ 6 ).
Table 18. Validity on other coin seeds and from other training seeds, within radius 24. Upper part, at training seed 0: the examples valid on the three canvases of the development seeds, and of these the examples valid on the three canvases of the fresh seeds, which no decision used; on the examples without a certificate the method is the octave rule. Lower part: the examples valid at training seeds 0, 1 and 2 and at all three, for the method on the twelve certified examples other than SmileCity, whose method rule was trained from seeds 0 and 1 but not from seed 2 (Table 31 ), and for the octave rule on all 52 public examples; and the range of the total variation (TV) of the method’s 3 × 3 3 \times3 3 × 3 κ f = 2 / 3 \kappa_f = 2/3 κ f = 2/3
Conclusion
A local generator needs more than independent coins to make the worlds that some examples allow. When validity carries a quantity along an axis and the example’s statistics make it vary, no generator on independent coins is both free of forbidden windows and faithful to the statistics, however far each cell reads, and at a finite radius its defects fall only as the inverse of the radius, an order that is attained. A certificate computed from the example finds such a quantity on most of the public examples that resist independent coins and on none of the others, and on examples from other implementations it again certifies only examples that resist. An input that distant cells share escapes the bound without giving up random access, and at any depth a generator free of forbidden windows needs one to vary the quantity between worlds; where the example’s rows glue, as on every example with a row invariant but 3Bricks, the row types drawn from the seed and the position are enough. Copying the example along this input already gives valid worlds on all but two of the certified examples that receive it, and a learned cellular automaton or a convolutional diffusion model given it becomes valid on most of them, where independent coins it is valid on none. Learning adds something of its own where nothing is certified, as the prior from which a mender starts, though a block solver started from the tiled example is valid there by construction. The learned rule needs a mender that rewrites part of each world, and regions mended separately are guaranteed to agree once each carries a margin as wide as a mending change can travel. What stays open is structure that the certificate does not name, such as the lattice of SmileCity’s faces, an input for a quantity that can change only one way or that runs along a diagonal, and a condition for worlds free of forbidden windows where the rows do not glue, as on 3Bricks.
The appendices. Appendices A to C hold random access in detail and the proofs. Appendices D to F describe the certificate search, the method and the protocols. Appendices G to L give the detailed results: the certificate on every example, more on the evidence of § 8 , the failure of independent coins, SmileCity, the diffusion model and further results. Appendix M sets each expectation we fixed before a run against what happened, and Appendix N holds the tables that only the appendices cite.
Random access in detail
One setting for every example. The repository sets the window size and the symmetry variants per example. We read every example periodically, at window size N = 3 N = 3 N = 3
Periods. Let T T T A \mathcal{A} A T Z 2 T\mathbb{Z}^{2} T Z 2 T T T p p p R R R R R R T = 16 T = 16 T = 16 § 6 ). The row-type sampler draws the row types of a band of L L L L L L
The three properties. Any region S S S S S S r r r S S S overrides the coins read in S S S S S S r r r S S S r r r
The mended output. A random-access generator must satisfy K K K r r r § 7 ) re-solves the defects that the rule leaves, block by block on a lattice fixed in absolute coordinates and with randomness hashed from the seed and the block coordinates, so its output depends on a cell’s position modulo twice the block size as well as on the coins, and a change it makes can travel beyond the rule’s radius. The mended output has a reach , a distance beyond which no coin can change a cell’s mended color, and we call such a construction random access in the extended sense : it is a generator in the general form of Definition 1 with its reach in place of the radius r r r § 8.4 measures the smaller margin at which every canvas we tested agrees.
Proofs
Throughout, K ⊆ [ C ] N × N K \subseteq[C]^{N \times N} K ⊆ [ C ] N × N x : Z 2 → [ C ] x : \mathbb{Z}^{2} \to[C] x : Z 2 → [ C ] Q v P ( x ) Q_{v}^{P}(x) Q v P ( x ) P × P P \times P P × P x x x v v v W v ( x ) = Q v N ( x ) W_{v}(x) = Q_{v}^{N}(x) W v ( x ) = Q v N ( x ) v v v r r r ( ω v ) (\omega_{v}) ( ω v ) X X X X v X_{v} X v ℓ ∞ \ell_{\infty} ℓ ∞ v v v X X X
The full labeling
For a weakly connected component c c c G P , e G_{P,e} G P , e ( a , b ) (a,b) ( a , b ) + 1 +1 + 1 d c d_{c} d c c c c d c = 0 d_{c} = 0 d c = 0 c c c c c c d c d_{c} d c φ ( a ) = ( c , level ) \varphi(a) = (c,\text{level}) φ ( a ) = ( c , level ) σ ( c , i ) = ( c , i + 1 m o d d c ) \sigma(c,i) = (c,i + 1 \bmod d_{c}) σ ( c , i ) = ( c , i + 1 mod d c ) V P V_{P} V P d c ≥ 2 d_c \ge2 d c ≥ 2 Table 8 reports constants for this labeling.
Theorem 1
Let k = 2 r + P k = 2r + P k = 2 r + P u j = j e u_j = je u j = j e j = 0 , … , k j = 0, \ldots, k j = 0 , … , k A A A Q u j P ( X ) Q_{u_j}^{P}(X) Q u j P ( X ) j j j A A A G P , e G_{P,e} G P , e φ ( Q u j + 1 P ) = σ ( φ ( Q u j P ) ) \varphi(Q_{u_{j+1}}^{P}) = \sigma(\varphi(Q_{u_j}^{P})) φ ( Q u j + 1 P ) = σ ( φ ( Q u j P )) φ ( Q u k P ) = σ k ( φ ( Q u 0 P ) ) \varphi(Q_{u_k}^{P}) = \sigma^k(\varphi(Q_{u_0}^{P})) φ ( Q u k P ) = σ k ( φ ( Q u 0 P )) u 0 u_0 u 0 [ − r , P − 1 + r ] [-r, P - 1 + r] [ − r , P − 1 + r ] e e e u k u_k u k [ k − r , k + P − 1 + r ] [k - r, k + P - 1 + r] [ k − r , k + P − 1 + r ] k ≥ 2 r + P k \ge2r + P k ≥ 2 r + P p ( v ) p^{(v)} p ( v ) φ \varphi φ v v v p ( u 0 ) = p ( u k ) = p p^{(u_0)} = p^{(u_k)} = p p ( u 0 ) = p ( u k ) = p
Pr [ A ] ≤ ∑ s p s p σ k ( s ) ≤ max t p t ∑ s p s ≤ max t p t . \operatorname{Pr}[A] \le\sum_s p_s p_{\sigma^k(s)} \le\max_t p_t \sum_s p_s \le\max_t p_t. Pr [ A ] ≤ s ∑ p s p σ k ( s ) ≤ t max p t s ∑ p s ≤ t max p t . If A A A ( P − N + 1 ) 2 (P - N + 1)^2 ( P − N + 1 ) 2 Pr [ Q v P ∉ V P ] ≤ ( P − N + 1 ) 2 ε \operatorname{Pr}[Q_v^P \notin V_P] \le(P - N + 1)^2\varepsilon Pr [ Q v P ∈ / V P ] ≤ ( P − N + 1 ) 2 ε k + 1 k + 1 k + 1 1 − max t p t ≤ Pr [ A c ] ≤ ( k + 1 ) ( P − N + 1 ) 2 ε 1 - \max_t p_t \le\operatorname{Pr}[A^c] \le(k + 1)(P - N + 1)^2\varepsilon 1 − max t p t ≤ Pr [ A c ] ≤ ( k + 1 ) ( P − N + 1 ) 2 ε
For a one-way quantity, write s ⇝ t s \leadsto t s ⇝ t t t t s s s G P , e G_{P,e} G P , e s ⇝ s s \leadsto s s ⇝ s A A A φ ( Q u k P ) \varphi(Q_{u_k}^{P}) φ ( Q u k P ) φ ( Q u 0 P ) \varphi(Q_{u_0}^{P}) φ ( Q u 0 P ) Pr [ A ] ≤ ∑ s ⇝ t p s p t \operatorname{Pr}[A] \le\sum_{s\leadsto t} p_s p_t Pr [ A ] ≤ ∑ s ⇝ t p s p t
ε ≥ 1 − ∑ s ⇝ t p s p t ( 2 r + P + 1 ) ( P − N + 1 ) 2 . \varepsilon\ge\frac{1-\sum_{s\leadsto t}p_s p_t}{(2r+P+1)(P-N+1)^2}. ε ≥ ( 2 r + P + 1 ) ( P − N + 1 ) 2 1 − ∑ s ⇝ t p s p t . For an invariant or a phase the only pairs allowed are t = σ k ( s ) t = \sigma^k(s) t = σ k ( s ) max s p s \max_s p_s max s p s κ ( δ ) \kappa(\delta) κ ( δ )
Inequality (1)
For P = N P = N P = N p s = h ( { w ∈ K : φ ( w ) = s } ) p_s = h(\{w \in K : \varphi(w) = s\}) p s = h ({ w ∈ K : φ ( w ) = s }) h h h W 0 ( X ) W_0(X) W 0 ( X ) [ C ] N × N [C]^{N \times N} [ C ] N × N f f f K K K h ( B ) ≤ f ( B ) + δ h(B) \le f(B) + \delta h ( B ) ≤ f ( B ) + δ B B B δ \delta δ h h h f f f max s p s ≤ max s f ( φ = s ) + δ \max_s p_s \le\max_s f(\varphi= s) + \delta max s p s ≤ max s f ( φ = s ) + δ P = N P = N P = N ε ( 2 r + N + 1 ) ≥ κ f − δ \varepsilon(2r + N + 1) \ge\kappa_f - \delta ε ( 2 r + N + 1 ) ≥ κ f − δ
The corollary on rare changes
The proof of Theorem 1 uses only the overlap graph of the locally valid patches, so it holds with K 0 = K ∖ J K_0 = K \setminus J K 0 = K ∖ J K K K K 0 K_0 K 0 K 0 K_0 K 0 h h h X X X D = 2 r + N + 1 D = 2r + N + 1 D = 2 r + N + 1 B s = { w ∈ K 0 : φ ( w ) = s } B_s = \{w \in K_0 : \varphi(w) = s\} B s = { w ∈ K 0 : φ ( w ) = s } K 0 K_0 K 0 ε + h ( J ) \varepsilon+ h(J) ε + h ( J ) P = N P = N P = N ( ε + h ( J ) ) D ≥ 1 − h ( B s ) (\varepsilon+ h(J))D \ge1 - h(B_s) ( ε + h ( J )) D ≥ 1 − h ( B s ) s s s h ( B s ) h(B_s) h ( B s ) h ( B ) ≤ f ( B ) + δ h(B) \le f(B) + \delta h ( B ) ≤ f ( B ) + δ B B B K K K J ∪ B s J \cup B_s J ∪ B s h ( B s ) ≤ θ + ( 1 − κ J ) + δ − h ( J ) h(B_s) \le\theta+ (1 - \kappa_J) + \delta- h(J) h ( B s ) ≤ θ + ( 1 − κ J ) + δ − h ( J ) ε D ≥ κ J − δ − ( D − 1 ) h ( J ) \varepsilon D \ge\kappa_J - \delta- (D - 1)h(J) ε D ≥ κ J − δ − ( D − 1 ) h ( J ) J J J h ( J ) ≤ θ + δ h(J) \le\theta+ \delta h ( J ) ≤ θ + δ ε D ≥ κ J − ( θ + δ ) D \varepsilon D \ge\kappa_J - (\theta+ \delta)D ε D ≥ κ J − ( θ + δ ) D J J J h ( J ) = 0 h(J) = 0 h ( J ) = 0 h ( B s ) ≤ 1 − κ f + δ h(B_s) \le1 - \kappa_f + \delta h ( B s ) ≤ 1 − κ f + δ
The linear program
Let P ≥ N P \ge N P ≥ N q q q V P V_P V P ( P − 1 ) × P (P - 1) \times P ( P − 1 ) × P P − 1 P - 1 P − 1 P − 1 P - 1 P − 1 P × ( P − 1 ) P \times(P - 1) P × ( P − 1 ) P − 1 P - 1 P − 1 P − 1 P - 1 P − 1 N × N N \times N N × N N × N N \times N N × N q q q X X X Q 0 P ( X ) Q_0^P(X) Q 0 P ( X ) V P V_P V P 0 0 0 N × N N \times N N × N X X X κ ( δ ) \kappa(\delta) κ ( δ ) q ( φ = s ) q(\varphi= s) q ( φ = s ) s s s q q q N × N N \times N N × N δ \delta δ f f f X X X δ \delta δ f f f max s p s ≤ 1 − κ ( δ ) \max_s p_s \le1 - \kappa(\delta) max s p s ≤ 1 − κ ( δ )
A one-way quantity. When φ \varphi φ f s f_s f s s s s κ f = 1 − ∑ s ⇝ t f s f t \kappa_f = 1 - \sum_{s\leadsto t} f_s f_t κ f = 1 − ∑ s ⇝ t f s f t κ ( δ ) \kappa(\delta) κ ( δ ) t t t s s s s s s t t t ∑ s p s ≤ 1 \sum_s p_s \le1 ∑ s p s ≤ 1 1 − ∑ s ⇝ t p s p t ≥ ∑ s ⇝̸ t p s p t 1-\sum_{s\leadsto t}p_sp_t \ge\sum_{s\not\leadsto t}p_sp_t 1 − ∑ s ⇝ t p s p t ≥ ∑ s ⇝ t p s p t δ \delta δ f f f p s p_s p s s s s
With defects. For P ≥ N P \ge N P ≥ N q q q Q P ( X ) Q^P(X) Q P ( X ) P × P P \times P P × P q V q_V q V V P V_P V P 1 − β 1-\beta 1 − β β ≤ ( P − N + 1 ) 2 ε \beta\le(P-N+1)^2\varepsilon β ≤ ( P − N + 1 ) 2 ε q q q V P V_P V P β \beta β β \beta β ( P − 1 ) × P (P-1) \times P ( P − 1 ) × P q V q_V q V 2 β 2\beta 2 β P × ( P − 1 ) P \times(P-1) P × ( P − 1 ) 4 β 4\beta 4 β N × N N \times N N × N q V q_V q V δ + β \delta+\beta δ + β f f f κ ( δ , η ) \kappa(\delta,\eta) κ ( δ , η ) φ \varphi φ q q q V P V_P V P [ 1 − η , 1 ] [1-\eta,1] [ 1 − η , 1 ] 2 η 2\eta 2 η N × N N \times N N × N δ + η \delta+\eta δ + η f f f η \eta η κ ( δ , 0 ) = κ ( δ ) \kappa(\delta,0)=\kappa(\delta) κ ( δ , 0 ) = κ ( δ ) q V q_V q V η = 2 β \eta=2\beta η = 2 β max s p s ≤ 1 − κ ( δ , 2 β ) \max_s p_s \le1-\kappa(\delta,2\beta) max s p s ≤ 1 − κ ( δ , 2 β ) η 0 ≥ 0 \eta_0 \ge0 η 0 ≥ 0
ε ≥ 1 ( P − N + 1 ) 2 min { η 0 2 , κ ( δ , η 0 ) 2 r + P + 1 } . \varepsilon\ge\frac{1}{(P-N+1)^2}\min\left\{\frac{\eta_0}{2},\frac{\kappa(\delta,\eta_0)}{2r+P+1}\right\}. ε ≥ ( P − N + 1 ) 2 1 min { 2 η 0 , 2 r + P + 1 κ ( δ , η 0 ) } . The program over exactly stationary measures, η = 0 \eta=0 η = 0 Table 8 reports. The table has 14 rows with an invariant or a phase: the 12 certified examples with one, and Chess and Stripes, two controls whose only K K K § 17 .§ 6 ). With defects allowed at η 0 = 0.01 \eta_0=0.01 η 0 = 0.01 δ = 0.05 \delta=0.05 δ = 0.05 1 / r 1/r 1/ r P = N P=N P = N κ f − δ \kappa_f-\delta κ f − δ κ ( 0.05 ) \kappa(0.05) κ ( 0.05 ) κ f − 0.05 = 0.015 \kappa_f-0.05=0.015 κ f − 0.05 = 0.015
Theorem 2
Let τ \tau τ e e e τ ′ \tau' τ ′ Z 2 \mathbb{Z}^2 Z 2 Z 2 \mathbb{Z}^2 Z 2 τ D \tau^D τ D D ≥ 1 D \ge1 D ≥ 1 X X X K K K e e e G P , e G_{P,e} G P , e
Invariants and phases. Under the full labeling φ = ( c , z ) \varphi=(c,z) φ = ( c , z ) σ ( c , z ) = ( c , z + 1 mod d c ) \sigma(c,z)=(c,z+1\mathbin{\operatorname{mod}}d_c) σ ( c , z ) = ( c , z + 1 mod d c ) ψ ( v ) = σ − j ( φ ( Q v P ( X ) ) ) \psi(v)=\sigma^{-j}(\varphi(Q^P_v(X))) ψ ( v ) = σ − j ( φ ( Q v P ( X ))) v = j e + v ′ v=je+v' v = j e + v ′ v ′ v' v ′ e e e e e e ψ \psi ψ λ \lambda λ d c 0 = 0 d_{c_0}=0 d c 0 = 0 e e e K K K d c ≥ 1 d_c \ge1 d c ≥ 1 d c d_c d c λ \lambda λ D D D d c ≥ 1 d_c \ge1 d c ≥ 1 σ D \sigma^D σ D λ ( τ D X ) = λ ( X ) \lambda(\tau^D X)=\lambda(X) λ ( τ D X ) = λ ( X ) { λ = s } \{\lambda=s\} { λ = s } τ D \tau^D τ D λ \lambda λ s 0 s_0 s 0 τ X \tau X τ X X X X λ ( τ X ) = σ ( λ ( X ) ) \lambda(\tau X)=\sigma(\lambda(X)) λ ( τ X ) = σ ( λ ( X )) σ ( s 0 ) = s 0 \sigma(s_0)=s_0 σ ( s 0 ) = s 0 d c 0 = 1 d_{c_0}=1 d c 0 = 1 c 0 c_0 c 0 s 0 s_0 s 0 τ m \tau^m τ m s 0 s_0 s 0 m m m φ = s 0 \varphi=s_0 φ = s 0
One-way quantities. Let φ \varphi φ m m m m − 1 m-1 m − 1 q q q v v v v + e v+e v + e n n n n q nq n q m − 1 m-1 m − 1 n n n q = 0 q=0 q = 0 φ \varphi φ
Statistics. With φ \varphi φ max s p s = 1 \max_s p_s=1 max s p s = 1 δ \delta δ f f f max s p s ≤ 1 − κ ( δ ) \max_s p_s \le1-\kappa(\delta) max s p s ≤ 1 − κ ( δ ) 1 − ∑ s ⇝̸ t p s p t ≥ κ ( δ ) 1-\sum_{s\not\leadsto t}p_sp_t \ge\kappa(\delta) 1 − ∑ s ⇝ t p s p t ≥ κ ( δ ) X X X δ \delta δ f f f κ ( δ ) > 0 \kappa(\delta)>0 κ ( δ ) > 0 P = N P=N P = N p s ≤ f ( φ = s ) + δ p_s \le f(\varphi=s)+\delta p s ≤ f ( φ = s ) + δ 1 ≤ 1 − κ f + δ 1 \le1-\kappa_f+\delta 1 ≤ 1 − κ f + δ δ ≥ κ f \delta\ge\kappa_f δ ≥ κ f
Proposition 1
In full, part (c) reads as follows. *Suppose every block has length at most T T T e e e T T T e e e e e e X v X_v X v e e e φ \varphi φ D ≥ 1 D \ge1 D ≥ 1 d c d_c d c μ \mu μ c c c d c d_c d c T T T d c = 0 d_c = 0 d c = 0
ε ≥ μ 2 ( 2 r + ( D + 1 ) T + P ) ( P − N + 1 ) 2 . \varepsilon\ge\frac{\mu}{2\left(2r+(D+1)T+P\right)\left(P-N+1\right)^2}. ε ≥ 2 ( 2 r + ( D + 1 ) T + P ) ( P − N + 1 ) 2 μ . Part (a) gives no floor when the quantity is fixed by position, and blocks fixed in absolute coordinates tell a rule its position, since it sees the coins change at a block boundary. A rule that leaves no forbidden window must fix the quantity by position. Two cells far apart along e e e T T T e e e d d d d d d T T T μ \mu μ T T T P = N P=N P = N δ \delta δ μ \mu μ δ \delta δ ℓ = ∞ \ell=\infty ℓ = ∞
(a) Follow the proof of Theorem 1 with k = ℓ + 2 r + P k=\ell+2r+P k = ℓ + 2 r + P u 0 u_0 u 0 [ − r , P − 1 + r ] [-r,P-1+r] [ − r , P − 1 + r ] e e e u k u_k u k [ k − r , k + P − 1 + r ] [k-r,k+P-1+r] [ k − r , k + P − 1 + r ] k − 2 r − P + 2 = ℓ + 2 k-2r-P+2=\ell+2 k − 2 r − P + 2 = ℓ + 2 P − 1 + r P-1+r P − 1 + r k − r k-r k − r ℓ \ell ℓ X X X p ( u 0 ) p^{(u_0)} p ( u 0 ) p ( u k ) p^{(u_k)} p ( u k ) p ∗ p^* p ∗ p s ( v ) p_s^{(v)} p s ( v ) Pr [ A ] ≤ ∑ s p s ( u 0 ) p σ k ( s ) ( u k ) ≤ p ∗ \Pr[A]\le\sum_s p_s^{(u_0)}p_{\sigma_k(s)}^{(u_k)}\le p^* Pr [ A ] ≤ ∑ s p s ( u 0 ) p σ k ( s ) ( u k ) ≤ p ∗ u u u Pr [ Q v P ∉ V P ] \Pr[Q^P_v\notin V_P] Pr [ Q v P ∈ / V P ] ( P − N + 1 ) 2 ε (P-N+1)^2\varepsilon ( P − N + 1 ) 2 ε ε \varepsilon ε 1 − p ∗ ≤ ( k + 1 ) ( P − N + 1 ) 2 ε 1-p^*\le(k+1)(P-N+1)^2\varepsilon 1 − p ∗ ≤ ( k + 1 ) ( P − N + 1 ) 2 ε (1) follow as before, with δ \delta δ f f f
(b) Since K K K f f f f f f N − 1 N-1 N − 1 2 ( N − 1 ) / ℓ 2(N-1)/\ell 2 ( N − 1 ) / ℓ ε ≤ 2 ( N − 1 ) / ℓ \varepsilon\le2(N-1)/\ell ε ≤ 2 ( N − 1 ) / ℓ 2 ( N − 1 ) / ℓ 2(N-1)/\ell 2 ( N − 1 ) / ℓ f f f
(c) Let G \mathcal{G} G e e e G \mathcal{G} G T e Te T e G \mathcal{G} G e e e T T T e e e G \mathcal{G} G X X X q s ( v ) = Pr [ Q v P ∈ V P , φ ( Q v P ) = s ∣ G ] q_s(v)=\Pr[Q^P_v\in V_P,\varphi(Q^P_v)=s\mid\mathcal{G}] q s ( v ) = Pr [ Q v P ∈ V P , φ ( Q v P ) = s ∣ G ] q s ( v + T e ) = q s ( v ) q_s(v+Te)=q_s(v) q s ( v + T e ) = q s ( v ) k k k k ≡ 1 ( m o d D ) k\equiv1\pmod D k ≡ 1 ( mod D ) k T ≥ 2 r + T + P kT\ge2r+T+P k T ≥ 2 r + T + P k T + 1 ≤ 2 r + ( D + 1 ) T + P kT+1\le2r+(D+1)T+P k T + 1 ≤ 2 r + ( D + 1 ) T + P k k k D − 1 D-1 D − 1 ⌈ ( 2 r + T + P ) / T ⌉ \lceil(2r+T+P)/T\rceil ⌈( 2 r + T + P ) / T ⌉ u k = u 0 + k T e u_k=u_0+kTe u k = u 0 + k T e u 0 u_0 u 0 u k u_k u k G \mathcal{G} G G \mathcal{G} G A A A φ ( Q u k P ) = σ k T ( φ ( Q u 0 P ) ) \varphi(Q^P_{u_k})=\sigma^{kT}(\varphi(Q^P_{u_0})) φ ( Q u k P ) = σ k T ( φ ( Q u 0 P )) q = q ( u 0 ) q=q(u_0) q = q ( u 0 )
Pr [ A ∣ G ] ≤ ∑ s q s q σ k T ( s ) . \Pr[A\mid\mathcal{G}]\le\sum_s q_s q_{\sigma^{kT}(s)}. Pr [ A ∣ G ] ≤ s ∑ q s q σ k T ( s ) . On a component with d c ≥ 1 d_c\ge1 d c ≥ 1 σ k T = σ T \sigma^{kT}=\sigma^T σ k T = σ T k T ≡ T ( m o d d c ) kT\equiv T\pmod{d_c} k T ≡ T ( mod d c ) d c d_c d c T T T σ k T \sigma^{kT} σ k T Q c = ∑ s ∈ c q s Q_c=\sum_{s\in c}q_s Q c = ∑ s ∈ c q s σ k T = σ T \sigma^{kT}=\sigma^T σ k T = σ T T m o d d c ≠ 0 T\bmod d_c\ne0 T mod d c = 0 d c = 0 d_c=0 d c = 0 σ k T \sigma^{kT} σ k T k T ≥ 1 kT\ge1 k T ≥ 1 σ k T \sigma^{kT} σ k T π \pi π ( ∑ s q s ) 2 ≥ ∑ s q s 2 + ∑ s q s q π ( s ) ≥ 2 ∑ s q s q π ( s ) \left(\sum_s q_s\right)^2\ge\sum_s q_s^2+\sum_s q_s q_{\pi(s)}\ge2\sum_s q_s q_{\pi(s)} ( ∑ s q s ) 2 ≥ ∑ s q s 2 + ∑ s q s q π ( s ) ≥ 2 ∑ s q s q π ( s ) ( s , π ( s ) ) (s,\pi(s)) ( s , π ( s )) q s q π ( s ) ≤ ( q s 2 + q π ( s ) 2 ) / 2 q_s q_{\pi(s)}\le(q_s^2+q_{\pi(s)}^2)/2 q s q π ( s ) ≤ ( q s 2 + q π ( s ) 2 ) /2 Q c 2 / 2 ≤ Q c / 2 Q_c^2/2\le Q_c/2 Q c 2 /2 ≤ Q c /2 Pr [ A ∣ G ] ≤ 1 − μ G / 2 \Pr[A\mid\mathcal{G}]\le1-\mu_{\mathcal{G}}/2 Pr [ A ∣ G ] ≤ 1 − μ G /2 μ G \mu_{\mathcal{G}} μ G u 0 u_0 u 0 d c d_c d c T T T Pr [ A c ] \Pr[A^c] Pr [ A c ] u 0 u_0 u 0 φ \varphi φ u 0 u_0 u 0 μ / 2 ≤ ( k T + 1 ) ( P − N + 1 ) 2 ε \mu/2 \le(kT+1)(P-N+1)^2\varepsilon μ /2 ≤ ( k T + 1 ) ( P − N + 1 ) 2 ε § 13 .§ 11 evaluates.
Proposition 2
Proposition 2. Let ω v = ( U v , t v ) \omega_v=(U_v,t_v) ω v = ( U v , t v ) U v U_v U v [ 0 , 1 ] [0,1] [ 0 , 1 ] t v t_v t v Y Y Y B r ( v ) = { v + u : ∥ u ∥ ∞ ≤ r } B_r(v)=\{v+u:\lVert u\rVert_\infty\le r\} B r ( v ) = { v + u : ∥ u ∥ ∞ ≤ r } m v m_v m v B r ( v ) B_r(v) B r ( v ) X v = Y ( v − m v + t m v ) X_v=Y(v-m_v+t_{m_v}) X v = Y ( v − m v + t m v ) X v X_v X v B r ( v ) B_r(v) B r ( v ) X X X r r r
Fix a window, the N × N N\times N N × N W W W w w w B r ( v ) B_r(v) B r ( v ) v ∈ W v\in W v ∈ W U U U 2 r + N 2r+N 2 r + N I I I 2 r + 2 − N 2r+2-N 2 r + 2 − N r ≥ N r\ge N r ≥ N z z z U U U z ∈ I z\in I z ∈ I z z z m v = z m_v=z m v = z v ∈ W v\in W v ∈ W m v = z m_v=z m v = z v ∈ W v\in W v ∈ W z ′ ∈ I z'\in I z ′ ∈ I z ′ z' z ′ U U U z ′ = z z'=z z ′ = z z z z U U U W W W ∣ I ∣ / ∣ U ∣ = 1 − q r |I|/|U|=1-q_r ∣ I ∣/∣ U ∣ = 1 − q r X X X w w w Y Y Y w − z + t z w-z+t_z w − z + t z z z z t z t_z t z f f f ε ≤ q r \varepsilon\le q_r ε ≤ q r h h h ( 1 − q r ) f + q r g (1-q_r)f+q_rg ( 1 − q r ) f + q r g g g g ∥ h − f ∥ T V = q r ∥ g − f ∥ T V ≤ q r \lVert h-f\rVert_{\mathrm{TV}}=q_r\lVert g-f\rVert_{\mathrm{TV}}\le q_r ∥ h − f ∥ TV = q r ∥ g − f ∥ TV ≤ q r a = ( 2 r + 2 − N ) / ( 2 r + N ) a=(2r+2-N)/(2r+N) a = ( 2 r + 2 − N ) / ( 2 r + N ) ( 0 , 1 ) (0,1) ( 0 , 1 ) 2 ≤ N ≤ r 2\le N\le r 2 ≤ N ≤ r q r = ( 1 − a ) ( 1 + a ) < 2 ( 1 − a ) = 4 ( N − 1 ) / ( 2 r + N ) q_r=(1-a)(1+a)<2(1-a)=4(N-1)/(2r+N) q r = ( 1 − a ) ( 1 + a ) < 2 ( 1 − a ) = 4 ( N − 1 ) / ( 2 r + N )
For the comparison in § 3 , let P = N P=N P = N r r r q r q_r q r f f f ε ≥ ( κ f − q r ) / ( 2 r + N + 1 ) \varepsilon\ge(\kappa_f-q_r)/(2r+N+1) ε ≥ ( κ f − q r ) / ( 2 r + N + 1 ) q ↦ q ( 2 r + N + 1 ) / ( κ f − q ) q\mapsto q(2r+N+1)/(\kappa_f-q) q ↦ q ( 2 r + N + 1 ) / ( κ f − q ) [ 0 , κ f ) [0,\kappa_f) [ 0 , κ f ) κ f ( 2 r + N ) > 4 ( N − 1 ) \kappa_f(2r+N)>4(N-1) κ f ( 2 r + N ) > 4 ( N − 1 ) ε \varepsilon ε
4 ( N − 1 ) ( 2 r + N + 1 ) κ f ( 2 r + N ) − 4 ( N − 1 ) . \frac{4(N-1)(2r+N+1)}{\kappa_f(2r+N)-4(N-1)}. κ f ( 2 r + N ) − 4 ( N − 1 ) 4 ( N − 1 ) ( 2 r + N + 1 ) . which tends to 4 ( N − 1 ) / κ f 4(N-1)/\kappa_f 4 ( N − 1 ) / κ f r r r
What the bounds bind in our pipeline
Theorems 1 and 2 bind generators on independent coins, among them the independent-coin rule of § 3 , with or without its repair rounds. They do not bind the method. Its row types and the octaves’ coins of whole rows are shared along whole lines, which escape both theorems and Proposition 1(a), and its phase channels, the coordinates modulo the certified period d d d d d d § 6 ), fall under Proposition 1(c) as a whole: their coins of finite scale lie on blocks nested in one lattice of period T = 16 T=16 T = 16 T T T § 3 above that threshold on any certified example, so no result there requires the mended independent-coin rule to be invalid; where we searched for witnesses, they show why it is (§ 8.1 ).
These conclusions rest on the following values. The rule runs 32 rounds of a radius-one update, so its radius is 32, and each of its four repair rounds adds N N N ℓ = 48 \ell=48 ℓ = 48 § 16 .§ 3 ), so the reach of the whole pipeline is r = 804 r=804 r = 804 § 2 ).
Fabric under the octaves. Fabric’s phase has period 5 and is read off single windows, so P = N P=N P = N T = 16 T=16 T = 16 D = 5 D=5 D = 5 T T T μ f \mu_f μ f k = 6 k=6 k = 6 2 ( k T + 1 ) ( P − N + 1 ) 2 = 194 2(kT+1)(P-N+1)^2=194 2 ( k T + 1 ) ( P − N + 1 ) 2 = 194 3.0 ⋅ 10 − 3 3.0\cdot10^{-3} 3.0 ⋅ 1 0 − 3 1.6 ⋅ 10 − 3 1.6\cdot10^{-3} 1.6 ⋅ 1 0 − 3 T T T T T T 1.5 ⋅ 10 − 4 1.5\cdot10^{-4} 1.5 ⋅ 1 0 − 4
The mended independent-coin rule. The mender’s randomness is hashed from the seed and the coordinates of its blocks, of side ℓ \ell ℓ ( 2 r + ℓ + P + 1 ) ( P − N + 1 ) 2 (2r+\ell+P+1)(P-N+1)^2 ( 2 r + ℓ + P + 1 ) ( P − N + 1 ) 2 P = N P=N P = N Table 8 with an invariant or a phase is the column κ ( 0 ) \kappa(0) κ ( 0 ) κ f \kappa_f κ f P = N P=N P = N 4.6 ⋅ 10 − 4 4.6\cdot10^{-4} 4.6 ⋅ 1 0 − 4
Two classes of constraints
Section 3 cites the following two bounds. Let ε ( r ) \varepsilon(r) ε ( r ) r r r
Proposition 3 (two classes). (a) If the locally checkable labeling of K K K O ( log ∗ n ) O(\log^* n) O ( log ∗ n ) n × n n\times n n × n ε ( r ) ≤ C e − c r \varepsilon(r)\le Ce^{-cr} ε ( r ) ≤ C e − cr C , c > 0 C,c>0 C , c > 0 K K K K K K P ≥ N P\ge N P ≥ N P × P P\times P P × P m ≥ 2 m\ge2 m ≥ 2 P × ( P − 1 ) P\times(P-1) P × ( P − 1 ) ( P − 1 ) × P (P-1)\times P ( P − 1 ) × P ε ( r ) ≥ 1 / ( 2 ( 2 r + P + 1 ) ( P − N + 1 ) 2 ) \varepsilon(r)\ge1/(2(2r+P+1)(P-N+1)^2) ε ( r ) ≥ 1/ ( 2 ( 2 r + P + 1 ) ( P − N + 1 ) 2 )
Proof of (a). Brandt et al. [11 ] show that such a K K K A ′ ∘ S k A'\circ S_k A ′ ∘ S k k k k ρ 0 \rho_0 ρ 0 Δ = ( 2 k + 1 ) 2 − 1 \Delta=(2k+1)^2-1 Δ = ( 2 k + 1 ) 2 − 1 Δ + 1 \Delta+1 Δ + 1 1 / ( Δ + 1 ) 1/(\Delta+1) 1/ ( Δ + 1 ) t t t ( 1 − 1 / ( Δ + 1 ) ) t (1-1/(\Delta+1))^t ( 1 − 1/ ( Δ + 1 ) ) t t t t A ′ A' A ′ ρ 0 + k \rho_0+k ρ 0 + k A ′ A' A ′ ρ 0 \rho_0 ρ 0 k k k C ( 1 − 1 / ( Δ + 1 ) ) t C(1-1/(\Delta+1))^t C ( 1 − 1/ ( Δ + 1 ) ) t C = ( 2 ρ 0 + 2 k + 1 ) 2 C=(2\rho_0+2k+1)^2 C = ( 2 ρ 0 + 2 k + 1 ) 2 O ( k t ) = r O(kt)=r O ( k t ) = r [11 ] prove the normal form correct on all sufficiently large tori; since A ′ A' A ′ k k k r r r 1 / tower ( c r ) 1/\operatorname{tower}(cr) 1/ tower ( cr ) [20 ] , Cor. 3.3), and cutting it off at radius r r r ε ( r ) ≤ C / tower ( c r ) \varepsilon(r)\le C/\operatorname{tower}(cr) ε ( r ) ≤ C / tower ( cr )
Proof of (b). The phase of a locally valid patch, the index of the translate it comes from, is a transported quantity along every lattice direction, with σ \sigma σ m ≥ 2 m\ge2 m ≥ 2 e e e σ \sigma σ e e e Pr [ phase ( v ) = i ] = Pr [ phase ( v + e ) = i ] \Pr[\operatorname{phase}(v)=i]=\Pr[\operatorname{phase}(v+e)=i] Pr [ phase ( v ) = i ] = Pr [ phase ( v + e ) = i ] v + e v+e v + e σ ( i ) ≠ i \sigma(i)\ne i σ ( i ) = i 1 2 \frac{1}{2} 2 1 max i p i ≤ 1 2 \max_i p_i\le\frac{1}{2} max i p i ≤ 2 1 e e e
The same argument shows that a forced edit on an agreement constraint can need an unbounded repair: pin a cell to a phase its neighborhood does not have, and any valid completion within radius ρ \rho ρ § 13 .11 in its simplest form.
Witnesses
A transported quantity can also prove that a particular mending instance has no completion. A mending instance frees the cells of a region F F F F F F a a a b b b u u u u + k e u+ke u + k e F F F Q u + j e P Q^P_{u+je} Q u + j e P 0 ≤ j ≤ k 0\le j\le k 0 ≤ j ≤ k F F F φ ( b ) = σ k ( φ ( a ) ) \varphi(b)=\sigma^k(\varphi(a)) φ ( b ) = σ k ( φ ( a )) φ ( b ) ≠ σ k ( φ ( a ) ) \varphi(b)\ne\sigma^k(\varphi(a)) φ ( b ) = σ k ( φ ( a )) witness : it proves without any search that the instance has no completion (Figure 2 (d); Appendix § 20 .§ 1 counts the witnesses on the failed instances). □
A sequence of row types at finite radius
Coins shared along whole rows can carry an invariant along rows at finite radius, once the rule turns them into an allowed sequence of row types, one in which every two consecutive types can be consecutive in a coloring free of forbidden windows. Suppose some type τ \tau τ x 1 , … , x m x_1,\ldots,x_m x 1 , … , x m τ , x 1 , … , x m , τ \tau,x_1,\ldots,x_m,\tau τ , x 1 , … , x m , τ M M M y y y U y U_y U y y y y start if U y < U y ′ U_y < U_{y'} U y < U y ′ y ′ y' y ′ M M M y + 1 y+1 y + 1 y + m y+m y + m y y y y y y τ \tau τ M M M M M M τ \tau τ M M M z z z z − M z-M z − M z − 1 z-1 z − 1 2 M 2M 2 M z z z
The certificate search
On every public example where the search of § 6 reports a phase, and on Chess and Stripes, d c d_c d c c c c d c d_c d c P + 1 P+1 P + 1 § 19 ). Appendix § 15 gives the order in which the search tries patch sizes and directions.
Proofs of the characterization
Theorems 1 and 2 bound generators whose distant cells share no randomness. Run given the coins that a generator shares along the quantity’s direction, their two arguments prove Theorem 3, and where the example’s rows glue, a generator that reads the row types band by band, and its position, needs nothing more (Theorem 4).
The setting
We read Definition 1 as follows. The input of a generator in the general form consists of finitely many families of coins. A family is a lattice of blocks fixed in absolute coordinates, every block a rectangle, possibly unbounded in one direction or in both; each block carries a vector of coins, and these vectors are i.i.d. within a family and independent across families. The cells’ own coins form one family, whose blocks are single cells, and so does every scale pair of § 2 and every further lattice of Definition 1. Cell v v v v m o d p v\bmod p v mod p v + [ − r , r ] 2 v+[-r,r]^2 v + [ − r , r ] 2
Fix an axis direction e e e extent of a family along e e e e e e 2 i 2^i 2 i 2 j 2^j 2 j ( i , j ) (i,j) ( i , j ) w w w e e e w w w e e e shared along e e e G e \mathcal{G}_e G e e e e σ \sigma σ ℓ \ell ℓ
For a translation t t t Z 2 \mathbb{Z}^2 Z 2 τ t \tau_t τ t ( τ t x ) v = x v + t (\tau_t x)_v=x_{v+t} ( τ t x ) v = x v + t θ t \theta_t θ t B B B B + t B+t B + t § 3 , Λ \Lambda Λ t ∈ p Z 2 t\in p\mathbb{Z}^2 t ∈ p Z 2 T T T T e ∈ Λ Te\in\Lambda T e ∈ Λ t ∈ Λ t\in\Lambda t ∈ Λ v v v X ( θ t ω ) X(\theta_t\omega) X ( θ t ω ) v + t v+t v + t X ( ω ) X(\omega) X ( ω ) v m o d p = ( v + t ) m o d p v\bmod p=(v+t)\bmod p v mod p = ( v + t ) mod p
X ( θ t ω ) = τ t X ( ω ) ( t ∈ Λ ) . (2) X(\theta_t\omega)=\tau_t X(\omega)\qquad(t\in\Lambda). \tag*{(2)} X ( θ t ω ) = τ t X ( ω ) ( t ∈ Λ ) . (2) This is what it means for X X X Λ \Lambda Λ X X X p p p θ t \theta_t θ t X X X τ t \tau_t τ t t ∈ Λ t\in\Lambda t ∈ Λ a a a Λ \Lambda Λ v v v v _v v a ( v ) a(v) a ( v ) Λ \Lambda Λ v _v v a ( v + u ) a(v+u) a ( v + u ) v _v v a ( v ) a(v) a ( v ) u ∈ Z 2 u \in\mathbb{Z}^2 u ∈ Z 2 ε = avg v Pr [ W v ( X ) ∉ K ] \varepsilon= \operatorname{avg}_v \Pr[W_v(X) \notin K] ε = avg v Pr [ W v ( X ) ∈ / K ] a ( v ) a(v) a ( v ) 1 − max s q s ( v ) 1-\max_s q_s(v) 1 − max s q s ( v ) a ˉ = avg v E [ a ( v ) ] \bar{a} = \operatorname{avg}_v \mathbb{E}[a(v)] a ˉ = avg v E [ a ( v )] Λ \Lambda Λ θ t \theta_t θ t G e \mathcal{G}_e G e G e \mathcal{G}_e G e
Theorem 3(b): the floor given the shared coins
In full, part (b) reads as follows. If φ \varphi φ X X X r r r G e \mathcal{G}_e G e ℓ \ell ℓ e e e
ε ≥ 1 − max s q s ( 2 r + P + ℓ ) ( P − N + 1 ) 2 . \varepsilon\ge\frac{1-\max_s q_s}{(2r+P+\ell)(P-N+1)^2}. ε ≥ ( 2 r + P + ℓ ) ( P − N + 1 ) 2 1 − max s q s . where q s ( v ) q_s(v) q s ( v ) G e \mathcal{G}_e G e P × P P \times P P × P X X X v v v φ = s \varphi=s φ = s Λ \Lambda Λ
The counting argument of Theorem 1 needs two patches far apart along e e e G e \mathcal{G}_e G e
Lemma 1. Let X X X r r r G e \mathcal{G}_e G e ℓ \ell ℓ e e e k ≥ 2 r + P + ℓ − 1 k \ge2r+P+\ell-1 k ≥ 2 r + P + ℓ − 1 v v v Q v P ( X ) Q_v^P(X) Q v P ( X ) Q v + k e P ( X ) Q_{v+ke}^P(X) Q v + k e P ( X ) G e \mathcal{G}_e G e
Proof. The patch at v v v v m o d p v \bmod p v mod p G e \mathcal{G}_e G e v + [ − r , P − 1 + r ] 2 v+[-r,P-1+r]^2 v + [ − r , P − 1 + r ] 2 v + k e v+ke v + k e k e ke k e v v v e e e − r -r − r P − 1 + r P-1+r P − 1 + r k − r k-r k − r k + P − 1 + r k+P-1+r k + P − 1 + r e e e P − 1 + r P-1+r P − 1 + r k − r k-r k − r k − 2 r − P + 2 ≥ ℓ + 1 k-2r-P+2 \ge\ell+1 k − 2 r − P + 2 ≥ ℓ + 1 G e \mathcal{G}_e G e G e \mathcal{G}_e G e G e \mathcal{G}_e G e
As in Theorem 3, q s ( v ) q_s(v) q s ( v ) G e \mathcal{G}_e G e Q v P ( X ) Q_v^P(X) Q v P ( X ) φ = s \varphi=s φ = s
Proposition 4 (the floor given the shared coins, sharp form). Under the assumptions of Lemma 1, for a transported quantity φ \varphi φ e e e σ \sigma σ
ε ( k + 1 ) ( P − N + 1 ) 2 ≥ avg v E [ 1 − ∑ s q s ( v ) q σ k ( s ) ( v + k e ) ] . (3) \varepsilon(k+1)(P-N+1)^2
\ge\operatorname{avg}_v \mathbb{E}\left[1-\sum_s q_s(v)q_{\sigma^k(s)}(v+ke)\right]. \tag*{(3)} ε ( k + 1 ) ( P − N + 1 ) 2 ≥ avg v E [ 1 − s ∑ q s ( v ) q σ k ( s ) ( v + k e ) ] . (3) and for a one-way quantity the same holds with ∑ s ⇝ t q s ( v ) q t ( v + k e ) \sum_{s\leadsto t}q_s(v)q_t(v+ke) ∑ s ⇝ t q s ( v ) q t ( v + k e )
Proof. Let A A A k + 1 k+1 k + 1 Q v + j e P ( X ) Q_{v+je}^P(X) Q v + j e P ( X ) 0 ≤ j ≤ k 0 \le j \le k 0 ≤ j ≤ k A A A G P , e G_{P,e} G P , e φ ( Q v + k e P ( X ) ) = σ k ( φ ( Q v P ( X ) ) ) \varphi(Q_{v+ke}^P(X))=\sigma^k(\varphi(Q_v^P(X))) φ ( Q v + k e P ( X )) = σ k ( φ ( Q v P ( X )))
Pr [ A ∣ G e ] ≤ ∑ s Pr [ φ ( Q v P ) = s , φ ( Q v + k e P ) = σ k ( s ) ∣ G e ] = ∑ s q s ( v ) q σ k ( s ) ( v + k e ) , \begin{aligned}
\Pr[A\mid\mathcal{G}_e]\le\sum_s \Pr\left[\varphi(Q_v^P)=s,\ \varphi(Q_{v+ke}^P)=\sigma^k(s)\mid\mathcal{G}_e\right] \\
&= \sum_s q_s(v)q_{\sigma^k(s)}(v+ke),
\end{aligned} Pr [ A ∣ G e ] ≤ s ∑ Pr [ φ ( Q v P ) = s , φ ( Q v + k e P ) = σ k ( s ) ∣ G e ] = s ∑ q s ( v ) q σ k ( s ) ( v + k e ) , where each event includes that both patches are locally valid. If A A A k + 1 k+1 k + 1 ( P − N + 1 ) 2 (P-N+1)^2 ( P − N + 1 ) 2 Pr [ A c ] ≤ ∑ j = 0 k ∑ u Pr [ W v + j e + u ( X ) ∉ K ] \Pr[A^c]\le\sum_{j=0}^k\sum_u \Pr[W_{v+je+u}(X)\notin K] Pr [ A c ] ≤ ∑ j = 0 k ∑ u Pr [ W v + j e + u ( X ) ∈ / K ] u u u v v v Λ \Lambda Λ ( k + 1 ) ( P − N + 1 ) 2 (k+1)(P-N+1)^2 ( k + 1 ) ( P − N + 1 ) 2 ε \varepsilon ε avg v E [ 1 − ∑ s q s ( v ) q σ k ( s ) ( v + k e ) ] ≤ avg v Pr [ A c ] ≤ ( k + 1 ) ( P − N + 1 ) 2 ε \operatorname{avg}_v\mathbb{E}\left[1-\sum_s q_s(v)q_{\sigma^k(s)}(v+ke)\right]\le\operatorname{avg}_v\Pr[A^c]\le(k+1)(P-N+1)^2\varepsilon avg v E [ 1 − ∑ s q s ( v ) q σ k ( s ) ( v + k e ) ] ≤ avg v Pr [ A c ] ≤ ( k + 1 ) ( P − N + 1 ) 2 ε A A A v + k e v+ke v + k e v v v
Proof of Theorem 3(b). Since σ k \sigma^k σ k ∑ s q s ( v ) q σ k ( s ) ( v + k e ) ≤ max s q s ( v ) ∑ t q t ( v + k e ) ≤ max s q s ( v ) \sum_s q_s(v)q_{\sigma^k(s)}(v+ke)\le\max_s q_s(v)\sum_t q_t(v+ke)\le\max_s q_s(v) ∑ s q s ( v ) q σ k ( s ) ( v + k e ) ≤ max s q s ( v ) ∑ t q t ( v + k e ) ≤ max s q s ( v ) k = 2 r + P + ℓ − 1 k=2r+P+\ell-1 k = 2 r + P + ℓ − 1
For a one-way quantity the sum over the pairs s ⇝ t s\leadsto t s ⇝ t max s q s ( v ) \max_s q_s(v) max s q s ( v )
Defects, fidelity and what is shared. Let p s ( v ) = E [ q s ( v ) ] p_s(v)=\mathbb{E}[q_s(v)] p s ( v ) = E [ q s ( v )] v v v φ = s \varphi=s φ = s v v v
I ( v ) = E [ max s q s ( v ) ] − max s p s ( v ) ≥ 0 , I(v)=\mathbb{E}\left[\max_s q_s(v)\right]-\max_s p_s(v)\ge0, I ( v ) = E [ s max q s ( v ) ] − s max p s ( v ) ≥ 0 , is how much knowing G e \mathcal{G}_e G e φ \varphi φ v v v E [ 1 − max s q s ( v ) ] = 1 − max s p s ( v ) − I ( v ) \mathbb{E}[1-\max_s q_s(v)]=1-\max_s p_s(v)-I(v) E [ 1 − max s q s ( v )] = 1 − max s p s ( v ) − I ( v ) ϵ ( 2 r + P + ℓ ) ( P − N + 1 ) 2 + avg v I ( v ) ≥ avg v ( 1 − max s p s ( v ) ) \epsilon(2r+P+\ell)(P-N+1)^2+\operatorname{avg}_v I(v)\ge\operatorname{avg}_v(1-\max_s p_s(v)) ϵ ( 2 r + P + ℓ ) ( P − N + 1 ) 2 + avg v I ( v ) ≥ avg v ( 1 − max s p s ( v )) P = N P=N P = N δ v \delta_v δ v W v ( X ) W_v(X) W v ( X ) f f f p s ( v ) ≤ f ( φ = s ) + δ v p_s(v)\le f(\varphi=s)+\delta_v p s ( v ) ≤ f ( φ = s ) + δ v 1 − max s p s ( v ) ≥ κ f − δ v 1-\max_s p_s(v)\ge\kappa_f-\delta_v 1 − max s p s ( v ) ≥ κ f − δ v δ ˉ = avg v δ v \bar{\delta}=\operatorname{avg}_v\delta_v δ ˉ = avg v δ v I ˉ = avg v I ( v ) \bar{I}=\operatorname{avg}_v I(v) I ˉ = avg v I ( v )
ϵ ( 2 r + N + ℓ ) + δ ˉ + I ˉ ≥ κ f . (4) \epsilon(2r+N+\ell)+\bar{\delta}+\bar{I}\ge\kappa_f. \tag*{(4)} ϵ ( 2 r + N + ℓ ) + δ ˉ + I ˉ ≥ κ f . (4) A generator can thus meet the example’s spread κ f \kappa_f κ f f f f e e e I ˉ = 0 \bar{I}=0 I ˉ = 0 ℓ = 1 \ell=1 ℓ = 1 δ ˉ \bar{\delta} δ ˉ δ \delta δ f f f (4) is inequality (1). In general δ ˉ \bar{\delta} δ ˉ δ ˉ \bar{\delta} δ ˉ
The earlier floors as cases. When nothing is shared, G e \mathcal{G}_e G e ℓ = 1 \ell=1 ℓ = 1 q s ( v ) = p s q_s(v)=p_s q s ( v ) = p s e e e ℓ \ell ℓ G e \mathcal{G}_e G e q s ( v ) = p s ( v ) ≤ p ∗ q_s(v)=p_s(v)\le p^* q s ( v ) = p s ( v ) ≤ p ∗ 2 r + P + ℓ 2r+P+\ell 2 r + P + ℓ 2 r + ℓ + P + 1 2r+\ell+P+1 2 r + ℓ + P + 1 § 13 .§ 9 ) separates the two patches by one step more than they need.
Proposition 1(c) works by a different mechanism. There a rule may fix the quantity by its position given the shared coins, so that max s q s ( v ) = 1 \max_s q_s(v)=1 max s q s ( v ) = 1 T T T σ T \sigma^T σ T T T T T e Te T e G e \mathcal{G}_e G e q s ( v + T e ) = q s ( v ) q_s(v+Te)=q_s(v) q s ( v + T e ) = q s ( v ) k T kT k T § 13 .§ 9 , with k ≡ 1 k\equiv1 k ≡ 1 D D D d c d_c d c k T ≥ 2 r + T + P kT\ge2r+T+P k T ≥ 2 r + T + P 2 r + P + ℓ − 1 2r+P+\ell-1 2 r + P + ℓ − 1 G e \mathcal{G}_e G e T T T e e e ϵ ( k T + 1 ) ( P − N + 1 ) 2 ≥ avg v E [ 1 − ∑ s q s ( v ) q σ k T ( s ) ( v ) ] \epsilon(kT+1)(P-N+1)^2\ge\operatorname{avg}_v\mathbb{E}[1-\sum_s q_s(v)q_{\sigma^{kT}(s)}(v)] ϵ ( k T + 1 ) ( P − N + 1 ) 2 ≥ avg v E [ 1 − ∑ s q s ( v ) q σ k T ( s ) ( v )] § 13 .§ 9 bounds the sum by 1 − μ G / μ 1-\mu_G/\mu 1 − μ G / μ μ G \mu_G μ G T T T Λ \Lambda Λ e e e
Theorem 3(a): the quantity is a function of the shared coins
Theorem 2 uses ergodicity in place of a radius, and given G e \mathcal{G}_e G e e e e
The coins given G e \mathcal{G}_e G e Write the coins as ω = ( γ , ω ′ ) \omega=(\gamma,\omega') ω = ( γ , ω ′ ) γ \gamma γ G e \mathcal{G}_e G e ω ′ \omega' ω ′ ω ′ \omega' ω ′ e e e θ T e \theta_{Te} θ T e e e e γ \gamma γ θ T e \theta_{Te} θ T e ξ n \xi_n ξ n n n n ξ n \xi_n ξ n n ∈ Z n\in\mathbb{Z} n ∈ Z θ T e \theta_{Te} θ T e ( ξ n ) (\xi_n) ( ξ n ) θ T e \theta_{Te} θ T e ω ′ \omega' ω ′ θ D T e \theta_{DTe} θ D T e ω ′ \omega' ω ′ D ≥ 1 D\ge1 D ≥ 1 X ( γ , θ T e ω ′ ) = τ T e X ( γ , ω ′ ) X(\gamma,\theta_{Te}\omega')=\tau_{Te}X(\gamma,\omega') X ( γ , θ T e ω ′ ) = τ T e X ( γ , ω ′ ) γ \gamma γ ω ′ \omega' ω ′ γ \gamma γ E E E X X X K K K γ \gamma γ ω ′ \omega' ω ′ θ T e \theta_{Te} θ T e K K K K K K
Proof of part (a) for a transported quantity. Fix a cell v ′ v' v ′ e e e λ ( X ) = φ ( Q v ′ P ( X ) ) \lambda(X)=\varphi(Q_{v'}^P(X)) λ ( X ) = φ ( Q v ′ P ( X )) E E E v ′ v' v ′ e e e G P , e G_{P,e} G P , e
φ ( Q v ′ + j e P ( X ) ) = σ j ( λ ( X ) ) ( j ∈ Z ) . (5) \varphi\left(Q_{v'+je}^P(X)\right)=\sigma^j(\lambda(X))\qquad(j\in\mathbb{Z}). \tag*{(5)} φ ( Q v ′ + j e P ( X ) ) = σ j ( λ ( X )) ( j ∈ Z ) . (5) These patches form a bi-infinite walk in the finite graph G P , e G_{P,e} G P , e a a a m ≥ 1 m\ge1 m ≥ 1 φ ( a ) = σ m ( φ ( a ) ) \varphi(a)=\sigma^m(\varphi(a)) φ ( a ) = σ m ( φ ( a )) σ \sigma σ φ \varphi φ V P V_P V P D ≥ 1 D\ge1 D ≥ 1 σ D \sigma^D σ D λ \lambda λ E E E d c ≥ 1 d_c\ge1 d c ≥ 1 σ \sigma σ D D D j = T j=T j = T λ ( θ T e X ) = σ T ( λ ( X ) ) \lambda(\theta_{Te}X)=\sigma^T(\lambda(X)) λ ( θ T e X ) = σ T ( λ ( X )) E E E λ ( θ D T e X ) = λ ( X ) \lambda(\theta_{DTe}X)=\lambda(X) λ ( θ D T e X ) = λ ( X ) E E E γ \gamma γ ω ′ ↦ λ ( X ( γ , ω ′ ) ) \omega' \mapsto\lambda(X(\gamma,\omega')) ω ′ ↦ λ ( X ( γ , ω ′ )) θ D T e \theta_{DT e} θ D T e E E E h ( v ′ , γ ) h(v',\gamma) h ( v ′ , γ ) γ \gamma γ s s s Pr [ λ ( X ) = s ∣ G e ] = 1 \Pr[\lambda(X)=s \mid\mathcal{G}_e]=1 Pr [ λ ( X ) = s ∣ G e ] = 1 ω ′ \omega' ω ′ θ T e ω ′ \theta_{T e}\omega' θ T e ω ′ λ ( X ( γ , θ T e ω ′ ) ) = σ T ( λ ( X ( γ , ω ′ ) ) ) \lambda(X(\gamma,\theta_{T e}\omega'))=\sigma^T(\lambda(X(\gamma,\omega'))) λ ( X ( γ , θ T e ω ′ )) = σ T ( λ ( X ( γ , ω ′ ))) λ ( X ( γ , ω ′ ) ) \lambda(X(\gamma,\omega')) λ ( X ( γ , ω ′ )) σ T ( h ( v ′ , γ ) ) = h ( v ′ , γ ) \sigma^T(h(v',\gamma))=h(v',\gamma) σ T ( h ( v ′ , γ )) = h ( v ′ , γ ) h v = σ j ∘ h ( v ′ , ⋅ ) h_v=\sigma^j\circ h(v',\cdot) h v = σ j ∘ h ( v ′ , ⋅ ) v = v ′ + j e v=v'+je v = v ′ + j e (5) , φ ( Q v P ( X ) ) = h v ( G e ) \varphi(Q^P_v(X))=h_v(\mathcal{G}_e) φ ( Q v P ( X )) = h v ( G e ) h v + e = σ ∘ h v h_{v+e}=\sigma\circ h_v h v + e = σ ∘ h v h v + T e = σ T ∘ h v = h v h_{v+T e}=\sigma^T\circ h_v=h_v h v + T e = σ T ∘ h v = h v
Proof of part (a) for a one-way quantity. Let φ \varphi φ m m m φ \varphi φ m − 1 m-1 m − 1 c j = 1 c_j=1 c j = 1 X ∈ E X\in E X ∈ E v ′ + j e v'+je v ′ + j e v ′ + ( j + 1 ) e v'+(j+1)e v ′ + ( j + 1 ) e c j = 0 c_j=0 c j = 0 γ \gamma γ X X X τ T e \tau_{T e} τ T e E [ c j + T ∣ γ ] = E [ c j ∣ γ ] \mathbb{E}[c_{j+T}\mid\gamma]=\mathbb{E}[c_j\mid\gamma] E [ c j + T ∣ γ ] = E [ c j ∣ γ ]
n ∑ j = 0 T − 1 E [ c j ∣ γ ] = E [ ∑ j = 0 n T − 1 c j ∣ γ ] ≤ m − 1 n\sum_{j=0}^{T-1}\mathbb{E}[c_j\mid\gamma]=\mathbb{E}\left[\sum_{j=0}^{nT-1}c_j\mid\gamma\right]\le m-1 n j = 0 ∑ T − 1 E [ c j ∣ γ ] = E [ j = 0 ∑ n T − 1 c j ∣ γ ] ≤ m − 1 for every n n n c j c_j c j φ \varphi φ e e e λ ( τ T e X ) = λ ( X ) \lambda(\tau_{T e}X)=\lambda(X) λ ( τ T e X ) = λ ( X ) θ T e \theta_{T e} θ T e γ \gamma γ { λ ( X ) = s } \{\lambda(X)=s\} { λ ( X ) = s } λ ( X ) \lambda(X) λ ( X ) h ( v ′ , G e ) h(v',\mathcal{G}_e) h ( v ′ , G e ) h v = h ( v ′ , ⋅ ) h_v=h(v',\cdot) h v = h ( v ′ , ⋅ ) v v v
Order parameters
The same argument needs no patch. Let Ω ′ \Omega' Ω ′ K K K τ e Ω ′ = Ω ′ \tau_e\Omega'=\Omega' τ e Ω ′ = Ω ′ V V V σ \sigma σ V V V Φ : Ω ′ → V \Phi:\Omega'\to V Φ : Ω ′ → V order parameter along e e e Φ ( τ e x ) = σ ( Φ ( x ) ) \Phi(\tau_e x)=\sigma(\Phi(x)) Φ ( τ e x ) = σ ( Φ ( x )) x ∈ Ω ′ x\in\Omega' x ∈ Ω ′ λ \lambda λ Ω ′ \Omega' Ω ′ K K K V V V σ \sigma σ φ \varphi φ
Proposition 5 (order parameters). Let X X X X ∈ Ω ′ X\in\Omega' X ∈ Ω ′ Φ \Phi Φ e e e Ω ′ \Omega' Ω ′ Φ ( X ) = h ( G e ) \Phi(X)=h(\mathcal{G}_e) Φ ( X ) = h ( G e ) h h h σ T ∘ h = h \sigma^T\circ h=h σ T ∘ h = h
Proof. Let D D D σ \sigma σ { X ∈ Ω ′ } \{X\in\Omega'\} { X ∈ Ω ′ } θ T e \theta_{T e} θ T e Φ ( τ D T e X ) = σ D T ( Φ ( X ) ) = Φ ( X ) \Phi(\tau_{DT e}X)=\sigma^{DT}(\Phi(X))=\Phi(X) Φ ( τ D T e X ) = σ D T ( Φ ( X )) = Φ ( X ) θ D T e \theta_{DT e} θ D T e γ \gamma γ Φ ( X ) \Phi(X) Φ ( X ) h ( γ ) h(\gamma) h ( γ ) ω ′ \omega' ω ′ θ T e \theta_{T e} θ T e σ T ( h ( γ ) ) = h ( γ ) \sigma^T(h(\gamma))=h(\gamma) σ T ( h ( γ )) = h ( γ )
SmileCity’s lattice of faces
SmileCity’s example has eight rows and eight columns. Its first and last rows and columns are black, and the six by six cells inside them hold a face in which no cell is black. In a coloring, call a face run a run of non-black cells in a row with a black cell at each end; in the tiled example every face run is six cells wide and starts at a column of one residue class modulo eight. Let Ω 1 \Omega_1 Ω 1 K K K Φ ( x ) ∈ Z / 8 \Phi(x)\in\mathbb{Z}/8 Φ ( x ) ∈ Z /8 offset of the faces of x x x e 1 e_1 e 1 e 2 e_2 e 2 Ω 1 \Omega_1 Ω 1
Φ ( τ e 1 x ) = Φ ( x ) − 1 , Φ ( τ e 2 x ) = Φ ( x ) ( x ∈ Ω 1 ) . \Phi(\tau_{e_1}x)=\Phi(x)-1,\qquad\Phi(\tau_{e_2}x)=\Phi(x)\qquad(x\in\Omega_1). Φ ( τ e 1 x ) = Φ ( x ) − 1 , Φ ( τ e 2 x ) = Φ ( x ) ( x ∈ Ω 1 ) . So Φ \Phi Φ σ \sigma σ s ↦ s − 1 s\mapsto s-1 s ↦ s − 1 σ \sigma σ K K K § 21 ), which is why the certificate search cannot find it.
What both the coins shared along rows and those shared along columns determine is determined by the coins they have in common.
Lemma 2. Let U U U U ′ U' U ′ Π \Pi Π Z Z Z Z = a ( U , Π ) Z=a(U,\Pi) Z = a ( U , Π ) Z = b ( U ′ , Π ) Z=b(U',\Pi) Z = b ( U ′ , Π ) a a a b b b Z = c ( Π ) Z=c(\Pi) Z = c ( Π ) c c c
Proof. The law of ( U , U ′ , Π ) (U,U',\Pi) ( U , U ′ , Π ) π \pi π Π \Pi Π a ( U , π ) = b ( U ′ , π ) a(U,\pi)=b(U',\pi) a ( U , π ) = b ( U ′ , π ) π \pi π s s s { a ( U , π ) = s } \{a(U,\pi)=s\} { a ( U , π ) = s } { b ( U ′ , π ) = s } \{b(U',\pi)=s\} { b ( U ′ , π ) = s } U U U U ′ U' U ′ a ( U , π ) a(U,\pi) a ( U , π ) c ( π ) c(\pi) c ( π ) s s s Pr [ a ( U , π ) = s ] = 1 \Pr[a(U,\pi)=s]=1 Pr [ a ( U , π ) = s ] = 1 π \pi π Z = c ( Π ) Z=c(\Pi) Z = c ( Π )
In the language of σ \sigma σ σ \sigma σ ( U , Π ) (U,\Pi) ( U , Π ) ( U ′ , Π ) (U',\Pi) ( U ′ , Π ) σ \sigma σ Π \Pi Π
Corollary 3 (SmileCity’s lattice). On SmileCity , let X X X K K K X ∈ Ω 1 X\in\Omega_1 X ∈ Ω 1 Φ ( X ) \Phi(X) Φ ( X ) Λ \Lambda Λ v v v v v v
Proof. By Proposition 5 along rows, Φ ( X ) = h 1 ( G e 1 ) \Phi(X)=h_1(\mathcal{G}_{e_1}) Φ ( X ) = h 1 ( G e 1 ) σ T 1 ∘ h 1 = h 1 \sigma^{T_1}\circ h_1=h_1 σ T 1 ∘ h 1 = h 1 h 1 − T 1 ≡ h 1 h_1-T_1\equiv h_1 h 1 − T 1 ≡ h 1 T 1 T_1 T 1 Λ \Lambda Λ T 1 T_1 T 1 Φ ( X ) = h 2 ( G e 2 ) \Phi(X)=h_2(\mathcal{G}_{e_2}) Φ ( X ) = h 2 ( G e 2 ) U U U U ′ U' U ′ Π \Pi Π G e 1 \mathcal{G}_{e_1} G e 1 ( U , Π ) (U,\Pi) ( U , Π ) G e 2 \mathcal{G}_{e_2} G e 2 ( U ′ , Π ) (U',\Pi) ( U ′ , Π ) Z = Φ ( X ) Z=\Phi(X) Z = Φ ( X ) Φ ( X ) = c ( Π ) \Phi(X)=c(\Pi) Φ ( X ) = c ( Π ) v v v Φ ( X ) \Phi(X) Φ ( X ) v v v Π \Pi Π Φ ( X ) \Phi(X) Φ ( X )
The hypothesis that the faces lie on one lattice cannot be dropped, since validity alone does not put them there. The example’s black first and last rows span the whole width, so a window that meets the two black rows between consecutive rows of faces sees at most one row of faces, and is a window of the tiled example at that row’s shift. Shifting each band of eight rows of the tiled example, the rows 8 b 8b 8 b 8 b + 7 8b+7 8 b + 7 K K K y y y G e 1 \mathcal{G}_{e_1} G e 1 y y y
Rigid layouts. Part (a) and Proposition 5 constrain a generator that shares nothing along e e e
Corollary 4 (rigid layouts). Let X X X K K K X X X e e e e e e Λ \Lambda Λ e e e X X X d c d_c d c T T T P = N P=N P = N X X X f f f
Proof. (a) With G e \mathcal{G}_e G e h v h_v h v h h h t ∈ Λ t\in\Lambda t ∈ Λ φ ( Q v + t P ( X ) ) = φ ( Q v P ( τ t X ) ) \varphi(Q^{P}_{v+t}(X))=\varphi(Q^{P}_{v}(\tau_tX)) φ ( Q v + t P ( X )) = φ ( Q v P ( τ t X )) τ t X = X ( θ ω ) \tau_tX=X(\theta\omega) τ t X = X ( θ ω ) X X X h v + t = h v h_{v+t}=h_v h v + t = h v ( c , z ) (c,z) ( c , z ) σ T \sigma^T σ T T T T d c d_c d c d c ≤ 1 d_c\leq1 d c ≤ 1 d c d_c d c T T T P = N P=N P = N X X X f f f
Part (a) is why a generator given the phase channels and no coin shared along the phase’s direction lays the phase out the same way for every seed. Part (b) is Proposition 1(c) without a radius. On Fabric, whose phase period 5 does not divide the octaves’ period T = 16 T=16 T = 16 T T T Λ \Lambda Λ
Theorem 4
Theorem 4 gives a generator free of forbidden windows that reads only the coin from which its band’s row types are drawn and its position.
Rows and strips. Let the example have H H H W W W Y c , c ∈ Z / H Y_{c,c}\in\mathbb{Z}/H Y c , c ∈ Z / H W W W R \mathcal{R} R τ s Y c \tau^sY_c τ s Y c s ∈ Z / W s\in\mathbb{Z}/W s ∈ Z / W H W HW H W R \mathcal{R} R N N N K K K W W W P P P P × P P\times P P × P G P , e G_{P,e} G P , e y y y P P P y − j 0 y-j_0 y − j 0 j 0 = ⌊ P / 2 ⌋ j_0=\lfloor P/2\rfloor j 0 = ⌊ P /2 ⌋
The sampler’s sequences. Band b b b b L bL b L b L + L − 1 bL+L-1 b L + L − 1 t 0 , … , t L + 1 t_0,\ldots,t_{L+1} t 0 , … , t L + 1 b L bL b L b L + L + 1 bL+L+1 b L + L + 1 ( t 0 , t 1 ) (t_0,t_1) ( t 0 , t 1 ) ( t L , t L + 1 ) (t_L,t_{L+1}) ( t L , t L + 1 ) α \alpha α W \mathcal{W} W
Realizations
A realization of w = ( t 0 , … , t L + 1 ) ∈ W w=(t_0,\ldots,t_{L+1})\in\mathcal{W} w = ( t 0 , … , t L + 1 ) ∈ W R 0 , … , R L + P − 2 R_0,\ldots,R_{L+P-2} R 0 , … , R L + P − 2 R \mathcal{R} R j = 0 , … , L − 1 j=0,\ldots,L-1 j = 0 , … , L − 1 P P P R j R_j R j t j + j 0 t_{j+j_0} t j + j 0 b L bL b L b L + L + P − 2 bL+L+P-2 b L + L + P − 2 b L + j bL+j b L + j y − j 0 y-j_0 y − j 0 y = b L + j + j 0 y=bL+j+j_0 y = b L + j + j 0 y y y b L + j 0 bL+j_0 b L + j 0 b L + L − 1 + j 0 bL+L-1+j_0 b L + L − 1 + j 0 t y − b L t_{y-bL} t y − b L w w w b L bL b L b L + j 0 − 1 bL+j_0-1 b L + j 0 − 1 b − 1 b-1 b − 1 w w w t L − 1 + j 0 t_{L-1+j_0} t L − 1 + j 0 j 0 ≤ 2 j_0\leq2 j 0 ≤ 2 P ≤ 5 P\leq5 P ≤ 5 P = 3 P=3 P = 3 P = 4 P=4 P = 4 P P P j 0 j_0 j 0
The example’s rows glue if there is a strip Z = ( Z 0 , … , Z P − 2 ) Z=(Z_0,\ldots,Z_{P-2}) Z = ( Z 0 , … , Z P − 2 ) R \mathcal{R} R w ∈ W w\in\mathcal{W} w ∈ W R 0 , … , R P − 2 R_0,\ldots,R_{P-2} R 0 , … , R P − 2 Z Z Z R L , … , R L + P − 2 R_L,\ldots,R_{L+P-2} R L , … , R L + P − 2 Z Z Z Z Z Z Z Z Z K K K Z Z Z
Proof of Theorem 4. Let the rows glue with the strip Z Z Z L ≥ P − 1 L\geq P-1 L ≥ P − 1 Table 2 ). The bands are the blocks of a lattice fixed in absolute coordinates, groups of L L L ω b \omega_b ω b b b b w ( b ) ∈ W w^{(b)}\in\mathcal{W} w ( b ) ∈ W ρ ( b ) = ( R 0 ( b ) , … , R L + P − 2 ( b ) ) \rho^{(b)}=(R_0^{(b)},\ldots,R_{L+P-2}^{(b)}) ρ ( b ) = ( R 0 ( b ) , … , R L + P − 2 ( b ) ) w ( b ) w^{(b)} w ( b ) Z Z Z X ( x , y ) = R y − b L ( b ) ( x ) X_{(x,y)}=R_{y-bL}^{(b)}(x) X ( x , y ) = R y − b L ( b ) ( x ) b L ≤ y < b L + L bL\leq y<bL+L b L ≤ y < b L + L ( x m o d W , y m o d L ) (x\bmod W,y\bmod L) ( x mod W , y mod L ) p p p W W W L L L X X X
Table 2. The gluing check on the eight examples with a row invariant, run after the copier’s results were known. For each example: the patch size P P P L L L Z Z Z
The rows ( b + 1 ) L (b+1)L ( b + 1 ) L ( b + 1 ) L + P − 2 (b+1)L+P-2 ( b + 1 ) L + P − 2 b + 1 b+1 b + 1 L ≥ P − 1 L\geq P-1 L ≥ P − 1 R 0 ( b + 1 ) , … , R P − 2 ( b + 1 ) R_0^{(b+1)},\ldots,R_{P-2}^{(b+1)} R 0 ( b + 1 ) , … , R P − 2 ( b + 1 ) Z Z Z R L ( b ) , … , R L + P − 2 ( b ) R_L^{(b)},\ldots,R_{L+P-2}^{(b)} R L ( b ) , … , R L + P − 2 ( b ) ρ ( b ) \rho^{(b)} ρ ( b ) b L bL b L b L + L + P − 2 bL+L+P-2 b L + L + P − 2 y y y b b b y y y y + N − 1 ≤ b L + L + N − 2 ≤ b L + L + P − 2 y+N-1\leq bL+L+N-2\leq bL+L+P-2 y + N − 1 ≤ b L + L + N − 2 ≤ b L + L + P − 2 ρ ( b ) \rho^{(b)} ρ ( b ) K K K P P P b b b y y y b L + j 0 bL+j_0 b L + j 0 b L + L − 1 + j 0 bL+L-1+j_0 b L + L − 1 + j 0 w ( b ) w^{(b)} w ( b )
The statistics of a generator that glues rows.
Suppose the rule records, with every row it outputs, the row c c c s s s τ s Y c \tau^sY_c τ s Y c stretch is a maximal run of output rows that copy consecutive rows c , c + 1 , … c,c+1,\ldots c , c + 1 , … cut is the boundary between two consecutive stretches. A cut is free if every strip of N N N N − 1 N-1 N − 1 N N N ρ c u t \rho_{\mathrm{cut}} ρ cut y y y N N N y y y y y y N N N ν ( c ) \nu(c) ν ( c ) c c c c c c ν ˉ = ν / ( 1 − ρ c u t ) \bar{\nu}=\nu/(1-\rho_{\mathrm{cut}}) ν ˉ = ν / ( 1 − ρ cut ) U H U_H U H H H H
Proposition 6 (statistics). The window statistics h X h_X h X ∥ h X − f ∥ T V ≤ ∥ ν ˉ − U H ∥ T V + ρ c u t \lVert h_X-f\rVert_{\mathrm{TV}}\leq\lVert\bar{\nu}-U_H\rVert_{\mathrm{TV}}+\rho_{\mathrm{cut}} ∥ h X − f ∥ TV ≤ ∥ ν ˉ − U H ∥ TV + ρ cut P = N P=N P = N K K K ∥ h X − f ∥ T V ≥ ∥ π S − π f ∥ T V \lVert h_X-f\rVert_{\mathrm{TV}}\geq\lVert\pi_S-\pi_f\rVert_{\mathrm{TV}} ∥ h X − f ∥ TV ≥ ∥ π S − π f ∥ TV π S \pi_S π S π f \pi_f π f
Proof. The law of X X X L L L p p p W W W c ∈ Z / H c\in\mathbb{Z}/H c ∈ Z / H f c f_c f c W W W c c c f = 1 H ∑ c f c f=\frac{1}{H}\sum_c f_c f = H 1 ∑ c f c y y y c c c f c f_c f c h X = ∑ c ν ( c ) f c + ρ c u t g h_X=\sum_c\nu(c)f_c+\rho_{\mathrm{cut}}g h X = ∑ c ν ( c ) f c + ρ cut g g g g
∥ h X − f ∥ T V ≤ 1 2 ∑ c ∣ ν ( c ) − 1 H ∣ + ρ c u t 2 ≤ ( 1 − ρ c u t ) ∥ ν ˉ − U H ∥ T V + ρ c u t . \begin{aligned}
\lVert h_X-f\rVert_{\mathrm{TV}}\leq\frac{1}{2}\sum_c\left|\nu(c)-\frac{1}{H}\right|+\frac{\rho_{\mathrm{cut}}}{2} \\
&\leq(1-\rho_{\mathrm{cut}})\lVert\bar{\nu}-U_H\rVert_{\mathrm{TV}}+\rho_{\mathrm{cut}}.
\end{aligned} ∥ h X − f ∥ TV ≤ 2 1 c ∑ ν ( c ) − H 1 + 2 ρ cut ≤ ( 1 − ρ cut ) ∥ ν ˉ − U H ∥ TV + ρ cut . using ∣ ν ( c ) − 1 H ∣ ≤ ∣ ν ( c ) − 1 − ρ c u t H ∣ + ρ c u t H |\nu(c)-\frac{1}{H}|\leq|\nu(c)-\frac{1-\rho_{\mathrm{cut}}}{H}|+\frac{\rho_{\mathrm{cut}}}{H} ∣ ν ( c ) − H 1 ∣ ≤ ∣ ν ( c ) − H 1 − ρ cut ∣ + H ρ cut P = N P=N P = N P P P y y y y y y y + j 0 y+j_0 y + j 0 h X h_X h X X X X π S \pi_S π S f f f π f \pi_f π f
The distance of such a generator from the example’s statistics thus has two sources: how often it uses each row of the example, which the sampled types largely fix, and the cuts that are not free. Where the sampler’s law of types differs from the example’s, as when the run limits draw free runs of lengths the example does not show, no generator that follows the sampled types comes closer to f f f
Deciding whether the rows glue
Whether the rows glue with a given strip Z Z Z realization automaton has as states the sequences of P − 1 P-1 P − 1 R \mathcal{R} R N N N P P P Table 3 ): its states are the pairs of consecutive types, with a counter for the length of the current free run. For a candidate strip Z Z Z Z Z Z { Z } \{Z\} { Z } P − 1 P-1 P − 1 Z Z Z Z Z Z Z Z Z W W W L + P − 1 L+P-1 L + P − 1
Table 3. The row-type sampler on the examples the procedure gives it: the patch size P P P L L L
The candidates for Z Z Z P − 1 P-1 P − 1 R \mathcal{R} R Z Z Z R \mathcal{R} R R \mathcal{R} R R \mathcal{R} R
We ran the check after the copier’s results were known, so it explains them rather than predicting them. The rows glue on seven of the eight examples with a row invariant (Table 2 ), the examples on which the copier exists, and on six of them they glue already at shift zero. Configurations stay few: at most 120 at any one row, and at most 17,425 over a whole band. On Wall the rows glue only with their shifts: over the rows at shift zero, some sequences of corners cannot end on the strip they began with, while the shifts let every band return to it, as the copier’s offsets, chained within a band toward the next band’s first offset, do (Appendix § 17 ). They glue on Wall even with the shifts restricted to multiples of three, and then every strip of three rows in a realization is a strip of the tiled example, so a generator built on these realizations has only free cuts, and by Proposition 6 its distance from the example’s statistics comes from its row usage alone. On 3Bricks the rows glue with no strip. Started from the set of all valid strips of three rows of R \mathcal{R} R § 24 ), with rows that are not rows of the example, so free runs of every drawn length exist over other rows; whether some larger finite set of rows glues, with one pinned strip, is open.
On the three walls we drew or transposed for the held-out test (Appendix § 19 ), the check ran first and its result was recorded before any copier was built. The rows glue on each, and the copier then left no forbidden window on any of their nine canvases, three seeds each, before any mending. On the wall drawn with mortar two rows high, no window of three rows meets two courses, so every joint allows every offset, and there the copier draws each stretch’s offset from its own coin without chaining.
Why mixing alone does not suffice
A mixing condition on the sequence of rows cannot take the place of gluing for generators that commute with unit shifts along the columns, which read neither their row nor coins on a fixed grid of row blocks. The proper colorings of Z \mathbb{Z} Z Z \mathbb{Z} Z [27 ] use this to separate block factors from finitely dependent processes, and a block factor can make its errors rare as its radius grows but cannot remove them. If the constraint between consecutive rows were of this kind, a generator that commutes with unit shifts along the columns and reads only independent coins of bounded extent along them would therefore cause defects at every radius. Reading the position, or coins on a fixed grid of blocks that reveal it, removes this obstruction but not the cost of Theorem 3: the coloring X y = y m o d 3 X_y=y\bmod3 X y = y mod 3 Z Z Z L L L ℓ \ell ℓ L L L
The decision procedure and its constants
The steps below run in this order on every example and fix every constant of the method; Table 3 gives what the row-type sampler reads from each example it serves.
Certificate search. For every patch size P P P N N N § 6 looks for a quantity carried by the locally valid P × P P \times P P × P P P P κ f = 1 − max s f ( φ = s ) \kappa_f=1-\max_s f(\varphi=s) κ f = 1 − max s f ( φ = s ) f ( φ = s ) f(\varphi=s) f ( φ = s ) s s s
Input. An invariant along rows gives the row-type sampler, a phase of period d d d d d d
type sampler goes to 3Bricks, Flowers, MoreFlowers, Platformer, SimpleWall, Skyline, Skyline2 and Wall, the phase channels to Fabric, RedMaze, SimpleMaze and SmileCity, and the octaves alone to the other 40 public examples. The sampler reads the row types at the certificate’s patch size P P P N N N
Row types and states. The type of row y y y P P P y − ⌊ P / 2 ⌋ y-\lfloor P/2\rfloor y − ⌊ P /2 ⌋ P P P y − 1 y-1 y − 1 y + 1 y+1 y + 1 P = 3 P=3 P = 3 ( a , b ) (a,b) ( a , b ) ( b , c ) (b,c) ( b , c ) a a a b b b c c c a a a ( a , a ) (a,a) ( a , a ) j j j ( a , a ) (a,a) ( a , a ) j + 1 j+1 j + 1 a a a
Run limits. The automaton read from the windows allows free runs that no coloring shows. On Skyline, Skyline2 and Platformer it allows runs of 2 rows, while the complete solver colors no open strip with a free run shorter than 4 rows on Skyline, 3 on Skyline2 and 4 on Platformer. Every free run is therefore held between the larger of the solver’s least run and the example’s shortest run, and the larger of the example’s longest run and 31 rows, with each run counted exactly in the states of the walk. The upper limit is 30 repeated states, R − 2 R-2 R − 2 R = 32 R=32 R = 32 R R R
Anchor and band length. The anchor is the example’s most frequent state that does not step to itself, with ties going to the lowest index: on the skylines the last free row above the ground, on Wall the top row of a course. The band length L L L n n n n n n L L L
Walks. Band b b b b L bL b L b L + L − 1 bL+L-1 b L + L − 1 b L bL b L L − 1 L-1 L − 1 ( b + 1 ) L (b+1)L ( b + 1 ) L L L L k k k L L L
Row-color term. For the first 30 percent of the 16 000 updates, that is, before update 4 800, the loss gains, for every row of the training canvas, the cross entropy between the example’s color histogram over the rows of that row’s type and the rule’s color distribution on the last round, averaged along the row, at the training temperature. Its weight is fixed at the first update so that the term equals the rest of the loss there. From update 4 800 on the term is absent.
Phase channels. One-hot channels of x m o d d x\bmod d x mod d y m o d d y\bmod d y mod d d = 5 d=5 d = 5
Octaves. Each cell has eight coins of its own and two coins for each of the 24 scale pairs ( i , j ) (i,j) ( i , j ) i , j ∈ { 0 , 2 , 3 , 4 , ∞ } i,j\in\{0,2,3,4,\infty\} i , j ∈ { 0 , 2 , 3 , 4 , ∞ } ( 0 , 0 ) (0,0) ( 0 , 0 )
Rule. State width 64, 32 rounds to generate, and 16 000 updates, each drawing its number of rounds from 8 to 32; the other weights and schedules are in Appendix § 16 .§ 2 .
Variation term. At every update its weight makes it a tenth of the loss without it, on every example. On the rigid examples (Appendix § 17 .§ 3 ), where every valid world is a translate of the tiling, the term cannot fall without a defect, and it is kept there at the same share.
Repair. The rule’s output passes through four coin-gated repair rounds.
Mending. Mending radius ρ max = 24 \rho_{\max}=24 ρ m a x = 24 B = 48 B=48 B = 48 N − 1 N-1 N − 1
Where the run limits leave few run lengths, the sampler leaves little more than an order: Platformer’s band of 1,040 rows holds sixteen stretches of 32 rows from one visit of the anchor to the next and sixteen of 33, so its walks differ only in the order of these stretches. No sampled free run is longer than 31 rows on any example, and within that limit runs longer than the example’s own do appear: SimpleWall’s example shows free runs of 2 and 3 rows, and its sampled runs reach 11.
How the search and the procedure were arrived at. The search as first fixed looked for invariants and phases only, under a coarser labeling that pooled every patch outside the certified component into one value, and it certified the same examples except Town; the one-way quantity, which certifies Town alone, and the full labeling were added after that run (Appendix § 18 ). The examples shaped parts of the procedure, and each part falls in one of two groups. Fixed before any training were the reading of the row types from the certificate’s strips, the automaton and its transition weights, the band length, and the lower run limit set by the complete solver. Added after a diagnosed failure were the phase channels at the certified period, after channels of the coordinates modulo powers of two left Fabric, whose period is 5, invalid; the row-color term, after the lagged reading on Wall; the anchor at a state that does not step to itself, the upper run limit and the example’s shortest run as a second lower limit, after Skyline and Skyline2 failed at the feet of buildings under free runs longer than the rule’s radius, and Skyline also under runs shorter than the example’s; and the reading of the types at the certificate’s own patch size, after the reading at patch size N N N § 8.2 ). Appendix § 24 lists every step with what we expected and what happened.
Why the input follows the certificate. Where the octaves could carry the quantity (§ 3 ), a rule must learn to extract it, and a rule told its position outright by channels of the coordinates extracted it on the mazes and on Wall but painted the same raw canvas for every seed (Appendix § 23 .§ 8 ). The certificate names the quantity itself, so the input gives that and leaves the rest to the coins. No input was built for a one-way quantity: the search had found one on Town before any of these parts existed, and the octave rule was already valid there. In a stationary world free of forbidden windows a one-way quantity is constant along the lines of its direction (proof of Theorem 2), so its values could be supplied as row types are.
The learned automaton and the mender
The rule and its objective
The rule. The rule is a neural cellular automaton ([47 ] ) with a radius-one update and a state s s s ω \omega ω 1 × 1 1 \times1 1 × 1 A A A s 0 + a tanh ( A ω ) s_{0}+a\tanh(A\omega) s 0 + a tanh ( A ω ) s 0 s_{0} s 0 s ← s + tanh ( W 2 silu ( W 1 ∗ s ) ) + b tanh ( A ω ) s \leftarrow s+\tanh(W_{2}\operatorname{silu}(W_{1}*s))+b\tanh(A\omega) s ← s + tanh ( W 2 silu ( W 1 ∗ s )) + b tanh ( A ω ) W 1 W_{1} W 1 3 × 3 3 \times3 3 × 3 W 2 W_{2} W 2 1 × 1 1 \times1 1 × 1 a a a b b b § 16 .§ 2 ). A linear output layer gives C C C R R R R R R R R R
Objective. Training draws random seeds and random absolute positions, so that block boundaries fall anywhere on the canvas, and asks the output of every round for a valid coloring with the example’s statistics. Let p t p_t p t t t t hard output of round t t t e t + p t − sg ( p t ) e_t+p_t-\operatorname{sg}(p_t) e t + p t − sg ( p t ) e t e_t e t sg \operatorname{sg} sg p t p_t p t u u u R u R_u R u
L = ∑ t = 1 R u w t [ S t + λ F KL ( f ∥ f ^ t ) + λ H H t + 1 [ u ≥ u 0 ] ( λ E E t + λ M KL ( ν ∥ ν ^ t ) ) + λ V V + 1 [ u < u 0 ] λ C C ] , (6) \mathcal{L}=\sum_{t=1}^{R_u}w_t\left[S_t+\lambda_F\operatorname{KL}(f\mathbin{\|}\hat{f}_t)+\lambda_H H_t+1[u\geq u_0]\left(\lambda_E E_t+\lambda_M\operatorname{KL}(\nu\mathbin{\|}\hat{\nu}_t)\right)+\lambda_V V+1[u<u_0]\lambda_C C\right], \tag*{(6)} L = t = 1 ∑ R u w t [ S t + λ F KL ( f ∥ f ^ t ) + λ H H t + 1 [ u ≥ u 0 ] ( λ E E t + λ M KL ( ν ∥ ν ^ t ) ) + λ V V + 1 [ u < u 0 ] λ C C ] , (6) with round weights w t = t / ∑ s = 1 R u s w_t=t/\sum_{s=1}^{R_u}s w t = t / ∑ s = 1 R u s S t S_t S t H t H_t H t p t p_t p t f f f f ^ t \hat{f}_t f ^ t K K K ν \nu ν ν ^ t \hat{\nu}_t ν ^ t E t E_t E t warm-up , the updates before u 0 u_0 u 0 f ^ t \hat{f}_t f ^ t u 0 u_0 u 0 f ^ t \hat{f}_t f ^ t V V V C C C § 16 .§ 2 gives the weights and schedules.
The soft term gives a dense gradient from the first update, but alone it is gamed: most rules trained on it collapsed to one constant valid pattern that ignores the coins (Section N.9). A spread distribution cannot lower the hard terms, and the color-marginal term penalizes a constant output even when all of its windows are allowed. Weighting the later rounds more and drawing the round count afresh at every update train the rule as a repair protocol over the whole range of round counts.
The variation term. The variation term guards against a shortcut that shared coins open and the rest of the objective does not rule out: the rule could copy the example on each coarse block and ignore its fine coins, which Proposition 1(b) shows to be valid and faithful away from the blocks’ boundaries, though it varies only from block to block. Under the row types the copy can be exact, with stretches of the example between two anchors (§ 8.3 ), and Appendix § 23 .§ 8 reports what a rule trained without the term does. To make the fine coins matter, each update draws, for every canvas of the batch, a second input with the same seed and position, the coarse channels unchanged and the fine channels hashed from a fresh seed, and runs the rule on it for the same number of rounds. The fine channels are the cell’s own coins and the 6 pairs with one scale 0 and the other finite, whose blocks are one cell wide; the other 18 pairs are coarse, and so are the row types and the phase channels where the rule reads them. The variation term V V V ∑ c p ( c ) p ′ ( c ) \sum_c p(c)p'(c) ∑ c p ( c ) p ′ ( c )
The row-color term. Given the row types, the rule has to learn which colors each type means, and on the rest of the objective it can settle in a stable wrong reading. On Wall the first rule trained on the row-type sampler read each row as the type of a row ahead of it, by a lag that differed between the example’s short and tall courses, and none of its rows had the sampled type. Rules given the row types therefore carry, during the warm-up, the row-color term C C C
The independent-coin rule and the octaye rule. The independent-coin rule of § 3 runs this construction on the cell’s own coins alone: it reads none of the octaves, the row types or the phase channels, and its objective has neither the variation term nor the row-color term. The octave rule is the construction on the octaves alone, on every example; it is the method wherever the procedure gives the octaves alone. The method and these two rules share the rest of the objective, its schedule, repair, mending and the evaluation.
Training
Configuration. Each cell carries a state of width 64 and 8 coins of its own, computed by an integer hash of the seed, the two coordinates and the channel. In the update above, the learned vector s 0 s_0 s 0 a a a b b b 2 ⋅ 10 − 3 2 \cdot10^{-3} 2 ⋅ 1 0 − 3 R ′ = 32 R' = 32 R ′ = 32 (6) are λ F \lambda_F λ F λ H \lambda_H λ H λ E \lambda_E λ E E t E_t E t λ M \lambda_M λ M u 0 u_0 u 0 λ C \lambda_C λ C Table 18 ). Skyline and Skyline2 also have runs at seed 1 made with the row-type sampler as it stood before its anchor and run limits were changed after the skylines failed (Appendix § 15 ), so they are not rules of the method. A training run takes a median of 98 minutes on one T4 for the octave rule, whose variation term adds a second forward and backward pass, and 56 minutes for the independent-coin rule. Table 48 measures its variants against an earlier configuration of the independent-coin rule, with a fixed horizon of R = 16 R = 16 R = 16
Table 48. Objective variants on five examples, one seed each, for the rule on independent coins: the median over examples of the variant’s forbidden-window rate at 16, 32 and 64 test-time rounds, divided by the earlier configuration’s rate at its trained 16 rounds; how many curves fall monotonically from 8 to 64 rounds; and collapses to a constant pattern. The configuration the paper uses is marked.
Table 48.
The octaves’ coins. For every scale pair ( i , j ) (i,j) ( i , j ) i , j ∈ { 0 , 2 , 3 , 4 , ∞ } i,j \in\{0,2,3,4,\infty\} i , j ∈ { 0 , 2 , 3 , 4 , ∞ } ( 0 , 0 ) (0,0) ( 0 , 0 ) ⌊ x / 2 i ⌋ \lfloor x/2^i\rfloor ⌊ x / 2 i ⌋ ⌊ y / 2 j ⌋ \lfloor y/2^j\rfloor ⌊ y / 2 j ⌋ x x x y y y ∞ \infty ∞
How the weights were set. The objective’s weights were not searched. The variation term’s was ablated: the octave rule was also trained without the term on every example, and so were the method’s rules on Wall and Skyline, in the configuration above otherwise (Appendix § 23 .§ 8 ). The forbidden-window weight was raised once, together with a lower temperature, among the objective variants of the earlier configuration (Table 48 ), and the other weights were fixed before training. The scales of the octaves were chosen by hand and not searched.
3Bricks. 3Bricks has 423 distinct windows, and at batch 8 its training runs out of the memory of a T4 when the hard terms switch on. Every rule of 3Bricks, the independent-coin rule, the octave rule and the rule on the row-type sampler, is therefore trained at batch 2 from scratch, with everything else unchanged; it is the only example trained at another batch.
Repair, mending and the reach
Repair. The rule’s output passes through four repair rounds. A cell covered by a forbidden window is defective . In each round every defective cell scores each color by the number of windows through it that the color would make allowed, and the defective cells that win a fair coin take their best color, so that adjacent cells do not all flip at once. These coins are hashed from the seed, the round and the position, so the rule with repair is still a random-access generator (Definition 1), its radius larger by N N N
Mending. Mending re-solves what repair leaves, on a lattice of square blocks of side B B B ρ \rho ρ ρ = 1 , 2 , … \rho= 1, 2, \ldots ρ = 1 , 2 , … ρ max \rho_{\max} ρ m a x min ( ρ , ⌊ ( B − N + 1 ) / 2 ⌋ ) \min(\rho, \lfloor(B-N+1)/2 \rfloor) min ( ρ , ⌊( B − N + 1 ) /2 ⌋) ρ \rho ρ [3 ] from above, and only from above, since the solver does not backtrack. When no radius up to the cap completes the block’s defects together, cluster completion grows the block’s defective cells by N − 1 N-1 N − 1 2 B 2B 2 B B / 2 B/2 B /2 ρ max \rho_{\max} ρ m a x mending radius and set B = 2 ρ max B = 2\rho_{\max} B = 2 ρ m a x ρ max = 24 \rho_{\max} = 24 ρ m a x = 24 B = 48 B = 48 B = 48 Table 17 adds ρ max = 8 \rho_{\max} = 8 ρ m a x = 8 ρ max = 16 \rho_{\max} = 16 ρ m a x = 16 2 B 2B 2 B
Table 17. Table 17. Validity at three mending radii, with blocks of twice the radius and cluster completion: the examples (of 52) valid on all three canvases for the octavе rule, the method (radius 24 only), the independent-coin rule, block-shifted tiles (radius 24 only) and i.i.d. colors drawn from the example’s color frequencies (at radius 16 only on the examples the octavе rule leaves invalid at radius 8), and for the octavе rule and the method on all eight canvases of the robustness test; for the octavе rule, the median share of cells that mending changes on its valid examples and the smallest margin at which chunks mended separately agree with whole-canvas mending on every canvas tested (Appendix § 23 .§ 9 ). Entries marked a use the mender without cluster completion, which at radius 8 makes the same examples valid. A dash marks a test we did not run.
What mending guarantees. Every window that touches a re-solved region is allowed by construction, so the residual after mending counts only defects for which the solver, which can miss a completion that exists (Appendix § 20 .§ 6 ), found none within the cap. How far a change can travel is counted from the mender’s dependencies. In each of the eight class steps of the two passes, a solve writes only cells within m = ⌊ ( B − N + 1 ) / 2 ⌋ m = \lfloor(B-N+1)/2 \rfloor m = ⌊( B − N + 1 ) /2 ⌋ m + N − 1 m+N-1 m + N − 1 B + 2 m + N − 2 B+2m+N-2 B + 2 m + N − 2 N N N N − 1 N-1 N − 1 N N N reach of the whole pipeline, its margin of random access in the extended sense of § 2 . For a rule on shared coins, a coin read at a cell within the reach may be shared with cells beyond it, so changing a coarse coin reaches every cell within 804 cells of its block. The count is a bound read off the dependency structure of the code, and the seam test of Appendix § 23 .§ 9 probes it from below: chunked mending agrees with whole-canvas mending at margins of 64 cells and more at radius 8, and at radius 24 on every tested canvas from a margin of 256 cells, with one canvas still differing at 224 (§ 8.4 ).
Changes not adopted. Two further changes were tried at radius 24 and not adopted. A pass that put back, greedily in scan order, every changed cell whose old color keeps all windows through it allowed changed no example’s validity and left the share of cells changed almost where it was (Appendix § 23 .§ 1 ). Retrying a failed block with its clusters grouped over 24 cells, then over 8, before single clusters changed no example’s validity under the octave rule and left Wall’s residual unchanged (Table 32).
Protocols, references and measures
The comparisons and their protocols
Generation and evaluation. We call the comparison of the first row of Table 4 the corpus evaluation ; the method, the octave rule and the independent-coin rule are evaluated there by the same code, at the same radii and coin seeds. Each canvas is generated from the coins of its own cells and of a margin of 44 cells around it, the radius of the rule with its repair rounds, and every evaluation generates it again in chunks of 64 × 64 cells, each with the same margin, and checks that the two agree cell for cell (Appendix § 23 .§ 9 ). The canvases are then mended whole; mending in chunks needs a wider margin and is tested separately (§ 8.4 , Appendix § 23 .§ 9 ). The evaluation at radius 24 records every measure of Appendix § 17 .§ 3 after mending, and the robustness test records the residual alone. Regions of 256 2 256^2 25 6 2 1024 2 1024^2 102 4 2 2 ^2 2 256 2 256^{2} 25 6 2 1024 2 1024^{2} 102 4 2 R ′ ∈ { 4 , 8 , 16 , 32 , 64 } R' \in\{4, 8, 16, 32, 64\} R ′ ∈ { 4 , 8 , 16 , 32 , 64 } § 17 .§ 3 and the seam test hold for both rules on every public example (Table 44 ). For the octave rule, the first three of the eight canvases of the comparison against the references are those of the corpus evaluation. The generation times of the octave rule and of the independent-coin rule are compared on CPU with 4 threads, on canvases of up to 4096 × 4096 4096 \times4096 4096 × 4096
Table 44. The independent-coin rule, example by example, one rule per example run for 32 rounds, 1 evaluation seed each. Columns: the number ∣ K ∣ |K| ∣ K ∣ N × N N \times N N × N C C C 1024 2 1024^2 102 4 2 1024 2 1024^2 102 4 2 64 2 64^2 6 4 2 Table 47 ); whether chunked and one-shot generation agree cell for cell (seam) and whether redrawing the coins of a 16 2 16^2 1 6 2 1024 2 1024^2 102 4 2 256 2 256^2 25 6 2
Table 44.
The classes. The classes depend on the independent-coin rule and its mender, while the certificate of § 6 is computed from the example alone, so comparing the two is not circular as a computation. On the three canvases of the main protocol at radius 8, the independent-coin rule is valid on the same examples as on the single canvas that defines the classes, and Appendix § 20 .§ 3 counts them.
Which rule. The octave rule and the independent-coin rule are one rule per example each, in every comparison of Table 4 and in the measures of connectivity, correlation and timing, with one exception: mending at 1024 2 1024^{2} 102 4 2 Table 13 ) uses three further independent-coin rules per example, trained in the same configuration from three seeds, and the first of them is the rule of the complete-solver study on its five main examples and on Wall (Table 14 ). The same example’s residual differs between tables, since a wider radius leaves less than a narrower one on the examples it helps, the two menders leave different residuals, and these three further rules differ from the main independent-coin rule as two training runs do.
Table 13. Table 13. Mending at 1024 2 1024^2 102 4 2 256 2 256^2 25 6 2 64 2 64^2 6 4 2
Table 14. Table 14. The complete solver on canvases of the independent-coin rule: on Angular, which mends within radius 8, on City and Qud, which are partial, on Skew2 and Sewers, which are resistant and uncertified, and on Wall. That rule is the first of the three independent-coin rules of Table 13 at 32 rounds, on one 256 2 256^2 25 6 2 ρ = 8 \rho= 8 ρ = 8
The references
Shifted replay and the i.i.d. draw. Shifted replay tiles the example from a uniformly random offset, so it is valid and faithful and varies only by a translation. An i.i.d. draw from the example’s color frequencies copies nothing, so it sets the floor of the measures of copying and the ceiling of divergence, and mended as the method is, it shows what mending does from noise.
The block reference. Block solvers keep every window allowed with no learned rule, by re-solving blocks of a copy of the example, in the manner of model synthesis ([44 ] ) and the block solvers of Boris the Brave [10 ] and Kleineberg [35 ] . The block reference starts from shifted replay. In each sweep it shifts its lattice of 16 × 16 16 \times16 16 × 16 [8 ] ) with random variable order and random initial phases, which is randomized but not uniform; a block it cannot solve within a fixed budget keeps its content, so every window stays allowed at every step. Its number of sweeps is set per example to the smallest whole number that brings its cost per cell to at least twelve times the independent-coin rule’s mean cost, estimated from its first sweep; the octave rule costs as much per cell as the independent-coin rule. Its measured cost per cell is 16 times the octave rule’s at the median, in single-thread CPU time, where the octave rule’s cost counts generation, four repair rounds and mending within radius 8 without cluster completion. Mending within radius 24 costs more, so at that radius the ratio would be smaller. We call an example frozen for the reference when the reference changes no cell of shifted replay; these examples are Chess, Fabric, RedMaze, SimpleMaze and Stripes, and none of the 27 examples the octave rule makes valid is among them. This is a property of the reference’s moves, weaker than the rigidity of Appendix § 17 .§ 3 .
The random-access block solver. The random-access block solver makes the block reference random access. It starts from shifted replay on the infinite plane and re-solves the 16 × 16 16 \times16 16 × 16 § 23 .§ 7 ).
Block-shifted tiles, painted row types and the copier. Two references test what mending does without a rule. Block-shifted tiles fill each 64 × 64 64 \times64 64 × 64 painted row types take the row types that the row-type sampler draws and draw each cell of a row from the example’s color histogram over the rows of that row’s type, the histograms of the row-color term (Appendix § 16 ), before the same mending. The copier tests what the prescribed input carries alone: it fills the sampled sequence of row types from the example alone. It cuts the sequence at its anchors, matches each stretch to a stretch of the example with the same row types, lengthens a run by repeating one of its rows where every window stays a window of the example, and copies each stretch with a horizontal offset hashed from the seed, chosen on the walls among the offsets that its joint with the stretch above allows. On the walls the offsets chain only within a band of the row-type sampler: the first stretch of a band takes an offset hashed from the seed and the band, and the others are drawn with coins hashed from the seed and their first rows, uniformly over the sequences of allowed joints that lead to the next band’s first offset, so any offset costs work bounded by L L L
The Metropolis rules. Two priors written by hand stand in for the rule. The Metropolis rule is the hand-written rule of Appendix § 23 .§ 3 : hashed coins drive annealed Metropolis updates of the window energy defined there, in nine parallel phases of radius 2. As a prior for mending it runs for 64 sweeps, and for 1 024 in a longer test, before the method’s four repair rounds and mending. The Metropolis filler runs it on the row types that the row-type sampler draws: a cell’s proposals come from the colors of its row type, a window counts as allowed only where the example has it centered on a row of the same type, and the energy adds the log frequencies of the windows within their type. It runs for 256 sweeps before the same mending, and each of the nine phases of a sweep reads two cells farther, so its reach grows with every sweep. Appendix § 23 .§ 3 also defines the second hand-written rule compared there, independent sampling followed by many rounds of our repair.
Wave Function Collapse. Our implementation of Wave Function Collapse, the overlapping model with minimum-entropy collapse and propagation, is the reference for window statistics (Section N.8). It restarts from scratch on a contradiction instead of backtracking, and on a few examples it completes no large canvas; where it produced no 256 2 256^{2} 25 6 2 Table 47 ).
Table 47. Size-matched pattern KL to the example of the raw canvas (before repair and mending): the independent-coin rule (“indep.”), the octave rule, and our Wave Function Collapse implementation (“WFC”), at 64 2 64^2 6 4 2 128 2 128^2 12 8 2 256 2 256^2 25 6 2 N × N N \times N N × N 256 2 256^2 25 6 2
Table 47.
The measures
Defects and window statistics. The defect rate is the density of forbidden windows among the 3 × 3 3 \times3 3 × 3 residual . The total variation of § 2 is bounded and needs no smoothing for the windows a canvas lacks, so the body reports it; the appendix tables add the Kullback–Leibler divergence KL ( f ∥ h ) \operatorname{KL}(f \mathbin\Vert h) KL ( f ∥ h ) f f f h h h h h h 10 − 12 10^{-12} 1 0 − 12
The transported quantity. For the transported quantity of § 3 we count how often it departs from the transport along its direction, per hundred window positions of the raw output, its switch rate ; for an invariant along rows, that is how often its value changes along a row. For a rule given row types we measure the share of rows of its raw output whose type, read from the output’s windows with the certificate’s labels, is the type the row-type sampler drew for that row.
Copying and variation. Three measures separate copying from variation. Let a a a a 0 a_0 a 0 normalized agreement ( a − a 0 ) / ( 1 − a 0 ) (a-a_0)/(1-a_0) ( a − a 0 ) / ( 1 − a 0 ) Repetition is the share of the canvas’s 16 × 16 16 \times16 16 × 16 Aligned variation is the share of cells that differ between two canvases of one method drawn from different seeds, after the relative translation of at most 64 cells along each axis that makes it smallest, averaged over the pairs of canvases of one method. Since it searches translations of up to 64 cells, it cannot align an example whose period is longer, which matters only for shifted replay on Font.
Edits. Each edit overrides some or all of the coins read in a region, in the sense of Appendix § 12 , and leaves every coin outside the region as it was (Table 5 ). Local variation , which we also call the fine redraw where a rule reads shared coins, edits one 32 × 32 32 \times32 32 × 32 full redraw redraws every coin that the region’s cells read. For the independent-coin rule both are the redraw of its cells’ own coins. The cell-coin edit is the generator’s own test of containment: on a raw canvas of side 192 it resamples only the cells’ own coins on a 16 × 16 16 \times16 16 × 16 Table 25 reports the fine and the full redraw, and Table 44 the cell-coin edit.
Table 5. The edits we measure. Each overrides coins read in a square region and leaves every coin outside the region as it was. Local variation and the full redraw are measured on mended canvases and report the share of the canvas that changes and the share of the changed cells that lie only in allowed windows; for the independent-coin rule the two are the same edit. The cell-coin edit is measured on a raw canvas of side 192 and reports the cells that change.
Table 25. The evaluation against replay for the octave rule, on the examples it makes valid at radius 8; means over eight 256 2 256^2 25 6 2 3 × 3 3 \times3 3 × 3 ( a − a i i d ) / ( 1 − a i i d ) (a-a_{\mathrm{iid}})/(1-a_{\mathrm{iid}}) ( a − a iid ) / ( 1 − a iid ) a i i d a_{\mathrm{iid}} a iid 16 × 16 16 \times16 16 × 16 32 × 32 32 \times32 32 × 32 § 17 .§ 3 ); and the block reference’s cost per cell over the octave rule’s, single-thread CPU time.
Structure beyond the window. Two further measures look past the window, and no rule is trained on either. For connectivity, the passable color of an example is the color, among those that cover at least a fifth of it, whose 4-connected components on shifted replay hold the largest share of its cells in a single component; an example on which no such color reaches half is left out. A generator keeps the example’s connectivity when its largest component of that color holds at least 0.8 times the share that shifted replay’s does. For correlation we use the connected same-color correlation S ( d ) = Pr [ x v = x v + d ] − ∑ c p c 2 S(d) = \Pr[x_v = x_{v+d}] - \sum_c p_c^2 S ( d ) = Pr [ x v = x v + d ] − ∑ c p c 2 p c p_c p c S S S S ( 1 ) S(1) S ( 1 ) Figure 7 come from raw 512 × 512 512 \times512 512 × 512
Figure 7. Connected two-point correlation against the lag, one panel per example plotted: the octave rule and the independent-coin rule on raw 512 2 512^2 51 2 2 64 2 64^2 6 4 2 16 × 16 16 \times16 16 × 16 128 2 128^2 12 8 2
Examples whose worlds are fixed. On RedMaze and SimpleMaze, which we call rigid , the locally valid patches of some size are exactly the patches of the tiled example, each with one successor along each axis, so every K K K
Further controls and three dimensions
Chess and Stripes. Two controls of known class are added to the public examples. Chess and Stripes are agreement constraints, whose only K K K K K K r r r 1 / r 1/r 1/ r § 13 ).
Further controls. The per-example tables also list two proper 3-coloring controls: proper3, whose constraint set is every proper 3-coloring of the window with uniform frequencies, and Col3, a random proper 3-coloring of a torus used as an example. Both count in no claim about the public examples. A random proper 4-coloring of a torus is left out as a control: its example contains only 966 of the 9 612 proper 4-colored windows (10%), so it does not stand for the proper 4-coloring constraint.
One voxel example. The construction runs unchanged on Z 3 \mathbb{Z}^3 Z 3 4 3 4^3 4 3 3 × 3 × 3 3 \times3 \times3 3 × 3 × 3
The certificate on every example
Whether a constant coloring exists does not predict which examples resist. One has no forbidden window on 44 of the 52 public examples, spread over every class that mending gives under independent coins, while the certificate falls on resistant examples only (Table 6 , § 8.1 ). Among the resistant examples that no constant coloring satisfies, the search certifies 4 of 6, Wall among them. When the search widens for the resistant examples left without a certificate (§ 8.1 ), the patches grow to side 7 to 11.
Table 6. Certified public examples and examples a constant coloring satisfies, by how far mending within radius 8 gets under independent coins (the classes of Table 11 ). Chess and Stripes are not counted.
The first certificate found is an invariant along rows on 8 of the certified examples and a phase on 4 (Table 8 ). On Town, at P = 6 P = 6 P = 6 κ ( 0 ) = 0.146 \kappa(0) = 0.146 κ ( 0 ) = 0.146 κ f = 2 / 9 \kappa_f = 2/9 κ f = 2/9 P > N P > N P > N 3 × 3 3 \times3 3 × 3 κ ( 0 ) \kappa(0) κ ( 0 ) P = N P = N P = N δ = 0.05 \delta= 0.05 δ = 0.05 § 13 .§ 7 allows defects as well. The floor in Table 8 is κ ( 0 ) / ( ( 2 r + P + 1 ) ( P − N + 1 ) 2 ) \kappa(0)/((2r + P + 1)(P - N + 1)^2) κ ( 0 ) / (( 2 r + P + 1 ) ( P − N + 1 ) 2 ) § 20 .§ 7 says where it binds the trained independent-coin rule. The labeling fixed before the search ran pooled every patch outside the certified component into one value, and on the phase examples it gives smaller constants (Table 32).
Dependence at a distance in a solver's worlds
Could validity carry a quantity on the resistant examples without a certificate that the search’s patches do not reveal? A quantity carried along a direction leaves a trace that no patch size bounds: as long as its value varies between worlds, two windows on that line stay dependent however far apart they lie. A generator of radius r r r 2 r 2r 2 r
For every public example but Cats, which gave no valid world at either size, and for the controls Chess, Stripes and Col3, our implementation of Wave Function Collapse (Appendix § 17 .§ 2 ), which restarts on a contradiction and does not backtrack, made 32 worlds free of forbidden windows on a 128 × 128 128 \times128 128 × 128 96 × 96 96 \times96 96 × 96 k k k 3 × 3 3 \times3 3 × 3 k k k D D D D D D
The dependence persists along the certified direction on eleven of the twelve certified examples whose quantity is not one-way, where we expected it on at least 10, and along rows on Town, whose one-way quantity runs along rows (Table 7 ). On Skyline2, the one it misses, D D D D D D
Table 7. Dependence between 3 × 3 3 \times3 3 × 3 D 16 D_{16} D 16 D 64 D_{64} D 64 D 16 D_{16} D 16 96 × 96 96 \times96 96 × 96
Read after the run, the scan shows that on these examples the dependence reaches well beyond the window but fades: where it is strongest it falls more than sevenfold between the two distances, and on Nested and Skew2 it is gone at 64 in that direction. Dependence of this reach is not peculiar to them: Mountains, which does not resist, keeps more of it at 64 cells than any of them. The test sees a quantity only if a pair of 3 × 3 3 \times3 3 × 3
A second test, fixed before its run, asked the same question of the min-coin copy of Appendix § 20 .§ 2 . Where a quantity is carried beyond the reach of mending, the copy’s share of forbidden windows after mending should fall as one over the copy’s radius, the order of Theorem 1, as it does on the certified controls SimpleMaze, SimpleWall, RedMaze and Fabric; where none is, we assumed it would fall faster. Over radii 8 to 128, the slope of the logarithm of the share against that of the radius lies in the interval we read as carried, from − 1.3 -1.3 − 1.3 − 0.7 -0.7 − 0.7 − 1.6 -1.6 − 1.6
We take the scan’s reading on Cat and ColoredCity, for a reason found after both runs. A dependence that reaches beyond the mending radius and then fades, as theirs does, can by itself make the share fall near one over the radius across this ladder, so the slope cannot tell a carried quantity from a long but finite dependence. Their curves show it: the share falls faster than the carried interval allows from radius 32 to 64 and more slowly than it allows after, so their slopes land in the interval as averages, while on the certified controls every step of the ladder lies within it. The scan measures the dependence itself and was checked on both sides, on the certified examples, where it persists on all but one, and on the examples that do not resist, where it fires once, on noise. The two tests rank these examples in much the same order, with a rank correlation of 0.67, and both find the longest reach on Cat and ColoredCity.
More on where independent coins fail and where the method is valid
The test of selectivity in § 8.1 compares the share certified among the 21 examples that resist independent coins with the share among the 21 that independent coins mend, leaving out the partial ones. The search as first fixed, before we added the one-way quantity and the full labeling, certified the same examples but Town, at p = 3 ⋅ 10 − 5 p = 3 \cdot10^{-5} p = 3 ⋅ 1 0 − 5 § 15 ).
The certified quantities. The quantities are of the kinds § 3 describes (Table 8 , Figure 8 ). On the brick walls, the flowers, the skylines and the platformer, a line of one kind runs straight across the plane, and the quantity is an invariant
Figure 8. The thirteen certified examples in the order of Table 8 , each scaled to fill its panel, with its size in cells and the kind of quantity its certificate finds: an invariant along rows, the row type of § 3 ; a phase of period d d d 64 × 64 64 \times64 64 × 64
along rows, the row type. On the two mazes it is a phase along rows, on SmileCity and Fabric a phase along columns, and on Town a one-way quantity along rows, which can pass from one strongly connected component of the overlap graph to the other but never back. A constant coloring is valid on nine of the 13 certified examples, so on these the constraints alone force no defect. The example’s statistics force them: the linear program of § 3 gives κ ( 0 ) > 0 \kappa(0) > 0 κ ( 0 ) > 0 p s p_s p s § 20 .§ 7 ). Figure 2 shows the mechanism on Wall: the independent-coin rule’s forbidden windows sit where the row type changes along a row, and the method, whose rule reads the row types, keeps each row’s type across the canvas.
Mending under independent coins. With the mender of the main protocol, independent coins are valid on none of the resistant examples, certified or not (Figure 5 ). The bound does not require this failure after mending (§ 3 , Appendix § 13 .§ 11 ), but on every certified example a witness accounts for most of the mending instances at radii 4 to 16 that have no completion, and at radius 16 for at least 76% of them (Appendix § 20 .§ 1 ). Chess and Stripes, whose only valid colorings are the two phases of a period-two pattern, stay above one forbidden window in a hundred under independent coins: a mender of bounded radius can remove a boundary between the two phases only by freeing all of the region it encloses, so the boundaries the rule draws around larger regions survive mending (Appendix § 13 ). They stay above it under the octaves too, although the octaves’ blocks reveal the parity (Proposition 1), so there the octave rule fails to learn what its input could carry.
The method on the certified examples. Under the row-type sampler the method is valid on six of the seven examples with a row invariant other than Wall, all but 3Bricks, and under the phase channels on Fabric and on both mazes, whose valid worlds are essentially translates of the tiling (Appendix § 17 .§ 3 ). Table 9 sets these worlds against the theorems on every certified example (§ 8.2 ). On Wall, SimpleWall, RedMaze, SimpleMaze and Fabric, where P = N P = N P = N κ f \kappa_f κ f (1) also says what the exclusion costs at a finite radius: a generator on independent coins with a canvas’s statistics and the reach of the whole pipeline would leave at least 11 forbidden windows on it in expectation. On Platformer the canvases lie farther than κ f \kappa_f κ f Figure 6 ). On Flowers, MoreFlowers and Skyline the program reaches zero below the method’s distance, and only the floor from the method’s own spread of the row type sets it apart, at the pipeline’s reach and in expectation. On Skyline2 and Town, which the method makes valid on the development seeds but not on all eight canvases, neither bound sets it apart: Skyline2’s canvases keep forbidden windows, and on Town the floor from its own spread expects fewer than one per canvas. There the evidence is the measured failure of independent coins at every radius we tried. Of the certified examples that shaped no part of the procedure, the octave rule alone makes five valid, Flowers, MoreFlowers, Platformer, SimpleWall and Town, and the prescribed input adds RedMaze and SimpleMaze, where reading the example at the coordinates the phase channels give already yields the tiled example. On Wall the rules trained from training seeds 1 and 2 keep no forbidden window either (Appendix § 23 ).
The held-out examples. The procedure was tested on five examples that did not shape it, three walls and two mazes. Wall and SimpleWall transposed, whose invariant runs along columns, test the exchange of axes; a wall drawn for this test before any training, with course heights that Wall does not have and thicker mortar, is a new example. The search certifies the invariant on all three, along columns on the transposed walls, and the procedure, applied unchanged, gives each the row-type sampler, under which the method is valid on all three. On every canvas of the three, each row of the rule’s output, or each column on the transposed walls, has the type the sampler drew. The octave rule alone, trained the same way, behaves on the transposed walls as on the public ones. It is not valid on transposed Wall, where each of its three canvases keeps at least 5.4 ⋅ 10 − 3 5.4 \cdot10^{-3} 5.4 ⋅ 1 0 − 3
The two mazes were drawn as the same spanning tree of rooms on a torus, with walls on a lattice of period 3, which does not divide the octaves’ period. In the first, passages two cells wide hide the lattice from the 3 × 3 3 \times3 3 × 3 16 × 16 16 \times16 16 × 16
Examples from other implementations. A search of public repositories, logged before any run, found 27 licensed example images in eight other open-source implementations of Wave Function Collapse and related generators; none is among the 52 examples of the original repository. One more image was left out before any run: it has more colors than the rule draws coins per cell, so its repair rounds would break ties with a global random generator, and its worlds would no longer be a function of the seed and the position. The procedure ran on the rest unchanged, from the search and the input it prescribes to training from training seed 0 and validity under the main protocol. The search certifies five, GbDiamond, GbMountain, GbLattice, GbTriangles and GbZigzag, all from one repository, and gives GbMountain, GbLattice, GbTriangles and GbZigzag an input other than the octaves. On GbDiamond the certified invariant runs along a diagonal, for which the procedure has no input, so there the method is the octave rule; we fixed before the run that it counts with that rule’s result, as Town does.
The certificate again marks examples that resist independent coins: all five certified examples resist them, five of the nine that do. Given its input, the method is valid on all four examples that receive one, and so are its rules trained from training seeds 1 and 2; the octave rule alone is valid on one of them. GbLattice, GbTriangles and GbZigzag are each one period of a pattern, with the period of their phase as their side, and there the method’s world is the tiled example. On GbMountain the octave rule is valid under the main protocol but not on all eight canvases, while the method is valid on all of them. Over all 27 examples the method is valid on 21 and invalid on GreedyA, GreedyB, GreedyC, GbDiamond, KrCave and DbPathway. On the 22 uncertified examples the octave rule is valid on 17, block-shifted tiles of the example under the same mender on 16, and i.i.d. colors on none. As on the public examples, the min-coin copy of Proposition 2 is valid after mending on none of the certified examples, and on each of them the independent-coin rule’s share of forbidden windows before repair lies above the floor of Theorem 1, by a factor of six or more. Table 19 gives every generator on every example.
The failure of independent coins
Witnesses
A single pair of patches, the witness of Appendix § 13 .11, explains most of the unsolvable mending instances on every certified example (Table 10 ). An instance frees every cell within radius 4, 8 or 16 of one forbidden window, or of a cluster of them, and frees every other cell, as in Appendix § 20 .§ 6 ; these radii lie below the main mender’s, 24. The forbidden windows are those of the independent-coin rule of the main protocol, and on Wall, Sewers and Skew2 those of the rule of Table 14 . Each locally valid patch is labeled by the full labeling of the certificate, or for Town’s one-way quantity by its strongly connected component. A witness is a pair of frozen patches on one line along the certificate’s direction, on the two sides of the free region, whose labels no locally valid walk of the needed length joins, or for Town whose downstream component the upstream one cannot reach.
The share of unsolvable instances with a witness is highest at the largest radius on every certified example: at radius 16 it is at least 76% on each, lowest on MoreFlowers, and on Skyline it grows from 49% at radius 4 to 85%. A witness proves that its instance has no completion, so the search finds none on the 362 instances that have one, as it must; that count checks the search, and so do two controls. The search finds no witness on 6 240 free regions cut at random from colorings without forbidden windows, the tiled examples and the outputs of Wave Function Collapse, and it finds one on every instance of three seams built to break the quantity, 150 on each: of mixed phase on Chess and on Stripes, and in the forbidden order on Town. A second search that uses no labels, a reachability search over the locally valid patches along the witness’s line, confirms every witness found, those on the seams included.
On Fabric and the mazes the solver refutes at least 97% of the unsolvable instances before any search, and the witnesses there mostly pair patches from two different weak components of the overlap graph: a pair of two levels of one component appears in 26% to 38% of the witnessed instances. On SmileCity, which visits a single component, all but one of the witnessed instances hold a pair of two levels of it. On Town the pair the search reports is the forbidden order between the example’s two strongly connected components on 60% of the witnessed instances, and on the others at least one side lies in a component the example never visits.
An unsolvable instance often holds witnesses on several rows: the median witnessed instance has them on 14 rows on Wall and on 3 on Skyline, so freeing one frozen patch leaves the others in place. On Wall, SimpleWall, Skyline and Flowers, freeing the nearer patch of one witness made no instance solvable, and neither did freeing as many other frozen cells at random.
On the eight resistant examples without a certificate, where the labeling of patches of size 3 has one value and no witness can exist, the labeling of patches of size 4 along rows or columns finds a witness in only 0.4% of their unsolvable instances, and in at most 2% of them on any one example, so a quantity at that patch size explains almost none of them. Each witness found there pairs the component of the labeling that the example visits with one it never shows. On these examples a witness needs a frozen patch from such a component, so the share is low partly for that reason.
The min-coin copy on the corpus
We ran the min-coin copy of Proposition 2 on the certified examples, on Chess and Stripes, and on uncertified examples for contrast. It runs on tori, so no margin of width r r r § 7 . The radii from 8 to 128, each twice the one before, cover the thirteen certified examples, Chess, Stripes and ten uncertified examples spread over the classes of § 7 , and Wall alone runs at the two radii beyond, up to 512. Radius 64, fixed before the run, and the independent-coin rule’s radius 32, added before it, cover all 52 public examples. At radius 64 the share of the copy’s windows that straddle two regions about equals the share of the windows of block-shifted tiles that straddle a block boundary, so the two can be compared there. Each canvas is measured before mending and after mending as in the main protocol.
The copy behaves as the proposition says. No forbidden window on any canvas has cells that all copy from one cell, the share of windows whose cells copy from more than one cell lies within 4% of q r q_r q r q r q_r q r ε \varepsilon ε p s p_s p s κ ( 0 ) \kappa(0) κ ( 0 ) 1 − max s p s 1-\max_s p_s 1 − max s p s r ε r\varepsilon r ε ε / q r \varepsilon/q_r ε / q r
On Wall, mending removes few of the copy’s forbidden windows, and the mended rate still falls as 1 / r 1/r 1/ r r r r
On the uncertified examples mending repairs far more of the copy’s defects, in an analysis we made after the run. At radius 64, mending removes the largest share of the copy’s forbidden windows among the certified examples on SimpleWall, 44%, and the smallest among the uncertified ones on ColoredCity, 51%; the medians are 28% and 98%. The uncertified side includes the eight uncertified examples that resist independent coins, although every one of them stays invalid. At radius 32, where the regions are smaller, the ranges overlap: mending removes up to 29% on a certified example (Flowers) and as little as 15% on an uncertified one (Cat).
At these two radii the copy makes nothing valid that the independent-coin rule or block-shifted tiles leave invalid. At radius 32 it is valid after mending on 16 uncertified examples, all among the 28 that the rule makes valid, and at radius 64 on 19, all among the 23 that the tiles make valid (§ 8.3 ). At radius 128, where the regions are larger, it is valid on six of the ten uncertified examples of the ladder, among them Skew2, which resists independent coins.
The mending maps
Under independent coins mending makes some examples valid and leaves others far from valid. Of the 52 public examples, 16 mend to at most one forbidden window in a thousand within radius 4, and 5 more, Dungeon, Angular, Office, Office2 and Cats, once radius 8 is allowed, for 21 in all (Table 11 ). 10 are partial, at most one forbidden window in a hundred, and 21 are resistant, the skylines, the brick walls, most of the cities, the mazes RedMaze, ScaledMaze and SimpleMaze and the figurative Cat among them; a constant coloring satisfies 15 of these. The knots and links, whose crossings must stay consistent along a strand, are not among them. With blocks of 32 and radius 16 the independent-coin rule becomes valid on SimpleKnot, Lines, City, Water and TrickKnot as well (Table 12 ), and with cluster completion at radius 24 on 28 examples in all (Table 17 ). From radius 8 to radius 24 it gains seven examples, City, Lines, Link, Qud, SimpleKnot, TrickKnot and Water, every one of them partial, so it makes no resistant example valid at any radius we tried.
Table 11. The mending map of the independent-coin rule: one 256 2 256^2 25 6 2 ∣ K ∣ |K| ∣ K ∣ Figure 5 groups the examples by this class. The classes rest on this one canvas, and every certified example lies far from their boundaries, with at least 0.024 of its windows forbidden at radius 8. Sorted by the radius-8 residual.
Table 12. Wider mending of the independent-coin rule without cluster completion on the ten partial examples: the forbidden-window rate after mending within radius 8, 12 and 16 (blocks of 16, 24 and 32) on the canvas of Table 11, and on how many of three seeds radius 16 leaves at most one forbidden window in a thousand.
On Wall, Fabric, Flowers, Skyline and SmileCity the radius-8 residual is higher than the radius-4 one, because a block for which the solver finds no completion is left as it was and the two maps use different block lattices. At 1024 2 1024^2 102 4 2 Table 13 ), Chess and Stripes stay at about 6% and 6%, Wall at 9% and Qud at 2%, while Col3 mends to 0.8%. The mending radii concentrate within 2 on the examples the independent-coin rule handles best and spread to 3 and 4 on the harder ones. On Sand, Rooms, Maze and Sewers the divergence of the mended output rises over the rule’s own, since the solver’s completions are not draws from the rule’s distribution.
The complete solver
The mender’s failures under independent coins are not an artifact of its capped solver. A complete SAT solver, CaDiCaL 1.9.5 ([8 ] ), given each block that the mender failed on within radius 8 together with its frozen surroundings, completes none of them, on Wall or on the uncertified examples we tested, and the rule’s defects are harder to complete than random errors placed at the same density on a valid canvas (Table 14 ). This holds for each block as the rule left it: cluster completion within radius 24 frees a wider region one cluster at a time and makes City and Qud valid under independent coins. On Skew2 and Sewers, which resist independent coins and carry no certificate, the share of unsolvable instances hardly changes as the radius grows, and the octave rule makes both valid.
Each test concerns one instance, a frozen surrounding and a free region, and says what no mender could do there; it does not say that the example itself forces defects. When every cell within radius 8 of a single defect is freed, the instance is unsolvable for 77% to 96% of the rule’s defects on City, Qud, Skew2 and Sewers, against 43% to 69% for random errors placed at the same density on a canvas free of forbidden windows. The gap persists when the number of other forbidden windows nearby is kept fixed.
The SAT encoding is sound, and the solver decides what we ask of it. An instance frees every cell within distance ρ \rho ρ
The share of unsolvable defects changes little with the radius. A profile is the share of unsolvable instances at ρ = 4 \rho= 4 ρ = 4 ρ = 16 \rho= 16 ρ = 16 Table 14 , 37 of 46 profiles change by at most 10 points from ρ = 4 \rho= 4 ρ = 4 ρ = 16 \rho= 16 ρ = 16 ρ = 8 \rho= 8 ρ = 8
gave the same picture: Cave’s defects are all solvable within radius 4 (100%), Maze’s mostly (81%), Wall’s not at radius 16 (100% unsolvable), and of the 117 defects the mender left on the five examples of Table 14 other than Wall, 2.6% are solvable within radius 8. That design left 0% of its instances at ρ ≤ 8 \rho\le8 ρ ≤ 8
The floor on the independent-coin rule
Through the example’s statistics the floor constrains the trained independent-coin rule only where that rule’s statistics lie within κ f \kappa_f κ f δ \delta δ Table 8 gives that distance. On 5 of the 10 examples with P = N P = N P = N δ \delta δ κ f \kappa_f κ f (1) holds whatever its defect density. On 3Bricks, where P > N P > N P > N δ \delta δ κ f = 0.125 \kappa_f = 0.125 κ f = 0.125 κ ( δ ) = 0.051 \kappa(\delta) = 0.051 κ ( δ ) = 0.051 (1) , and at the upper end of the rule’s δ \delta δ η 0 = 0.001 \eta_0 = 0.001 η 0 = 0.001 § 13 .§ 7 ), it stays positive on 3Bricks, Platformer and Skyline2. On Town the rule’s δ \delta δ κ ( 0 ) \kappa(0) κ ( 0 ) κ f \kappa_f κ f ({xref}Table 9`), and its value can only grow as δ \delta δ δ \delta δ δ \delta δ κ f \kappa_f κ f
Theorem 1 with the rule’s own statistics needs no comparison with the example: it bounds ε \varepsilon ε p s p_s p s Table 15 measures p s p_s p s § 7 on eleven of the twelve examples, all but 3Bricks, as we expected before measuring, but this count leans on the rule’s own defects: when P = N P = N P = N ε \varepsilon ε φ \varphi φ φ \varphi φ Table 8 ).
Table 15. Table 15. Theorem 1 with the independent-coin rule’s own statistics, on the certified examples with an invariant or a phase. Each row pools the rule’s three 256 2 256^2 25 6 2 p s p_s p s P × P P \times P P × P φ = s \varphi= s φ = s ( 1 − max s p s ) / ( ( 2 r + P + 1 ) ( P − N + 1 ) 2 ) (1 - \max_s p_s)/((2r + P + 1)(P - N + 1)^2) ( 1 − max s p s ) / (( 2 r + P + 1 ) ( P − N + 1 ) 2 ) ε \varepsilon ε max s p s \max_s p_s max s p s max s p s \max_s p_s max s p s
SmileCity’s box lattice
SmileCity stays invalid under the input that the procedure prescribes: the rule does not keep its faces on one lattice, and that lattice is not a quantity that a certificate over finite patches names. Its example is one face six cells wide inside a black border one cell wide, so its tiling is a lattice of faces with gaps two cells wide, of period eight along both axes. Each face has rows of eyes, a mouth row and white rows between them, and the mouth is the only place where the example puts two red cells side by side. The search finds a phase of period two along columns, from patch size five, and on every canvas of both training seeds the rule given the phase channels respects that phase at every patch, before and after mending. Almost every forbidden window touches a face of the wrong width instead, at vertical walls where the rule switches between the two lattices of faces modulo eight along the rows.
The widths a face can take explain why no patch fixes that lattice. A complete SAT solver, CaDiCaL 1.9.5 (Biere et al., [8 ] ), run on the example’s window set, with every coloring it returns checked again by our counter of forbidden windows, finds that a face with a bottom, a run of non-black cells with black on both sides and black below, is satisfiable only six cells wide among the widths from one to 30, while a face without a bottom, running to the edge of the grid, is satisfiable at exactly the widths that are multiples of three, at every eight from two to 24, and so is a column of faces that never closes. Strips of eight rows that wrap along the rows are periodic with periods 3, 5, 6, 8, 9, . . . when they hold no mouth, and only with periods 8, 13, 16, 18, 19, 21, 22, . . . when they hold a mouth with the rows above and below it. Whether a face has a bottom is not a property of any finite patch: a column of faces three cells wide, alternating rows of eyes and white rows with no mouth, fits beside the example’s gap columns at any vertical alignment, so strips that repeat the example’s eight columns m m m 8 m + 5 8m + 5 8 m + 5
The solver also shows where a world free of forbidden windows can change the lattice: between two strips of faces separated by two black rows across the whole width, at every shift, and along the rows through a column of faces three cells wide that never closes, which shifts it by five. In the instances we solved it never changes without such rows, although black strips that do not span the width occur in them, and never along a strip bounded by black rows. The rule’s vertical walls between the two lattices are neither, and mending within radius 24 cannot remove them, since a wall runs through many faces. Within radius 48 mending lowers the share of forbidden windows to 0.32 of its value, still above the threshold. Within radius 96, where the mender’s first block covers nearly the whole canvas and rewrites 50% of its cells, it removes them on every canvas, and the total variation of the window statistics from the example’s rises from 0.16 to 0.33 (Appendix § 23 .§ 10 ). The lattice is within the rule’s reach, since the octaves’ grid already carries the position modulo eight along the rows, eight dividing 16, and with the coordinates modulo 4, 8 and 16 given as channels the rule still leaves 0.018 of its windows forbidden after mending (Table 31 ), so it does not place its faces on the lattice. The lattice is no obstacle to random access as such: since the example’s first and last rows are black, shifting each band of eight rows of the tiled example by an offset drawn from the band’s coin leaves no forbidden window for any value of the coins and keeps the example’s statistics exactly (Appendix § 14 ). The learned rule does not find such worlds, and we report SmileCity as open for it.
Table 31. SmileCity under inputs that carry the position of its faces, each given with the octaves and trained as the method’s rules are: the range over the three canvases of the share of forbidden windows after mending within radius 24, at training seeds 0 and 1, one value where its ends agree; a dash marks a rule we did not train. The first row is the input the procedure prescribes; the others are not prescribed. None is valid. Figure 5 gives the octave rule’s.
The diffusion model and its protocol
The diffusion model of § 7 is a generic convolutional denoiser that draws each cell from independent noise within a finite radius, so Theorem 1 applies to it. Of its settings only the training budget and the number of levels were chosen on a trial run, described at the end of this appendix.
Denoiser. The denoiser is fully convolutional. A 3 × 3 3 \times3 3 × 3 3 × 3 3 \times3 3 × 3 [53 ] ), a SiLU and a 1 × 1 1 \times1 1 × 1 1 × 1 1 \times1 1 × 1 3 × 3 3 \times3 3 × 3
Examples and input. On noise alone the model is trained on the thirteen certified examples, on Chess and Stripes, and on the ten uncertified examples of Appendix § 20 .§ 2 , of which the independent-coin rule makes Cave, Maze, Knot, Rooms, Office and City valid. With the input, the first convolution also reads at every level the input that the decision procedure of § 6 gives the method’s rule, without the octaves: the state of the cell’s row, drawn by the row-type sampler, where the certificate is an invariant, and the phase channels where it is a phase. This covers Chess, Stripes and every certified example but Town, whose one-way quantity gets no input.
Training. Each model learns Gaussian diffusion (Ho et al., 2020) on one example’s one-hot colors, scaled to ± 1 \pm1 ± 1 [48 ] (offset 0.008, the noise variance added at each level capped at 0.999), and predicts the added noise. An update draws 32 crops of 64 by 64 cells from the tiled example at uniformly random offsets, each at a uniformly drawn level, and the loss is the squared error of the predicted noise on the cells that the unpadded convolutions leave, so neither padding nor position enters training. With the input, a crop carries the example’s own input at its cells, the states of its rows or its coordinates modulo the period, set to zero on 10% of the crops so that the network also predicts without it. Training runs 20 000 updates of AdamW (Loshchilov & Hutter, [41 ] ) at a constant learning rate of 2 ⋅ 10 − 4 2 \cdot10^{-4} 2 ⋅ 1 0 − 4 (6) , the variation term included.
With the input, training shows the denoiser only the example’s own sequence of row states, and on Wall, SimpleWall and 3Bricks most stretches of rows that one step reads, as the sampler draws them, never occur in it. On Wall at training seed 0 the model is valid after mending on the sampler’s input, and also on the example’s own sequence repeated down the canvas, on canvases kept out of every count.
Sampling. Canvases are drawn by ancestral sampling (Ho et al., 2020) over 50 of the 1 000 levels, spaced evenly with both ends kept (Nichol & Dhariwal, [48 ] ). Each step clips the predicted clean image to [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] [58 ] ). The secondary sampler is the deterministic sampler of Song et al. [61 ] , over the same levels from the same initial noise. With the input, the primary sampler is the plain conditional model, and guidance (Ho & Salimans, 2022) at weight w = 2 w = 2 w = 2 ϵ ^ ( x , c ) \hat{\epsilon}(x,c) ϵ ^ ( x , c ) ( 1 + w ) ϵ ^ ( x , c ) − w ϵ ^ ( x , 0 ) (1+w)\hat{\epsilon}(x,c)-w\hat{\epsilon}(x,0) ( 1 + w ) ϵ ^ ( x , c ) − w ϵ ^ ( x , 0 )
Drawing a canvas. A canvas of side S S S S + 2 r S+2r S + 2 r r = 300 r = 300 r = 300 r r r
Evaluation. Canvases are measured as the rule’s are. The primary sampler draws canvases on the development and robustness seeds, the secondary sampler and guidance on the development seeds only. The sampler has no repair rounds, so the mender of § 7 takes its output as it is, within radius 24 on blocks of 48, with cluster completion, in two passes. Each canvas is measured before mending, as the raw canvas, and after, by the defect rate, total variation, normalized agreement and repetition of Appendix § 17 .§ 3 , with the share of cells the mender changes; aligned variation is taken over the mended canvases of the development seeds. On the raw canvases of the examples with a transported quantity, p s p_s p s § 17 .§ 3 , taken on patches of the certificate’s size, counts how often the quantity departs from its transport between consecutive locally valid patches along its direction, per hundred patch positions. A sweep draws one raw canvas of side 2 048 at each of 10, 20, 50 and 100 levels on noise alone at training seed 0, on Wall, SimpleWall, Fabric and Cave.
What the model does with and without the input. Given the input, fewer than one in a hundred of a canvas’s 16 × 16 patches occur in the tiled example on Flowers, MoreFlowers, Platformer, SimpleWall and Wall, so those worlds are not copies. Nor do the mended worlds, which the model and the mender make together, copy whole rows, as the copier does while keeping few of the example’s patches: in a test we wrote down before reading its canvases (Table 32), none of the 17 409 rows with more than one color on their mended canvases, 16 per example over both training seeds, is a row of the example up to a shift, against our prediction that on Wall and SimpleWall at least half would be, while on Fabric, RedMaze and SimpleMaze every such row is. On Wall 3% to 4% of the model’s windows as tall as a course and 16 cells wide occur in the example. On nine of the examples with the input the quantity never switches value along its direction (§ 8.5 ). On the two skylines, where the model given the input stays invalid, the mender changes at least 38% of their cells. From noise alone the model is a rougher generator than the independent-coin rule, whose objective penalizes forbidden windows: on the certified examples it leaves 1.4 to 3.1 times as many forbidden windows as the rule does before its repair rounds, and on the controls a median of 7.4 times as many. More levels barely help: over 100 levels its share on Wall, SimpleWall and Fabric is at least 0.89 of its share over 20. More levels also make each denoising step smaller, so the sweep does not isolate a cause, but the min-coin copy does far better at the model’s radius (Figure 3 ), so the radius alone does not force rates this high.
Seams. Chunks drawn separately agree with the whole canvas, and only the precision of the arithmetic limits how exactly a canvas is reproduced. On Wall, under both conditions and at both training seeds, a chunk of 64 by 64 cells drawn on its own larger canvas is compared with the same cells of the whole canvas. Canvases are sampled in half precision, in which the two pass through convolutions of different shapes that the GPU library does not promise to round alike, so each check is repeated in single precision and read there. In single precision none of the chunk’s cells differ from the whole canvas, and in half precision none. The whole canvas drawn in half and again in single precision differs on 0.021% to 0.22% of its cells.
Budget and levels. The training budget and the number of levels were set on Cave before the study’s other runs, against a bar fixed in advance that no setting met. The setting was to be the smallest budget, then the fewer levels, at which the model on noise alone is valid on Cave after mending and its raw rate at each development seed is at most three times the independent-coin rule’s raw rate, before repair, at that seed, so that a failure on the certified examples could not be put down to a poor sampler. Cave was trained at training seed 0 for 20 000 and 60 000 updates and sampled at 20 and 50 levels; Wall, trained alongside under both conditions, took no part in the choice. Every setting was valid on Cave after mending and none met the bar: more updates raised the raw rate, and more levels lowered it a little. We ran the study at the setting with the lowest raw rate, 20 000 updates and 50 levels, and the models of Wall and Cave trained there for the choice are the study’s models at training seed 0. At that setting Cave’s raw rate is 19 times the independent-coin rule’s, and the mender changes 15% of its cells against 0.45% for the rule. The model is thus rougher than the rule before mending, and Table 16 gives its raw rate against the rule’s and the share of cells the mender changes beside every count.
The other samplers. The counts change little with the sampler. Given the input, the deterministic sampler is valid after mending on 18 of the 28 models and guidance on 19, against 20 for the primary sampler; on noise alone the deterministic sampler is valid on 4 of the 50 models, and the primary sampler on 4.
Further results
Validity across radii, canvases and seeds
The octavе rule’s lead over independent coins grows with the mending radius, from six examples at radius 8 to twelve at radius 24 (Table 17 ). At radius 8 that lead is net of one loss, Cats, which independent coins make valid and the octavе rule only from radius 16 on; from radius 8 to radius 24 the octavе rule gains thirteen examples and loses none. Cluster completion makes no example valid at radius 8 that mending without it leaves invalid, under either rule. It gains at radii 16 and 24, whose blocks are large enough to hold several clusters of defects.
Validity survives added canvases and fresh coin seeds on all but a few examples. On all eight canvases of the robustness test the method is valid on 41 examples, losing Cat, Cats, Skyline2 and Town, and on the fresh seeds, which no decision used, it loses only Cat, while the independent-coin rule is valid on all eight canvases and on the fresh seeds on the same 28 examples as on the development seeds (Table 17 and Table 18 ). Nor does validity lean on the threshold’s allowance. On 34 of the examples the method makes valid no canvas keeps a single forbidden window, and the same holds on 27 of the octave rule’s 40 valid examples and on 23 of the independent-coin rule’s 28.
The one certified example that the method loses at another training seed (§ 10 ), Skyline2, is invalid at seed 1 and valid at seed 2. On Wall every canvas at every seed is free of forbidden windows and lies closer to the example’s statistics than Theorem 2 allows any generator on independent coins free of them (Table 18 ). The octave rule, trained from seeds 1 and 2 on every example, is valid on 38 and on 38 examples, against 40 at seed 0, and on 36 at all three.
The mender’s second pass, which re-solves the blocks of a lattice shifted by half a block, is part of the method. With one pass at radius 24 the octave rule is valid on 32 examples and the independent-coin rule on 25, and the second pass takes 13% of the mending time.
Wider mending rewrites more of the canvas. On the examples the octave rule makes valid at radius 8, mending changes a median of 0.071 of the cells at that radius and 0.12 at radius 24; on the examples that only radius 24 makes valid it changes 0.31, and up to 0.52 on one example. The independent-coin rule’s median on its own valid examples at radius 24 is 0.23, and on the examples the method makes valid the median is 0.18. The mender redraws every cell it frees, so these shares count cells rewritten whether or not they were wrong. A pass that put back every changed cell whose old color keeps its windows allowed left the shares almost where they were, so almost every rewritten cell would make a window forbidden if its old color returned, and we did not adopt the pass.
Examples from other implementations
Table 19 gives every generator of the test of Appendix § 19 on each of the 27 examples, grouped by the repository each came from.
Hand-written priors and the mender
Random-access rules written by hand do worse than the learned independent-coin rule, in rate or in divergence, on every example we ran them on. The first draws every cell independently from the example’s color marginals with hashed coins and then runs our own coin-gated repair step for 32 or 64 rounds. The second, the Metropolis rule, puts hashed coins on the window energy E = Λ ⋅ # { forbidden windows } − ∑ allowed log f ( w ) E = \Lambda\cdot\#\{\text{forbidden windows}\} - \sum_{\text{allowed}} \log f(w) E = Λ ⋅ # { forbidden windows } − ∑ allowed log f ( w ) Λ = 2 max ( − log f ) \Lambda= 2\max(-\log f) Λ = 2 max ( − log f )
✓ valid: after mending within radius 24, at most one window in a thousand forbidden on each canvas; – invalid rule’s radius. Both were run on the examples of Table 13 with Chess, Stripes and Col3, at 256 2 256^2 25 6 2 512 2 512^2 51 2 2
The Metropolis rule’s raw forbidden-window rate is at least twice the learned rule’s on 11 of 12 examples at 32 sweeps and on 10 of 12 at 64, at median ratios of 5.2 and 3.9. Independent sampling followed by repair sits 7.6 times above the learned rule at the median after 32 rounds and 5.7 times after 64, and at least ten times above it on 3 of 12. The Metropolis rule’s divergence is worse than the learned rule’s on 5 of 12. After mending, the learned rule’s residual is at most half the Metropolis rule’s on 11 of 12, at a median ratio of 6.8. No hand-written rule comes within twice the learned rule on both the rate and the divergence on any example (0 of 12). Sand is the one example where a hand-written rule reaches a lower rate than the learned rule, and it does so by collapsing to nearly one color, which its energy rewards and its divergence reports (Table 20 ). The term − ∑ log f ( w ) -\sum\log f(w) − ∑ log f ( w )
Table 20. Hand-written rules against the learned independent-coin rule, on one 256 2 256^2 25 6 2 Table 11 . The forbidden-window rate of the independent-coin rule at 32 rounds, raw and after four repair rounds and mending within radius 4 with blocks of 8, of independent sampling followed by 32 or 64 rounds of our repair step, and of the Metropolis rule after 32 and 64 sweeps and after the same mending; the pattern KL to the example of the independent-coin rule’s raw output and of the Metropolis output after 64 sweeps.
As a prior for the mender of the main protocol, run for 64 sweeps before the method’s repair rounds, the Metropolis rule is valid on 20 examples, none of them certified, as many as the octave rule run for 4 rounds. It reaches Link2, Mountains and Skew1, which neither learned rule makes valid (Appendix § 23 .§ 11 ). A longer run adds nothing. At 1 024 sweeps, sixteen times as many, it stays invalid on all nineteen uncertified examples it misses at 64, and the octave rule makes 17 of them valid, so the octave rule’s lead there does not come from the budget of the sampler.
What the learned rule leaves decides how far the same mender gets. The octave rule’s weights, run for 4, 8, 16 and 32 rounds before the same four repair rounds and the same mender within radius 24, are valid on 20, 32, 39 and 40 examples, each set contained in the next, while the median share of forbidden windows before mending falls from 0.092 at 4 rounds to 0.020 at 32.
Mending alone does not make a world from noise. Started from i.i.d. colors at the example’s color frequencies and mended within radius 24, each of the 52 public examples keeps at least 0.38 of its windows forbidden on every canvas. Nor do the row-type sampler and the mender make a wall on their own: from the painted row types of Appendix § 17 .§ 2 , mended within radius 24, between 0.75 and 0.99 of the windows stay forbidden on Wall, Skyline and Skyline2. In both cases the mender frees regions bordered by noise on every side, and almost none of them can be filled; on the painted row types it changes no cell.
Block-shifted tiles, whose forbidden windows all lie on block boundaries, are valid after mending on 23 examples, all of which the octave rule makes valid but Skew1, and on none of the certified ones: there, two blocks whose courses or phases differ meet at a boundary that no completion within the mender’s box joins, as Proposition 1(a) leads one to expect. A median of 0.46 of their 16 × 16 16 \times16 16 × 16
The input alone, and composition under it
The copier is valid before mending wherever it exists (§ 8.2 ), and § 8.3 compares it with the rule. Given the row types and only its own independent coins, without the octaves, a learned rule is valid on two of the three examples we tried, Skyline and Wall. On Fabric, RedMaze and SimpleMaze, each of them one period of its phase in size, painting the example’s cell at the coordinates the phase channels give yields the tiled example (§ 8.2 ), and on the two mazes this world is the only valid one up to translation. Given only the coordinate along the certificate’s direction, the rule is valid on
Fabric and on neither maze.
On Wall and SimpleWall, whose courses are short and whose offsets at the joints vary, fewer than one in a hundred of the copier’s 16 × 16 16 \times16 16 × 16 Table 21 ). The method’s rule on Wall leaves about one in a hundred of its windows forbidden before mending, mending rewrites 3% to 6% of its cells, and between 0.011 and 0.021 of its windows as tall as a course and 16 cells wide occur in the example. On the eight examples with a row invariant, the octave rule’s share of rows that are rows of the example, up to a horizontal shift, lies between 0.043 and 0.30.
To generate a chunk, the re-solved copier draws the copier’s canvas over every block the chunk depends on, re-solves each block of the random-access block solver’s lattice under its frozen surroundings with the same complete solver, in two passes, and then mends the chunk with the main mender, which finds nothing to change. The passes redraw 16% to 37% of the cells. One thread spends 46 to 457 CPU seconds per 256 2 256^2 25 6 2 256 2 256^2 25 6 2 § 23 .§ 9 ).
The re-solved copier’s statistics are those of the solver. On Wall they lie 0.13 to 0.14 from the example’s, against 0.12 for the random-access block solver run from the tiled example (Table 37 ). On each of the six examples where both were measured, every example with a copier but Skyline2, its distance from the example’s statistics is within 0.02 of the distance the same solver reaches when it starts from the tiled example; among them is Platformer, the one example where the re-solved copier lies farther from the example’s statistics than the rule. On Wall its bricks are nearly the block reference’s, with a median of 8 cells and a 90th percentile of 18–19, against 8 throughout the example, and so are its joints (Table 22 ). It keeps less of the tiling than the copier on all seven examples, since the passes redraw the copied rows while the sampled layout stays. On Wall its worlds vary between seeds at least as much as the method’s and keep as little of the tiling (Table 24 ).
Table 37. The independent-coin rule after mending against the random-access block solver of § 7 , which starts from shifted replay and re-solves the 16 × 16 16 \times16 16 × 16 256 2 256^2 25 6 2 Table 36 ; the last column is the solver’s cost per cell over the independent-coin rule’s, single-thread CPU time.
The rule’s distance from the example’s statistics on Wall lies in how it fills its rows: the distribution of its row types is within 0.014 of the example’s in total variation. Wall’s example has courses of bricks between rows of mortar, and inside a course a joint of the mortar color ends each brick. We call a cell a course cell when its 3 × 3 3 \times3 3 × 3 Table 22 ). A window that holds a joint is one outcome class of the window statistics, so the total variation is at least the difference between two generators’ masses on that class; for the method this difference is about 70% of its total variation, and the same share holds for the block reference and the Metropolis filler. Wave Function Collapse’s own output lies 0.26 from the example’s statistics on Wall, and the two block solvers, which keep the tiled example’s layout of rows, lie closer still, as does the re-solved copier, which follows the sampled layout.
The Metropolis filler of Appendix § 17 .§ 2 , after 256 sweeps and the same mender, is not valid on Platformer, Skyline, Skyline2 or 3Bricks, where at least 0.067 of its windows remain forbidden after mending. On all eight examples with a row invariant the rule’s worlds lie closer to the example’s statistics than the filler’s on every canvas (Table 21 ). The filler also reads farther: after 256 sweeps its reach is 4 608 cells on each side, against the rule’s 32.
Composition before mending. A 16 × 16 16 \times16 16 × 16 Table 23 counts only the patches that hold none, and the rows with more than one color that no forbidden window touches. On every example with a row invariant they are at least 5% of the rule’s patches, 1 495 989 patches and 4 178 rows in all, and none of them occurs in the example. Nor does any of the 16 × 16 16 \times16 16 × 16
Copies and variation
The block solvers keep the tiled example’s layout of rows. On the seven examples whose row type is read from a single 3 × 3 3 \times3 3 × 3 § 8.3 ), only the rows around the fixed course tops where the sampler’s bands meet have the same type on every canvas (Figure 10 ). On the other examples with a row invariant the method’s worlds keep more of the tiling than on Wall, up to a normalized agreement of 0.37 on Platformer, whose bands differ only in the order of their runs (Appendix § 15 ).
The octave rule’s valid worlds are not copies of the example either, and they vary as much as those of independent coins. Over the examples each rule makes valid within radius 24, the octave rule’s median aligned variation is 0.39, against 0.37 for the independent-coin rule, and its median normalized agreement is 0.065, near that of an i.i.d. draw. On the 28 examples both rules make valid, it is 0.061, against 0.046 for the independent-coin rule. Before mending, the window statistics of both rules are as close to the example’s as Wave Function Collapse’s own output on most examples, and after mending the octave rule’s lie the closer at the median (Section N.8).
Against the references at radius 8 each measure separates the methods example by example (Table 25 ). At the median over the 27 examples the octave rule makes valid there, none of a canvas’s 16 × 16 16 \times16 16 × 16 Figure 9 ).
Figure 9. Variation against window statistics on the 27 examples the octave rule makes valid at radius 8. For each example, the variation between two canvases after the best alignment (higher means more varied) against the total variation of their 3 × 3 windows from the example’s (lower means closer statistics), for the octave rule mended within radius 8 and for the block reference of § 7 ; a line joins the two. Means over eight canvases. Shifted replay matches the statistics and does not vary; its value on Font reflects an alignment search shorter than Font’s period. An i.i.d. draw from the color frequencies lies beyond the axis.
The random-access block solver after its first pass varies less than the octave rule, 0.31 against 0.36, and keeps more of the tiling, with normalized agreement 0.37 against 0.07; the octave rule varies more on 21 of the 27 examples (Table 26 ). After both passes, the least it can run, the solver varies as much as the octave rule at the median, 0.37, and still keeps more of the tiling, 0.11 against 0.07. Example by example the two measures favor different methods: the solver varies more than the octave rule on 17 of the 27 examples and on 17 of the 24 of them that carry no certificate, and the octave rule keeps less of the tiling than the solver on 19 of the 27 and on 16 of the 24 (Table 26 ). Neither copies the example’s patches: on none of these examples does a 16 × 16 16 \times16 16 × 16 § 23 .§ 9 ).
Table 26. The octave rule after mending against the random-access block solver of § 7 , which starts from shifted replay and resolves the 16 × 16 blocks of an absolute lattice class by class, each block seeded by its coordinates, read after its first pass and after both. The octave rule is run under the protocol of the references (Table 4 ): mended within radius 8 without cluster completion, on the 27 examples it makes valid at that radius. Means over eight 2562 ^{2} 2 Table 25 .
Table 26.
Edits are contained by construction, within the reach of § 2 , and they change little of the world. Redrawing the fine coins of a 32 × 32 32 \times32 32 × 32
No rule is trained on structure larger than the window, and the two rules keep the example’s connectivity about equally often. On the 19 examples of the independent-coin rule’s valid set at radius 8 that have a passable color, the largest region of that color holds at least four fifths of its share under shifted replay on 16 under the octave rule and on 15 under independent coins. On City, Dungeon and Angular the octave rule’s correlation stays above the tenth of its value at lag one at every lag we measured, up to 32, while the independent-coin rule’s falls below it at lag 9 to 10, and part of what persists follows the grid of the octaves (Figure 7 ). Appendix § 17 .§ 3 defines both measures.
The octaves and the variation term
Training finds the direction of the rows among the octaves without being told it. The octaves share coins along rows and along columns alike, and on SimpleWall the octave rule’s mended worlds keep no forbidden window on its three canvases (Figure 6 ), so the row type stays constant along every row. On Wall the octave rule lowers the residual of independent coins but leaves Wall invalid (Figure 5 ); there the row types that the certificate prescribes keep every row’s type, as in Figure 2 (c).
The octaves leave their grid in the output. On raw canvases we compared the 3 × 3 windows that straddle a boundary of the blocks of side 4 or 16 with all other windows, by the total variation between their histograms, and took the largest value over the two periods and the two axes. For the independent-coin rule, which commutes with every shift, this grid statistic measures sampling noise alone. Over the 27 examples the octave rule makes valid at radius 8, its median is 0.11 for the octave rule and 0.029 for the independent-coin rule. The same statistic at periods 5 and 7, which a law periodic in 16 cannot favor, measures the octave rule’s own longer-range structure, and the value at the block periods is more than twice that on all but 9 of the examples. Coins that vary smoothly between lattice points, as in octave noise, keep random access and exact seams. Trained in the same way on every public example, they lower the statistic to 0.060, against 0.10 for the block coins, on the examples both families make valid at radius 8. They make fewer examples valid at each radius (Table 27 ), so the method keeps the block coins.
Table 27 . Block coins, the octaves of the method, against coins that vary smoothly between lattice points, as in octave noise, each read by the octave rule’s construction and trained on every public example. Columns: the examples valid on all three canvases after mending within radius 8 without cluster completion and within radii 16 and 24 with it, and the median of the grid statistic of Appendix § 23 .§ 8 on the raw canvases of the examples both families make valid at radius 8. The block coins’ counts are those of Table 17 ; the smooth coins’ were measured with the same menders and coin seeds.
Table 27.
The variation term is not what keeps the rules from copying. Trained without it, nothing else changed, the octave rule is valid on about as many examples, with the same median normalized agreement (Table 28 ), so it does not take the shortcut of Proposition 1(b), a copy of the example on each coarse block. Under the row types the shortcut is exact, as the copier shows, and the method’s rules on Wall and Skyline trained without the term do not take it either. The rule on Wall is then valid on all eight coin seeds and the rule on Skyline valid on all eight coin seeds, no 16 × 16 16 \times16 16 × 16 Table 28 ). We keep the term because with it the rule leaves the mender less to rewrite, and as a guard on the examples we did not train without it.
Table 28 . The variation term left out, nothing else changed. Upper part: the octave rule on every public example, mended within radius 8 without cluster completion; the examples valid on all three canvases, and the median normalized agreement over the examples the independent-coin rule makes valid at that radius. Lower part: the method’s rules on Wall and Skyline, mended within radius 24; their normalized agreement, and the ranges over the three canvases of the total variation (TV) of the 3 × 3 3 \times3 3 × 3
Table 28.
The term guards against the block copy under coins, not against a layout tied to coordinates the rule is given. Given one-hot channels of its coordinates modulo the octaves’ block sides, 4, 8 and 16, the rule painted one raw canvas for every seed on seven of the ten examples it was trained on, with the term at its standard weight, and under the phase channels every seed gives the same canvas on Fabric (§ 10 ).
Seams and the cost of mending
Seams are exact before mending, and after mending at the margins we tested. The generator’s own seam test, chunked against one-shot generation, is part of every evaluation: it holds cell for cell for the octave rule on all 52 public examples, raw and after repair, and for the independent-coin rule on every public example. For the mended output we take each of the octave rule’s repaired canvases, mend it once as a whole, and mend its interior again in chunks, each chunk mended alone from a window that adds a margin on every side and that keeps its absolute coordinates, so that the lattice, the classes, the passes and every seed are those of the whole canvas. The mender is seeded by the seed, the absolute block coordinates and the cluster’s index alone, so the test does not depend on which coins the rule reads.
With cluster completion within radius 24 and blocks of 48 (Table 29 ), chunked and whole-canvas mending agree on every interior cell at a margin of 64 cells on only 10 of the 120 canvases, at 128 on 81, at 192 on 117 and at 224 on 119. At 192 the canvases that still differ are Cat, Link and Nested, and at 224 one canvas of Cat differs in 442 cells. At a margin of 256 cells every canvas agrees. Each of these tests compares the chunk with one whole canvas of finite size, so it sees only the context that this canvas adds beyond the window: at a margin of 256, with a central chunk of 64 cells on canvases 768 wide, 96 cells. We therefore also mended twelve whole canvases 2048 cells wide, the octave rule on Cat, Link and Nested and the method on Wall at three coin seeds each, whose edge lies 992 cells from a central chunk of 64 cells, past the counted reach, so that on the chunk they have the values of the unbounded world. On all twelve, a chunk mended alone agrees with the whole canvas on every cell at margins of 256, 384, 512 and 760. The margin of 256 remains a measurement on the canvases we tested, not a guarantee, and we do not call chunked mending at this radius exact below the reach counted in Appendix § 16 .§ 3 , 760 cells. The reach grows with the block, since each of the eight class steps reads and writes a box that grows with it. Without cluster completion, within radius 8 and blocks of 16, on 90 canvases (three coin seeds for each of the octave rule’s examples valid at radius 8 and for Wall, Skyline and SimpleWall), no interior cell differs at margins of 64 and 96 cells, nor at a margin of 128 cells on a chunked 512 2 512^2 51 2 2
Table 29. Chunked against whole-canvas mending within radius 24 with blocks of 48 and cluster completion, on 120 canvases (three coin seeds for each of the 40 examples the octave rule makes valid at that radius): the canvases on which every interior cell agrees, at each margin. Margins of 64 and 96 tile the interior of a 256 2 256^2 25 6 2 512 2 512^2 51 2 2 b ^{b} b
The method’s own rules, which read the row types or the phase channels, keep the same seams. On eleven of the twelve certified examples whose input is not the octaves, all but SmileCity, whose rule this test did not include, chunks agree with whole-canvas mending at a margin of 256 cells on all 33 canvases. The rules on the phase channels of Fabric, RedMaze and SimpleMaze leave nothing to mend; on the other eight, mending changes up to 44% of the 64 2 64^2 6 4 2
Mending is the larger part of the pipeline’s cost. On one CPU thread the octave rule and its four repair rounds take a median of 13 seconds per 256 2 256^2 25 6 2 256 2 256^2 25 6 2 § 8.4 ) the ratio of their costs per chunk has a median of 1.0. At that margin a chunk of 64 2 64^2 6 4 2
Wider mending
Are the method’s failures a matter of the mender’s reach? For the seven public examples the method leaves invalid, we mended its repaired canvases again on eight coin seeds, with the same mender within radius 48 in blocks of 96 and within radius 96 in blocks of 192, and wrote down beforehand what we expected (Table 32). Each run first mended one canvas again at radius 24 and checked that it equals the stored canvas cell for cell. The wider blocks lengthen the reach that random access must cover, from 760 cells to 1528 at radius 48 and 3064 at 96.
Within radius 48 the method becomes valid on Skew1 and ScaledMaze (Table 30 ), on all eight canvases, and does not copy: replay agreement and the share of the example’s patches move by at most 0.08. On Skew1 the window statistics move away from the example’s, from a total variation of 0.21 to 0.30. The other five stay invalid. The rates of Lake, Link2 and Mountains do not fall as a group (their median ratio to radius 24’s is 1.02), SmileCity’s falls to 0.32 of its value, and on 3Bricks, whose rows do not glue, six of the eight canvases keep more than one forbidden window in a thousand, against five at radius 24.
Table 30. The seven public examples the method leaves invalid, mended again within radius 48 (blocks of 96) and 96 (blocks of 192), from the same repaired canvases: the share of forbidden windows on the worst of the three canvases that validity reads, the median total variation of the 3 × 3 window statistics from the example’s, and the median share of cells that mending at 96 rewrites. An asterisk marks an example valid on all eight canvases, a dagger a certified example given its input; the run on 3Bricks at 96 reached the time limit set in advance.
Within radius 96 the mender’s first block covers nearly the whole canvas, so where its solve succeeds the mender is close to a global solver. On four examples one or a few block calls leave no forbidden window on any canvas after rewriting 31% to 50% of the cells; Mountains and SmileCity become valid this way, with the window statistics about 2.1 times as far from the example’s as at radius 24. On SmileCity this repairs the lattice of faces that no input of the procedure fixes (Appendix § 21 ). On Lake and Link2 the first solve fails, the mender goes on block by block, and some canvases stay invalid.
What stays open
The certified examples that the method leaves invalid, 3Bricks and SmileCity (§ 8.2 ), are those whose invariant or phase needs a patch larger than the window (Table 8 ). The canvas of 3Bricks that it misses keeps 0.0011 of its windows forbidden. On SmileCity, inputs that carry the position of its faces do not make it valid either: phase channels of period eight along the rows, which the procedure does not prescribe, leave more windows forbidden than the prescribed input, and so do the coordinates modulo 4, 8 and 16 (Table 31 ).
The octave rule leaves five uncertified examples invalid, Lake, Link2, Mountains, ScaledMaze and Skew1. The Metropolis rule with the same mending makes three of them valid, Link2, Mountains and Skew1, so a random-access generator exists for each of these, and the octave rule failed to learn one at each of its three training seeds. On Lake and ScaledMaze neither is valid at training seed 0, and trained from seed 1 the octave rule is valid on ScaledMaze.
Expectations and outcomes
Which of our expectations did the experiments meet, and which did they miss? We wrote each expectation in a version-controlled log before the experiment ran, with the threshold it had to meet and what methods without learning score. Table 32 gives, for each study in the order of the paper, what we expected and what happened, as it fell. The log also holds the expectations for runs that the paper does not report.
Some analyses ran without an expectation written in advance and have no row, among them the mending maps of the whole corpus (Table 11 and Table 45 ), the correlations beyond the window (Figure 7 ), the check of inequality (1) on measured outputs (Section N.4), the full labeling, the linear program with defects and the comparison of each rule’s δ \delta δ κ f \kappa_f κ f Table 8 ), the one-way quantity, added to the certificate search after its first run, which certifies Town, the theorems set against the method’s worlds (Table 9 ), and the count of patches and rows free of forbidden windows before mending (Table 23 ). The forced edits (Section N.7) were planned with the first runs and measured after them. The row-color term, the boundary anchor and the run limits were set after a run had been seen, as was the decision that a certified example counts only with the input its certificate prescribes. Cluster completion departs from the criterion we had fixed for adopting it, which asked that it raise the residual on no canvas at radius 8 and make some example valid there: it raised the residual slightly on a canvas of Wall and made no example valid. We kept it as a candidate because it never lost at radius 16, and it became our mender after comparisons with i.i.d. colors and with independent coins under the same mender, written down before they ran. The comparison of the octave rule with the random-access block solver was set in advance for the solver’s first pass only; its reading after the second pass and its counts on the uncertified examples came after the run (Table 26 ). The rows say what was changed before a run, give both readings where our recount of an outcome differs from the reading made at the time, and say which predictions were never scored.
Table 45. The mending map of the independent-coin rule, run for 32 rounds with four repair rounds, one 256 2 256^2 25 6 2
Where an expectation missed, its row names the parts that did. The independent-coin rule fell short of the rates we expected: with an earlier objective most of its rules of radius 32 collapsed to a constant pattern, and the voxel examples missed their bars. Mending, the certificate, the witnesses, complete search and training for local completability each missed bars of their own. Several early generators for the certified examples missed, Fabric and the mazes were not rigid at the patch size we expected, a floor without learning made Wall valid, and a held-out maze was not certified. The octave rule missed most of its study on thirteen examples and its divergence before mending, the octaves leave their grid in its output, and cluster completion changed more cells than we allowed. The hand-written rules trailed the learned rule on fewer examples than we expected, the random-access block solver kept a higher aligned variation than the independent-coin rule, and the diffusion model missed its pilot, its controls and validity without copying, so by the measure set in advance the input is not sufficient for that model at our training budget. The scan of a solver’s worlds found no persistent dependence on the resistant examples without a certificate, where we expected one on most of them, and the slope of the min-coin copy agreed with the scan on fewer of them than we expected.
Table 32. What we expected from each study, in the order of the paper, and what happened. Counts of the form “a of b” are examples unless the row says otherwise; valid means valid on every canvas of the protocol the row names.
Table 32 (PDF p. 68). Table 32, continued
What a learned rule adds
@page 68/85 starts_mid=1 ends_mid=1
Table 32 (PDF p. 69). Table 32, continued
Additional tables
These tables and figures carry measurements that the paper states without showing, and those that the record of what we expected (Appendix § 24 ) cites. Every table here that mends was made before cluster completion, within radius 8 and blocks of 16, except Table 45 , which mends within radius 4 with blocks of 8, Table 46 , which mends around the pinned block within radius 6, and the wider radii of Table 34 .
Table 34. The octave rule mended wider without cluster completion, on every example where it leaves a defect at radius 8 on some seed: the mean residual over the three canvases of Table 33 after mending within radius 8, 12 and 16 (blocks of 16, 24 and 32), on how many of the three each radius leaves at most one forbidden window in a thousand, and the share of cells that mending within radius 16 changes. Class and asterisk as in Table 33 .
Table 46. Forced edits with the independent-coin rule (32 rounds, four repair rounds): a 192 2 192^2 19 2 2 6 × 6 6 \times6 6 × 6
The octave rule at radius 8
The corpus evaluation without cluster completion, on the same canvases at radius 8, also mended the octave rule’s canvases within radius 12 and 16 with blocks of 24 and 32 (Table 34 ).
At radius 8 the octave rule is valid on 27 examples (Table 33 ), and its worst canvas tells the same story as its mean on almost every example. Without cluster completion, mending within radius 12 makes it valid on 31 and within radius 16 on 32 (Table 34 ), against 35 at radius 16 with cluster completion (Table 17 ). The larger radius changes more cells, and on a few examples, Village among them, the residual at radius 16 is slightly above the one at radius 12. That mender leaves a block as it was when it finds no completion of all its defects together, so one defect it cannot complete keeps every other defect of its block, and a larger block keeps more. This is the effect that cluster completion removes. The 4 phase examples, Fabric, RedMaze, SimpleMaze and SmileCity, keep nearly the same residual at every radius, and the radius-16 mender changes almost none of their cells.
Table 33. Both rules on the corpus at radius 8, evaluated by the same code: three 256 2 256^{2} 25 6 2 3 × 3 3 \times3 3 × 3 Table 11 ); an asterisk marks a certified example. Figure 5 gives the residuals after mending within radius 24.
Validity at radius 8 holds beyond the three canvases. On eight canvases per example (Table 35 ), 26 of the 27 examples are valid on every canvas, and Flowers on all but one. The 4 phase examples stay above one forbidden window in a hundred on every canvas.
Table 35. The octave rule’s residual after mending within radius 8, without cluster completion, on the eight canvases per example of Table 25 : on how many it is at most one forbidden window in a thousand, the mean and the worst. A dagger marks the examples the octave rule makes valid on the three canvases of Table 33 ; class and asterisk as there.
The independent-coin rule against the references
Table 36 is the same evaluation for the independent-coin rule, whose normalized agreement has a median of 0.04 against 0.08 for the block reference.
Table 36. The same evaluation for the independent-coin rule on the 21 examples it makes valid, with the same seeds, mender and block reference. Columns: the total variation from the example’s 3 × 3 3 \times3 3 × 3 ( a − a i i d ) / ( 1 − a i i d ) (a-a_{\mathrm{iid}})/(1-a_{\mathrm{iid}}) ( a − a iid ) / ( 1 − a iid ) 16 × 16 16 \times16 16 × 16
Table 36.
Against the independent-coin rule the random-access block solver runs its two passes, with the lattice shifted by half a block between them, which are the least it can run, and they cost 6 to 56 times the independent-coin rule’s compute per cell, whose cost counts generation, repair and mending within radius 8, so we compared at that cost (Table 37 ). Its outputs have no forbidden window by construction, and they keep more of the replay they start from: normalized agreement 0.10 against 0.04 at the median, and the independent-coin rule’s is lower on 17 of the 21 examples. Its aligned variation is higher, 0.40 against 0.36, and the independent-coin rule’s is higher on 8 of them. Its total variation is above the independent-coin rule’s on 13 examples. On the certified examples it is valid and close to replay, with normalized agreement 0.43 to 0.67 against the independent-coin rule’s 0.02 to 0.09.
The study of the variation term. The study of the octaves on thirteen examples, SimpleWall, Wall, Skyline, Cave, Rooms and the 8 uncertified resistant examples (Table 38 ), trains the same family with no term and with the weight set to 0.3 of the loss. Its rules at the standard weight are the octave rules of those examples, and the rules of the other examples were trained afterwards in the same configuration. The octave rule was also trained without the term on every example, in the configuration above otherwise (Appendix § 23 .§ 8 ).
Table 38. The study of the octaves on thirteen examples (three 256 2 256^2 25 6 2 3 × 3 3 \times3 3 × 3 § 16 (“term 0.3”, three tenths of the loss).
Rules given the direction. The row-coin rule, on SimpleWall, Wall and Skyline, and the column-coin rule, on SimpleWall, are trained from scratch in the configuration of Appendix § 16 , with eight extra channels in place of the coin family and no variation term. Row coins are hashed from the seed, the row and the channel only, so they are equal along every row; column coins are the same channels hashed from the column. On the examples whose certified quantity is a phase of period d d d x m o d d x \bmod d x mod d y m o d d y \bmod d y mod d 2 ⋅ 10 − 4 2 \cdot10^{-4} 2 ⋅ 1 0 − 4
The study of the octaves on thirteen examples separates what the octaves give from what the variation term gives (Table 38 ). The octave rule without the term already reaches or passes the row-coin rule on SimpleWall and Wall (4.5·10− 4 ^{-4} − 4
Shared input given by hand. With row coins the residual falls on all three walls (Table 39 ), by about 98 times on SimpleWall, and the coin edit changes fewer cells. With the phase of the coordinates as input, the residual, the divergence and the cells changed by a coin edit are all zero, which is the signature of a rule that outputs the coordinate tiling, the escape through coordinates of § 3 . On Cave the row coins leave the divergence at 0.028, against 0.026 for the independent-coin rule.
Table 39. The certified quantity as an extra input given by hand. The independent-coin rule, and the same construction trained with row coins (SimpleWall, Skyline, Wall) or with the phase of its coordinates as one-hot channels (Chess, Stripes, RedMaze, SimpleMaze), at 32 rounds with four repair rounds, on three 256 2 256^2 25 6 2
Table 39.
On SimpleWall (Table 40 ) a heavier statistical weight lowers the divergence of the independent-coin rule below its starting value without lowering its residual, and lowers that of the row-coin rule from 0.053 to 0.036 at the heaviest weight, which is still above the independent-coin rule’s starting 0.016. The fine-tuned row-coin rules keep residuals from 3.6 ⋅ 10 − 5 3.6 \cdot10^{-5} 3.6 ⋅ 1 0 − 5 5.1 ⋅ 10 − 4 5.1 \cdot10^{-4} 5.1 ⋅ 1 0 − 4
Table 40. Coins shared by hand on SimpleWall: the independent-coin rule (“ordinary”), the row-coin rule and the column-coin rule, with the weight on the window statistics each was trained or fine-tuned with; means over the three 256 2 256^2 25 6 2 Table 39 , mended as there. Columns: the raw forbidden-window rate, the residual and the 3 × 3 3 \times3 3 × 3 § 7 ), and the agreement with the best translated tiling.
Table 40.
Training for completability. Rewarding a rule on independent coins for leaving defects that the mender completes did not help consistently. We fine-tuned it on City, Qud, Skew2 and Sewers with two rewards: one for each forbidden window removed, and one for each block the mender completes (Table 41 ). The mender’s reward cut the residual to a third of the starting rule’s or less on Qud alone, and to below half of what the defect reward reaches on Sewers alone, where both rewards left more defects than the starting rule.
Table 41. Training for local completability: the mended residual and KL of the starting rule, of the rule fine-tuned with a reward for each defect it removes, and of the rule fine-tuned with the mender’s own success as the reward. The starting rule is the first of the three independent-coin rules of Table 13 ; every rule is run for 32 rounds with four repair rounds on three 256 2 256^2 25 6 2
Table 41.
Inequality (1) on measured outputs
Every measured output that inequality (1) covers satisfies it. Table 42 and Table 43 evaluate it on every output we stored for the certified examples with P = 3 P = 3 P = 3 κ f \kappa_f κ f § 3 . Mended outputs are listed without a slack, since the mender works on an absolute lattice.
Table 42. Inequality (1), ε ( 2 r + 4 ) + δ ≥ κ f \varepsilon(2r + 4) + \delta\ge\kappa_f ε ( 2 r + 4 ) + δ ≥ κ f P = 3 P = 3 P = 3 ε \varepsilon ε δ \delta δ 3 × 3 3 \times3 3 × 3 κ f \kappa_f κ f r r r ε ( 2 r + 4 ) + δ − κ f \varepsilon(2r + 4) + \delta- \kappa_f ε ( 2 r + 4 ) + δ − κ f 1024 2 1024^2 102 4 2 c ^c c 256 2 256^2 25 6 2 Table 36 , mended within radius 8 with blocks of 16; the rows with row coins or a phase input are the rules of Table 39 , three 256 2 256^2 25 6 2 c ^c c ε \varepsilon ε L 1 L_1 L 1 δ \delta δ
The same as Table 42 for SimpleWall, with every rule of Table 40 , each on its three 256 2 256^{2} 25 6 2
Table 43.
The independent-coin rule, example by example
Before mending, the rule on independent coins leaves forbidden windows on most examples, fewer with more rounds within the trained range (Table 44 ). At 32 rounds the median forbidden-window rate is 3.1% raw and 2.8% after four repair rounds, with 35 of the 52 public examples below 5% and 8 below 1%, from 0.1% on Font to 12.3% on RedMaze. The rate falls steeply over the trained range of round counts (Figure 11 ) and is monotone out to 64 rounds on 19 of 56 rules, controls included; beyond the trained range some curves flatten or rise. Chess and Stripes decay at about the rate 1 / r 1/r 1/ r
Figure 11. The independent-coin rule’s forbidden-window rate at 1024 2 1024^2 102 4 2 1 / r 1/r 1/ r
Varying the radius alone (Figure 12 ), Chess and Stripes fall with log-log slopes of − 0.91 -0.91 − 0.91 − 0.94 -0.94 − 0.94 1 / r 1/r 1/ r − 0.78 -0.78 − 0.78 − 1.35 -1.35 − 1.35 − 0.71 -0.71 − 0.71 − 0.54 -0.54 − 0.54 − 0.89 -0.89 − 0.89 − 0.29 -0.29 − 0.29 − 0.60 -0.60 − 0.60
Figure 12. The radius varied alone, from 8 to 64 rounds at one fixed training configuration of the independent-coin rule: the forbidden-window rate at the trained radius against the radius, log-log, with guide lines at 1 / r 1/r 1/ r 1 / r 2 1/r^2 1/ r 2
The mending map at radius 4
Table 45 gives the mending map of the independent-coin rule on every example, mended as a whole within radius 4.
Forced edits
A designer can pin content into a generated world wherever the canvas around it is valid. A coin edit is contained by construction, but a pinned block is a mending problem: the block is frozen at a random position near the center of a mended 92 2 92^{2} 9 2 2 Table 46 ). On Angular and Paths the canvas is rarely free of forbidden windows before the pin, so the changed cells cannot be charged to the pin alone. The resistant examples of Table 11 , whose canvases keep forbidden windows after mending, were not tested with this rule. The forced edits use the independent-coin rule of the corpus evaluation, run for 32 rounds.
Window statistics against Wave Function Collapse
Before mending, both rules match the example’s window statistics at least as well as Wave Function Collapse on most examples, the independent-coin rule more often than the octave rule. The comparison is made on canvases of the same size, scored by the same estimator, since its bias depends on the size (Table 47 ). The independent-coin rule’s divergence is at or below Wave Function Collapse’s on 43 of the 50 examples Wave Function Collapse completes at 128 2 128^2 12 8 2 64 2 64^2 6 4 2 256 2 256^2 25 6 2
Variants of the objective
Each part of the objective removes a failure we saw without it. An earlier run used the soft objective alone, and at radius 32 most of its rules collapsed to a constant pattern with no forbidden window, with a large divergence to the example and no cell changed by a coin edit. The straight-through objective with the color-marginal term and training at every round removed the collapse at 16 rounds on every example (0 of 56 rules collapsed), with a median rate of 5.9% at 16 rounds. Trained at a fixed 32 rounds, the same objective still collapsed on 9 of 52 rules: their output ignored the coins or sat far from the example’s statistics, and on several of them it was a constant coloring with no forbidden window. Drawing the round count afresh at every update removes this. Table 48 reports the variants we ran. More optimization moves the rate furthest of any single change, a harder temperature helps less, and a score-function reward on the hard windows makes the curves fall monotonically from 8 to 64 rounds, beyond the trained horizon. The final configuration combines longer training, the hard-window settings and round counts drawn afresh, and roughly halves the residual again. The octave rule uses the same objective, with the variation term added, and the same schedule (Appendix § 16 ).
