Paper deep dive
Approximate Homomorphisms and Convergent Representations in Transducers
Santiago Cifuentes
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/24/2026, 4:17:28 AM
Summary
This paper investigates the stability of minimal representations in controlled stochastic processes, specifically transducers, under perturbations. It introduces the concept of approximate homomorphisms to measure structural similarity between different transducer implementations. The study demonstrates that while standard transducers may lack robust convergent structures, linear and predictive transducers exhibit stability: minimal implementations for interfaces close to a target interface share an approximate homomorphism with error linear in the perturbation size. These findings provide theoretical support for the 'Platonic Representation Hypothesis,' suggesting that neural networks may converge to shared structural representations (world models) in their latent layers.
Entities (8)
Relation Signals (6)
Approximate Homomorphism → measuressimilarityof → Transducer
confidence 95% · We introduce notions of approximate homomorphism capturing local structural similarity between them
Linear Transducer → exhibitsstabilityunder → Perturbation
confidence 94% · all minimal linear transducers implementing interfaces sufficiently close to I have an approximate homomorphism to the minimal implementation of I, with error linear in the perturbation size.
Predictive Transducer → exhibitsstabilityunder → Perturbation
confidence 94% · We prove an analogous stability result for predictive transducers under a residual metric
Standard Transducer → lacksstabilityfor → Simple Interfaces
confidence 93% · For standard transducers, we show that there exist simple interfaces for which there is no approximate homomorphism between the different implementations of the dynamics.
Transducer → models → World Model
confidence 92% · We use transducers to model world models.
Transducer → supports → Platonic Representation Hypothesis
confidence 91% · this gives some theoretical support to the hypothesis that their latent representations exhibit structural convergence.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the stability of minimal representations of controlled stochastic processes (in particular, transducers) under perturbations. This question is motivated by recent experiments finding predictive-state structure in the latent representations of neural networks. We consider standard, linear and predictive transducers. We introduce notions of approximate homomorphism capturing local structural similarity between them, together with metrics comparing their induced dynamics (which we refer to as interfaces), and prove properties such as composability of the approximate homomorphisms. For standard transducers, we show that there exist simple interfaces for which there is no approximate homomorphism between the different implementations of the dynamics. In contrast, for every finite-rank interface $\mathcal I$, we prove that all minimal linear transducers implementing interfaces sufficiently close to $\mathcal I$ have an approximate homomorphism to the minimal implementation of $\mathcal I$, with error linear in the perturbation size. We prove an analogous stability result for predictive transducers under a residual metric using some mild hypothesis regarding the indistinguishability of the belief states. These results identify conditions under which canonical transducer representations are robust to perturbations, while showing that such convergence fails without additional structural restrictions. Under the assumption that these type of abstractions are embedded into the hidden layers of modern AI models, this gives some theoretical support to the hypothesis that their latent representations exhibit structural convergence.
Tags
Links
- Source: https://arxiv.org/abs/2608.20428v1
- Canonical: https://arxiv.org/abs/2608.20428v1
Trouble viewing inline? Open PDF directly →
Full Text
133,828 characters extracted from source content.
Expand or collapse full text
Approximate Homomorphisms and Convergent Representations in Transducers Santiago Cifuentes Affiliation: Dovetail Research Group Affiliation: ICC CONICET, Universidad de Buenos Aires August 2026 Abstract We study the stability of minimal representations of controlled stochastic processes (in particular, transducers) under perturbations. This question is motivated by recent experiments finding predictive-state structure in the latent representations of neural networks. We consider standard, linear and predictive transducers. We introduce notions of approximate homomorphism capturing local structural similarity between them, together with metrics comparing their induced dynamics (which we refer to as interfaces), and prove properties such as composability of the approximate homomorphisms. For standard transducers, we show that there exist simple interfaces for which there is no approximate homomorphism between the different implementations of the dynamics. In contrast, for every finite-rank interface ℐI, we prove that all minimal linear transducers implementing interfaces sufficiently close to ℐI have an approximate homomorphism to the minimal implementation of ℐI, with error linear in the perturbation size. We prove an analogous stability result for predictive transducers under a residual metric using some mild hypothesis regarding the indistinguishability of the belief states. These results identify conditions under which canonical transducer representations are robust to perturbations, while showing that such convergence fails without additional structural restrictions. Under the assumption that these type of abstractions are embedded into the hidden layers of modern AI models, this gives some theoretical support to the hypothesis that their latent representations exhibit structural convergence. 1 Introduction Since the beginning of neural networks, many AI architectures have included some type of hidden or intermediate layers between the input and output gates in which the models can encode partial results of their computation. In these layers the models usually learn, through training, to represent latent variables and general information useful for their goals [4, 6, 31]. Although the training process is not deterministic and depends on things such as the training algorithm, the initial parameters and the choice of hyperparameters, it has been observed from the beginning of the deep learning revolution that some structure of these hidden layers coincides between different models [33, 37], even when they are implemented in different architectures. There are different ways of measuring this similarity, but for most of them this “convergent phenomenon” can be found [28]. To name a few of these metrics, similarity can be measured by comparing the distribution of latent vectors inside each layer [9, 29], by comparing functional aspects of the different layers [28], or by finding a linear transformation able to transfer features from one model to another [2, 9, 13, 18]. These experimental results have motivated the recent proposal of the “Platonic Representation Hypothesis” [23]: the idea that “Neural networks, trained with different objectives on different data and modalities, are converging to a shared statistical model of reality in their representation spaces”. Although it is unclear to what extent this hypothesis may hold [10, 15, 19], most results suggest that some kind of convergence can sometimes be found in different models trained for a similar task. Overall, there are three core hypotheses which can help to understand this situation [23]. First, the simplicity bias hypothesis states that deep AI architectures trained through stochastic gradient descent have a tendency to converge to structurally simple representations which usually generalize well [5, 25, 51]. Meanwhile, the capacity hypothesis states that as models include more parameters they encompass a larger set of possible behaviours, and thus it is more likely for different architectures to have a non-empty intersection regarding the instantiations they allow [23]. Finally, the multitask hypothesis states that there are fewer representations capable of performing multiple tasks at the same time [8, 39], and thus as we train models for more complex goals the optimal configurations become sparser. There exists an ongoing theoretical program trying to give support to these hypotheses. For instance, ideas such as implicit regularization [22] or neural collapse [24], or entire frameworks such as singular learning theory [52] try to explain how modern gradient descent finds robust representations in current deep learning architectures although the number of model parameters allows for overfitting. A different approach relies on the idea of a world model [20, 21, 44]. More precisely, different empirical and theoretical results support the idea that modern agents develop an internal mechanism equivalent to a description of the dynamics of the environment surrounding them [11, 38, 43, 46]. If we formalize these structures using some mathematical abstraction, then we can ask the question of whether the set of these abstractions implementing the same dynamics has some shared structure [44]. If the answer is positive, this provides some support for the idea that agents learning from a similar data distribution should share some aspects of their internal representations. See Figure 1 for a diagrammatic sketch of this idea. Figure 1: The world model-based approach for understanding convergent structure. We expect that each internal layer of a neural network architecture encodes a world model through some mathematical abstraction (such as a transducer). Then, we search for convergent structure in these abstractions by looking for a minimal model representing the dynamics. In this work we investigate this idea using transducers as an abstraction of world models. A transducer is a controlled stochastic system with hidden states, inputs, and outputs, which induces an interface: for every finite sequence of interventions, the interface specifies a probability distribution over the corresponding sequence of observations in the real world. These types of structures have been studied recently as tools to formalize world models [7, 44], and different experimental results support the idea that modern AI agents implement this type of structure in their residual stream [46, 47]. Moreover, in [44] it was proven that in some situations the set of transducers implementing a specified behaviour has a unique minimal implementation such that all other implementations can be structurally mapped into the minimal one. From our perspective, this is a positive result encouraging the possibility of convergent structure. Our goal is to improve this type of result by weakening some of its hypotheses. More precisely, we aim to improve the result by making it robust to noise and approximation. Consider that we have two transducers implementing a similar behaviour (measured through some proper metric). Then, is it the case that they share some structure, measured through some other metric? Note that in practical scenarios we expect different models to learn from slightly different datasets, and thus we need the convergence of transducers to hold also in the case in which they implement slightly different interfaces. Our Contributions. We consider three types of transducers: the “standard” ones, linear transducers and predictive transducers, and do the following: 1. We give a notion of approximate homomorphism for all types of transducers that allows to decide when a transducer is ε -similar to another one. Our notion is robust with respect to composition and preserves the dynamics that the transducers represent up to an error that scales as O(ε)O( ) under discounted metrics (i.e. metrics that weight differences in long-horizon predictions using a discount factor that decays exponentially with the number of steps). 2. In the context of standard transducers, we show that there exist interfaces such that the standard transducer implementing these interfaces are structurally far away (using our notion of approximate homomorphism to measure distance). This result shows that the result from [44] regarding the non-existence of a minimal representation for normal transducers cannot be salvaged by introducing an error term in the homomorphism. 3. For linear transducers, we show that for a significant subset of interfaces it is the case that all minimal linear transducers implementing an interface ε -similar (for a sufficiently small ε>0 >0) to interface ℐI can be mapped to a common linear transducer introducing some error that scales as Γℐε _I , where Γℐ _I represents a constant depending only on ℐI. This shows that the minimality of linear implementations is robust to noise in a small neighbourhood of the interface. This result is obtained by inspecting the canonical construction of the minimal linear transducer, which is obtained by working with the Hankel matrix of the interface. 4. Finally, we obtain an analogous result for predictive transducers by leveraging the construction of the minimal predictive implementation based on the notion of a ϵε-machine from computational mechanics [3]. Taken together, these results show that the existence of minimal representations (and thus of potential convergent structure) is robust to error for the family of linear and predictive transducers. Thus, we provide more theoretical support for the Platonic Representation Hypothesis under the hypothesis that world models show up inside the internal structure of modern AI architectures in the form of these types of abstractions. In the case of predictive transducers, this was partially observed empirically [46, 47]. Meanwhile, although there is no previous experiment finding linear transducers within the hidden layers of modern models, we suspect that these architectures should leverage the fact that any representation they contain is embedded in a linear space, and thus it is natural for them to prefer linear transducers over predictive ones. We believe that a fruitful direction for future work would be to reproduce the set-up of [47] but looking for a minimal linear transducer (or a functionally equivalent mechanism) inside the residual stream. The remainder of the paper is organized as follows. Section 2 reviews standard, linear, and predictive transducers together with their exact notions of reduction and minimality. Section 3 introduces approximate homomorphisms, metrics on interfaces, and the composability and continuity results. Section 4 studies approximate common minima for nearby interfaces, giving respectively the negative result for unrestricted transducers and the positive results for linear and predictive transducers. Finally, in Section 5 we conclude the paper by summarizing our results, discussing their limitations and describing future lines of research. All proofs are deferred to the Appendix to improve readability. Related work. Finite-state transducers have a long history in automata theory, beginning with the Mealy and Moore machines [34, 36]. In their deterministic form, they describe systems whose internal state is updated in response to an input while producing an output. Weighted and probabilistic variants replace deterministic transitions by numerical weights or stochastic kernels, and have been extensively studied in formal language theory [35]. The stochastic transducers considered here are closely related to controlled Markov models, and in particular they resemble Markov Decision Processes (MDPs) [40]. To identify convergent structure we use the notion of homomorphism, which corresponds to a map from one transducer to another that preserves local structure. This type of “coarse-graining” operations have a long history in the different abstractions we mentioned before. For Markov chains, classical lumpability identifies states whose transition probabilities agree after aggregation [26]. Probabilistic bisimulation gives a related behavioural equivalence for labelled probabilistic transition systems [30]. In the MDP literature, [17] develops exact state equivalences and model minimization based on bisimulation, while [41] formulates MDP and semi-MDP homomorphisms as maps that preserve rewards and aggregate transition probabilities. These notions have subsequently been organized into broader taxonomies of state abstraction [32]. We will study notions of homomorphism that allow for some error, and thus we refer to them as approximate homomorphisms. In the context of MDPs, such approximate reductions have already been considered [1, 42, 50], and our definitions as well as our robustness results (regarding composition and preservation of the interface up to discounted metrics) have analogues in the literature. In probabilistic transition systems, the notion of approximate bisimulation has a long history [14, 16] and remains an active area of research [27, 49]. The notion of the Hankel matrix of a process was introduced in the context of weighted automata to construct minimal linear implementations [45]. In that setting, the minimal realizations obtained are unique up to an invertible linear change of coordinates (i.e. a base change). Regarding predictive transducers, we use tools from computational mechanics [12, 48] to obtain minimal representations. In particular, the extension of computational mechanics to input-output processes [3] can be applied almost directly to our context. 2 Types of transducers In this section we describe the different types of transducers that we will consider in this paper. 2.1 “Standard” Transducers We use transducers to model world models. Definition 1. A transducer is given by a tuple (,,,κ,p)(S,A,O,κ,p) where S is a set of states, A is a set of actions (or inputs), O is a set of reactions (or outputs), κ is a Markov kernel11 1 In this context, a Markov kernel is simply a set of conditional distributions. of the form κτ(s′,o|s,a):s,s′∈,a∈,o∈,τ∈ℕ\ _τ(s ,o|s,a):s,s ,a ,o ,τ \ and p∈Δ()p∈ (S) is an initial distribution over the set of states. Transducers represent a world model indicating, for every possible sequence of actions a1…ana_1… a_n, a distribution on the reaction o1…ono_1… o_n of the environment. They use (hidden) states to keep track of the previous events, and the function κ describes the relation between actions and outputs and how the state is updated. This function can depend on the timestep τ∈ℕτ , but for simplicity we will assume that κτ=κ0 _τ= _0 for every τ (this corresponds to assuming stationary dynamics). Also, we may omit κ in the notation and simply talk about the probabilities of the events. For example, we write Pr(o|s,a)T _T (o|s,a ) to denote the value ∑s′∈κ(s′,o|s,a) _s κ(s ,o|s,a), or similarly Pr(s′|s,a,o)T _T (s |s,a,o ) to denote κ(s′,o|s,a)/Pr(o|s,a)Tκ(s ,o|s,a)/ _T(o|s,a) whenever the denominator is positive. We will assume for simplicity that ,S,A and O are countable. A trace over T is a finite or infinite sequence of outputs. As mentioned, any transducer defines a probability for each trace conditioned on each sequence of actions. We refer to such a description (i.e. a list of probabilities Pr(o1…on|a) (o_1… o_n|a ) for every finite sequence o1…on∈no_1… o_n ^n and infinite sequence ∈ωa ^ω) as an interface ℐI. We will only be interested in anticipation-free interfaces, i.e. those that satisfy Pr(o1…on|a)=Pr(o1…on|a1…an) (o_1… o_n|a )= (o_1… o_n|a_1… a_n ). Anticipation-free interfaces coincide exactly with interfaces “implementable” by transducers [44][Lemma 4]. More precisely, given o1…ono_1… o_n and a1…ana_1… a_n the (conditioned) probability that the transducer T induces can be computed as Pr(o1…on|a1…an)T=∑s0…sn∈n+1p(s0)∏t=1nκ(st,ot|st−1,at) _T (o_1… o_n|a_1… a_n )= _s_0… s_n ^n+1p(s_0) _t=1^nκ(s_t,o_t|s_t-1,a_t) (1) Whenever ||,||,||<∞|S|,|A|,|O|<∞ this computation can be simplified: if Ma,o∈ℝ||×||M_a,o ^|S|×|S| is given by Ma,o(s,s′)=κ(s′,o|s,a)M_a,o(s,s )=κ(s ,o|s,a), then Pr(o1…on|a1…an)T=pMa1,o1…Man,on _T(o_1… o_n|a_1… a_n)=pM_a_1,o_1… M_a_n,o_n1 Example 1. Figure 2 shows a transducer with deterministic dynamics (i.e. for every s∈,a∈s ,a there is some s′∈s and o∈o such that κ(s′,o|s,a)=1κ(s ,o|s,a)=1). The states are =s0,s1S=\s_0,s_1\, the actions =continue,stayA=\ continue, stay\, and the possible outputs =0,1O=\0,1\. The initial distribution is concentrated in state s0s_0. It represents a system that outputs 010101…010101… indefinitely as long as the action continue is chosen at each step. If stay is employed instead, the dynamics are “frozen” for one step. s0s_0s1s_1stay/0stay/1continue/0continue/1 Figure 2: Example of a “deterministic” transducer. Each edge contains an action a followed by an output o. An edge from s to s′s with label a/oa/o indicates that κ(s′,o|s,a)=1κ(s ,o|s,a)=1. We will assume that all the states of a transducer are reachable from some state with initial positive probability. Namely, for every state s there must exist a state s0s_0 such that p(s0)>0p(s_0)>0 and a sequence of actions a1…aka_1… a_k such that PrT(s|s0,a1…ak)>0 _T (s|s_0,a_1… a_k )>0. Also, we will sometimes use Σ=× =A×O. There is a well-defined notion of homomorphism for these objects, which allows us to coarse-grain states as well as input and output symbols. Definition 2. Given two transducers T1=(1,1,1,κ1,p1)T_1=(S_1,A_1,O_1, _1,p_1) and T2=(2,2,2,κ2,p2)T_2=(S_2,A_2,O_2, _2,p_2), a homomorphism is given by three mappings ⟨ϕ:1→2,f:1→2,g:1→2⟩ φ:S_1 _2,f:A_1 _2,g:O_1 _2 satisfying κ2(s2,o2|ϕ(s1),f(a1)) _2(s_2,o_2|φ(s_1),f(a_1)) =∑s′∈ϕ−1(s2)o′∈g−1(o2)κ1(s′,o′|s1,a1), = _ subarraycs ∈φ^-1(s_2)\\ o ∈ g^-1(o_2) subarray _1(s ,o |s_1,a_1), (2) p2(s2) p_2(s_2) =∑s1∈ϕ−1(s2)p1(s1), = _s_1∈φ^-1(s_2)p_1(s_1), (3) for every s1∈1s_1 _1, a1∈1a_1 _1, s2∈2s_2 _2, and o2∈2o_2 _2. Condition (2) says that the joint one-step distribution on the next state and output is preserved after applying the coarse-grainings ϕφ and g (and translating actions through f). Condition (3) makes sure that the initial distributions are equivalent up to ϕφ. If we require 1=2O_1=O_2 and 1=2A_1=A_2 then both transducers have the same “type”. Moreover, if also f=g=idf=g= id and ϕφ is surjective we say that the homomorphism is a reduction. Example 2. Consider the transducer from Figure 3. There is a reduction from this transducer to the one from Figure 2: define ϕφ as ϕ(s0)=ϕ(s2)=s0φ(s_0)=φ(s_2)=s_0 and ϕ(s1)=ϕ(s3)=s1φ(s_1)=φ(s_3)=s_1, while taking f=g=idf=g= id. In some sense, the transducer from Figure 3 implements the interface in an “inefficient” manner. s0s_0s1s_1s2s_2s3s_3stay/0 stay/0stay/1 stay/1stay/0 stay/0stay/1 stay/1continue/0 continue/0continue/1 continue/1continue/0 continue/0continue/1 continue/1 Figure 3: Example of a “deterministic” transducer that implements the same interface as the one from Figure 2. An edge from s to s′s with label a/oa/o indicates that κ(s′,o|s,a)=1κ(s ,o|s,a)=1. Reductions can be composed. Thus, after fixing an interface ℐI we can look at the set of transducers implementing ℐI, and if we quotient them properly (identifying transducers T1T_1 and T2T_2 such that there are reductions both from T1T_1 to T2T_2 and from T2T_2 to T1T_1) then the reduction relation gives the set a poset structure. In [44] some properties of these posets are proven, and in particular the fact that in general they need not have a unique minimum. This situation can be salvaged in at least two ways. First, if we consider linear transducers (which allow for “negative” probabilities), then uniqueness of the minimum can be proven [44][Theorem 2]. Second, we can restrict attention to the subposet of predictive transducers (intuitively, those whose state transitions are deterministic given the last state, action and output): in that case, there is a unique minimum, and it coincides with the ϵε-machine from computational mechanics [3] representing the dynamics [44][Theorem 3]. Before proceeding, we note that the definition of homomorphism we introduced is not exactly the same as the one from [44]. In Appendix A.1 we compare them and show nonetheless that they coincide when we restrict to reductions. Later we will see that our proposal is easier to extend to the approximate setting. In particular, Condition (2) states that κ2 _2 must be equal to the pushforward of κ1 _1 through ϕφ and g. Thus, we can introduce an error term in the homomorphism by comparing κ2 _2 to this pushforward using any distance between distributions. 2.2 Linear transducers We will also consider linear transducers: a model of a transducer in which the states are embedded in a vector space. From now on we define, for every interface ℐI, its associated formal series: for every w∈Σ∗=(×)∗w∈ ^*=(A×O)^* let Fℐ(w)=Fℐ((a1,o1)…(an,on))=Pr(o1⋯on∣a1⋯an)ℐ,Fℐ(ϵ)=1,F_I(w)=F_I((a_1,o_1)…(a_n,o_n))= _I(o_1·s o_n a_1·s a_n), F_I(ε)=1, where ϵε denotes the empty word. Definition 3. A linear transducer over (,)(A,O) is a tuple G=(V,ξ,λ,Mσ∈Σ)G=(V,ξ,λ,\M_σ\_σ∈ ), where V is a real vector space, ξ∈Vξ∈ V is an initial vector, λ∈V∗λ∈ V^* is a linear functional, and each Mσ:V→VM_σ:V→ V is a linear map. For a word w=σ1⋯σnw= _1·s _n we define MwM_w recursively by Mϵ=idV,Mwσ=MσMw.M_ε=id_V, M_wσ=M_σM_w. The linear transducer generates the formal series FG(w)=λ(Mwξ).F_G(w)=λ(M_wξ). We say that G implements an interface ℐI if FG=FℐF_G=F_I. We will assume without loss of generality that V=spanMwξ:w∈Σ∗V=span\M_wξ:w∈ ^*\, i.e. that the whole space V is ‘used’ by the transducer22 2 We add this hypothesis to improve the clarity of our exposition. All results still hold when removing this condition.. The size of a linear transducer is measured by the dimension of the linear space needed to represent the series, which can be infinite. We now introduce the concept of the Hankel matrix of the interface. Definition 4. The Hankel matrix of ℐI is the infinite matrix Hℐ(u,v)=Fℐ(uv),u,v∈Σ∗.H_I(u,v)=F_I(uv), u,v∈ ^*. For each prefix u∈Σ∗u∈ ^* define the row hℐ(u):Σ∗→ℝh_I(u): ^* such that hℐ(u)(v)=Fℐ(uv)h_I(u)(v)=F_I(uv). Then, the dimension of ℐI is dim(ℐ)=rank(Hℐ)=dimspanhℐ(u):u∈Σ∗. (I)=rank(H_I)= \h_I(u):u∈ ^*\. If this rank is finite, we call ℐI a finite-rank interface. A linear transducer implementing an interface can be obtained from its Hankel matrix. Let Vℐ=spanhℐ(u):u∈Σ∗.V_I=span\h_I(u):u∈ ^*\. Pick ξℐ=hℐ(ϵ) _I=h_I(ε) and let λℐ:Vℐ→ℝ _I:V_I be evaluation at the empty suffix as λℐ(r)=r(ϵ). _I(r)=r(ε). For every σ∈Σσ∈ , define the shift operator Rσℐ:Vℐ→VℐR^I_σ:V_I→ V_I by Rσℐhℐ(u)=hℐ(uσ),R^I_σh_I(u)=h_I(uσ), and extend linearly. This is well-defined: if ∑iαihℐ(ui)=0 _i _ih_I(u_i)=0, then for every suffix v, ∑iαihℐ(uiσ)(v)=∑iαiFℐ(uiσv)=∑iαihℐ(ui)(σv)=0. _i _ih_I(u_iσ)(v)= _i _iF_I(u_iσ v)= _i _ih_I(u_i)(σ v)=0. Thus, it follows that Gℐ=(Vℐ,ξℐ,λℐ,Rσℐσ∈Σ)G_I=(V_I, _I, _I,\R^I_σ\_σ∈ ) is a linear transducer, and λℐ(Rwℐξℐ)=Fℐ(w) _I(R^I_w _I)=F_I(w) for every word w. This representation is minimal: if G=(V,ξ,λ,Mσ)G=(V,ξ,λ,\M_σ\) implements ℐI, then hℐ(u)(v)=Fℐ(uv)=λ(MvMuξ).h_I(u)(v)=F_I(uv)=λ(M_vM_uξ). for every word u,vu,v. Hence all Hankel rows are obtained from vectors Muξ∈VM_uξ∈ V, so rank(Hℐ)≤dimV.rank(H_I)≤ V. Note that minimal linear transducers are unique up to invertible linear changes of coordinates. In the context of linear transducers we will use linear reductions to formalize the idea of homomorphisms between models. Definition 5. Let G=(V,ξ,λ,Mσ∈Σ)G=(V,ξ,λ,\M_σ\_σ∈ ) and G′=(W,ξ′,λ′,Nσ∈Σ)G =(W,ξ ,λ ,\N_σ\_σ∈ ) be linear transducers over the same input and output alphabets. A linear reduction from G to G′G is a surjective linear map L:V→WL:V→ W satisfying 1. Lξ=ξ′Lξ=ξ . 2. LMσ=NσL for every σ∈ΣLM_σ=N_σL for every σ∈ . 3. λ′L=λ L=λ. The first condition preserves the initial vector, the second says that L translates the internal dynamics, and the third preserves the “reading” of the vectors. These conditions imply that λ′(Nwξ′)=λ(Mwξ)λ (N_wξ )=λ(M_wξ) for every word w. By the construction above, it can be proven that any linear transducer G implementing ℐI can be reduced to GℐG_I. Lemma 1. Let G=(V,ξ,λ,Mσ)G=(V,ξ,λ,\M_σ\) be a linear transducer implementing an interface ℐI. Then there is a linear reduction ρG:G→Gℐ _G:G→ G_I given by ρG(Mwξ)=hℐ(w). _G(M_wξ)=h_I(w). Example 3. The deterministic transducer T from Figure 2 admits a simple linear representation. Let V=ℝ2,ξ=(10),λ(x0,x1)=x0+x1,V=R^2, ξ= pmatrix1\\ 0 pmatrix, λ(x_0,x_1)=x_0+x_1, where the two standard basis vectors represent the states s0s_0 and s1s_1. Consider the transition maps M,0=(0010),M,1=(0100),M_ continue,0= pmatrix0&0\\ 1&0 pmatrix, M_ continue,1= pmatrix0&1\\ 0&0 pmatrix, and M,0=(1000),M,1=(0001).M_ stay,0= pmatrix1&0\\ 0&0 pmatrix, M_ stay,1= pmatrix0&0\\ 0&1 pmatrix. Then, the linear transducer G=(V,ξ,λ,(Mσ)σ∈Σ)G=(V,ξ,λ,(M_σ)_σ∈ ) implements the same interface as T. In general, every standard transducer T can be transformed into a linear transducer whose underlying space has dimension equal to the number of states of T. 2.3 Predictive transducers We finally consider predictive transducers, which correspond to transducers whose internal states do not contain predictive information that is unavailable from the observable input–output history. From now on, we say that a history h=(a1,o1)…(an,on)∈Σ∗h=(a_1,o_1)…(a_n,o_n)∈ ^* is admissible for an interface ℐI if Prℐ(o1⋯on∣a1⋯an)>0 _I(o_1·s o_n a_1·s a_n)>0. The empty history is always admissible. For any admissible history h=(a1,o1)…(an,on)h=(a_1,o_1)…(a_n,o_n) of an interface ℐI, we consider the residual interface ℐhI^h as the interface obtained by conditioning on h: for every u∈mu ^m and v∈mv ^m, Pr(v∣u)ℐh:=Prℐ(o1⋯onv∣a1⋯anu)Prℐ(o1⋯on∣a1⋯an). _I^h(v u):= _I(o_1·s o_nv a_1·s a_nu) _I(o_1·s o_n a_1·s a_n). (4) For a transducer T=(,,,κ,p)T=(S,A,O,κ,p) and a state s∈s , let ℐT,sI_T,s denote the interface generated by the same kernel κ with initial distribution δs _s (i.e. when all probability mass is concentrated on s). For an admissible history h=(a1,o1)…(an,on)h=(a_1,o_1)…(a_n,o_n), also write qT(s∣h):=Pr(Sn=s∣o1:n,a1:n)Tq_T(s h):= _T(S_n=s o_1:n,a_1:n) for the posterior distribution over the internal state at step n after observing h. Definition 6. Let T be a transducer. We say that T is predictive if, for every admissible history h and every state s such that qT(s∣h)>0q_T(s h)>0, ℐT,s=ℐTh. _T,s=I_T^h. (5) Equivalently, conditional on the observable history, knowing the current internal state does not change the expected distribution for future events. For this class of transducers there is always a minimal implementation of each interface, and it can be constructed explicitly. To do this, identify histories that make exactly the same predictions: for admissible histories h and h′h , define the predictive equivalence relation as h∼ℐh′⟺ℐh=ℐh′. h _Ih ^h=I^h . Denote the equivalence class of h by [h]ℐ[h]_I and let ϵ(ℐ):=[h]ℐ:h is admissible for ℐ.S_ε(I):=\[h]_I:h is admissible for I\. The transitions are defined in the expected way in the next definition. This construction corresponds to the notion of an ϵε-machine from computational mechanics [3]. Definition 7. Let ℐI be an interface. Its ϵε-transducer is given by E(ℐ)=(ϵ(ℐ),,,κϵ,δ[ϵ]ℐ),E(I)=(S_ε(I),A,O, _ε, _[ε]_I), where, for every admissible history h, action a, and output o, we set κϵ(s′,o∣[h]ℐ,a) _ε(s ,o [h]_I,a) :=μϵ(o∣[h]ℐ,a)s′=δϵ([h]ℐ,a,o). := _ε(o [h]_I,a)1\s = _ε([h]_I,a,o)\. (6) where μϵ(o∣[h]ℐ,a)=Prℐh(o∣a) _ε(o [h]_I,a)= _I^h(o a) and δϵ([h]ℐ,a,o)=[h(a,o)]ℐ _ε([h]_I,a,o)=[h(a,o)]_I. Observe that this transducer evolves deterministically: for every state s, input a and output o there is a unique next possible state s′s . This ensures that Eq. (5) is satisfied. The next proposition states that this implementation is the minimal one among the predictive ones. Proposition 1. The transducer E(ℐ)E(I) implements ℐI and is predictive. Moreover, if T=(,,,κ,p)T=(S,A,O,κ,p) is any predictive transducer implementing ℐI, then there is a reduction from T to E(ℐ)E(I). Example 4. The transducer from Figure 2 is predictive. Moreover, it is also the minimal predictive transducer for that interface. See Figure 4 for a diagram showcasing the structure of the poset of standard, linear and predictive transducers. As already mentioned, due to Lemma 1 and Proposition 1 the poset for linear and predictive transducers each has a minimum for every interface. Meanwhile, for the case of standard transducers there are interfaces for which there is no unique minimum. Figure 4: A diagram of the lattice of transducers for standard, linear and predictive implementations. Due to Lemma 1 and Proposition 1 the lattice of linear and predictive transducers has a unique minimum, while the one of standard transducers can have more than one minimal element. 3 Approximate homomorphisms and the space of interfaces In this section we provide approximate variants of the notions of homomorphisms introduced in the previous section, and prove some basic properties. 3.1 The case of “standard” transducers The type of coarse-grainings that Definition 2 allows is exact in a strong structural sense. It says that the whole one-step mechanism of T2T_2 is obtained by pushing forward the one-step mechanism of T1T_1 along the maps ϕφ, f, and g. Thus, if two states of T1T_1 are identified by ϕφ, they must have exactly the same coarse-grained output law and exactly the same coarse-grained transition law. For real world models obtained through learning or other iterative procedures we don’t expect them to be structurally identical. Thus, the purpose of approximate homomorphisms is to introduce some degree of error in this notion. We keep the maps ϕφ, f, and g; but we now allow the push-forward dynamics to differ by some ε>0 >0. Definition 8. Given two transducers T1=(1,1,1,κ1,p1)T_1=(S_1,A_1,O_1, _1,p_1) and T2=(2,2,2,κ2,p2)T_2=(S_2,A_2,O_2, _2,p_2), a ε -homomorphism is given by three mappings ⟨ϕ:1→2,f:1→2,g:1→2⟩ φ:S_1 _2,f:A_1 _2,g:O_1 _2 satisfying ‖(ϕ×g)∗κ1(⋅,⋅|s1,a1)−κ2(⋅,⋅|ϕ(s1),f(a1))‖TV \|(φ× g)_* _1(·,·|s_1,a_1)- _2(·,·|φ(s_1),f(a_1)) \|_TV ≤ε ≤ (7) ‖ϕ∗p1−p2‖TV \| _*p_1-p_2 \|_TV ≤ε, ≤ , (8) for every s1∈1s_1 _1 and a1∈1a_1 _133 3 Here (ϕ×g)∗(φ× g)_* and ϕ∗ _* denote the push-forwards of the distributions. See Appendix A.2 for a precise definition.. The choice of total variation is not completely arbitrary: we will see that due to its properties (which are enumerated in the Appendix A.2) approximate homomorphisms are composable. Example 5. Consider the actionless transducers from Figure 5 with ε∈(0,1] ∈(0,1]. Each edge has a label (o,p)(o,p) indicating the probability p of transitioning using that edge and outputting o in the process. There is a ε -reduction from the transducer on the left to the one on the right: take ϕ(s0)=t0φ(s_0)=t_0 and ϕ(s1)=ϕ(s2)=t1φ(s_1)=φ(s_2)=t_1. Meanwhile, there is no 0-reduction (i.e. exact reduction) between them. s0s_0s1s_1s2s_2$, 12 120,10,1$, 12 120,1−ε0,1- 1,ε1, 0t_0t1t_1$, 110, 10,\,1 Figure 5: Two actionless transducers (or rather, transducers with a single action a), with outputs =0,1,$O=\0,1,\$\. An edge from s to s′s with label o,po,p indicates that κ(s′,o|s,a)=pκ(s ,o|s,a)=p. This notion of approximate homomorphism ensures each state s∈1s _1 gets mapped to a state whose one-step dynamics are similar after coarse-graining. Thus, if we look at approximate reductions (enforcing that 1=2A_1=A_2, 1=2O_1=O_2, f=g=idf=g= id, and ϕφ is surjective), one transducer T1T_1 can be approximately reduced to another one T2T_2 only if their states are locally similar. Does this imply that the interfaces they induce are also similar? We recall that for exact homomorphisms this is the case. Observation 1. If there is a reduction from T1T_1 to T2T_2 then ℐT1=ℐT2I_T_1=I_T_2 [44][Lemma 5]. To approach this question in the approximate setting we need a way to compare different interfaces, i.e. a metric over this space. Observe that an interface ℐI is given essentially by a map Dℐ:∗→Δ(∗)D_I:A^*→ (O^*) such that Dℐ(a1…an)D_I(a_1… a_n) represents the distribution Pr(⋅|a1…an)ℐ _I (·|a_1… a_n ) which has support over nO^n. Then, to define a metric for interfaces we can pick any metric for distributions and then aggregate it over all the possible action sequences in ∗A^*. For instance, we can consider total variation to compare the distributions and aggregate them with the supremum, obtaining d∞(ℐ1,ℐ2)=supa∈∗‖Dℐ1(a)−Dℐ2(a)‖TV d_∞(I_1,I_2)= _a ^*||D_I_1(a)-D_I_2(a)||_TV (9) We could also weight each sequence of actions according to its length, reflecting the choice to place less weight on long-horizon discrepancies. Thus, we can consider dγ(ℐ1,ℐ2)=∑n=0∞γnsupa∈n‖Dℐ1(a)−Dℐ2(a)‖TV d_γ(I_1,I_2)= _n=0^∞γ^n _a ^n||D_I_1(a)-D_I_2(a)||_TV (10) for some γ∈(0,1)γ∈(0,1). Note that the distances in Eqs. (9) and (10) are indeed well-defined metrics over the set of interfaces. Since each transducer T induces an interface ℐTI_T through Eq. (1), any metric between interfaces can be seen as a pseudometric44 4 It is a pseudo metric because different transducers implementing the same interface are at distance 0. between transducers as d(T1,T2)=d(ℐT1,ℐT2). d(T_1,T_2)=d(I_T_1,I_T_2). Are these metrics “continuous” with respect to the notion of reduction? Namely, is there a metric d and a function f:ℝ>0→ℝ≥0f:R_>0 _≥ 0 with f(x)→x→00f(x) x→ 0→0 such that, if there is an ε -reduction from T1T_1 to T2T_2, then d(ℐT1,ℐT2)≤f(ε)d(I_T_1,I_T_2)≤ f( )? We first observe that this is not the case for the supremum distance in Eq. (9). Example 6. Pick d∞d_∞ as in Eq. (9), and consider the transducers from Example 5. Then, if T1T_1 is the transducer on the left and T2T_2 the one on the right, it can be seen that d(ℐT1,ℐT2)=1d(I_T_1,I_T_2)=1 for every ε>0 >0. Intuitively, the supremum distance is not controlled by the approximate homomorphism notion because the error bound applies only to the one-step dynamics. Thus, the interfaces implemented by the two transducers at long horizons (i.e. the distribution Pr(⋅|a) (·|a ) for a∈na ^n with n→∞n→∞) can be arbitrarily far away in metrics such as total variation. Nonetheless, this observation suggests that the discounted metrics from Eq. (10) might be preserved by the approximate homomorphism notion, and indeed this is the case. Theorem 1. Suppose there is an ε -reduction from T1T_1 to T2T_2. Then, if dγd_γ is the distance from Eq. (10), it holds that dγ(ℐT1,ℐT2)≤ε(1−γ)2. d_γ(I_T_1,I_T_2)≤ (1-γ)^2. (11) We write T1→T2T_1 →T_2 to indicate that there is an ε -homomorphism from T1T_1 to T2T_2. As already noted, exact homomorphisms can be composed, and thus the reduction relation is transitive. For approximate homomorphisms we can prove the following additive version. Proposition 2. If T1→ε1T2T_1 _1→T_2 and T2→ε2T3T_2 _2→T_3, then T1→ε1+ε2T3T_1 _1+ _2→T_3. This proposition states the existence of the dashed arrow in the following diagram: T1 @inpgf@ignorespaces T_1T2 @inpgf@ignorespaces T_2T3 @inpgf@ignorespaces T_3ε1 @inpgf@ignorespaces _1ε1+ε2 @inpgf@ignorespaces _1+ _2ε2 @inpgf@ignorespaces _2 Theorem 1 and Proposition 2 suggest that this notion of approximate homomorphism is natural and algebraically convenient. We recall that composability can be shown because we use total variation to compare the one-step dynamics: a different choice of distance to compare the distributions may not preserve this property. 3.2 The case of linear transducers To introduce an approximation error in the exact linear reduction we will equip each state vector space with a norm, which we will use to measure the distance between different vectors (mainly, between the vector obtained through the reduction and the vectors from the transducer itself). Throughout this subsection, we assume that the output alphabet O is finite. If V is a normed vector space, we denote its dual norm by ∥⋅∥V∗\|·\|_V^*. Given a linear operator C, we write ‖C‖a→b||C||_a→ b to denote the norm supx:‖x‖a=1||Cx||b _x:||x||_a=1||Cx||_b. An arbitrary linear transducer does not necessarily implement an interface. In particular, there are some transducers for which the norm of the state vector tends to infinity as the transducer reads symbols. Such a behaviour troubles our notion of approximate reduction, since a small margin of error in the one-step dynamics can be amplified arbitrarily in the subsequent steps. Thus, to rule out this situation, we introduce the notion of contractive transducer. Definition 9. A linear transducer G=(V,ξ,λ,Ma,o(a,o)∈A×O)G=(V,ξ,λ,\M_a,o\_(a,o)∈ A× O) is contractive if ‖ξ‖V≤1,‖λ‖V∗≤1,‖Ma,ox‖V≤‖x‖V,\|ξ\|_V≤ 1, \|λ\|_V^*≤ 1, \|M_a,ox\|_V≤\|x\|_V, for every a∈Aa∈ A, o∈Oo∈ O, and x∈Vx∈ V. The last condition ensures that after applying an evolution operator the norm of the vector state does not increase. Note that the canonical representation given by the Hankel matrix satisfies this definition. Indeed, on the Hankel row space VℐV_I, the prediction norm ‖r‖pred=supv∈Σ∗|r(v)|\|r\|_pred= _v∈ ^*|r(v)| makes every shift Ra,oℐR^I_a,o nonexpansive, because ‖Ra,oℐr‖pred=supv∈Σ∗|r((a,o)v)|≤‖r‖pred.\|R^I_a,or\|_pred= _v∈ ^*|r((a,o)v)|≤\|r\|_pred. Moreover, ‖ξℐ‖pred=1\| _I\|_pred=1, while ‖λℐ‖Vℐ∗≤1\| _I\|_V_I^*≤ 1 because λℐ(r)=r(ϵ) _I(r)=r(ε). We now introduce our notion of approximate linear reduction. Definition 10. Let G=(V,ξ,λ,Ma,oa,o)G=(V,ξ,λ,\M_a,o\_a,o) and G′=(W,ξ′,λ′,Na,oa,o)G =(W,ξ ,λ ,\N_a,o\_a,o) be contractive linear transducers over the same input and output alphabets, and let ε≥0 ≥ 0. A bounded surjective linear map L:V→WL:V→ W is a ε -linear reduction from G to G′G if ‖Lξ−ξ′‖W \|Lξ-ξ \|_W ≤ε, ≤ , ‖LMa,ox−Na,oLx‖W \|LM_a,ox-N_a,oLx\|_W ≤ε‖x‖V, ≤ \|x\|_V, ‖λ′L−λ‖V∗ \|λ L-λ\|_V^* ≤ε, ≤ , for every (a,o)∈A×O(a,o)∈ A× O and x∈Vx∈ V. We write G→G′G G when such a map exists. When G and G′G are contractive, the conditions for ε=0 =0 are precisely the equations defining an exact linear reduction. This definition extends approximate reductions between standard transducers. Proposition 3. Let T1T_1 and T2T_2 be finite standard transducers over the same alphabets, and suppose that a surjective state map ϕ:1→2φ:S_1 _2 is an ε -reduction. Then, if G1G_1 and G2G_2 are the linear implementations corresponding to T1T_1 and T2T_2 equipped with their ℓ1 _1 norms, there exists a 2ε2 -linear reduction from G1G_1 to G2G_2 induced by ϕφ. Approximate linear reductions can be composed in the same way as the standard approximate reductions. From now on, for a bounded linear map L, write c(L)=max1,‖L‖c(L)= \1,\|L\|\. The following holds. Proposition 4. Suppose that G0→ε1G1G_0 _1G_1 through the linear map L and G1→ε2G2G_1 _2G_2 through the linear map K. Then KLKL is a c(K)ε1+c(L)ε2c(K) _1+c(L) _2 linear reduction from G0G_0 to G2G_2. We next compare the interfaces implemented by approximately reduced linear transducers. In the case of standard transducers we could prove in Theorem 1 that the discounted metrics were preserved after an approximate reduction. For linear transducers we obtain a similar result, but with a weaker bound. Theorem 2. Let G and G′G be contractive linear transducers implementing interfaces ℐGI_G and ℐG′I_G . If G→G′G G , then, for every n≥1n≥ 1, supa∈n‖DℐG(a)−DℐG′(a)‖TV≤min1,n+22|O|nε. _a ^n\|D_I_G(a)-D_I_G (a)\|_TV≤ \1, n+22|O|^n \. (12) Consequently, for every γ∈(0,1)γ∈(0,1), dγ(ℐG,ℐG′)≤∑n≥0γnmin1,n+22|O|nε,d_γ(I_G,I_G )≤ _n≥ 0γ^n \1, n+22|O|^n \, (13) which converges to 0 as ε→0 → 0. Note that this implies that for small enough ε both transducers implement a similar interface. The bound is somewhat weaker when compared to the one from Theorem 1 because the notion of approximate reduction for standard transducers is stronger with respect to the one-step equivalence of the dynamics. For instance, Eq. (7) requires that the overall error (i.e. total variation) is bounded, while in Definition 10 we bound each error independently. This is the reason why a term |||O| shows up in the bound. We could fix this by changing the definition of approximate linear reduction, but it would require us to also modify the notion of contractive transducer. Moreover, the required change gives a notion of contractive transducer which does not include the canonical Hankel representations, which we want to use in later proofs. Nonetheless, we want to highlight the fact that there are many other valid choices regarding these definitions. In our case, we wanted to prioritize the fact that our abstractions should extend the notion of approximate reduction for standard transducers (proven in Proposition 3), should allow to represent the canonical Hankel constructions and should satisfy the simple and basic properties already seen for standard transducers (composability in Proposition 4 and continuity with regard to the discounted metrics in Theorem 2). 4 Approximate reductions between implementations of similar interfaces In this section we will study the set of transducers which implement a given interface ℐI, and we will try to relate them through approximate homomorphisms. Moreover, we will look at the set of transducers implementing a similar interface (using one of the distances for interfaces mentioned previously). Ideally, we would like for this set of transducers to share some property, since that would indicate an emergent property related to the representation of the interfaces. The following definition formalizes this set. Definition 11. Let ℐI be an interface, ε≥0 ≥ 0 and d some metric over the set of interfaces. We define ℒℐε,d=T:T is a transducer and d(ℐT,ℐ)≤ε. _I ,d= \T:T is a transducer and d(I_T,I)≤ \. as the set of transducers that ε -approximate ℐI. For every set ℒℐε,dL_I ,d we would like to understand whether there is some T∈ℒℐε,dT _I ,d such that, for every other T′∈ℒℐε,dT _I ,d, it holds that T′→T δ→T for some small δ, ideally scaling as δ=O(ε)δ=O( ). We call such a transducer a δ-minima of ℒℐε,dL_I ,d. We define δε(ℐ)=infδ∈ℝ≥0:ℒℐε,d has a δ-minima. _ (I)= \δ _≥ 0:L_I ,d has a $δ$-minima \. With this notation, our goal is to find bounds for δε(ℐ) _ (I) in terms of ε . Is there a subset of interfaces which is well-behaved in this sense? Does it matter which type of transducers we consider? See Figure 6 for a sketch of the type of behaviour that we aim for. In the next subsections we will consider the set ℒℐε,dL_I ,d restricted to different types of transducers. To avoid cluttering the notation we won’t add any more indices to this symbol, but rather take the convention that in each respective subsection this set is restricted to the set of transducers studied in the corresponding subsection. Figure 6: Schematic description of the type of convergence result we would like to prove. After fixing an interface of interest ℐI, we look at all interfaces ε -close to ℐI in some distance. For each of these interfaces (such as 1J_1 and 2J_2) there are many transducers implementing the dynamics (respectively, T1T_1 and T2T_2). We say that there is a O(ε)O( )-minimum if there is some transducer TminT_min implementing an interface from Bε(ℐ)B_ (I) such that for any transducer T implementing an interface in Bε(ℐ)B_ (I) it holds that T→O(ε)TminT O( )→T_min. In the diagram this is represented by the transducer TminT_min implementing the interface ℐI, and there are O(ε)O( )-reductions from both T1T_1 and T2T_2. 4.1 Non-existence of δ-minima for standard transducers As mentioned before, there exist an ℐI such that ℒℐ0,dL_I^0,d does not have a 0-minimum when considering only standard transducers55 5 Note that if ε=0 =0 the choice of distance is irrelevant.. Can this situation be avoided using δ reductions? Note that as δ increases we allow more reductions (in the limit, taking δ=1δ=1 allows every possible reduction), and thus it should make it simpler for convergent structures to arise. In the next proposition we show that this is not the case. Proposition 5. There exists an interface ℐI such that, for every δ<1δ<1, the set ℒℐ0,dL_I^0,d does not have a δ-minima. Even though ℒℐ0,dL_I^0,d does not have a common representation, it might be the case that when looking at approximate implementations of ℐI there is some convergent structure. Again, the answer is negative. Proposition 6. Let ℐI be the interface from Proposition 5. Then, for every ε≥0 ≥ 0, every transducer C, and every δ<1/2δ<1/2, it is not true that T′T δ-reduces to C for every T′∈ℒℐε,d∞T _I ,d_∞. In particular, ℒℐε,d∞L_I ,d_∞ does not have a δ-minima. These two results show that, in the case of standard transducers, there are interfaces for which no convergent structure exists between the different implementations of the interface, at least when we formalize this structure through our local notion of approximate homomorphism. This result is robust even when nearby interfaces are considered. Moreover, the counterexample is simple (it is a low-dimensional finite-rank interface), and the result can be proven for other distances (such as the discounted one dγd_γ). Thus, we don’t believe that there is a reasonable restricted set of interfaces for which we could bound δε(ℐ) _ (I) by O(ε)O( ). We remark that these results are an extension of the ones from [44] in the context of approximate homomorphisms and approximate implementations of interfaces. 4.2 Existence of δ-minima for linear transducers We now show a positive result for linear transducers. We will show that for all finite-rank interfaces ℐI all nearby interfaces have a canonical representation which is similar to the one from ℐI. This is intuitive: note that the canonical construction is induced by the rows of the Hankel matrix. If an interface is slightly perturbed then the Hankel matrix is slightly perturbed as well. Thus, we can map the new Hankel matrix to the original one identifying each row with the corresponding one from the original matrix. To obtain the strongest result possible we will give a norm to the canonical representation which dominates the predictive one. Definition 12. Let ℐI be an interface and let Vℐ=spanhℐ(w):w∈Σ∗V_I=span\h_I(w):w∈ ^*\ be its Hankel row space. For r∈Vℐr∈ V_I, define the atomic norm as ‖r‖at,ℐ:=inf∑i=1m|αi|:r=∑i=1mαihℐ(wi).\|r\|_at,I:= \ _i=1^m| _i|:r= _i=1^m _ih_I(w_i) \. We write GℐatG_I^at for the canonical Hankel implementation equipped with this norm. We are using the word atom to refer to each row of the Hankel matrix. We formally show that ||⋅||at||·||_at is a norm. Lemma 2. Let ℐI be an interface and equip its Hankel row space VℐV_I with the atomic norm. Then ‖⋅‖at,ℐ\| ·\|_at,I is a norm and, for every r∈Vℐr∈ V_I, ‖r‖pred≤‖r‖at,ℐ.\|r\|_pred≤\|r\|_at,I. Moreover, ‖ξℐ‖at,ℐ=1,‖λℐ‖(Vℐ,‖⋅‖at,ℐ)∗=1,\| _I\|_at,I=1, \| _I\|_(V_I,\| ·\|_at,I)^*=1, and every shift RσℐR^I_σ is nonexpansive. Consequently, GℐatG_I^at is a contractive linear transducer. This norm measures what is the best way to write r as a linear sum of the rows of the Hankel matrix, where we weight each sum with the sum of the absolute values of its coefficients. Our notion of linear reduction requires the mapping to be surjective. Thus, to ensure this property we will look at invertible minors of the Hankel matrix. Let ℐI be a finite-rank interface with d=rank(Hℐ)d=rank(H_I). We can choose prefixes p1,…,pdp_1,…,p_d and suffixes q1,…,qdq_1,…,q_d such that Cℐ:=(Fℐ(piqj))i,j=1dC_I:= (F_I(p_iq_j) )_i,j=1^d (14) is invertible and q1=ϵq_1=ε. Put Bℐ=(hℐ(p1)hℐ(pd)),Γℐ:=‖Cℐ−1‖∞→1.B_I= pmatrixh_I(p_1)\\[-2.84526pt] \\[-2.84526pt] h_I(p_d) pmatrix, _I:=\|C_I^-1\|_∞→ 1. For any interface J, define analogously C:=(F(piqj))i,j=1dC_J:= (F_J(p_iq_j) )_i,j=1^d and ev:V→ℝdev_J:V_J ^d given by ev(r):=(r(q1),…,r(qd)),ev_J(r):= (r(q_1),…,r(q_d) ), . Finally, let Π→ℐ:V⟶Vℐ _J :V_J V_I be the linear map Π→ℐ(r):=ev(r)Cℐ−1Bℐ. _J (r):=ev_J(r)C_I^-1B_I. The mapping Π→ℐ _J translates r∈Vr∈ V_J into a vector from VℐV_I by first evaluating the suffixes qi1≤i≤d\q_i\_1≤ i≤ d, then doing a change of coordinates using CℐC_I and finally projecting the result into the rows from VℐV_I indexed by pi1≤i≤d\p_i\_1≤ i≤ d. The following lemma shows that this mapping commutes with the shift operators up to a small error with respect to the ||⋅||at||·||_at norm if the interfaces are close. Moreover, whenever C_J is invertible the mapping is surjective. Lemma 3. If d∞(ℐ,)≤εd_∞(I,J)≤ , then, for every w∈Σ∗w∈ ^*, ‖Π→ℐh(w)−hℐ(w)‖at,ℐ≤Γℐε.\| _J h_J(w)-h_I(w)\|_at,I≤ _I . Moreover, if C_J is invertible, then Π→ℐ _J is surjective. It is a well-known fact that if a finite matrix M is invertible, then adding a small amount of noise to M keeps it invertible. We apply this observation to CℐC_I to guarantee that C_J remains invertible. Theorem 3. Let ℐI be a finite-rank interface and choose the minor CℐC_I as in (14), with q1=ϵq_1=ε. Then, there exists ε¯(ℐ)>0 (I)>0 such that, for every interface J satisfying d∞(ℐ,)≤ε<ε¯(ℐ),d_∞(I,J)≤ < (I), the map Π→ℐ:Gat→Gℐat _J :G_J^at→ G_I^at is a 2Γℐε2 _I -linear reduction. From this theorem we get as an immediate corollary the existence of δ-minima for a small enough neighbourhood of every finite-rank interface. Corollary 1. For every finite-rank interface ℐI, its canonical realization GℐG_I, equipped with the atomic norm, is a 2Γℐε2 _I -minimum of ℒℐε,d∞L_I ,d_∞ for every 0≤ε<ε¯(ℐ)0≤ < (I), when restricting ℒℐε,d∞L_I ,d_∞ to contain only the canonical linear realizations with the atomic norm. Note that our main theorem has to bound ε to ensure that the reduction is surjective. Even though this requirement is reasonable (otherwise, we could reduce small transducers into subcomponents of bigger ones), in many applications it might make sense to ignore this restriction. That’s why we phrased Theorem 3 in an independent way. The results in this section are in some sense satisfactory: we observed that convergent structure (i.e. a δ-minima for δ=O(ε)δ=O( )) exists for every finite rank interface in a neighbourhood of the interface. Observe that in our statements we have to pick a norm and a distance in a somewhat arbitrary way. However, a similar result can be proven using the predictive norm. Conceptually, we believe that these result indicate that the convergent structure exists at the level of linear transducers even in the presence of perturbations in the implementations. We remark that in Corollary 1 we restrict the lattice to the minimal linear implementations. If we don’t do this, we still can prove the existence of a reduction from any linear transducer G in the set by composing the map ρG _G from Lemma 1 with the one from Theorem 3 whenever ρG _G is bounded. Then, using Proposition 4 we would obtain an error that depends on ‖ρG‖\| _G\|. However, there is no uniform bound on this value when using the atomic norm. There are other choices of norms which can solve this problem but they seem quite unnatural, and therefore we prefer to keep the corollary as stated, applying only to the lattice of “optimal” implementations. 4.3 Existence of δ-minima for predictive transducers under a specific metric As already mentioned, restricting to predictive transducers restores a canonical minimum for each fixed interface, which we denote by (ℐ) E(I) (see Proposition 1). This exact statement is not stable under the supremum metric. Proposition 7. There is an interface ℐI and a sequence of interfaces (n)n≥1(J_n)_n≥ 1 such that d∞(ℐ,n)=2−n⟶0,d_∞(I,J_n)=2^-n 0, but every approximate reduction (n)→(ℐ) E(J_n) δ→ E(I) satisfies δ≥1/2δ≥ 1/2. Moreover, if a transducer C receives δ-reductions from both (ℐ) E(I) and (n) E(J_n), then δ≥1/4δ≥ 1/4. This counterexample also applies to the discounted metric, and we believe it highlights a limitation of predictive transducers. More precisely, if there is a history h such that the interface ℐI conditioned on h behaves in an extremely different way from the interface J conditioned on h, then the local structure related to both predictive states will be different, even if h is highly unlikely (and thus, it is ignored by most reasonable metrics). We now show that, as one would expect, this problem can be avoided by using precisely a notion of distance between interfaces that values every possible conditioning independently of its probability. For a positive probability history h, let ℐhI^h denote the residual interface after conditioning on h (see Eq. (4) for the exact definition). Write supp(ℐ)supp(I) for the set of positive probability histories and define dres(ℐ,)=suph∈supp(ℐ)d∞(ℐh,h),supp(ℐ)=supp(),1,otherwise.d_res(I,J)= cases _h (I)d_∞(I^h,J^h),&supp(I)=supp(J),\\[5.16663pt] 1,&otherwise. cases This metric compares the predictive laws after every history, including the ones with low probability. Let [h]ℐ[h]_I denote the state of (ℐ) E(I) reached after h, and put Δℐ=infd∞(ℐh,ℐu):h,u∈supp(ℐ),[h]ℐ≠[u]ℐ. _I= \d_∞(I^h,I^u):h,u (I),[h]_I≠[u]_I \. We use the convention Δℐ=+∞ _I=+∞ if there is only one predictive state. If (ℐ) E(I) is finite, then Δℐ>0 _I>0. Intuitively, Δℐ _I is a lower bound on the difference between the interfaces induced by each of the predictive states. If there is an interface J such that dres(ℐ,)d_res(I,J) is much smaller than Δℐ _I then the predictive transducers implementing ℐI and J will be similar. We formalize this in our last theorem. Theorem 4. Let ℐI and J be interfaces over the same input and output alphabets. Suppose that Δℐ>0 _I>0 and that dres(ℐ,)≤ε<min1,Δℐ2.d_res(I,J)≤ < \1, _I2 \. Then the assignment ϕ([h]):=[h]ℐ,φ([h]_J):=[h]_I, is a well-defined surjective state map and determines an ε -reduction E()⟶E(ℐ)E(J) E(I). Consequently, every predictive transducer implementing J admits an ε -reduction to E(ℐ)E(I). The intuition for the condition ε<Δℐ2 < _I2 comes from the triangle inequality: if we want to prove that ϕφ is well defined, we need to ensure that if h1∼h2h_1 h_2 in J then h1∼h2h_1 h_2 in ℐI. This is equivalent to verifying that ℐh1=ℐh2I^h_1=I^h_2, and by triangle inequality we see that d∞(ℐh1,ℐh2) d_∞(I^h_1,I^h_2) ≤d∞(ℐh1,h1)+d∞(h1,h2)+d∞(h2,ℐh2) ≤ d_∞(I^h_1,J^h_1)+d_∞(J^h_1,J^h_2)+d_∞(J^h_2,I^h_2) ≤2ε<Δℐ. ≤ 2 < _I. Then, by definition of Δℐ _I it must be the case that ℐh1=ℐh2I^h_1=I^h_2. As a corollary, we obtain the existence of δ-minimums for the set of predictive transducers. Corollary 2. Let ℐI be an interface such that Δℐ>0 _I>0. Then, for every 0<ε<min1,Δℐ20< < \1, _I2 \ and every predictive transducer T implementing an interface J with dres(ℐ,)≤εd_res(I,J)≤ there is a ε -reduction from T to (ℐ) E(I). This is a positive result regarding convergent structure, but its application is restricted to scenarios where the residual distance makes sense. In the following we describe an example of a situation in which two different stochastic systems can induce interfaces which are close according to dresd_res. Example 7. Let ==0,1,2S=O=\0,1,2\ and =⋆A=\ \ (i.e. the dynamics are actionless because there is a single action). and consider the transition matrix P=(1/21/41/41/41/21/41/41/41/2).P= pmatrix1/2&1/4&1/4\\ 1/4&1/2&1/4\\ 1/4&1/4&1/2 pmatrix. Let state i output i before making a transition. Thus, the transition kernel is κ(j,o∣i)=P(i,j)o=i.κ(j,o i)=P(i,j)1_\o=i\. Consider two transducers T and TεT_ using the kernel κ, but with different initial distributions given by p=(13,13,13)p= ( 13, 13, 13 ) for T and pε=(13+ε,13−ε,13)p_ = ( 13+ , 13- , 13 ) for TεT_ . See Figure 7 for a visual description. Transition matrixs0s_0s1s_1s2s_214 1414 1414 1412 1212 1212 12Initial distributionsTTp=(13,13,13) p= ( 13, 13, 13 )TεT_ pε=(13+ε,13−ε,13) p_ = ( 13+ , 13- , 13 ) Figure 7: We consider two transducers T and TεT_ with the same transition kernel described by the Markov process on the left but different initial distributions given on the right side. It can be seen that for small enough ε>0 >0 the induced interfaces satisfy dres(ℐT,ℐTε)≤ε<Δℐ/2d_res(I_T,I_T_ )≤ < _I/2. It can be seen that dres(ℐT,ℐTε)≤εd_res(I_T,I_T_ )≤ : note that conditioning on any non-empty history h the interfaces ℐThI^h_T and ℐTεhI^h_T_ are equal, and moreover d∞(ℐT,ℐTε)≤εd_∞(I_T,I_T_ )≤ . Moreover, it can be seen that ΔℐT=16 _I_T= 16. Thus, due to Theorem 4 we conclude that if ε<112 < 112 it holds that the minimal predictive implementation of ℐTI_T and of ℐTεI_T_ are ε -close through an approximate reduction. More generally, different processes with the same transition dynamics but different initial distributions can be close in the dresd_res metric whenever the effect of conditioning ensures that the current state for both processes is the same. 5 Conclusion Summary. In this work we looked for theoretical evidence supporting the empirical observation that different neural network models, sometimes even supported on different architectures, tend to converge to similar representations in their internal layers. To investigate this idea we proposed the approach described in Figure 1: we assumed that the reasoning inside the internal layers can be represented through some abstraction, and then we tried to prove some convergence at the level of these objects. In our case, we considered transducers to capture these world models, and to find convergent structure we looked for homomorphisms between them. Previous work had already proven that for the case of linear and predictive transducers there always exists a minimal transducer implementing a given dynamics, and that for all other non-minimal transducers there is a homomorphism to this minimal one [44]. In this paper we improved this result by showing that the existence of such an homomorphism remains even when we consider transducers that do not implement exactly the same dynamics. To do this, we first introduced a notion of approximate homomorphism for standard transducers (Definition 8) as well as for the linear ones (Definition 9). We showed that, although there are many ways to define such a family of homomorphisms, the ones proposed here have good algebraic properties: they preserve the dynamics under discounted metrics (Theorems 1 and 2), are composable (Propositions 2 and 4), and the linear approximate homomorphism is a direct extension of the standard one (Proposition 3). With these tools developed, we looked for convergence theorems in the approximate setting: we looked for conditions under which all transducers implementing similar dynamics share some common structure, which we aimed to capture through approximate homomorphisms (see Figure 6 for a visual sketch of the idea). In particular, we showed that (1) For standard transducers, this type of convergence seems to not be possible, even when considering simple dynamics (Propositions 5 and 6), (2) For linear transducers, simple enough dynamics (more technically, finite-rank interfaces) always admit a type of convergence between all the minimal linear implementations of ε -close dynamics (Theorem 3), and, finally, that (3) For predictive transducer, there is a metric such that all transducer implementing dynamics close enough according to this metric will share structural properties between them (Theorem 4). We believe these are positive theoretical results regarding the existence of convergent structure, in the context of both both linear and predictive transducers. The former family seems to be the natural model for capturing latent representation in modern neural networks, considering especially that the model parameters live in a vector space. The latter one, although less natural, still has been seen to show up inside the residual stream of transformers [46, 47], and thus understanding these representational properties might shed light into the behaviour of modern LLMs. Limitations. Through the development of this work we discovered that there are many ways to formalize approximate convergence in the context of transducers. Although the proposals here satisfy good properties and extend previous ones [41] there is still room for developing a more general theory of approximate homomorphisms. Moreover, in the context of linear transducers we had to equip the underlying vector space with a norm to measure distance between vectors, thus introducing another “parameter” to our theory. Although many of our main theorems can be proven for other choices of norms and distances (such as Theorem 3), it would be great to have a more robust understanding of the precise hypothesis required to conclude structural convergence in the approximate setting. Future work. We describe some future lines of work starting from the developments in this paper. • Experimental validation: these results give predictions on the structural convergence of deep neural networks under the hypothesis that they use transducers in their latent space. In particular, for models trained on similar data it must be the case that their internal representation can be translated with a linear map (such type of translation scheme is usually referred to as “stitching”, and has been studied in the literature [2, 9]). To validate these hypotheses, it would be interesting to train modern models with data generated from specific linear transducers and then see whether these transducers can be found in the learned representations. To do this, one could reproduce the setting from [46, 47]. • Poset structure: the original goal of this project was to study the poset of approximate homomorphism between world models. More precisely, we would like to understand how this poset looks like when we order it through the relation induced by the existence of an approximate homomorphism. A central and simple question is: under which hypothesis can we guarantee that this poset has cut-points, in the sense of intermediate models M such that, for any other model M′M , it holds that M has an homomorphism to M′M or the other way around. Given the introduced notions of approximate homomorphisms, this question can now be approached in the context of transducers. • Improved abstractions: Our abstractions are still limited and do not represent the myriad of forms on which “abstraction” and “reasoning” can occur inside modern AI models. Two recognizable improvement would be (1) introducing some non-linearity in the notion of linear transducers, to model the effect of the activation functions between layers, and (2) introducing a global error inside the notion of approximate homomorphism to allow homomorphisms that preserve the local structure of most of the states but fail completely in a small subset (such a notion would capture more faithfully what happens during model stitching when the target network is a bigger model than the source network). 6 Acknowledgements This work was funded by the Advanced Research + Invention Agency (ARIA) through project code MSAI-SE01-P005. We would like to thank the Dovetail Research team66 6 https://dovetailresearch.org/. for comments and suggestions on the draft of this paper, and we are especially grateful to Alex Altair, Alfred Harwood, Jose Faustino and Neal Batra for fruitful discussions. AI disclosure: We used ChatGPT 5.5 and 5.6 for proofreading, creating diagrams, writing down simple proofs (such as the proof from Lemma 2) and quickly exploring variants of the results (such as checking whether the proof of Theorem 3 holds for other choices of distances and norms). All content created by AI was revised and rewritten to improve readability and clarity of exposition. Appendix A Appendix A.1 Comparison of notions of exact homomorphisms We describe the original formulation of homomorphism and see how it differs from ours. Definition 13 (Homomorphism from [44]). Given two transducers T1=(1,1,1,κ1,p1)T_1=(S_1,A_1,O_1, _1,p_1) and T2=(2,2,2,κ2,p2)T_2=(S_2,A_2,O_2, _2,p_2), a homomorphism is given by three mappings ⟨ϕ:1→2,f:1→2,g:1→2⟩ φ:S_1 _2,f:A_1 _2,g:O_1 _2 satisfying (3), the condition Pr(o2|ϕ(s1),f(a1))T2=∑o1∈g−1(o2)Pr(o1|s1,a1)T1. _T_2(o_2|φ(s_1),f(a_1))= _o_1∈ g^-1(o_2) _T_1(o_1|s_1,a_1). (15) for every s1∈1,a1∈1s_1 _1,a_1 _1 and o2∈2o_2 _2, and whenever Pr(o1|s1,a1)T1>0 _T_1(o_1|s_1,a_1)>0 the condition Pr(s2|ϕ(s1),f(a1),g(o1))T2=∑s′∈ϕ−1(s2)Pr(s′|s1,a1,o1)T1 _T_2(s_2|φ(s_1),f(a_1),g(o_1))= _s ∈φ^-1(s_2) _T_1(s |s_1,a_1,o_1) (16) for every o1∈1o_1 _1 and s2∈2s_2 _2. We now show that this definition and ours coincide when g is injective. Proposition 8. Definitions 2 and 13 coincide if g is injective. Proof. Let T1=(1,1,1,κ1,p1)T_1=(S_1,A_1,O_1, _1,p_1) and T2=(2,2,2,κ2,p2)T_2=(S_2,A_2,O_2, _2,p_2) be transducers, and let ⟨ϕ,f,g⟩ φ,f,g be maps ϕ:1→2φ:S_1 _2, f:1→2f:A_1 _2 and g:1→2g:O_1 _2. We will prove that this tuple satisfies Definition 2 if and only if it satisfies Definition 13. Assume first that the joint-kernel condition (2) holds. Summing both sides over s2∈2s_2 _2 gives Pr(o2|ϕ(s1),f(a1))T2 _T_2(o_2|φ(s_1),f(a_1)) =∑s2∈2κ2(s2,o2|ϕ(s1),f(a1)) = _s_2 _2 _2(s_2,o_2|φ(s_1),f(a_1)) =∑s2∈2∑s′∈ϕ−1(s2)o′∈g−1(o2)κ1(s′,o′|s1,a1) = _s_2 _2 _ subarraycs ∈φ^-1(s_2)\\ o ∈ g^-1(o_2) subarray _1(s ,o |s_1,a_1) =∑o′∈g−1(o2)Pr(o′|s1,a1)T1, = _o ∈ g^-1(o_2) _T_1(o |s_1,a_1), which is exactly (15). Now fix o1∈1o_1 _1 such that Pr(o1|s1,a1)T1>0 _T_1(o_1|s_1,a_1)>0. Since g is injective, g−1(g(o1))=o1g^-1(g(o_1))=\o_1\. Hence Pr(s2|ϕ(s1),f(a1),g(o1))T2 _T_2(s_2|φ(s_1),f(a_1),g(o_1)) =κ2(s2,g(o1)|ϕ(s1),f(a1))PrT2(g(o1)|ϕ(s1),f(a1)) = _2(s_2,g(o_1)|φ(s_1),f(a_1)) _T_2(g(o_1)|φ(s_1),f(a_1)) =∑s′∈ϕ−1(s2)κ1(s′,o1|s1,a1)PrT1(o1|s1,a1) = _s ∈φ^-1(s_2) _1(s ,o_1|s_1,a_1) _T_1(o_1|s_1,a_1) =∑s′∈ϕ−1(s2)Pr(s′|s1,a1,o1)T1. = _s ∈φ^-1(s_2) _T_1(s |s_1,a_1,o_1). Thus the original conditional formulation follows. The initial condition is the same in both definitions. Conversely, assume Definition 13. We prove (2). If o2∉g(1)o_2∉ g(O_1), then the right-hand side of (15) is zero. Therefore Pr(o2|ϕ(s1),f(a1))T2=0 _T_2(o_2|φ(s_1),f(a_1))=0, and then κ2(s2,o2|ϕ(s1),f(a1))=0 _2(s_2,o_2|φ(s_1),f(a_1))=0 for every s2s_2. It remains to consider o2∈g(1)o_2∈ g(O_1). By injectivity there is a unique o1∈1o_1 _1 such that g(o1)=o2g(o_1)=o_2. If Pr(o1|s1,a1)T1>0 _T_1(o_1|s_1,a_1)>0, multiplying (16) by (15) gives κ2(s2,o2|ϕ(s1),f(a1)) _2(s_2,o_2|φ(s_1),f(a_1)) =Pr(o2|ϕ(s1),f(a1))T2Pr(s2|ϕ(s1),f(a1),o2)T2 = _T_2(o_2|φ(s_1),f(a_1)) _T_2(s_2|φ(s_1),f(a_1),o_2) =Pr(o1|s1,a1)T1∑s′∈ϕ−1(s2)Pr(s′|s1,a1,o1)T1 = _T_1(o_1|s_1,a_1) _s ∈φ^-1(s_2) _T_1(s |s_1,a_1,o_1) =∑s′∈ϕ−1(s2)κ1(s′,o1|s1,a1) = _s ∈φ^-1(s_2) _1(s ,o_1|s_1,a_1) =∑s′∈ϕ−1(s2)o′∈g−1(o2)κ1(s′,o′|s1,a1). = _ subarraycs ∈φ^-1(s_2)\\ o ∈ g^-1(o_2) subarray _1(s ,o |s_1,a_1). If Pr(o1|s1,a1)T1=0 _T_1(o_1|s_1,a_1)=0, then (15) gives Pr(o2|ϕ(s1),f(a1))T2=0 _T_2(o_2|φ(s_1),f(a_1))=0. Again nonnegativity forces both sides of (2) to be zero. The kernel condition therefore holds in all cases, and the initial condition is shared by the two definitions. ∎ When g is not injective, the two formulations need not agree. In the original definition, the only outputs that can be coarse-grained are those with the same output laws for each state. Meanwhile, our formulation only requires equality after averaging over the whole fiber g−1(o)g^-1(o) and ϕ−1(s)φ^-1(s). As already mentioned, since we focus on reductions this distinction is irrelevant. A.2 Total variation We collect here some relevant facts about total variation. All probability spaces in the sequel are finite or countable. Definition 14 (Total variation). Let μ,ν∈Δ(X)μ,ν∈ (X). Their total variation distance is ‖μ−ν‖TV=supA⊆X|μ(A)−ν(A)|=12∑x∈X|μ(x)−ν(x)|.\|μ-ν\|_TV= _A X|μ(A)-ν(A)|= 12 _x∈ X|μ(x)-ν(x)|. If h:X→Yh:X→ Y is a map and μ∈Δ(X)μ∈ (X), we write h∗μ∈Δ(Y)h_*μ∈ (Y) for the push-forward distribution, (h∗μ)(y)=∑x∈h−1(y)μ(x).(h_*μ)(y)= _x∈ h^-1(y)μ(x). If K:X→Δ(Y)K:X→ (Y) is a Markov kernel and μ∈Δ(X)μ∈ (X), we write μK∈Δ(Y)μ K∈ (Y) for the distribution (μK)(y)=∑x∈Xμ(x)K(y|x).(μ K)(y)= _x∈ Xμ(x)K(y|x). Lemma 4. Let μ,ν∈Δ(X)μ,ν∈ (X), let h:X→Yh:X→ Y and r:Y→Zr:Y→ Z be maps, and let K,L:X→Δ(Y)K,L:X→ (Y) be Markov kernels. Then, the following properties hold: 1. Convexity. If λi≥0 _i≥ 0, ∑iλi=1 _i _i=1, and μi,νi∈Δ(X) _i, _i∈ (X), then ‖∑iλiμi−∑iλiνi‖TV≤∑iλi‖μi−νi‖TV. \| _i _i _i- _i _i _i \|_TV≤ _i _i\| _i- _i\|_TV. 2. Push-forwards compose. (r∘h)∗μ=r∗(h∗μ).(r h)_*μ=r_*(h_*μ). 3. Push-forward contraction. ‖h∗μ−h∗ν‖TV≤‖μ−ν‖TV.\|h_*μ-h_*ν\|_TV≤\|μ-ν\|_TV. In particular, marginalization contracts total-variation. 4. Kernel contraction. ‖μK−νK‖TV≤‖μ−ν‖TV.\|μ K-ν K\|_TV≤\|μ-ν\|_TV. 5. Kernel perturbation bound. If supx∈X∥K(⋅|x)−L(⋅|x)∥TV≤ε, _x∈ X\|K(·|x)-L(·|x)\|_TV≤ , then ‖μK−νL‖TV≤‖μ−ν‖TV+ε.\|μ K-ν L\|_TV≤\|μ-ν\|_TV+ . Proof. Convexity follows directly from the ℓ1 ^1 expression for total variation and the triangle inequality: ‖∑iλiμi−∑iλiνi‖TV \| _i _i _i- _i _i _i \|_TV =12∑x|∑iλi(μi(x)−νi(x))| = 12 _x | _i _i( _i(x)- _i(x)) | ≤∑iλi12∑x|μi(x)−νi(x)| ≤ _i _i 12 _x| _i(x)- _i(x)| =∑iλi‖μi−νi‖TV. = _i _i\| _i- _i\|_TV. The composition identity is immediate from the definition of push-forward. For push-forward contraction, use the supremum characterization: ‖h∗μ−h∗ν‖TV=supB⊆Y|μ(h−1(B))−ν(h−1(B))|≤supA⊆X|μ(A)−ν(A)|=‖μ−ν‖TV.\|h_*μ-h_*ν\|_TV= _B Y|μ(h^-1(B))-ν(h^-1(B))|≤ _A X|μ(A)-ν(A)|=\|μ-ν\|_TV. Kernel contraction follows from the ℓ1 ^1 expression: ‖μK−νK‖TV \|μ K-ν K\|_TV =12∑y|∑x(μ(x)−ν(x))K(y|x)| = 12 _y | _x(μ(x)-ν(x))K(y|x) | ≤12∑x|μ(x)−ν(x)|∑yK(y|x)=‖μ−ν‖TV. ≤ 12 _x|μ(x)-ν(x)| _yK(y|x)=\|μ-ν\|_TV. Finally, ‖μK−νL‖TV≤‖μK−νK‖TV+‖νK−νL‖TV.\|μ K-ν L\|_TV≤\|μ K-ν K\|_TV+\|ν K-ν L\|_TV. The first term is bounded by ‖μ−ν‖TV\|μ-ν\|_TV by kernel contraction, and the second by ∑xν(x)∥K(⋅|x)−L(⋅|x)∥TV≤ε _xν(x)\|K(·|x)-L(·|x)\|_TV≤ by convexity. This proves the perturbation bound. ∎ A.3 Deferred proofs Proof of Lemma 1. We first check that ρG _G is well-defined. Suppose that ∑iαiMwiξ=0 _i _iM_w_iξ=0. Then, for every suffix v∈Σ∗v∈ ^*, ∑iαihℐ(wi)(v)=∑iαiFℐ(wiv)=∑iαiλ(MvMwiξ)=λ(Mv∑iαiMwiξ)=0. _i _ih_I(w_i)(v)= _i _iF_I(w_iv)= _i _iλ(M_vM_w_iξ)=λ\! (M_v _i _iM_w_iξ )=0. Hence ∑iαihℐ(wi)=0 _i _ih_I(w_i)=0, so the assignment is well-defined. Linearity is immediate from the definition. It is surjective because VℐV_I is spanned by the rows hℐ(w)h_I(w). The identities ρGξ=ξℐ _Gξ= _I, ρGMσ=RσℐρG _GM_σ=R^I_σ _G and λℐρG=λ _I _G=λ follow directly. ∎ Proof of Proposition 1. Starting from [ϵ]ℐ[ε]_I, Eq. (6) reproduces the conditional output probabilities of ℐI after every admissible history. Hence E(ℐ)E(I) implements ℐI. Its state after observing h is [h]ℐ[h]_I, so the residual future law is determined by the current state. Thus, it is predictive. Now let T be a predictive transducer implementing ℐI. For each reachable s∈s , choose an admissible history h such that qT(s∣h)>0q_T(s h)>0 and define ϕT(s)=[h]ℐ. _T(s)=[h]_I. (17) This is well defined: if both h and h′h are compatible with s, predictivity gives ℐh=ℐT,s=ℐh′I^h=I_T,s=I^h . It is surjective because every admissible history has at least one state in the support of its posterior. Also, every state with positive initial probability is compatible with the empty history, so (ϕT)∗p=δ[ϵ]ℐ( _T)_*p= _[ε]_I. Fix s and choose a compatible history h. Predictivity gives Pr(o∣s,a)T=Pr(o∣a)ℐh _T(o s,a)= _I^h(o a). Moreover, whenever κ(s′,o∣s,a)>0κ(s ,o s,a)>0, the state s′s is compatible with the extended history h(a,o)h(a,o), and therefore ϕT(s′)=[h(a,o)]ℐ _T(s )=[h(a,o)]_I. Thus all the probability mass associated with output o is pushed forward to the unique state prescribed by Eq. (6), and (ϕT×id)∗κ(⋅,⋅∣s,a)=κϵ(⋅,⋅∣ϕT(s),a).( _T× id)_*κ(·,· s,a)= _ε(·,· _T(s),a). Hence ϕT _T is a reduction. ∎ Proof of Theorem 1. Let ϕ:1→2φ:S_1 _2 be the map of the ε -reduction. Since a reduction preserves the input and output alphabets, let’s write the common alphabets of both transducers as A and O. Fix a section r:2→1r:S_2 _1 of ϕφ, so that ϕ(r(u))=uφ(r(u))=u for every u∈2u _2. For ∈na ^n, define two probability distributions P_a and Q_a on n×2O^n×S_2 by P(,u) P_a(o,u) =∑s∈ϕ−1(u)Pr(O1:n=,Sn1=s∣A1:n=)T1, = _s∈φ^-1(u) _T_1\! (O_1:n=o,\,S_n^1=s A_1:n=a ), Q(,u) Q_a(o,u) =Pr(O1:n=,Sn2=u∣A1:n=)T2, = _T_2\! (O_1:n=o,\,S_n^2=u A_1:n=a ), where SniS_n^i is a random variable denoting the state of the transducer TiT_i at step n, O1:nO_1:n denotes the first n observed outputs and A1:nA_1:n the first n inputs. Thus, P_a is the joint law of the output prefix and the coarse-grained state ϕ(Sn1)φ(S_n^1) under T1T_1 assuming inputs a, whereas Q_a is the corresponding joint law under T2T_2. We prove by induction on n that, for every ∈na ^n, ‖P−Q‖TV≤(n+1)ε.\|P_a-Q_a\|_TV≤(n+1) . (18) This is intuitive: initially the two distribution differ by at most ε because of the error in the initial distribution, and after each step this error increases by at most ε because the one-step transitions between T1T_1 and T2T_2 differ locally (i.e. when comparing s∈1s _1 with ϕ(s)φ(s)) by at most ε For n=0n=0, the output prefix is empty and Pϵ(ϵ,u)=(ϕ∗p1)(u),Qϵ(ϵ,u)=p2(u).P_ε(ε,u)=( _*p_1)(u), Q_ε(ε,u)=p_2(u). Consequently, the initial-distribution condition in the definition of an ε -reduction gives ‖Pϵ−Qϵ‖TV=‖ϕ∗p1−p2‖TV≤ε.\|P_ε-Q_ε\|_TV=\| _*p_1-p_2\|_TV≤ . Now fix ∈na ^n, a next action b∈b , and (,u)∈n×2(o,u) ^n×S_2. Define a probability distribution λ,,u _a,o,u on ϕ−1(u)φ^-1(u) as follows. If P(,u)>0P_a(o,u)>0, let λ,,u(s)=PrT1(O1:n=,Sn1=s∣1:n=)P(,u). _a,o,u(s)= _T_1\! (O_1:n=o,\,S_n^1=s _1:n=a )P_a(o,u). If P(,u)=0P_a(o,u)=0, set arbitrarily λ,,u=δr(u) _a,o,u= _r(u). Then, λa,o,u(s) _a,o,u(s) represents the probability for the state of transducer T1T_1 to be s at step n conditioned on T1T_1 being at a state in ϕ−1(u)φ^-1(u). For ∈no ^n, let j:2×⟶n+1×2,j(u′,o)=(o,u′),j_o:S_2×O ^n+1×S_2, j_o(u ,o)=(oo,u ), where ooo denotes concatenation. Consider the Markov kernels K^1,,b K_1,a,b and K^2,b K_2,b from n×2O^n×S_2 to n+1×2O^n+1×S_2 given by K^1,,b(⋅∣,u) K_1,a,b ( · ,u ) =(j)∗[∑s∈ϕ−1(u)λ,,u(s)(ϕ×id)∗κ1(⋅,⋅∣s,b)], =(j_o)_* [ _s∈φ^-1(u) _a,o,u(s)\,(φ×id_O)_* _1( ·, · s,b) ], K^2,b(⋅∣,u) K_2,b ( · ,u ) =(j)∗κ2(⋅,⋅∣u,b). =(j_o)_* _2( ·, · u,b). The first kernel performs one step of T1T_1, coarse-grains the next state through ϕφ, and retains the already observed output prefix. The second kernel performs the corresponding operation for T2T_2. For every (,u)(o,u), push-forward contraction, convexity of total variation, and the one-step condition of the ε -reduction give ‖K^1,,b(⋅∣,u)−K^2,b(⋅∣,u)‖TV \| K_1,a,b( · ,u)- K_2,b( · ,u) \|_TV ≤‖∑s∈ϕ−1(u)λ,,u(s)(ϕ×id)∗κ1(⋅,⋅∣s,b)−κ2(⋅,⋅∣u,b)‖TV ≤ \| _s∈φ^-1(u) _a,o,u(s)(φ×id_O)_* _1( ·, · s,b)- _2( ·, · u,b) \|_TV ≤∑s∈ϕ−1(u)λ,,u(s)‖(ϕ×id)∗κ1(⋅,⋅∣s,b)−κ2(⋅,⋅∣ϕ(s),b)‖TV ≤ _s∈φ^-1(u) _a,o,u(s) \|(φ×id_O)_* _1( ·, · s,b)- _2( ·, · φ(s),b) \|_TV ≤ε. ≤ . (19) Moreover, by construction of the conditional distributions λ,,u _a,o,u it follows that Pb=PK^1,,b,Qb=QK^2,b.P_ab=P_a K_1,a,b, Q_ab=Q_a K_2,b. Thus, applying the kernel perturbation bound from Lemma 4 and then the induction hypothesis yields ‖Pb−Qb‖TV \|P_ab-Q_ab\|_TV ≤‖P−Q‖TV+sup(,u)‖K^1,,b(⋅∣,u)−K^2,b(⋅∣,u)‖TV ≤\|P_a-Q_a\|_TV+ _(o,u) \| K_1,a,b( · ,u)- K_2,b( · ,u) \|_TV ≤(n+1)ε+ε=(n+2)ε. ≤(n+1) + =(n+2) . This completes the induction. The output distribution DℐT1()D_I_T_1(a) is the marginal of P_a on nO^n, and DℐT2()D_I_T_2(a) is the corresponding marginal of Q_a. Since marginalization contracts total variation, ‖DℐT1()−DℐT2()‖TV≤(n+1)ε \|D_I_T_1(a)-D_I_T_2(a) \|_TV≤(n+1) for every ∈na ^n. Therefore dγ(ℐT1,ℐT2) d_γ(I_T_1,I_T_2) =∑n=0∞γnsup∈n‖DℐT1()−DℐT2()‖TV = _n=0^∞γ^n _a ^n \|D_I_T_1(a)-D_I_T_2(a) \|_TV ≤ε∑n=0∞(n+1)γn=ε(1−γ)2. ≤ _n=0^∞(n+1)γ^n= (1-γ)^2. ∎ Proof of Proposition 2. Let ⟨ϕ1,f1,g1⟩ _1,f_1,g_1 be the ε1 _1-homomorphism from T1T_1 to T2T_2 and ⟨ϕ2,f2,g2⟩ _2,f_2,g_2 the ε2 _2-homomorphism from T2T_2 to T3T_3. Define the homomorphism ⟨ϕ=ϕ2∘ϕ1,f=f2∘f1,g=g2∘g1⟩ φ= _2 _1,f=f_2 f_1,g=g_2 g_1 from T1T_1 to T3T_3. We will prove that this is a (ε1+ε2)( _1+ _2)-homomorphism. Fix s∈1s _1 and a∈1a _1. By the composition rule for push-forwards, the triangle inequality, and contraction of total variation under push-forwards, ‖(ϕ×g)∗κ1(⋅,⋅∣s,a)−κ3(⋅,⋅∣ϕ(s),f(a))‖TV \|(φ× g)_* _1( ·, · s,a)- _3( ·, · φ(s),f(a)) \|_TV ≤‖(ϕ2×g2)∗((ϕ1×g1)∗κ1(⋅,⋅∣s,a)−κ2(⋅,⋅∣ϕ1(s),f1(a)))‖TV ≤ \|( _2× g_2)_* (( _1× g_1)_* _1( ·, · s,a)- _2( ·, · _1(s),f_1(a)) ) \|_TV +‖(ϕ2×g2)∗κ2(⋅,⋅∣ϕ1(s),f1(a))−κ3(⋅,⋅∣ϕ2(ϕ1(s)),f2(f1(a)))‖TV + \|( _2× g_2)_* _2( ·, · _1(s),f_1(a))- _3( ·, · _2( _1(s)),f_2(f_1(a))) \|_TV ≤ε1+ε2. ≤ _1+ _2. The initial distributions satisfy ‖ϕ∗p1−p3‖TV \| _*p_1-p_3\|_TV ≤‖(ϕ2)∗((ϕ1)∗p1)−(ϕ2)∗p2‖TV+‖(ϕ2)∗p2−p3‖TV ≤\|( _2)_*(( _1)_*p_1)-( _2)_*p_2\|_TV+\|( _2)_*p_2-p_3\|_TV ≤‖(ϕ1)∗p1−p2‖TV+‖(ϕ2)∗p2−p3‖TV ≤\|( _1)_*p_1-p_2\|_TV+\|( _2)_*p_2-p_3\|_TV ≤ε1+ε2. ≤ _1+ _2. Thus ⟨ϕ2∘ϕ1,f2∘f1,g2∘g1⟩ _2 _1,f_2 f_1,g_2 g_1 is an (ε1+ε2)( _1+ _2)-homomorphism. If both original maps are reductions, then the action and output maps are identities and ϕ1,ϕ2 _1, _2 are surjective. Hence ϕ2∘ϕ1 _2 _1 is surjective, so the composition is an (ε1+ε2)( _1+ _2)-reduction. ∎ Proof of Proposition 3. For i∈1,2i∈\1,2\, let Vi=ℝSiV_i=R^S_i with the ℓ1 _1 norm, let ξi=pi _i=p_i, and define λi(x)=∑s∈Sixs,Ma,oies=∑t∈Siκi(t,o∣s,a)et. _i(x)= _s∈ S_ix_s, M^i_a,oe_s= _t∈ S_i _i(t,o s,a)e_t. Each Ma,oiM^i_a,o is nonnegative and column-substochastic, and hence is an ℓ1 _1 contraction. Moreover, ‖ξi‖1=‖λi‖Vi∗=1\| _i\|_1=\| _i\|_V_i^*=1, so these linearizations are contractive. Define Lϕes=eϕ(s)L_φe_s=e_φ(s) and extend linearly. Since ϕφ is surjective, so is LϕL_φ, and ‖Lϕ‖1→1=1\|L_φ\|_1→ 1=1. The initial-state condition of the ordinary reduction gives ‖Lϕξ1−ξ2‖1=2‖ϕ∗p1−p2‖TV≤2ε.\|L_φ _1- _2\|_1=2\| _*p_1-p_2\|_TV≤ 2 . For a fixed s∈1s _1 and a∈a , the vector (LϕMa,o1−Ma,o2Lϕ)es(L_φM^1_a,o-M^2_a,oL_φ)e_s is the o-component of the difference between the two joint laws on 2×S_2×O appearing in the definition of an ordinary ε -reduction. Namely, (LϕMa,o1−Ma,o2Lϕ)es (L_φM^1_a,o-M^2_a,oL_φ)e_s =∑t1∈1κ1(t1,o|s,a)eϕ(t1)−∑t2∈2κ2(t2,o|ϕ(s),a)et2 = _t_1 _1 _1(t_1,o|s,a)e_φ(t_1)- _t_2 _2 _2(t_2,o|φ(s),a)e_t_2 =∑t2∈2[∑t1∈ϕ−1(t2)κ1(t1,o|s,a)−κ2(t2,o|ϕ(s),a)]et2 = _t_2 _2 [ _t_1∈φ^-1(t_2) _1(t_1,o|s,a)- _2(t_2,o|φ(s),a) ]e_t_2 Consequently, ‖(LϕMa,o1−Ma,o2Lϕ)es‖1≤2ε.\|(L_φM^1_a,o-M^2_a,oL_φ)e_s\|_1≤ 2 . Taking the maximum over the columns gives ‖LϕMa,o1−Ma,o2Lϕ‖1→1≤2ε.\|L_φM^1_a,o-M^2_a,oL_φ\|_1→ 1≤ 2 . Finally, λ2Lϕ=λ1 _2L_φ= _1. Thus LϕL_φ is a 2ε2 -linear reduction. The factor 22 shows up because of the normalization 12 12 in total variation. ∎ Proof of Proposition 4. Write Gi=(Vi,ξi,λi,Ma,oia,o)G_i=(V_i, _i, _i,\M^i_a,o\_a,o). Since L and K are bounded and surjective, so is KLKL. For the initial vectors, ‖KLξ0−ξ2‖≤‖K‖‖Lξ0−ξ1‖+‖Kξ1−ξ2‖≤‖K‖ε1+ε2. split\|KL _0- _2\|&≤\|K\|\,\|L _0- _1\|+\|K _1- _2\|\\ &≤\|K\| _1+ _2. split For each symbol (a,o)(a,o), KLMa,o0−Ma,o2KL=K(LMa,o0−Ma,o1L)+(KMa,o1−Ma,o2K)L, splitKLM^0_a,o-M^2_a,oKL=&K(LM^0_a,o-M^1_a,oL)\\ &+(KM^1_a,o-M^2_a,oK)L, split and hence the operator norm of this difference is at most ‖K‖ε1+‖L‖ε2\|K\| _1+\|L\| _2. Finally, λ2KL−λ0=(λ2K−λ1)L+(λ1L−λ0), _2KL- _0=( _2K- _1)L+( _1L- _0), whose dual norm is at most ‖L‖ε2+ε1\|L\| _2+ _1. All three quantities are bounded by c(K)ε1+c(L)ε2c(K) _1+c(L) _2. ∎ Proof of Theorem 2. Let L:V→WL:V→ W be the ε -linear reduction. For a=a1⋯an∈na=a_1·s a_n ^n and o=o1⋯on∈no=o_1·s o_n ^n, write Ma,o=Man,on⋯Ma1,o1M_a,o=M_a_n,o_n·s M_a_1,o_1 and Na,o=Nan,on⋯Na1,o1N_a,o=N_a_n,o_n·s N_a_1,o_1. Symbol-wise contractivity implies ‖Ma,oξ‖≤1\|M_a,oξ\|≤ 1. We claim that ‖LMa,oξ−Na,oξ′‖≤(n+1)ε.\|LM_a,oξ-N_a,oξ \|≤(n+1) . (20) For n=0n=0, this is the initial-vector condition. If the claim holds at length n and σ=(an+1,on+1)σ=(a_n+1,o_n+1), then ‖LMσMa,oξ−NσNa,oξ′‖≤‖(LMσ−NσL)Ma,oξ‖+‖Nσ(LMa,oξ−Na,oξ′)‖≤ε+(n+1)ε. split&\|LM_σM_a,oξ-N_σN_a,oξ \|\\ & ≤\|(LM_σ-N_σL)M_a,oξ\|+\|N_σ(LM_a,oξ-N_a,oξ )\|\\ & ≤ +(n+1) . split This proves (20) by induction. For every output word o∈no ^n, |λ(Ma,oξ)−λ′(Na,oξ′)|≤|(λ−λ′L)(Ma,oξ)|+|λ′(LMa,oξ−Na,oξ′)|≤(n+2)ε. split&|λ(M_a,oξ)-λ (N_a,oξ )|\\ & ≤|(λ-λ L)(M_a,oξ)|+|λ (LM_a,oξ-N_a,oξ )|\\ & ≤(n+2) . split Summing over the ||n|O|^n output words and dividing by two gives the second quantity in the minimum in (12), the bound by one holds because both sides are probability distributions. Equation (13) follows by summing the finite horizon bounds. For each fixed n, the remaining summand tends to zero with ε and is bounded by γnγ^n. Since ∑nγn<∞ _nγ^n<∞, we conclude that the right hand side converges to 0. ∎ Proof of Proposition 5. Fix =ℓ,gA=\ ,g\ and =$,0,1O=\\$,0,1\. Define ℐI as follows: in the first step, the output is the symbol $\$ with probability 1. Then, a fair coin is thrown, and the output is always 00 or 11 for all the next steps, depending on this coin. Thus, for every a1⋯ak∈ka_1·s a_k ^k with k≥2k≥ 2, we have Pr($∣a1)ℐ=1 _I(\$ a_1)=1 and Pr($0k−1∣a1⋯ak)ℐ=Pr($1k−1∣a1⋯ak)ℐ=12, _I(\$0^k-1 a_1·s a_k)= _I(\$1^k-1 a_1·s a_k)= 12, Note that the interface is independent of the actions taken. Consider the three-state transducer W with states SW=r,t0,t1S_W=\r,t_0,t_1\ and initial distribution centred at r and with kernel κW(t0,$∣r,a)=12,κW(t1,$∣r,a)=12, _W(t_0,\$ r,a)= 12, _W(t_1,\$ r,a)= 12, κW(t0,0∣t0,a)=1,κW(t1,1∣t1,a)=1. _W(t_0,0 t_0,a)=1, _W(t_1,1 t_1,a)=1. for every a∈a . Clearly W implements ℐI, and it can be proven that there is no transducer with less than 3 states implementing this interface. Now, let’s define another implementation U. Its states are SU=r,c00,c01,c10,c11,z0,z1S_U=\r,c_00,c_01,c_10,c_11,z_0,z_1\ with initial distribution centered at r. We describe the kernel by steps. First, we state that κU(cij,$∣r,a)=14(i,j∈0,1). _U(c_ij,\$ r,a)= 14 (i,j∈\0,1\). for every a∈a . Namely, in the first step the transducer transitions with uniform probability to any of the states cijc_ij. From cijc_ij, the action ℓ reads the first coordinate, while action g reads the second one. More precisely, we have κU(zi,i∣cij,ℓ)=1,κU(zj,j∣cij,g)=1. _U(z_i,i c_ij, )=1, _U(z_j,j c_ij,g)=1. Finally, for every a∈a we set κU(z0,0∣z0,a)=1,κU(z1,1∣z1,a)=1. _U(z_0,0 z_0,a)=1, _U(z_1,1 z_1,a)=1. It can be checked that the transducer U also implements ℐI: after the first output $\$, the pair (i,j)(i,j) is uniformly chosen; and whichever coordinate is read by the second action the final result is a fair bit. Afterwards, the machine moves to z0z_0 or z1z_1, where the same bit is repeated forever. Now suppose, towards a contradiction, that some T∈ℒℐ0,dT _I^0,d receives a δ-reduction from every element of ℒℐ0,dL_I^0,d, with δ<1δ<1. Since W∈ℒℐ0,dW _I^0,d, there is a surjective state map SW→STS_W→ S_T. Hence |ST|≤|SW|=3|S_T|≤|S_W|=3, and the fact that any implementation of ℐI must have at least three states implies that |ST|=3|S_T|=3. The three states of T can be labelled x$,x0,x1x_\$,x_0,x_1 depending on which node from W is the one mapped to them through the δ-reduction. Note that it must be the case that Pr(⋆|x⋆,a)T=1 _T( |x_ ,a)=1 for every ⋆∈ . To see this, first note that there must be some state which outputs $\$ with probability one. Otherwise, it would be impossible for T to implement ℐI exactly. With the same reasoning we can see that there must be some state that always outputs 00 and another one that always outputs 11. Then, we conclude that there is only one possibility for the reduction from W to T considering that δ<1δ<1. Since U∈ℒℐ0,dU _I^0,d, there is a δ-reduction ψ:U→Tψ:U δ→T. Consider the state c01∈SUc_01∈ S_U. There are three possible images, and we go through them one by one. If ψ(c01)=x$ψ(c_01)=x_\$ we reach an absurd, since the distributions between those states are at distance 11: c01c_01 assigns 0 probability to outputting $\$. If ψ(c01)=x0ψ(c_01)=x_0, then, under action g, the state c01c_01 outputs 11 with probability one, while x0x_0 outputs 00 with probability one. Thus ψ is not a proper δ-reduction with δ<1δ<1. If ψ(c01)=x1ψ(c_01)=x_1, we can argue in the same way. Therefore, no such transducer T∈ℒℐ0,dT _I^0,d exists. ∎ Proof of Proposition 6. Let W and U be the two exact implementations of ℐI constructed in the proof of Proposition 5. Since ℐW=ℐU=ℐI_W=I_U=I, we have W,U∈ℒℐε,d∞W,U _I ,d_∞ for every ε≥0 ≥ 0. Thus it is enough to prove the following claim: if W δ-reduces to C and U δ-reduces to C, then δ≥12δ≥ 12. Let φ:SW→SC :S_W→ S_C be the state map of a δ-reduction from W to C. Since ordinary reductions are surjective on states, we have |SC|≤|SW|=3|S_C|≤|S_W|=3. First suppose that |SC|≤2|S_C|≤ 2. The three states r,t0,t1r,t_0,t_1 of W have one-step output marginals δ$ _\$, δ0 _0 and δ1 _1 respectively, under every action. Since there are at most two states in C, two of r,t0,t1r,t_0,t_1 must have the same image x∈SCx∈ S_C. Hence, for two distinct outputs o≠o′o≠ o , the output marginal outC(x,a)out_C(x,a) is within total variation distance δ of both δo _o and δo′ _o . Marginalization cannot increase total variation, so 1=‖δo−δo′‖TV≤‖δo−outC(x,a)‖TV+‖outC(x,a)−δo′‖TV≤2δ.1=\| _o- _o \|_TV≤\| _o-out_C(x,a)\|_TV+\|out_C(x,a)- _o \|_TV≤ 2δ. Thus δ≥1/2δ≥ 1/2. It remains to consider the case |SC|=3|S_C|=3, where φ is bijective. Write x$=φ(r),x0=φ(t0),x1=φ(t1).x_\$= (r), x_0= (t_0), x_1= (t_1). as before. The reduction W→CW δ→C implies that, for every action a, ‖outC(x$,a)−δ$‖TV≤δ,\|out_C(x_\$,a)- _\$\|_TV≤δ, ‖outC(x0,a)−δ0‖TV≤δ,‖outC(x1,a)−δ1‖TV≤δ.\|out_C(x_0,a)- _0\|_TV≤δ, \|out_C(x_1,a)- _1\|_TV≤δ. Let ψ:SU→SCψ:S_U→ S_C be the map of a δ-reduction from U to C. Consider the state c01∈SUc_01∈ S_U. There are three possibilities. If ψ(c01)=x$ψ(c_01)=x_\$, then under action ℓ , the state c01c_01 outputs 00 with probability one. The reduction U→CU δ→C gives ‖δ0−outC(x$,ℓ)‖TV≤δ.\| _0-out_C(x_\$, )\|_TV≤δ. Together with the estimate coming from φ , we have ‖outC(x$,ℓ)−δ$‖TV≤δ,\|out_C(x_\$, )- _\$\|_TV≤δ, and then 1=‖δ0−δ$‖TV≤2δ.1=\| _0- _\$\|_TV≤ 2δ. If ψ(c01)=x0ψ(c_01)=x_0, then under action g, the state c01c_01 outputs 11 with probability one. Hence ‖δ1−outC(x0,g)‖TV≤δ.\| _1-out_C(x_0,g)\|_TV≤δ. But x0x_0 is δ-close to a 00-state, so ‖outC(x0,g)−δ0‖TV≤δ.\|out_C(x_0,g)- _0\|_TV≤δ. Therefore 1=‖δ1−δ0‖TV≤2δ.1=\| _1- _0\|_TV≤ 2δ. The last case can be treated in the same way. ∎ Proof of Lemma 2. For every w,v∈Σ∗w,v∈ ^* it is the case that 0≤hℐ(w)(v)=Fℐ(wv)≤10≤ h_I(w)(v)=F_I(wv)≤ 1. Hence, if r=∑i=1mαihℐ(wi)r= _i=1^m _ih_I(w_i), then ‖r‖pred \|r\|_pred =supv∈Σ∗|∑i=1mαihℐ(wi)(v)| = _v∈ ^* | _i=1^m _ih_I(w_i)(v) | ≤∑i=1m|αi|supv∈Σ∗|Fℐ(wiv)| ≤ _i=1^m| _i| _v∈ ^*|F_I(w_iv)| ≤∑i=1m|αi|. ≤ _i=1^m| _i|. Taking the infimum over all atomic decompositions of r gives ‖r‖pred≤‖r‖at,ℐ\|r\|_pred≤\|r\|_at,I. It is straightforward to prove that ‖λr‖at,ℐ=|λ|‖r‖at,ℐ\|λ r\|_at,I=|λ|\|r\|_at,I, and the triangle inequality is also easy to prove by concatenating atomic decompositions of the two summands. Finally, if ‖r‖at,ℐ=0\|r\|_at,I=0, the preceding inequality implies that ‖r‖pred=0\|r\|_pred=0. Thus r(v)=0r(v)=0 for every v∈Σ∗v∈ ^*, and hence r=0r=0. Therefore ‖⋅‖at,ℐ\| ·\|_at,I is a norm. We now check that ‖ξℐ‖at,ℐ=1\| _I\|_at,I=1. Since ξℐ=hℐ(ϵ) _I=h_I(ε) is itself an atom, ‖ξℐ‖at,ℐ≤1\| _I\|_at,I≤ 1. On the other hand, we have ‖ξℐ‖pred≥|ξℐ(ϵ)|=Fℐ(ϵ)=1\| _I\|_pred≥| _I(ε)|=F_I(ε)=1. Thus, using the previous shown relation between the atomic and predictive norms we conclude that ‖ξℐ‖at,ℐ=1\| _I\|_at,I=1. For the readout functional, recall that λℐ(r)=r(ϵ) _I(r)=r(ε). Thus |λℐ(r)|=|r(ϵ)|≤‖r‖pred≤‖r‖at,ℐ,| _I(r)|=|r(ε)|≤\|r\|_pred≤\|r\|_at,I, and consequently ‖λℐ‖(Vℐ,‖⋅‖at,ℐ)∗≤1\| _I\|_(V_I,\| ·\|_at,I)^*≤ 1. Since λℐ(ξℐ)=Fℐ(ϵ)=1 _I( _I)=F_I(ε)=1 and ‖ξℐ‖at,ℐ=1\| _I\|_at,I=1 the reverse inequality also holds, and we obtain ‖λℐ‖(Vℐ,‖⋅‖at,ℐ)∗=1\| _I\|_(V_I,\| ·\|_at,I)^*=1. Finally, we prove that the shift operators are nonexpansive in the atomic norm. For any atomic decomposition r=∑i=1mαihℐ(wi)r= _i=1^m _ih_I(w_i), the definition of the shift gives Rσℐr=∑i=1mαihℐ(wiσ).R_σ^Ir= _i=1^m _ih_I(w_iσ). Every hℐ(wiσ)h_I(w_iσ) is again a Hankel-row atom, and hence ‖Rσℐr‖at,ℐ≤∑i=1m|αi|.\|R_σ^Ir\|_at,I≤ _i=1^m| _i|. Taking the infimum over all atomic decompositions of r proves ‖Rσℐr‖at,ℐ≤‖r‖at,ℐ\|R_σ^Ir\|_at,I≤\|r\|_at,I. Using all the results, we can conclude that GℐatG_I^at is a contractive transducer. ∎ Proof of Lemma 3. Because the vectors hℐ(p1),…,hℐ(pd)h_I(p_1),…,h_I(p_d) form a basis of VℐV_I, every Hankel row of ℐI is reconstructed from its values on the selected suffixes. Namely, hℐ(w)=evℐ(hℐ(w))Cℐ−1Bℐ.h_I(w)=ev_I(h_I(w))C_I^-1B_I. Consequently, Π→ℐh(w)−hℐ(w)=ewCℐ−1Bℐ _J h_J(w)-h_I(w)=e_wC_I^-1B_I where ew=ev(h(w))−evℐ(hℐ(w))e_w=ev_J(h_J(w))-ev_I(h_I(w)). The condition d∞(ℐ,)≤εd_∞(I,J)≤ implies ‖ew‖∞≤ε\|e_w\|_∞≤ . Since the rows of BℐB_I are atoms for ∥⋅∥at,ℐ\|·\|_at,I, ‖ewCℐ−1Bℐ‖at,ℐ≤‖ewCℐ−1‖1≤Γℐε. split\|e_wC_I^-1B_I\|_at,I&≤\|e_wC_I^-1\|_1\\ &≤ _I . split The images of h(p1),…,h(pd)h_J(p_1),…,h_J(p_d) have coordinate matrix CCℐ−1C_JC_I^-1 in the basis given by the rows of BℐB_I. If C_J is invertible, these images span VℐV_I, proving surjectivity. ∎ Proof of Theorem 3. Choose ε¯(ℐ)>0 (I)>0 so that dε¯(ℐ)<σmin(Cℐ)d (I)< _ (C_I), where σmin(Cℐ) _ (C_I) denotes the minimal singular value of CℐC_I. Then, using standard perturbation arguments we may conclude that C_J is invertible, and Lemma 3 shows that Π→ℐ _J is surjective. More precisely, note that, because d∞(ℐ,)≤εd_∞(I,J)≤ , ‖C−Cℐ‖2≤‖C−Cℐ‖F≤dε<σmin(Cℐ),\|C_J-C_I\|_2≤\|C_J-C_I\|_F≤ d < _ (C_I), and therefore, for every x≠0x≠ 0, ‖Cx‖2 \|C_Jx\|_2 ≥‖Cℐx‖2−‖(C−Cℐ)x‖2 ≥\|C_Ix\|_2-\|(C_J-C_I)x\|_2 ≥σmin(Cℐ)‖x‖2−‖C−Cℐ‖2‖x‖2 ≥ _ (C_I)\|x\|_2-\|C_J-C_I\|_2\|x\|_2 ≥(σmin(Cℐ)−dε)‖x‖2>0. ≥( _ (C_I)-d )\|x\|_2>0. Applying Lemma 3 to the empty word gives ‖Π→ℐξ−ξℐ‖at,ℐ≤Γℐε.\| _J _J- _I\|_at,I≤ _I . For σ∈Σσ∈ and w∈Σ∗w∈ ^*, let Ew=Π→ℐh(w)−hℐ(w)E_w= _J h_J(w)-h_I(w). Since Rσℐhℐ(w)=hℐ(wσ)R^I_σh_I(w)=h_I(wσ), we have (Π→ℐRσ−RσℐΠ→ℐ)h(w)=Ewσ−RσℐEw. split&( _J R^J_σ-R^I_σ _J )h_J(w)\\ & =E_wσ-R^I_σE_w. split By Lemma 2, the shifts of GℐG_I are non-expansive with respect to the atomic norm, so ‖(Π→ℐRσ−RσℐΠ→ℐ)h(w)‖at,ℐ≤2Γℐε.\|( _J R^J_σ-R^I_σ _J )h_J(w)\|_at,I≤ 2 _I . (21) If r=∑iαih(wi)r= _i _ih_J(w_i), linearity and (21) give ‖(Π→ℐRσ−RσℐΠ→ℐ)r‖at,ℐ≤2Γℐε∑i|αi|. split&\|( _J R^J_σ-R^I_σ _J )r\|_at,I\\ & ≤ 2 _I _i| _i|. split Taking the infimum over all atomic decompositions of r proves the required bound. The choice q1=ϵq_1=ε makes the readout exact. Indeed, the first column of CℐC_I is Bℐ(ϵ)B_I(ε), and hence λℐ(Π→ℐr)=(Π→ℐr)(ϵ)=ev(r)Cℐ−1Bℐ(ϵ)=ev(r)e1=r(ϵ)=λ(r). split _I( _J r)&=( _J r)(ε)\\ &=ev_J(r)C_I^-1B_I(ε)\\ &=ev_J(r)e_1=r(ε)= _J(r). split Thus all three defects are bounded by 2Γℐε2 _I . Finally, we show that Π→ℐ _J is bounded. For every w∈Σ∗w∈ ^*, ‖Π→ℐh(w)‖at,ℐ≤‖hℐ(w)‖at,ℐ+‖Π→ℐh(w)−hℐ(w)‖at,ℐ≤1+Γℐε.\| _J h_J(w)\|_at,I≤\|h_I(w)\|_at,I+\| _J h_J(w)-h_I(w)\|_at,I≤ 1+ _I . Consequently, if r=∑i=1mαih(wi)r= _i=1^m _ih_J(w_i), then ‖Π→ℐr‖at,ℐ≤(1+Γℐε)∑i=1m|αi|.\| _J r\|_at,I≤(1+ _I ) _i=1^m| _i|. Taking the infimum over all atomic decompositions of r we conclude that ‖ΠJ→I‖≤1+ΓIε\| _J→ I\|≤ 1+ _I . ∎ Proof of Proposition 7. Let =0,1O=\0,1\, =⋆A=\ \ (i.e. the dynamics are actionless) and let ℐI be the process of independent fair bits. Write D(m)D_K^(m) for the length-m output law of an interface K. For n≥1n≥ 1, define nJ_n as follows. Its first n outputs are independent fair bits. If these outputs are 0n0^n, then every later output is 00; otherwise, all later outputs continue to be independent fair bits. The length-m distributions agree for m≤nm≤ n. For m>nm>n they differ only on strings beginning with 0n0^n, and a direct calculation gives ‖Dℐ(m)−Dn(m)‖TV=2−n−2−m. \|D_I^(m)-D_J_n^(m) \|_TV=2^-n-2^-m. Taking the supremum over m gives d∞(ℐ,n)=2−nd_∞(I,J_n)=2^-n. The transducer (ℐ) E(I) has one state, whose output law is 12δ0+12δ1 12 _0+ 12 _1. In (n) E(J_n), the state reached after 0n0^n outputs 00 deterministically. Any state map to the one-state target must send this state to the unique state of (ℐ) E(I). Marginalizing the joint one-step kernels to outputs therefore gives δ≥‖δ0−(12δ0+12δ1)‖TV=12.δ≥ \| _0- ( 12 _0+ 12 _1 ) \|_TV= 12. For the last claim, surjectivity of a reduction from the one-state transducer (ℐ) E(I) forces C to have one state. Let ν be its output law. The two reductions imply ‖ν−(12δ0+12δ1)‖TV≤δ,‖ν−δ0‖TV≤δ. \|ν- ( 12 _0+ 12 _1 ) \|_TV≤δ, \|ν- _0\|_TV≤δ. Then, the triangle inequality gives 1/2≤2δ1/2≤ 2δ. ∎ Proof of Theorem 4. Since dres(ℐ,)≤ε<1d_res(I,J)≤ <1, the definition of dresd_res implies that supp(ℐ)=supp()supp(I)=supp(J). Moreover, for every h in this common support we have d∞(ℐh,h)≤εd_∞(I^h,J^h)≤ . We first prove that ϕφ is well defined. Suppose that [h]=[u][h]_J=[u]_J. By definition of predictive equivalence, h=uJ^h=J^u. Therefore, by the triangle inequality, d∞(ℐh,ℐu) d_∞(I^h,I^u) ≤d∞(ℐh,h)+d∞(h,u)+d∞(u,ℐu) ≤ d_∞(I^h,J^h)+d_∞(J^h,J^u)+d_∞(J^u,I^u) ≤2ε<Δℐ. ≤ 2 < _I. If [h]ℐ≠[u]ℐ[h]_I≠[u]_I, the definition of Δℐ _I would instead give d∞(ℐh,ℐu)≥Δℐd_∞(I^h,I^u)≥ _I, which is a contradiction. Hence [h]ℐ=[u]ℐ[h]_I=[u]_I, proving that ϕφ is well defined. The map is surjective. Indeed, every state of E(ℐ)E(I) is of the form [h]ℐ[h]_I for some h∈supp(ℐ)h (I). Since the interfaces have the same support, h∈supp()h (J), and therefore [h]ℐ=ϕ([h]).[h]_I=φ([h]_J). It remains to verify the approximate one-step condition. For an interface K, write μKh(o∣a)=Pr(o∣a)Kh _K^h(o a)= _K^h(o a) for the one-step output law after h. Fix h∈supp(ℐ)=supp()h (I)=supp(J) and a∈a . For every o having positive conditional probability, the canonical transducers move respectively to [h(a,o)][h(a,o)]_J and [h(a,o)]ℐ[h(a,o)]_I. By definition of ϕφ, it holds that ϕ([h(a,o)])=[h(a,o)]ℐφ([h(a,o)]_J)=[h(a,o)]_I. Furthermore, equality of supports implies that μℐh(o∣a)>0 _I^h(o a)>0 if and only if μh(o∣a)>0 _J^h(o a)>0. Consequently, after pushing the kernel of E()E(J) forward through ϕφ, both joint kernels place their mass corresponding to o on the same pair ([h(a,o)]ℐ,o) ([h(a,o)]_I,o ). It follows that ‖(ϕ×id)∗κϵ,(⋅,⋅∣[h],a)−κϵ,ℐ(⋅,⋅∣[h]ℐ,a)‖TV \|(φ×id_O)_* _ε,J( ·, · [h]_J,a)- _ε,I( ·, · [h]_I,a) \|_TV =‖μh(⋅∣a)−μℐh(⋅∣a)‖TV 40.00006pt= \| _J^h( · a)- _I^h( · a) \|_TV ≤d∞(h,ℐh)≤ε. 40.00006pt≤ d_∞(J^h,I^h)≤ . The initial state is preserved exactly: ϕ∗δ[ϵ]=δ[ϵ]ℐ. _* _[ε]_J= _[ε]_I. Thus ϕφ determines an ε -reduction E()→E(ℐ)E(J)→ E(I). ∎ Proof of Corollary 2. Let T be a predictive transducer from the statement. By Proposition 1 there is an exact reduction from T to () E(J). Then, by Theorem 4 there is a ε -reduction from E()E(J) to E(ℐ)E(I). Composing them we get the desired result, using Proposition 2 to bound the error of the composition. ∎ References [1] D. Abel, D. Hershkowitz, and M. Littman (2016) Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, p. 2915–2923. Cited by: §1. [2] Y. Bansal, P. Nakkiran, and B. Barak (2021) Revisiting model stitching to compare neural representations. Advances in neural information processing systems 34, p. 225–236. Cited by: §1, 1st item. [3] N. Barnett and J. P. Crutchfield (2015) Computational mechanics of input–output processes: structured transformations and the ϵε-transducer. Journal of Statistical Physics 161 (2), p. 404–451. Cited by: item 4, §1, §2.1, §2.3. [4] Y. Bengio, A. Courville, and P. Vincent (2013) Representation learning: a review and new perspectives. IEEE transactions on pattern analysis and machine intelligence 35 (8), p. 1798–1828. Cited by: §1. [5] Y. Berchenko (2024) Simplicity bias in overparameterized machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 11052–11060. Cited by: §1. [6] L. Bereska and E. Gavves (2024) Mechanistic interpretability for ai safety–a review. arXiv preprint arXiv:2404.14082. Cited by: §1. [7] A. Boyd, F. Nowak, D. Hyland, M. Baltieri, and F. E. Rosas (2025) From monoliths to modules: Decomposing transducers for efficient world modelling. External Links: 2512.02193, Document Cited by: §1. [8] R. Cao and D. Yamins (2021) Explanatory models in neuroscience: part 2–constraint-based intelligibility. arXiv preprint arXiv:2104.01489. Cited by: §1. [9] A. Chen, J. Merullo, A. Stolfo, and E. Pavlick (2026) Transferring linear features across language models with model stitching. Advances in Neural Information Processing Systems 38, p. 48531–48563. Cited by: §1, 1st item. [10] L. Ciernik, L. Linhardt, M. Morik, J. Dippel, S. Kornblith, and L. Muttenthaler (2024) Objective drives the consistency of representational similarity across datasets. arXiv preprint arXiv:2411.05561. Cited by: §1. [11] S. Cifuentes (2026) General agents contain world models, even under partial observability and stochasticity. arXiv preprint arXiv:2602.03146. Cited by: §1. [12] J. P. Crutchfield (1989) Inferring the dynamic, quantifying physical complexity. In Measures of Complexity and Chaos, p. 327–338. Cited by: §1. [13] A. Csiszárik, P. Kőrösi-Szabó, A. Matszangosz, G. Papp, and D. Varga (2021) Similarity and matching of neural network representations. Advances in Neural Information Processing Systems 34, p. 5656–5668. Cited by: §1. [14] J. Desharnais, V. Gupta, R. Jagadeesan, and P. Panangaden (2004) Metrics for labelled markov processes. Theoretical computer science 318 (3), p. 323–354. Cited by: §1. [15] F. Ding, J. Denain, and J. Steinhardt (2021) Grounding representation similarity through statistical testing. Advances in neural information processing systems 34, p. 1556–1568. Cited by: §1. [16] N. Ferns, P. Panangaden, and D. Precup (2004) Metrics for finite Markov decision processes. In Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence, p. 162–169. Cited by: §1. [17] R. Givan, T. Dean, and M. Greig (2003) Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence 147 (1–2), p. 163–223. External Links: Document Cited by: §1. [18] M. Gorbett and S. Jana (2026) Characterizing linear alignment across language models. arXiv preprint arXiv:2603.18908. Cited by: §1. [19] F. Gröger, S. Wen, and M. Brbić (2026) Revisiting the platonic representation hypothesis: an aristotelian view. arXiv preprint arXiv:2602.14486. Cited by: §1. [20] D. Ha and J. Schmidhuber (2018) World models. arXiv preprint arXiv:1803.10122 2 (3), p. 440. Cited by: §1. [21] D. Hafner, J. Pasukonis, J. Ba, and T. Lillicrap (2023) Mastering diverse domains through world models. arXiv preprint arXiv:2301.04104. Cited by: §1. [22] W. Hu (2024) Understanding surprising generalization phenomena in deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 22669–22669. Cited by: §1. [23] M. Huh, B. Cheung, T. Wang, and P. Isola (2024) The platonic representation hypothesis. arXiv preprint arXiv:2405.07987. Cited by: §1, §1. [24] J. Jiang, J. Zhou, P. Wang, Q. Qu, D. Mixon, C. You, and Z. Zhu (2023) Generalized neural collapse for a large number of classes. arXiv preprint arXiv:2310.05351. Cited by: §1. [25] D. Kalimeris, G. Kaplun, P. Nakkiran, B. Edelman, T. Yang, B. Barak, and H. Zhang (2019) Sgd on neural networks learns functions of increasing complexity. Advances in neural information processing systems 32. Cited by: §1. [26] J. G. Kemeny J. L. Snell et al. (1969) Finite markov chains. Vol. 26, van Nostrand Princeton, NJ. Cited by: §1. [27] S. Kiefer and Q. Tang (2021) Approximate bisimulation minimisation. arXiv preprint arXiv:2110.00326. Cited by: §1. [28] M. Klabunde, T. Schumacher, M. Strohmaier, and F. Lemmerich (2025) Similarity of neural network models: a survey of functional and representational measures. ACM Computing Surveys 57 (9), p. 1–52. Cited by: §1. [29] S. Kornblith, M. Norouzi, H. Lee, and G. Hinton (2019) Similarity of neural network representations revisited. In International conference on machine learning, p. 3519–3529. Cited by: §1. [30] K. G. Larsen and A. Skou (1991) Bisimulation through probabilistic testing. Information and Computation 94 (1), p. 1–28. External Links: Document Cited by: §1. [31] Y. LeCun, Y. Bengio, and G. Hinton (2015) Deep learning. nature 521 (7553), p. 436–444. Cited by: §1. [32] L. Li, T. J. Walsh, and M. L. Littman (2006) Towards a unified theory of state abstraction for mdps.. AI&M 1 (2), p. 3. Cited by: §1. [33] Y. Li, J. Yosinski, J. Clune, H. Lipson, and J. Hopcroft (2015) Convergent learning: do different neural networks learn the same representations?. arXiv preprint arXiv:1511.07543. Cited by: §1. [34] G. H. Mealy (1955) A method for synthesizing sequential circuits. The Bell System Technical Journal 34 (5), p. 1045–1079. Cited by: §1. [35] M. Mohri (1997) Finite-state transducers in language and speech processing. Computational linguistics 23 (2), p. 269–311. Cited by: §1. [36] E. F. Moore et al. (1956) Gedanken-experiments on sequential machines. Automata studies 34 (129-153), p. 129–153. Cited by: §1. [37] A. Morcos, M. Raghu, and S. Bengio (2018) Insights on representational similarity in neural networks with canonical correlation. Advances in neural information processing systems 31. Cited by: §1. [38] A. Nayebi (2026) What capable agents must know: selection theorems for robust decision-making under uncertainty. arXiv preprint arXiv:2603.02491. Cited by: §1. [39] T. Nguyen, M. Raghu, and S. Kornblith (2020) Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth. arXiv preprint arXiv:2010.15327. Cited by: §1. [40] M. L. Puterman (2014) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons. Cited by: §1. [41] B. Ravindran and A. G. Barto (2003) SMDP homomorphisms: An algebraic approach to abstraction in semi-Markov decision processes. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, p. 1011–1016. Cited by: §1, §5. [42] B. Ravindran and A. G. Barto (2004) Approximate homomorphisms: A framework for non-exact minimization in Markov Decision Processes. Note: Manuscript External Links: Link Cited by: §1. [43] J. Richens, D. Abel, A. Bellot, and T. Everitt (2025) General agents contain world models. Note: Accepted at ICML 2025 External Links: 2506.01622, Document Cited by: §1. [44] F. Rosas, A. Boyd, and M. Baltieri (2025) AI in a vat: fundamental limits of efficient world modelling for agent sandboxing and interpretability. arXiv preprint arXiv:2504.04608. Cited by: item 2, §1, §1, §2.1, §2.1, §2.1, §4.1, §5, Definition 13, Observation 1. [45] M. P. Schützenberger (1961) On the definition of a family of automata. Inf. Control. 4 (2-3), p. 245–270. Cited by: §1. [46] A. Shai, L. Amdahl-Culleton, C. L. Christensen, H. R. Bigelow, F. E. Rosas, A. B. Boyd, E. A. Alt, K. J. Ray, and P. M. Riechers (2026) Transformers learn factored representations. arXiv preprint arXiv:2602.02385. Cited by: §1, §1, §1, 1st item, §5. [47] A. S. Shai, S. E. Marzen, L. Teixeira, A. G. Oldenziel, and P. M. Riechers (2024) Transformers represent belief state geometry in their residual stream. Advances in Neural Information Processing Systems 37, p. 75012–75034. Cited by: §1, §1, 1st item, §5. [48] C. R. Shalizi and J. P. Crutchfield (2001) Computational mechanics: pattern and prediction, structure and simplicity. Journal of statistical physics 104 (3), p. 817–879. Cited by: §1. [49] T. Spork, C. Baier, J. Katoen, J. Piribauer, and T. Quatmann (2024) A spectrum of approximate probabilistic bisimulations. In 35th International Conference on Concurrency Theory (CONCUR 2024), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 311, p. 37:1–37:19. External Links: Document Cited by: §1. [50] J. J. Taylor, D. Precup, and P. Panangaden (2008) Bounding performance loss in approximate MDP homomorphisms. In Advances in Neural Information Processing Systems 21, p. 1649–1656. Cited by: §1. [51] G. Valle-Perez, C. Q. Camargo, and A. A. Louis (2018) Deep learning generalizes because the parameter-function map is biased towards simple functions. arXiv preprint arXiv:1805.08522. Cited by: §1. [52] S. Watanabe (2018) Mathematical theory of bayesian statistics. CRC press. Cited by: §1.