A Formal Comparison Between Chain of Thought and Latent Thought — part 4/9

Cleaned-text code points [47035, 62116). Bibliography omitted here; source.md includes it.

Let the Transformer block be defined as the composition: TF dec ≔ ( id + 𝐅𝐅 L ) ∘ ( id + 𝐒𝐀 L ) ∘ ⋯ ∘ ( id + 𝐅𝐅 1 ) ∘ ( id + 𝐒𝐀 1 ) , \mathrm{TF}_{\mathrm{dec}}\coloneq(\id+\mathbf{FF}_{L})\circ(\id+\mathbf{SA}_{L})\circ\cdots\circ(\id+\mathbf{FF}_{1})\circ(\id+\mathbf{SA}_{1}), (5) where 𝐒𝐀 ℓ \mathbf{SA}_{\ell} and 𝐅𝐅 ℓ \mathbf{FF}_{\ell} denote the causal attention and the feedforward layers at depth ℓ ∈ [ L ] \ell\in[L] , respectively, and id \id denotes the identity function. Given an input sequence x = ( x 1 , … , x n ) ∈ 𝒱 n x=(x_{1},\dots,x_{n})\in{\mathcal{V}}^{n} , we define the initial sequence as: f cot 0 ​ ( x ) ≔ 𝐖𝐄 ⁡ ( x ) + 𝐏𝐄 ⁡ ( [ n ] ) , f_{\mathrm{cot}}^{0}(x)\coloneq\mathbf{WE}(x)+\mathbf{PE}([n]), where the input tokens are first embedded via the word embedding function 𝐖𝐄 \mathbf{WE} and the positional encoding 𝐏𝐄 \mathbf{PE} Then, the continuous thought (Coconut) computes recursively as: f ct k + 1 ​ ( x ) ≔ f ct k ​ ( x ) ⋅ ( TF dec ​ ( f cot k ​ ( x ) + 𝐏𝐄 ⁡ ( k ) ) ) , f_{\mathrm{ct}}^{k+1}(x)\coloneq f_{\mathrm{ct}}^{k}(x)\cdot(\mathrm{TF}_{\mathrm{dec}}(f_{\mathrm{cot}}^{k}(x)+\mathbf{PE}(k))), (6) where ⋅ \cdot denotes concatenation. The final output of the model after T ⁡ ( n ) T(n) steps is defined as the last output length m m tokens of OPEN Dec ⁡ ( 𝐎𝐔𝐓 ⁡ ( f ct T ⁡ ( n ) ​ ( x ) ) ) ) , \mathrm{Dec}\,\left(\mathbf{OUT}\,\left(f_{\mathrm{ct}}^{T(n)}(x))\right)\right), where the final output is produced by a linear projection 𝐎𝐔𝐓 \mathbf{OUT} and Dec ⁡ ( ⋅ ) \mathrm{Dec}(\cdot) is a decoding function that maps the output logits to a token in 𝒱 {\mathcal{V}} : in the deterministic model, Dec ⁡ ( z ) ≔ arg ⁡ max i ∈ [ | 𝒱 | ] ⁡ z i \mathrm{Dec}(z)\coloneq\arg\max_{i\in[|{\mathcal{V}}|]}z_{i} ; in the stochastic model, Dec ⁡ ( z ) ∼ Multinomial ⁡ ( z i / ∑ j z j ) \mathrm{Dec}(z)\sim\mathrm{Multinomial}({z_{i}}/{\sum_{j}z_{j}}) , assuming z i > 0 z_{i}>0 for all i i .

### A.5 Looped Transformer

###### Definition A.4 (Looped TF) .

Let the Transformer block be defined as the composition: TF ≔ ( id + 𝐅𝐅 L ) ∘ ( id + 𝐒𝐀 L ) ∘ ⋯ ∘ ( id + 𝐅𝐅 1 ) ∘ ( id + 𝐒𝐀 1 ) , \mathrm{TF}\coloneq(\id+\mathbf{FF}_{L})\circ(\id+\mathbf{SA}_{L})\circ\cdots\circ(\id+\mathbf{FF}_{1})\circ(\id+\mathbf{SA}_{1}), (7) where 𝐒𝐀 ℓ \mathbf{SA}_{\ell} and 𝐅𝐅 ℓ \mathbf{FF}_{\ell} denote the (non-causal) self-attention and feedforward layers at depth ℓ ∈ [ L ] \ell\in[L] .

Given an input token sequence x = ( x 1 , … , x n ) ∈ 𝒱 n x=(x_{1},\dots,x_{n})\in{\mathcal{V}}^{n} , the initial hidden state is: f loop 0 ​ ( x ) ≔ 𝐖𝐄 ⁡ ( x ) . f_{\mathrm{loop}}^{0}(x)\coloneq\mathbf{WE}(x). At each loop iteration k k , the hidden state is updated by: f loop k + 1 ​ ( x ) ≔ TF ⁡ ( f loop k ​ ( x ) ) . f_{\mathrm{loop}}^{k+1}(x)\coloneq\mathrm{TF}\left(f_{\mathrm{loop}}^{k}(x)\right). (8) The final outputs after T ⁡ ( n ) T(n) loop iterations are decoded as Dec ∘ 𝐎𝐔𝐓 ∘ f loop T ⁡ ( n ) ​ ( x ) , \mathrm{Dec}\circ\mathbf{OUT}\circ f_{\mathrm{loop}}^{T(n)}(x), and the model’s prediction is defined as the last output length m ≤ n m\leq n tokens of this projected sequence.

## Appendix B Deferred Proofs for Section 3

### B.1 Precision Modeling

We focus on signed floating-point numbers, following ( Li et al., 2024 ) , but omit exponents for simplicity.

###### Definition B.1 (Floating-point Representation, cf. ( Li et al., 2024 ) ) .

Consider floating-point numbers with a mantissa part of s s bits and a sign bit of 1, totaling ( s + 1 ) (s+1) bits. We denote the set of such floating-point numbers by 𝔽 s \mathbb{F}_{s} , and define B s ≜ max ⁡ 𝔽 s . B_{s}\triangleq\max\mathbb{F}_{s}.

###### Definition B.2 (Correct Rounding, cf. ( Li et al., 2024 ) ) .

For any x ∈ ℝ x\in\mathbb{R} and any closed subset 𝔽 ⊂ ℝ \mathbb{F}\subset\mathbb{R} containing 0 0 , we define the correct rounding round ⁡ ( x , 𝔽 ) \operatorname{round}(x,\mathbb{F}) as the number in 𝔽 \mathbb{F} closest to x x . In particular, rounding to a floating-point number with mantissa part s s bits is denoted by [ ⋅ ] s [\cdot]_{s} . Rounding applied to vectors is to be operated coordinate-wise.

They also define primitive arithmetic under finite precision by applying rounding after each basic operation. In particular, for multi-operand operations, rounding is applied after each binary operation. Finite-precision summation over more than two numbers is thus defined as follows.

###### Definition B.3 (Summation with Iterative Rounding ( Li et al., 2024 ) ) .

For any s , n ∈ ℕ + s,n\in\mathbb{N}^{+} and vector 𝒙 ∈ ℝ n {\bm{x}}\in\mathbb{R}^{n} , define the summation with iterative rounding to s s -bit precision sum s : ⋃ n ∈ ℕ + ( 𝔽 s ) n → 𝔽 s , \mathrm{sum}_{s}:\ \bigcup_{n\in\mathbb{N}^{+}}(\mathbb{F}_{s})^{n}\to\mathbb{F}_{s}, (9) where, for any n ∈ ℕ + n\in\mathbb{N}^{+} and 𝒙 = ( x 1 , … , x n ) ∈ ℝ n {\bm{x}}=(x_{1},\dots,x_{n})\in\mathbb{R}^{n} , sum s ( x ) ≔ [ [ ⋯ [ [ x 1 + x 2 ] s + x 3 ] s + ⋯ + x n − 1 ] s + x n ] s . \mathrm{sum}_{s}(x)\coloneqq\Bigl[\;\Bigl[\;\cdots\Bigl[\,[x_{1}+x_{2}]_{s}+x_{3}\Bigr]_{s}+\cdots+x_{n-1}\Bigr]_{s}+x_{n}\;\Bigr]_{s}. (10)

Based on this definition, all computations in the Transformer block of Definition A.1 can be represented in finite precision. The inner product and the matrix product are defined as 𝒙 ⊤ 𝒚 ≔ sum s ( 𝒙 ⊙ 𝒚 ) , ( 𝑨 𝑩 ) i , j ≔ 𝑨 i , : ⊤ 𝑩 : , j . {\bm{x}}^{\top}{\bm{y}}\coloneqq\operatorname{sum}_{s}({\bm{x}}\odot{\bm{y}}),\qquad({\bm{A}}{\bm{B}})_{i,j}\coloneqq{\bm{A}}_{i,:}^{\top}{\bm{B}}_{:,j}. (11) Throughout this section, we interpret all operations as finite-precision computations as defined above.

### B.2 Definition of Assumption 3.4

Our definition of polynomially efficient approximation follows that of Feng et al. (2023) , but differs in scope: while their framework targets real-valued functions, ours applies to symbolic functions.

###### Definition B.4 (Polynomially-efficient approximation) .

We say that a function f n : Σ ℓ ⁡ ( n ) → Σ f_{n}:\Sigma^{\ell(n)}\to\Sigma admits a polynomially efficient approximation if, for a sufficiently small error tolerance 0 < δ ≤ 1 3 0<\delta\leq\tfrac{1}{3} , there exists a feedforward network FF : 𝔽 s ⁡ ( n ) ℓ ⁡ ( n ) ⋅ | Σ | → 𝔽 s ⁡ ( n ) | Σ | , s ⁡ ( n ) = O ⁡ ( log ⁡ n ) , \mathrm{FF}:\mathbb{F}_{s(n)}^{\ell(n)\cdot|\Sigma|}\to\mathbb{F}_{s(n)}^{|\Sigma|},\ s(n)=O(\log n), such that the following holds: for every input 𝒙 = ( x 1 , … , x ℓ ⁡ ( n ) ) ∈ Σ ℓ ⁡ ( n ) {\bm{x}}=(x_{1},\ldots,x_{\ell(n)})\in\Sigma^{\ell(n)} , FF ​ ( 𝒆 ⁡ ( x 1 ) , … , 𝒆 ⁡ ( x ℓ ⁡ ( n ) ) ) i = { ≥ 1 − δ if 𝒆 ⁡ ( f n ​ ( 𝒙 ) ) = 𝒆 i , ≤ δ else , \mathrm{FF}(\bm{e}(x_{1}),\ldots,\bm{e}(x_{\ell(n)}))_{i}\;=\;\begin{cases}\;\geq 1-\delta&\text{if}\quad\bm{e}(f_{n}({\bm{x}}))={\bm{e}}_{i},\\ \;\leq\delta&\text{else },\end{cases} (12) where 𝒆 : Σ → { 0 , 1 } | Σ | \bm{e}:\Sigma\to\{0,1\}^{|\Sigma|} denote the one-hot encoding. Moreover, the number of parameters of the feedforward network is bounded by a polynomial in ℓ ⁡ ( n ) \ell(n) and 1 / δ 1/\delta .

### B.3 Technical lemmas

In this section, we provide the key components for our constructive proofs.

#### B.3.1 Orthogonal Vectors

We follow the notation of ( Li et al., 2024 ) . For any positive integer s ∈ ℕ + s\in\mathbb{N}^{+} and x ∈ { 0 , 1 , … , 2 s − 1 } x\in\{0,1,\dots,2^{s}-1\} , we denote by 𝖻𝗂𝗇 s ​ ( x ) ∈ { 0 , 1 } s \mathsf{bin}_{s}(x)\in\{0,1\}^{s} the standard binary representation of x x using s s bits, defined such that x = ∑ i = 1 s 2 i ⋅ ( 𝖻𝗂𝗇 s ​ ( x ) ) i . x=\sum_{i=1}^{s}2^{i}\cdot(\mathsf{bin}_{s}(x))_{i}. We further define the signed binary encoding of x x , denoted by 𝗌𝖻𝗂𝗇 s ​ ( x ) ∈ { − 1 , 1 } s \mathsf{sbin}_{s}(x)\in\{-1,1\}^{s} , as 𝗌𝖻𝗂𝗇 s ​ ( x ) = 2 ⋅ 𝖻𝗂𝗇 s ​ ( x ) − ( 1 , … , 1 ) . \mathsf{sbin}_{s}(x)=2\cdot\mathsf{bin}_{s}(x)-(1,\ldots,1). Let 𝒙 , 𝒚 ∈ ℝ s {\bm{x}},{\bm{y}}\in\mathbb{R}^{s} be two vectors of the same length. We define their interleaving, denoted by 𝒙 ⌢ ​ 𝒚 ∈ ℝ 2 ​ s {{\bm{x}}}^{\frown}{{\bm{y}}}\in\mathbb{R}^{2s} , as follows: ( 𝒙 ⌢ ​ 𝒚 ) 2 ​ i − 1 = x i , ( 𝒙 ⌢ ​ 𝒚 ) 2 ​ i = 𝒚 i ({{\bm{x}}}^{\frown}{{\bm{y}}})_{2i-1}=x_{i},({{\bm{x}}}^{\frown}{{\bm{y}}})_{2i}={\bm{y}}_{i} for all i ∈ [ s ] . i\in[s]. The orthogonal vectors under finite-precision arithmetic can be:

###### Lemma B.5 ( Li et al., 2024 ) .

For any s ∈ ℕ + s\in\mathbb{N}^{+} , let 𝐪 i = 𝗌𝖻𝗂𝗇 s ​ ( i ) ⌢ ​ 1 s {\bm{q}}_{i}={\mathsf{sbin}_{s}(i)}^{\frown}{1_{s}} and 𝐤 i = 2 s + 1 ⋅ ( 𝗌𝖻𝗂𝗇 s ​ ( i ) ⌢ ​ ( − 1 s ) ) {\bm{k}}_{i}=2^{s+1}\cdot({\mathsf{sbin}_{s}(i)}^{\frown}{(-1_{s})}) for all i ∈ [ 2 s − 1 ] i\in[2^{s}-1] , it holds that ⟨ 𝐪 i , 𝐤 j ⟩ s = − B s \left\langle{\bm{q}}_{i},{\bm{k}}_{j}\right\rangle_{s}=-B_{s} if i ≠ j i\neq j and ⟨ 𝐪 i , 𝐤 j ⟩ s = 0 \left\langle{\bm{q}}_{i},{\bm{k}}_{j}\right\rangle_{s}=0 if i = j i=j . Since [ exp ⁡ ( − B s ) ] s ≤ [ 2 − s − 1 ] s = 0 \bigl[\exp(-B_{s})\bigr]_{s}\leq\bigl[2^{-s-1}]_{s}=0 , it follows that [ exp ( ⟨ 𝐪 i , 𝐤 j ⟩ s ) ] s = 𝟏 [ i = j ] \left[\exp(\left\langle{\bm{q}}_{i},{\bm{k}}_{j}\right\rangle_{s})\right]_{s}=\mathbf{1}[i=j] for all i , j ∈ [ 2 s − 1 ] i,j\in[2^{s}-1] .

#### B.3.2 Position Selector

###### Lemma B.6 .

For any m ∈ ℕ + m\in\mathbb{N}^{+} and 𝐱 ∈ 𝔽 s m {\bm{x}}\in\mathbb{F}_{s}^{m} with x i > 0 x_{i}>0 for all i ∈ [ m ] i\in[m] , there exists a feedforward layer FF : 𝔽 s 2 ​ m → 𝔽 s 2 ​ m \mathrm{FF}:\mathbb{F}_{s}^{2m}\to\mathbb{F}_{s}^{2m} , for any i ∈ [ m ] i\in[m] , such that ( id + FF ) ​ ( ( 𝒙 , 𝒆 i ) ) = ( 𝒙 ⊙ 𝒆 i , 𝒆 i ) . (\id+\mathrm{FF})(({\bm{x}},{\bm{e}}_{i}))=({\bm{x}}\odot{\bm{e}}_{i},{\bm{e}}_{i})\,. (13)

###### Proof.

Let the input be 𝒛 = ( 𝒙 , 𝒆 i ) ∈ 𝔽 s 2 ​ m {\bm{z}}=({\bm{x}},{\bm{e}}_{i})\in\mathbb{F}_{s}^{2m} . Set the weight 𝑾 1 ∈ 𝔽 s m × 2 ​ m {\bm{W}}_{1}\in\mathbb{F}_{s}^{m\times 2m} and bias 𝒃 ∈ m ​ a ​ t ​ h ​ b ​ b ​ F s m {\bm{b}}\in\\ mathbb{F}_{s}^{m} by 𝑾 1 = [ 𝑰 m − B s ​ 𝑰 m ] , 𝒃 = 𝟎 , {\bm{W}}_{1}=\bigl[\,{\bm{I}}_{m}\;\;\;-B_{s}{\bm{I}}_{m}\,\bigr],\qquad{\bm{b}}={\bm{0}}, (14) to have 𝑾 1 ​ 𝒛 + 𝒃 = 𝒙 − B s ​ 𝒆 i . {\bm{W}}_{1}{\bm{z}}+{\bm{b}}={\bm{x}}-B_{s}{\bm{e}}_{i}. Applying the ReLU activation coordinate-wise gives ReLU ​ ( 𝒙 − B s ​ 𝒆 i ) j = { 0 , j = i , x j , j ≠ i . \mathrm{ReLU}({\bm{x}}-B_{s}{\bm{e}}_{i})_{j}=\begin{cases}0,&j=i,\\ x_{j},&j\neq i.\end{cases} (15) Hence, 𝒉 ≔ ReLU ⁡ ( 𝑾 1 ​ 𝒛 + 𝒃 ) = 𝒙 ⊙ ( 𝟏 − 𝒆 i ) . {\bm{h}}\coloneqq\mathrm{ReLU}({\bm{W}}_{1}{\bm{z}}+{\bm{b}})={\bm{x}}\odot({\bm{1}}-{\bm{e}}_{i}). (16)

Next, set the second linear layer 𝑾 2 ∈ 𝔽 s 2 ​ m × m {\bm{W}}_{2}\in\mathbb{F}_{s}^{2m\times m} by 𝑾 2 = [ − 𝑰 m 𝟎 m × m ] . {\bm{W}}_{2}=\begin{bmatrix}-{\bm{I}}_{m}\\ \mathbf{0}_{m\times m}\end{bmatrix}. (17) Thus we have 𝒛 + 𝑾 2 ​ 𝒉 = [ 𝒙 𝒆 i ] + [ − 𝒉 𝟎 ] = [ 𝒙 𝒆 i ] + [ − 𝒙 ⊙ ( 𝟏 − 𝒆 i ) 𝟎 ] = [ 𝒙 ⊙ 𝒆 i 𝒆 i ] . {\bm{z}}+{\bm{W}}_{2}{\bm{h}}=\begin{bmatrix}{\bm{x}}\\ {\bm{e}}_{i}\end{bmatrix}+\begin{bmatrix}-{\bm{h}}\\ {\bm{0}}\end{bmatrix}=\begin{bmatrix}{\bm{x}}\\ {\bm{e}}_{i}\end{bmatrix}+\begin{bmatrix}-{\bm{x}}\odot({\bm{1}}-{\bm{e}}_{i})\\ {\bm{0}}\end{bmatrix}=\begin{bmatrix}{\bm{x}}\odot{\bm{e}}_{i}\\ {\bm{e}}_{i}\end{bmatrix}. (18) ∎

#### B.3.3 Feedforward layers

###### Lemma B.7 .

Let N ∈ ℕ + N\in\mathbb{N}^{+} . For each i ∈ [ N ] i\in[N] , let f i : Σ ℓ i → Σ f_{i}:\Sigma^{\ell_{i}}\to\Sigma admit polynomially-efficient approximation by FF i \mathrm{FF}_{i} . Then there exists a feedforward layer FF : 𝔽 s ∑ i = 1 N ℓ i ​ | Σ | → 𝔽 s N ​ | Σ | \mathrm{FF}:\ \mathbb{F}_{s}^{\sum_{i=1}^{N}\ell_{i}|\Sigma|}\to\mathbb{F}_{s}^{N|\Sigma|} such that for every input tuple 𝐱 i = ( x 1 ( i ) , … , x ℓ i ( i ) ) ∈ Σ ℓ i {\bm{x}}_{i}=(x^{(i)}_{1},\ldots,x^{(i)}_{\ell_{i}})\in\Sigma^{\ell_{i}} , FF ( ∥ i = 1 N ( 𝒆 ( x 1 ( i ) ) , … , 𝒆 ( x ℓ i ( i ) ) ) ) = ∥ i = 1 N FF i ( 𝒙 i ) , \mathrm{FF}\!\left(\big\|_{i=1}^{N}\,(\bm{e}(x^{(i)}_{1}),\ldots,\bm{e}(x^{(i)}_{\ell_{i}}))\right)\;=\;\big\|_{i=1}^{N}\,\mathrm{FF}_{i}({\bm{x}}_{i}), (19) where ∥ \| denotes concatenation.

###### Proof.

For each i ∈ [ N ] i\in[N] , by Definition B.4 , there exist width w i ∈ ℕ w_{i}\in\mathbb{N} and parameters 𝑾 1 ( i ) ∈ 𝔽 s w i × ℓ i ​ | Σ | , 𝑾 2 ( i ) ∈ 𝔽 s | Σ | × w i , 𝒃 ( i ) ∈ 𝔽 s w i {\bm{W}}^{(i)}_{1}\in\mathbb{F}_{s}^{w_{i}\times\ell_{i}|\Sigma|},\quad{\bm{W}}^{(i)}_{2}\in\mathbb{F}_{s}^{|\Sigma|\times w_{i}},\quad{\bm{b}}^{(i)}\in\mathbb{F}_{s}^{w_{i}} (20) such that FF i ​ ( 𝒙 i ) = 𝑾 2 ( i ) ​ ReLU ​ ( 𝑾 1 ( i ) ​ 𝒆 ​ ( 𝒙 i ) + 𝒃 ( i ) ) . \mathrm{FF}_{i}({\bm{x}}_{i})={\bm{W}}^{(i)}_{2}\mathrm{ReLU}({\bm{W}}^{(i)}_{1}\,\bm{e}({\bm{x}}_{i})+{\bm{b}}^{(i)}).

Now, define block-diagonal matrices 𝑾 1 ≔ ⨁ i = 1 N 𝑾 1 ( i ) , 𝑾 2 ≔ ⨁ i = 1 N 𝑾 2 ( i ) , 𝒃 ≔ ⨁ i = 1 N 𝒃 ( i ) . {\bm{W}}_{1}\coloneqq\bigoplus_{i=1}^{N}{\bm{W}}^{(i)}_{1},\qquad{\bm{W}}_{2}\coloneqq\bigoplus_{i=1}^{N}{\bm{W}}^{(i)}_{2},\qquad{\bm{b}}\coloneqq\bigoplus_{i=1}^{N}{\bm{b}}^{(i)}. (21) Then the single feedforward layer FF ⁡ ( 𝒙 ) ≔ 𝑾 2 ​ ReLU ​ ( 𝑾 1 ​ 𝒙 + 𝒃 ) \mathrm{FF}({\bm{x}})\coloneqq{\bm{W}}_{2}\mathrm{ReLU}({\bm{W}}_{1}{\bm{x}}+{\bm{b}}) (22) applies each block independently to its corresponding input, yielding exactly FF ( 𝒙 ) = ∥ i = 1 N FF i ( 𝒙 i ) . \mathrm{FF}({\bm{x}})=\big\|_{i=1}^{N}\mathrm{FF}_{i}({\bm{x}}_{i}). ∎

###### Lemma B.8 .

Let f : Σ ℓ → Σ f:\Sigma^{\ell}\to\Sigma be a function that admits polynomially-efficient approximation ( Definition B.4 ). Then, there exist two feedforward layers FF 1 : 𝔽 s ( 1 + ℓ ) ​ | Σ | + 1 → 𝔽 s ( 1 + ℓ ) ​ | Σ | + 1 , FF 2 : 𝔽 s ( 1 + ℓ ) ​ | Σ | + 1 → 𝔽 s ( 1 + ℓ ) ​ | Σ | + 1 , \mathrm{FF}_{1}:\mathbb{F}_{s}^{(1+\ell)|\Sigma|+1}\to\mathbb{F}_{s}^{(1+\ell)|\Sigma|+1},\quad\mathrm{FF}_{2}:\mathbb{F}_{s}^{(1+\ell)|\Sigma|+1}\to\mathbb{F}_{s}^{(1+\ell)|\Sigma|+1}, (23) such that, for every 𝐱 = ( x 1 , … , x ℓ ) ∈ Σ ℓ {\bm{x}}=(x_{1},\ldots,x_{\ell})\in\Sigma^{\ell} and t ∈ { 0 , 1 } t\in\{0,1\} , ( id + FF 2 ) ∘ ( id + FF 1 ) ​ ( 𝟎 , 𝒆 ⁡ ( x 1 ) , … , 𝒆 ⁡ ( x ℓ ) , t ) = ( t ⋅ 𝒆 ⁡ ( f ⁡ ( 𝒙 ) ) , 𝒆 ⁡ ( x 1 ) , … , 𝒆 ⁡ ( x ℓ ) , t ) . (\id+\mathrm{FF}_{2})\circ(\id+\mathrm{FF}_{1})\big({\bm{0}},\ \bm{e}(x_{1}),\ldots,\bm{e}(x_{\ell}),\ t\big)\;=\;(t\cdot\bm{e}(f({\bm{x}})),\ \bm{e}(x_{1}),\ldots,\bm{e}(x_{\ell}),\ t). (24)

###### Proof.

Let n ≔ | Σ | n\coloneqq|\Sigma| and L ≔ ℓ ​ n L\coloneqq\ell n . Write 𝒖 = ( 𝒆 ⁡ ( x 1 ) , … , 𝒆 ⁡ ( x ℓ ) ) ∈ { 0 , 1 } L {\bm{u}}=(\bm{e}(x_{1}),\ldots,\bm{e}(x_{\ell}))\in\{0,1\}^{L} . By Definition B.4 , there exist w f ∈ ℕ w_{f}\in\mathbb{N} , matrices 𝑾 1 ( f ) ∈ 𝔽 s w f × L {\bm{W}}^{(f)}_{1}\in\mathbb{F}_{s}^{w_{f}\times L} , 𝑾 2 ( f ) ∈ 𝔽 s n × w f {\bm{W}}^{(f)}_{2}\in\mathbb{F}_{s}^{n\times w_{f}} , and bias 𝒃 ( f ) ∈ 𝔽 s w f {\bm{b}}^{(f)}\in\mathbb{F}_{s}^{w_{f}} such that FF f ​ ( 𝒖 ) ≔ 𝑾 2 ( f ) ​ ReLU ​ ( 𝑾 1 ( f ) ​ 𝒖 + 𝒃 ( f ) ) , FF f ​ ( 𝒖 ) i = { ≥ 1 − δ if ​ 𝒆 ​ ( f ⁡ ( 𝒙 ) ) = 𝒆 i , ≤ δ otherwise . \mathrm{FF}_{f}({\bm{u}})\coloneqq{\bm{W}}^{(f)}_{2}\,\mathrm{ReLU}({\bm{W}}^{(f)}_{1}{\bm{u}}+{\bm{b}}^{(f)}),\quad\mathrm{FF}_{f}({\bm{u}})_{i}=\begin{cases}\geq 1-\delta&\text{if }\ \bm{e}(f({\bm{x}}))={\bm{e}}_{i},\\ \leq\delta&\text{otherwise}.\end{cases} (25)