Convergence Analysis of Tsetlin Machines under Noise-Free and Noisy Training Conditions: From $2$ Bits to $k$ Bits
Authors: Xuan Zhang
Lei Jiao
Ole-Christoffer Granmo
Venue: ICLR 2026 Poster (2026)
Keywords: Tsetlin Automata
Propositional Logic
Tsetlin Machine
Convergence Analysis
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: The Tsetlin Machine (TM) is an innovative machine learning algorithm grounded in propositional logic, achieving state-of-the-art performance across a variety of pattern recognition tasks. Prior theoretical work has established convergence results for the 1-bit operator under both noisy and noise-free conditions, and for the 2-bit XOR operator under noise-free conditions. This paper first extends the analysis to the 2-bit AND and OR operators. We show that the TM converges almost surely to the correct 2-bit AND and OR operators under the noise-free training condition, and we identify a distinctive property of the 2-bit OR operator, where a single clause can jointly represent two sub-patterns, in contrast to the XOR operator. We further investigate noisy training scenarios, demonstrating that mislabelled samples prevent exact convergence but still permit efficient learning, whereas irrelevant variables do not prevent almost-sure convergence. Building on the 2-bit analysis, we then generalize the results to the $k$-bit setting ($k>2$), providing a unified theoretical treatment applicable to general scenarios. Together, these findings provide a robust and comprehensive theoretical foundation for analyzing TM convergence.

Published as a conference paper at ICLR 2026
CONVERGENCE ANALYSIS OF TSETLIN MACHINES UNDER NOISE-FREE AND NOISY TRAINING CONDI- TIONS: FROM 2 BITS TO k BITS
Xuan Zhang*.? Lei Jiao": Ole-Christoffer Granmo'
The Centre for Artificial Intelligence Research, University of Agder, Grimstad, Norway NORCE Research AS (NORCE), Grimstad, Norway xuzh@norceresearch.. no; [lei.jiam) ole. granorrammmuuur @uia.
ABSTRACT
The Tsetlin Machine (TM) is an innovative machine learning algorithm grounded in propositional logic, achieving state-of-the-art performance across variety of pattern recognition tasks. Prior theoretical work has established convergence re- sults for the 1-bit operator under both noisy and noise-free conditions, and for the 2-bit XOR operator under noise-free conditions. This paper first extends the anal- ysis to the 2- AND and OR operators. We show that the TM converges almost surely to the correct 2-bit AND and OR operators under the woise-free training condition, and we identify a distinctive property of the 2-bit OR operator, where a single clause can jointly represent two sub-patterns, in contrast to the XOR opera- tor. We further investigate noisy training scenarios, demonstrating that mislabelled samples prevent exact convergence but still permit efficient learning, whereas ir- relevant variables do not prevent almost-sure convergence. Building on the 2-bit analysis, then generalize the results to the k-bit setting (k 2), providing unified theoretical treatment applicable to general scenarios. Together, these find- ings provide robust and comprehensive theoretical foundation for analyzing TM convergence.
INTRODUCTION
The Tsetlin Machine (TM) is a classification algorithm. TM Granmo 2018) organizes clauses, each associated with team of Tsetlin Automata (TAs) Tsetlin 1961). collaboratively capture distinct sub-patterns"] for a certain class. A TA, which the core learning entity of TM, is a kind of learning automata (Zhang al. 2020 Yazidi al. 2019 Omslandseter
al. 2024) that tackles the multi-armed bandit problem, learning the optimal action through the interaction with its environment which gives rewards and penalties. In TM, all TAs play feedback tables. Each TA takes care of one literal of input, which takes boolean values of either 1. Literals are basically features of the input data. A TA decides "Include" "Exclude" the literal, i.c., to consider or not to consider the feature in the final classification. A clause is conjunction of all included literals, representing a sub-pattern patterns are learned by number of clauses, the overall pattern recognition task is completed by voting scheme from the clauses.
game orchestrated by the TM's
certain class. Once distinct sub-
The TM and its variants (Granmo et al. 2019 Abeyrathna et al. 202 Darshana Abeyrathna al., 2020 Sharma et al.] 2023) have been applied to diverse tasks, including word sense disambigua- aspect-based sentiment analysis (Yadav et al.] 2021b). novelty detec-
tion Yadav et al.) 2021c),
tion (Bhattarai et al. 2202 interpretable text classification (Yadav et al. [02 Yadav et al. (022),
federated learning (Qi et al. 2025), signal classification (Jeeru et al.] 2025a b). and contextual ban-
dits (Seraj et al. 2022), where they often match or surpass state-of ofate-of-the-ard the-art methods. As a symbolic
model, the TM offers transparent learning and inference (Granmo et al.) 2025 Bhattarai al. 2024
Abeyrathna et al. 2023 Rafiev et al. 2022) Its reliance solely on logical operations also makes
"Corresponding author.
'The concept of sub-pattem will he found in the example given in Section

---

Published as a conference paper at ICLR 2026
it wordddwwr---reeddeee and energy-efficinn (Maheshwari et al. 2023 Rahman al. 2022 Kishore
ct al. 2023; Tunheim et al.) 2025alb) b). Appendix provides a more detailed account of real-world
application examples.
The TM is proven to almost surely convergence to the Identity/NOT operator with 1-bit input in (Zhag et al. 2022), where the role of the hyperparameter is also revealed. In (Jiao et al. 2023). TM's 's convergence to the XOR operator with 2-bit input was proven, highlighting the func- tionality of the hyperparameter T. In this paper, we first analyze the 2-bit AND and OR operators using noise-free training samples. We then examine the convergence properties of AND, OR, and XOR under noisy conditions, including scenarios with incorrect labels and irrelevant inputs. Finally, we extend these results to the general k-bit case.
This paper differs from previous studies in several key aspects. While (Zhang al. 2022) used stationary distribution analysis of discrete-time Markov chains (DTMC), the current study focuses on absorbing states. For XOR (Jiao al., 2023). where sub-patterns are bit-wise exclusive, TM learns and converges sub-patterns individually. In contrast, the OR operator's sub-patterns share features (e.g., [x] 1, 22 1] and [-] = 1, 22 = OJ share æ = 1), allowing joint representation. We show that TM can effectively learn and represent these shared features, making the convergence process distinct. Additionally, this paper examines the role of Type II feedback, which was omitted in the prior XOR convergence study. Most notably, we analyze the convergence properties of the AND, OR, and XOR operators under noisy training samples, and extend these results to the general k-bit case, thereby making the analysis comprehensive and conclusive.
is worth noting that learning k-bit operators with or without noise, is a well-studied problem. For example, numerous studies in concept learning and probably approximately correct learning have extensively explored this topic [Valiant] 1984 Haussler et al. 1994] Mansour & Parnas 1998 Belaid al., 2025). While many elegant methods exist for learning conjunctions or disjunctions, their existence does not necessarily imply that the TM converges to such operators in the same manner. TM employs a unique approach, learning from samples construct conjunctive expressions and coordinating these expressions across various sub-patterns, which merits its own dedicated analysis.
2 NOTATIONS OF THE TM
To make the article self-contained, we present the TM notation. For more details on the inference and training concept. please refer Appendix A
The input of a TM is indicated as X the number of features. A literal is either 25g the original form or its negation -Ung. A clause is conjunction of literals. Each literal is associated with a TA. The TA is a 2-action learning automaton whose job is decide whether to Include/Exclude its literal in/from the clause, based on the current state of the TA. A clause is associated with 2o TAs, forming a TA team. A TA team is denoted in general as Gj (TA 1 < k' < 20). where k' is the index of the TA, j is the index of the TA team/clause (multiple TA teams form TM), and i is the index of the TM/class to identified (A TM identifies class, multiple TMs identify multiple classes).
FoJ. where I& E k = = =,,
O, and o
Suppose we are investigating the ith TM whose job is to identify class i, and that the TM is composed of m TA teams. Then (x) can be used to denote the output of the jth TA team, which a conjunctive clause:
Training (X
A LEez
a
A LEE;
for C) C *
(1)
for E), E = U.
Testing (x)
NEE]
A 26
NEEJ
u
EJ. E) *
(2)
0.
for E/, E =
In Eqs. and 2 E and E} are defined as the sets of indexes for the literals that have been included in the clause. E) contains the indexes of included original inputs, Zy. whereas Ej contains the indexes of included negated inputs, -EA-
2

---

Published as a conference paper at ICLR 2026
Each clause represents sub-pattem associated with class i by including literal (a feature or its negation) if it contributes to the sub-pattern, or excluding it when deemed irrelevant. Multiple clauses, i.e,, the TA teams, are assembled into complete TM to sum up the outputs of the clauses m
(C)( = Σ (j(X), where Cº (X) is the set of clauses for class i. The output of the TM
f0. for (x))(()) Th further determined by the unit step function: 8/ [1, for fy(C((()) 2 Th'
where Th is a
predefined threshold for classification. This indeed voting scheme.
Note that the TM can assign polarity to each TA team (Granmo 2018), and one can refer to Appendix Afror more information. In this study, for ease of analysis, we consider only positive polarity clauses. Nevertheless, this does not change the nature of TM learning.
Example: We use TM learning the OR logic as an example. A sample is classified into the OR class if its two bits and label follow the OR logic: 01 + 1, 10 1, = 1, or 0 = 0. Note that once the TM learns the pattern outputting 1, it inherently learns the complementary pattern outputting O. Hence the TM's learning and reasoning can be understood primarily identifying the pattern that results in an output of 1. In the OR logic, sub-patterns outputting 1 are 0 1, O, and 1, and can be represented by clauses - A T2, 21 -22, and T1 22, respectively.
A clause is learned by a TA team, and a TM can be composed of multiple TA teams. A TA team is of TAs, each responsible for handling one literal. A literal is input feature, in this example, in or I2; or the negation of it: -ih or -22- In this example, each TA team consists of four TAs, managing four literals: T1, -F F2, -22, respectively.
A TA decides, by its current state (which changes according to the state-transition probabilities as shown in [able[]ann and Table whether to Include or Exclude its literal in/from the final clause. In a TA team of four TAs, if TA, includes 21, TAg excludes -11, TA3 excludes 22, and TA, includes 22, the resulting clause from this TA team will be æ1 A -Z2-
A TM learns the pattern of the OR relationship from the input samples that follow the OR logic (training). As the training result, some TA teams converge clauses like -xy A I2, others to In A -22, or 21 A T2, all outputting 1. The process of determining whether an input conforms to the OR logic involves summing the outputs of all the clauses. Let's assume we have three TA teams, each converging
(-x1 A x2) + (x) A -22) + (x) x2). If test sample {[ 22], 3) = { 1], 1) is put into the TM, the output will be sum = (1 A 1) + (0 A 0) + (0 1) 1 11+0 0 0 1, indicating one TA team votes for positive classification. If the threshold Th is defined as 1. as sum 2 Th, TM evaluates the sample following the OR logic (testing).
one of the sub-patterns, then the sum is sum
T2............. 1..2........ Fol, y²) is fed into the TM, Training: In the training of a TM, the labeled data (X- [0], T2
where the TAs are guided by the feedback defined in Tables T and 2 Type I Feedback is triggered when the training sample has a positive label: y² = 1, while Type y' O. controls the granularity of the clauses. NA means not applicable. Examples demonstrating TA state transitions per feedback tables can be found in Section 3.1 in (Zhang et al. 2002).. In brief,
feedback is utilized when
Type feedback reinforces true positive and Type II feedback fights against false negative.
Value the clause C. (X) Value of the Literal 2 Jt.
P(Reward)
1-1
NA
Include Läteral
PInactiion)
A=1
P(Penalty]
NA
PReward))
0
Exclude Literal
P (Inaction)
P(Penalty]
Table 1: Type I Feedback Feedback upon receiving sample with label y 1, for single TA to decide whether to Include or Exclude a given literal x re/-0% into CJ. NA means not applica- ble (Granmo 2018).
3

---

Published as a conference paper at ICLR 2026
Value of the clause C.
(X)
Value of the Literal zs.
o
P(Reward)
NA
Include Literal
P [[naction]
1.0
NA
1.0
1.0
P(Penalty)
NA
P(Rwwadd)
Exclude Literal
Pllnaction]
1.
0
1.0
1.0
P(Penalty)
Table 2: Type II Feedback - to decide whether to Include or Exclude given literal ws/-Urx into Cj. (Granmo 2018).
Feedback upon receiving sample with label 3/ 0, for single TA
To avoid situations where a majority of the TA teams learn a subset of sub-pattems, forming an incomplete representationf) the hyperparameter T is used to regulate the resource allocation. The strategy works as follows (Granmo 2018):
Generating Type Feedback. If the label of the training sample is y² 1, we generate, in probability, Type Feedback for each clause Cj C² according to:
max( T, min(T, (x(*
Generating Type Feedback. If the label of the training sample X y² = 0, we generate, again, in probability, Type II Feedback each clause Cý C' according
T max(-T', min(T; (x(C((
(4)
27'
Here T is a positive integer, with its maximum value equal the total number of clauses. When multiple sub-patterns exist, T limits the maximum number of clauses that can be allocated to each sub-pattern. Briefly speaking, when the number of clauses representing one sub sub-pattern increases, learning from samples that correspond to that sub- sub-pattern will decrease as the probability of trigger- ing update will decrease. Once at least T clauses have learned a particular sub-pattern, any samples matching that sub-pattern will no longer trigger TM updates (the probability of triggering feedback 0). This prevents additional clause resources from being spent on a sub-pattern that is already considered learned (with T clauses representing it). With appropriate choice of T, the clause resources can be balanced across different sub-patterns, ensuring convergence of the system. In ad- dition, T plays crucial role in maintaining convergence when irrelevant bits present. Further insights and discussions on the role of T' are provided in the proofs.
3 CONVERGENCE ANALYSIS OF THE AND OPERATOR
TM has converged when the states of its TAs do not change any longer. We assume that the training samples are noise free, i.e., P (y 1 [= 1, = = 1, P, (y 0|z 0, = 1) 1, (y = 0/z1 = 1, = 0) = 1, P (y = 0/.²1 = 0, 22 = 0) = We assume that the training samples independently drawn from distribution with full support over the four cases, i.e., each case has strictly positive probability and therefore occurs infinitely often almost surely as time progresses. The same sampling assumption is maintained throughout all subsequent operator analyses.
Because the considered AND operator has only one sub sub- pattern of input, i.c., I1 = 1, 22 = 1, that will trigger true output, employ one clause in this TM, and we thus can ignore the indices of the classes and the clauses in the notation in the proof. After simplification, TA becomes TA2, and C becomes C. Since there are two input parameters, namely Iı and 222, implement four TAs in the clause, i.c., TA2, TAg, TAg, and TA,, TA, has two actions, i.c., including or excluding T1- Similarly, TA2 corresponds to including excluding ma,. TA3 and TA, determine the behavior of 22 and -2, respectively.
Once the TM converge correctly to the intended operation, the resulting clause will be 21 A 22, with the actions of TA, TA2, TAg, and TA4 being I, E, I, and E, respectively. Here we use "T" and "E" as abbreviations for include and exclude respectively.
In the OR example, one should avoid have majority of TA teams converge to A 322 to represent the sub-pattern of [0. 1]. and ignore the other sub-patterns [1, 0) and [1, 1).
4

---

Published as a conference paper at ICLR 2026
Theorem 1. Any clause will converge almost surely to A2y given noise free AND training samples in infinite time when u1 > 0 and U2 > O.
The complete proof of Theorem is in Appendix B We here outline the main steps of the proof.
The condition 0 and W2 guarantees that all types of samples are provided to the TM and no specific type is blocked by Eqs. (3) and 4 during training. The goal of the proof is to show that the system transitions will guarantee that there is unique absorbing state of the TM and the absorbing state has the actions of TA1, TA2, TA3, and TA4 to be I, E, respectively, corresponding to the expression 11 A 22-
To simplify the analysis of joint TA transitions, we use quasi-stationary analysis by freezing the transitions of the TAs for the first input bit and focusing the transitions of the TAs corresponding to the second input bit. Clearly, there are four possibilities when freezing the first bit T1. We name
them as cases: Case 1: TA1
E, TA2 I. i.c. include -1 Case 2: TA₁ I. TA2 E, Case 3: TA, = E, TA2 = E, i... exclude both Iı and I1. Case 4: TA1 = I, TA2 i.e., include both #1 and m-1-
i.c. include
In each of the above four cases, we analyze individually the transition of TA3 (TA,) with given current action, under different actions of TA, (TAa). We index the possibilities as situations: Sit- uation 1. We study the transition of TA3 when its current action is "Include", and when TA4 is frozen to "Include" or "Exclude". Situation 2. We study the transition of TA3 when its current action is "Exclude", and when TA₃ is frozen to be "Include" or "Exclude", Situation 3. We study the transition of TA4 when its current action is "Include", and when TA3 frozen to "Include" or "Exclude". Situation 4. We study the transition of TA4 when its current action is "Exclude", and when TA3 is frozen to be "Include" or "Exclude".
Within each of the situation, there are 8 possible instances, determined by 4 possible combinations of the input samples of 2 and T2, and the two possible frozen TA actions, i.e., Include and Exclude.
As example, randomly select instance in Case 1, Situation 1. The selected instance is when the training sample ([t; = 1, = 1]. y = 1), and TA4 is E. For this instance, the training sample will trigger Type feedback because y 1. Based
the current status of the TAs, the clause is in the form C = - A I2, which evaluates to 0 based on the input training sample. In Situation 1, the studied TA is TAg. whose corresponding literal is 22 Given y clause value 0, literal value 1, we go to Table I the third columm of transition probabilities for "Include Literal", and find the transition of TA3 to be: the penalty probability and the inaction probability e-1 To indicate the transitions of 3, we have plotted the transition diagram in Fig. [
Note that the overall transition
probability u1 ! where un is defined in Eq. (3). Here, we have assumed #1 > 0.
Penally
Rewoad
O
Figure 1: Transition of TAg when its current action is Include, TA,, TA2, and TA4's actions are Exclude, Include, and Exclude, respectively, upon a training sample ([æ) = 1, x2 = 11, y/ = 1).
Similar to the example instance, we derive total of 128 transition instances, which can be further summarized into the overall transition behavior of TA3 and TA,. These overall transitions reveal the directional dynamics of the two TAs, from which we observe that the unique absorbing state for TA₃ and TA, is (I, E), given that TA1 and TA2 fixed in states I and E, respectively.
The transitions of TA₁ and TA2 can be analyzed in the same manner as those of TAş and TA.- Based on this, conclude that the system has unique absorbing state in its full dynamics, with TA,, TA2, TA3. and TA, adopting the actions I, E, and E, respectively, and the TAs ultimately settling in their respective deepest states.
5

---

Published as a conference paper at ICLR 2026
4 CONVERGENCE ANALYSIS OF THE OR OPERATOR
We assume the training samples for the OR operator are noise free (i.e., Eq. (5) and are indepen- dently drawn from a distribution with full support over the four cases.
(y = 1/21 = 1, = 1) - 1, Pg = 1|m 0, = 1) = 1,
($)
tv 1 1, = 0)
0 0. 0)
Theorem 2.
The clauses in a TM can almost surely learn the 2-bit OR logic given noise free training samplex (shown in Eq. (5) in infinite time, when T S [
Theorem B
Lemma
Lemma
Leaunn
Lemns
Lemin
Figure 2: The dependence for the proof of Theorem 2
The proof of the theorem requires Lemma L-Lmma 5 and their dependence is shown in Fig, Clearly, there are three sub-patterns for the OR operator. In Lemma [ we will show that any clause is able converge and absorb sub-pattern is given, and when 4 > O and u22 > 0. In Lemma 2 we will show that the TM will not absorb when more sub-patterns jointly appear in the training samples and when ui > 0 and U2 > O. These two lemmas will be utilized in the proof of Lemma 3 Lemma 2 also reveals the non-absorbing nature of TM for the OR operator when the functionality of T not enabled, i.e., when u1 > 0 and > 0. This confirms the necessity of enabling the functionality of T in order to converge to an absorbing state that fulfills the OR operator, to be indicated by Lemma Lemma Specifically, Lemma [BLLemma5Janaa
intended sub-pattern when the training sample of only one
the system behavior when T is enabled and how T should be configured for the TM to converge to the OR operator. They guarantee that when the system reaches absorbing state, the intended sub-patterns will have number of clauses no less than T while the unintended sub- sub-pattern will have clause. Then the OR operator can be inferred by setting Th T. In what follows, will present and prove the lemmas.
Lemma 1. For any one of the three sub- sub-pattern resulting in y = shown in Eqs. 1 the TM can converge to the intended sub-po sub-pattern when noise free training samples following this sub- pattern, together with samples satisfying P (y- = 0/2 = 0, 22 = 0) 1, are provided, and when
W1 > 0, U2 > O.
Ply 1/m
1, 1) (g = 0/2; 0,,
(6)
P (y
1|
0, 1) P 0/m1 0,
(7)
P
1|21
1,
0) P 0/æ1 0,
(8)
The proof of Lemma involves demonstrating convergence for three sub-patterns: those governed by Eqs. 66. 7 and (8) These analyses build upon the convergence proofs for the XOR and AND operators. For the sub-pattern in Eq. (6). transition diagrams in Appendix B confirm that the TAs converge to TA,
I, TA₂ = E, TA3 = I, and TA, = E, when input samples [x] 0, and [z] = 1, x2 = 0] are excluded. The other two uub-patterns are proven using similar principles. Full details are provided in Appendix([]
From Lemma [ we show that the clauses converge to the intended sub-pattern when the training
samples follow that specific sub-pattern. In contrast, Lemma 2 will show that the system becomes non-absorbing when training samples contain two or more sub-patterns. In particular, we prove that the TM is non-absorbing for samples following Eq. (5) and Eqs. (--11) when #1 0 and u2 0.
[1]
(y = 1| m 1,2g 1) ( 1|m1
1,22 m
(9)
(y 0/z1 0,02
0) =.
( = 1| = 1, =)= 1)= P(v 1/0, = 0,22
(10)
P (y 0/z 0, 0)
P = 1| = 1,2, =0 0) pg 1/ = 0,
(11)
P 0/2 0,
Lemma 2. The TM becomes non non-absorbing if any two or more of the three sub-patterns jointly appear in the training samples, as shown in Eqs.
when un > u2 >

---

Published as a conference paper at ICLR 2026
The proof of Lemma can be found in Appendix D Lemma training samples from all sub-patterns without blocking the learnt patterns by using T via Eqs. (3) and 4 the system is non-absorbing. In other words, if we want to have the TM converge to the OR operator in an absorbing state, it is critical to utilize the feature of 7 to block any incoming need configure T (1) so that the absorbing states exist and (2) confirm that the absorbing states follows the OR operator. In what follows, we will, through Lemmas 3 5 show how T via Eqs. and can guarantee the convergence and how the value of T should be configured.
that if we always give TM the
training samples from updating the learnt sub-patterns. Specifically,
Let's revisit the functionality of T. T can block the training samples from updating a learnt sub- pattern. More specifically, if the number of the clauses reaches T for a certain sub- sub-pattern, the new training samples of this sub-pattern will be blocked by the TM. There are three sub-patterns in OR operator. When the number of clauses for each of the three sub-pattern reaches T, all training samples associated with Type I feedback are blocked. Simultaneously, if none of the samples for Type II feedback trigger any change to the states of the TAs, the TM reaches an absorbing state. In Lemma 3 we detail the necessity and sufficiency of the absorbing state.
Lemma 3. The system is absorbed if and only (1) the number of clauses for each intended sub-
pattern reaches T, i.e., (x)) = T. vX [x] 0, = 1] or [T1 1, 22
1] or
[2] = 1, = 0]. and (2) no clause is formed only by a negated literal or negated literals.
The proof of Lemma 3 can be found in Appendix F In Lemma 3 we find the conditions of the absorbing state. In the next Lemma, we will show how to set up the value of T so that the number of clauses for each intended sub-pattern can indeed reach T.
Lemma 4. T S [m/2] is required so that the number of clauses for each intended sub-pattern can reach T.
Proof of Lemma There are three intended sub- babb-patterss in the OR operator. Given m. clauses in total, to make sure each one has at least T votes, we have 3T S m. This requires T S [m/3] (I' is an integer). However, the nature of the OR operator offers the possibility to represent 2 sub-patterns jointly. For example, T clauses in the form of Φ1 will result in the number of clauses being for each of the following sub-patterns, i.e., [a1 = 1, 0] and [x] = 1, 22 1]. If there are other T clauses representing the remaining sub-pattern, in total 27 clauses can garantee that each of the intended sub-patterns represented by T clauses. We thus have T [m/2]. Note that the fact that two sub-patterns can be jointly represented by one clause has been observed and confirmed in experiments shown in Appendix
When we have a smaller T, different sub-patterns may be represented by distinct clauses. However, when T > [m/2], there will always be one or two sub-pattenn that cannot obtain a number of T clauses to represent them. For this reason, the maximum integer value is T = [m/2].
we show that the input sample [41 0, 22 = 0] will never cause the number of clauses associated with this unintended uub-pattern to reach or exceed T.. This is to avoid any possible false positive upon input [z] 0, x22 = 0) in testing.
In Lemma 5
Lemma 5. When absorbing. the sample from the unintended sub- sub-pattern, i.e., [2] 0, OJ, will never lead to the number of clauses representing this unintended sub-pattern becoming greater than or equal to T.
Proof of Lemma 5 To have a positive output from [x, 0, x2 = 0], the clause should be in the
form of C = 1 or C = I2 or C = - A -zz It has already shown in the proof of Lemma
that Type II feedback will eliminate such clauses. In fact, when the system is absorbed, no clause
will be in the form of C' = -1 C -22 or C = -w -v2. For this reason, [ar = 0, 22 0)
will never lead the number of clauses greater than or equal to
Proof of Theorem 2: Based on Lemmas
we understand that if T S [m/2] holds, Type
I feedback will eventually be blocked and Type II feedback will eventually only give "inaction" feedback. In this situation, no actual transition will be triggered and thus the system reaches the absorbing state. Before absorbed, the system moves back and forth in the intermediate states. Once absorbed, any of the intended sub- sub-patterns will have the number of clauses for that sub-pattern no less than I and the unintended sub- sub-pattern will have clauses. We thus have the OR logic almost surely by setting threshold Th- T and conclude the proof.
7

---

Published as a conference paper at ICLR 2026
Now let's study simple example with m = 2, T = 1. Here, C1 21 and C2 Ia can be an instance for an absorbing case. C1 = I1 and C2 = -2 A 22 also works. Clearly, the clauses can be in various forms, as long as the conditions in Lemma 3 fulfill. These converged clauses are not necessarily in the exact form of the three sub-patterns, which is distinct to that of the XOR operator.
Remark 1. Although both AND and OR operators converge, the approaches are different. For AND operator, the system is converged because the clauses become eventually absorbed to the intended pattern upon Type I and Type II feedback, even if the functionality of T is disabled (u1 > O and U2 > 0). As the TM enables the functionality of T by default, the system will be absorbed when T clauses converge to 21 A 22, before all clauses converge to this patter. However, for the OR operator, the finctionalityy of T is critical because the TM non-absorbing if un and u2 O. The absorbing state of the OR operator is achieved because the functionality of blocks all Type I feedback and Type Il feedback gives only "Inaction" " feedback. The concept of convergence for the OR operator is similar to that of XOR, but the form of clauses after absorbing varies due to the possible joint representation of sub-patterns in OR.
Remark 2. When T is greater than half the number of clauses, i.e., T [m/2], the system will not have an absorbing state. We conjecture that the system can still learn the sub-patterns in an unbalanced manner, as long as T not configured too close to the total number of clauses m.
Given T > Lm/2], Type feedback cannot be completely blocked and the TM is non non-absorbing. Nevertheless, if T is not close to m, there will be clauses that possibly learn distinct sub-patterns. In addition, Type II feedback can avoid the form of C -11 or C' = -2y or == -1 A -22 from happening. Therefore, with Th > 0, the TM may still learn the OR operator with high probability.
5 REVISIT THE XOR OPERATOR
Let revisit the proof of XOR operator. As stated in (Jiao et al. 2023), when the system is absorbed, the clauses follow the format C = Fn A -02 or C' = -1 A 22 precisely. In other words, a clause with just one literal, such C T1, cannot absorb the system. The reason is that the sub-patterns in XOR operator are mutual exclusive, i.e., the sub-patterns cannot be merged in any way. Although Type I feedback can be blocked when 7' clauses represent one sub-pattern using one literal, the Type ll feedback can force the other missing literal to be included. For example, when T clauses happens to converge to C I1, the Type feedback from any input samples of ([z) 1, Z2 = 0). y = 1) will be blocked. In this situation, the Type II feedback from ([zr) 1,32 = 11. = 0) will encourage the clause to include -22 This is because upon a sample ([rr = 1, 22 = 11 y 0). we have Type II feedback, C' = I1 1, and the studied literal is -I2 0. When the TA for excluding -x2 is considered, a large penalty, i.c., a penalty in probability 1, is given to the TA, moving it towards action Include, and thus C' = 21 eventually becomes C = 21 A -22. Following the same concept, we can analyze the development for C = 11, C = T2, and C = M2z which will eventually converge to C = - A x2 C 21 -22 upon Type II feedback.
CONVERGENCE ANALYSIS UNDER RANDOM NOISE
We studied the convergence properties of AND, OR, and XOR operators under training samples with noise. The noise type is noisy completely at random (Frénay & Verleysen] 2013), categorized as wrong labels and irrelevant input variables. A wrong label refers to an input that should be labeled as 1 but is instead labeled as O, vice versa. An irrelevant input variable, on the other hand, is one that does not contribute to the classification. We demonstrate that, with wrong labels, the TM does not converge the intended operators but can still learn efficiently. With irrelevant variables, the TM converges to the intended operators almost surely. Experimental results confirmed these findings (Appendix D). We summarize the main findings in this section. The proof details can be found in Appendix F and Appendix G
Theorem 3. The TM is non-absorbing given training samples with wrong labels for the AND, OR, and XOR operators.
The non-absorbing property of TM indicates that there is a non-zero probability that cannot learn the intended operator. The primary reason for the non-absen absorbbbg behavior when wrong labels are present is the statistically conflicting labely for the same input samples. These
Remark 3.
8

---

Published as a conference paper at ICLR 2026
inconsistency causes the TAs within clause learn conflicting outcomes for the same input. When a clause learns to evaluate an input as based on Type I feedback, samples with a label of 0 for the same input prompt it to learn the opposite. This conftict in labels confuses the TM, leading to back- mack-and-forth learning.
Remark 4. Although wrong labels will make the TM not converge (not absorbing with 100% ac- curacy for the intended logic), via experiments, we can still find that the TM are able learn the operators efficiently, shown in Appendix / This property aligns with the concept of PAC learn- able (Mansour & Parnas (998) or c-optimality (Zhang al. 2020, although formal proof re- mains open.
Theorem 4. The clauses in a TM can almost surely learn the 2-bit AND logic given training samples with q irrelevant input variables in infinite time, q > O, when T S m. Theorem 5. The clauses in a TM can almost surely learn the 2-bit XOR and OR logic given training samples with q irrelevant input variables in infinite time, q > 0, when T < mm/2].
The proofs of Theorems 4 and follow the same underlying methodology (see Appendix G We identify the conditions under which the TM becomes absorbed, and verify that the absorbing states correspond to the intended sub put--attern(ss; and no other absorbing states exist. From these proofs, it becomes clear that T is critical for convergence. The presence of irrelevant bits can make the TM non-absorbing if T is not functioning, whereas an appropriate configuration of T guarantees convergence the correct intended uub-patterns.
Remark 5. An interesting observation is that the TM does not always exclude all irrelevant literals. Our analysis and experiments reveal two distinct mechanisms through which TMs exhibit robustness irrelevant bits. When sufficient clause resources are available, the T clauses assigned to a sub- pattern may include irrelevant bits while another T clauses include their negations, yet both sets vote for the same target sub- uub-pattern, effectively canceling out their influence. When clause resources are limited, irrelevant bits tend to be excluded, and therefore do not affect the classification outcome.
7 CONVERGENCE ANALYSIS FOR k-BIT CASE
The analyses above focus on the 2-bit cases. In this section, extend the results to the general k-bit setting, where & > 2. Since the 2-bit analyses rely heavily on exhaustive search, increasing the number of bits immediately leads to combinatorial explosion. To avoid this, we go from literal level to clause level, by clustering the clause representations into three categories. By analyzing the transition properties among these categories, rather than the literal states, we can demonstrate the convergence behavior without being hindered by the exponential growth. We first present the main theorems, followed by an outline of the proof. The full proofs are provided in Appendix H
We begin with the noise-free case. For the bitit setting, the convergence analysis naturally splits into two subcategories: cases with a single sub- sub-pattern (analogous to the AND operator in the 2-bit case) and cases with multiple sub- aob-patterns (2 or more sub-patterns exist, analogous to OR or XOR in the 2-bit case). Formally, the single-sub-pe sub-patterrm category corresponds to the existence of a unique sub- pattern among the 2 possible input combinations that is labeled as 1, while all others are labeled as or remain undefined (where "undefined" means unlabeled). contrast, the multiple-sub pattern category includes scenarios where more than one sub-pattern is labeled as 1.
Theorem 6. In the k-bit single sub-pattern category, any clause will converge almost surely to the intended sub-pattern given noise free training samples in infinite time when in > 0 and u2 > O.
To prove Theorem 6 instead of examining all possible states of literals, we group the clause forms into three categories and summarize their possible transitions. The clause forms are defined as follows: (1) Exact match: The clause matches the intended sub-pattern exactly. A clause in this form outputs when the intended sub-pattern is presented (e.g., 41 A for the AND operator). (2) Partial match: The clause does not fully match the intended sub-pattern but matches a subset of it. Such clause also outputs for the intended sub-pattern (e.g., xi in the AND case). (3) Non-match: The clause matches neither the intended sub- pattern nor any subset of it. A clause in this category outputs 0 when the intended sub-pattemn is given (e.g., -2, for the AND case). The proof shows that once the TM reaches a clause of type (1), the system becomes absorbed, whereas (2) and (3) do not. This guarantees the existence of unique absorbing clause that represents the intended sub-pattern.

---

Published as a conference paper at ICLR 2026
Theorem 7. The clauses in TM can almost surely learn the k--bt multiple-sub- caub-pateer logic from noise-free training samples in infinite time, provided that T S [m/el, where e is the number of sub-pattern clusters.
In Theorem 7 a sub-pattem cluster is defined as a group of sub-patterns that share one or more common Is in their corresponding input bits. For example, in the OR case, (0, 1) and (1, 1) belong to the same cluster because they share a in ø2. In contrast, (1, 0) and (0, 1) do not belong to the same cluster, they do not share any common 1s. We introduce the notion of sub-pattem clusters because sub-patterns within the same cluster can potentially be represented jointly by a clause that learns their shared feature. The proof of Theorem 7 follows the same structure the proof of Theorem 2 We first show that when multiple sub-patterns are present, the system becomes non- absorbing if i > 0 and u2 > O. Then, by configuring the hyperparameter T appropriately, we can suppress further feedback once the clauses have captured all individual sub-patterns, thereby ensuring convergence.
With irrelevant bits, we have the following conclusions.
Theorem 8. The clauses TM can almost surely learn the k-bit single sub-pattern logic given training samples with q irrelevant input variables in infinite time, k 2 2, q > 0, when T S m.
Theorem 9. Consider training samples of fixed length n, and set of sub-patterns indexed by i, where the i-th sub- sub-pattern contains k; 2 2 informative bits and q; = n - kū > 0 irrelevant bits. A TM can almost surely learn all such subpil-sub--pteerr logic in infinite time when T S [m/e].
The proofs of Band insights of the convergence of the k-bit cases can be found in Appendix K
the same concept as those of Theorems and Experimental
Remark 6. By moving from the restrictive 2-bit setting to a k-bit formulation, the results now cap- ture the actual operating regime of general TM applications. Since practical TM systems universally rely on a preprocessing to transform any input data into booleanized k-bit feature representations, the generalized theory developed here provides the first principled explanation of the mechanism that govern the TM behavior in practical settings. Consequently, the theoretical findings presented here offer a broadly applicable explanation for the convergence properties and performance patterns repeatedly observed across diverse prior empirical studies.
8 INSIGHTS FOR PRACTICAL USAGE
We summarize here the insights from the proofs that are useful for the practical application of the TM. First, the hyperparameter T plays a crucial role. If one can estimate the number of sub- patterns and their clustering structure in classification task, it becomes easier to select a good initial value for T, reducing tuning effort and improving convergence. Second, while joint learning of sub-patterns enables clauses to capture concepts more compactly, it also means that individual sub-patterns may not appear explicitly, which can hinder interpretability since single clause may represent several sub-patterns simultaneously. Third, our robustness analysis shows that clauses can accumulate irrelevant literals when many clauses used, adding further interpretability challenges. For applications where transparency is essential, limiting clause length or the number of clauses may therefore be beneficial. To demonstrate practical relevance, we also include real-world TM applications on publicly available benchmark datasets in Appendix L
CONCLUSIONS
This work establishes a comprehensive theoretical framework for understanding the convergence behavior of the TM. By extending prior results from the 1-bit setting to the 2-bit AND. OR, and XOR operators, and further to the general k-bit case, we demonstrate that the TM reliably con- verges under noise-free training and irrelevant variables. The analysis highlights the critical role of T' in both multi-sub-pattern scenarios and those involving irrelevant bits. The analysis also reveals structural properties unique to certain operators, such the ability of OR clauses to jointly encode multiple sub-patterns. These insights not only clarify the learning dynamics of the TM but also provide practical guidance for model design, lectively, the results reinforce the TM as a theoretically grounded and practically effective approach to interpretable machine learning.
selection, and interpretability. Col-
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENT
This work was partially supported by NORCE Research and by the project Spacetime Vision: To- wards Unsupervised Learning in the 4D World, financed by the EEA and Norway Grants 2014-2021 under Grant No. DEA-RO--O--0188
It was also partially supported by the Research Council of Norway (NFR) through the project CaReLearner Causal Reasoning with Logical Interpretable Learning (Project No. 335700).
The authors would like to thank the two reviewers for their valuable feedback. One reviewer pro- vided critical comments that motivated insightful suggestions that led us to generalize the proof from bits to & bits. Their feedback signif- icantly improved the quality and scope of this paper.
extend the work to noisy cases. The other offered
REFERENCES
K. Darshana Abeyrathna, Bimal Bhattarai, Morten Goodwin, Saeed Gorji, Ole-Christoffer Granmo, Lei Jiao, Rupsa Saha, and Rohan K. Yadav. Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling. In JCML, 2021.
K Darshana Abeyrathna, Ahmed Abdulrahem Othman Abouzeid, Bimal Bhattarai, Charul Giri, Sondre Glimsdal, Che-Christoffer Granmo, Lei Jiao, Rupsa Saha, Jivitesh Sharma, Svein Anders Tunheim, and Xuan Zhang. Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size. In ICCAI, 2023.
Mohamed-Baud Belaid, Jivitesh Sharma, Lei Jiao, Ole-Christoffer Granmo, Per-Are Andersen, and Anis Yazidi. Generalized Convergence Analysis of Tsetlin Automaton Based Algorithms: A Probabilistic Approach Concept Learning. In AAAI, 2025.
Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. Measuring the Novelty of Natural Language Text Using the Conjunctive Clauses of Tsetlin Machine Text Classifier. In ICAART, pp. 410-
417, 2021.
Bimal Bhattarai, Ole-Christoffer Granmo, and Lei Jiao. Explainable Tsetlin Machine Framework for Fake News Detection with Credibility Score Assessment, In LREC, pp. 4894-4903, European Language Resources Association, June 2022.
Bimal Bhattarai, Ole-Christoffer Granmo, Lei Jiao, Rohan Yadav, and Jivitesh Sharma. Tsetlin Ma- chine Embedding: Representing Words Using Logical Expressions. In Findings of the Association for Computational Linguistics: EACL 2024, pages 1512-1522, 2024.
K Darshana Abeyrathna, Ole- CheiShristoffer Granmo, Xuan Zhang, Lei Jiao, and Morten Goodwin. The Regression Tsetlin Machine A Novel Approach to Interpretable Non- Regression. Philosophical Transactions of the Royal Society A, 378(2164), 2020.
Benoit Frénay and Michel Verleysen. Classification in the Presence of Label Noise: a Survey. IEEE transactions on neural networks and learning systems, 25(5):845-869, 2013.
Ole-Christoffer Granmo. The Tsetlin Machine A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic. arXiv:1804.01500 Apr 2018.
Granmo, Sondre Glimsdal, Lei Jiao, Morten Goodwin, Christian W Omlin, and Geir Thore Berge. The Convolutional Tsetlin Machine. arXiv preprint arXiv: 09688, 2019.
Ole-Christoffer
Granmo, Youmna Abdelwahab, Per-Ame Andersen, Paul FA Clarke, Kunal Dum- bre, Ylva Grønninsætter, Vojtech Halenka, Runar Helin, Lei Jiao, Ahmed Khalid, et al. The Tsetlin Machine Goes Deep: Logical Learning and Reasoning with Graphs. arXiv preprint 1rXiv:2507.14874 2025.
Ylva Gronningsæter, Halvor S. Smørvik, and Ole-Christoffer Granmo. An Optimized Toolbox for Advanced Image Processing with Tsetlin Machine Composites. In 2024 International Symposium the Tsetlin Machine (ISTM), pp. 1-8, 2024.
11

---

Published as a conference paper at ICLR 2026
David Haussler. Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1)-functions Ran- domly Drawn Points. Information and Computation, 115(2):248-22)) 292, 1994.
Sindhusha Jeeru, Lei Jiao, Per-Are Andersen, and Ole-Christoffer Granmo. Interpretable Rule- based Architecture for GNSS Jamming Signal Classification. 1EEE Sensors Journal, 25(10): 17942 17959, 2025a.
Sindhusha Jeeru, Rebekka Olsson Omslandseter, Per-Arne Andersen, Aiden James Morrison, Nadezda Sokolova, Olc-Christoffer Granmo, and Lei Jiao. MiXCTME: A Mixture of Convo- lutional Tsetlin Machine Experts Using Diverse Spectrogram Visualizations for Jamming Signal Classification. IEEE Internet of Things Journal, (22):47667 47677, 2025b.
Lei Jiao, Xuan Zhang, Ole-Christoffer Granmo, and Kuruge Darshana Abeyrathna. On the Conver- gence of Tsetlin Machines for the XOR Operator. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):6072-600) 6085, 2023.
C Kishore, Santhosh Sivasubramani, Rishad Shafik, and Amit Acharyya. Nano-Magnetic Logic based Architecture for Edge Inference Using Tsetlin Machine. In 21st IEEE Interregional NEW- CAS Conference (NEWCAS), pp. 1-5, 2023.
Baizhou Lin, Yuetong Fang, Renjing Xu, Rishad Shafik, and Jagmohan Chauhan. TsetlinKWS: A 65mm 16.58 uW, 0.63 mm2 State-driven Convolutional Tsetlin Machine-based Accelerator For Keyword Spotting, arXiv preprint arXiv:2510.24282, 2025.
Sidharth Maheshwari, Tousif Rahman, Rishad Shafik, Alex Yakovlev, Ashur Rafiev, Lei Jiao, and Ole-Christoffer Granmo. REDRESS: Generating Compressed Models for Edge Inference Us- ing Tsetlin Machines. IEEE Transactions on Puttern Analysis and Machine Intelligence, 45(9); 11152 11168, 2023.
Yishay Mansour and Michal Parnas. Learning Conjunctions with Noise under Product Distributions. Information Processing Letters, 68(4):189-196, 1998.
Rebekka Olsson Omslandseter, Lei Jiao, Xuan Zhang, Anis Yazidi, and B John Oommen. The Hierarchical Discrete Pursuit Learning Automaton: A Novel Scheme with Fast Convergence and epsilon-optimaalty. IEEE Transactions Neural Networks and Learning Systems, 35(6):8278 8292, 2024.
Shannon How Shi Qi, Jagmohan Chauhan, Geoff V Merrett, and Jonathon Hare. FedTMOS: Eff- cient One-shot Federated Learning with Tsetlin Machine. In ICLR, 2025.
Ashur Rafiev, Jordan Morris, Fei Xia, Rishad Shafik, Alex Yakovlev, Ole-Christoffer Granmo, and Andrew Brown. Visualization of Machine Learning Dynamics in Tsetlin Machines. In Interna- tional Symposium on the Tsetlin Machine (ISTM), pp. 81-88, 2022.
Tousif Rahman, Adrian Wheeldon, Rishad Shafik, Alex Yakovlev, Jie Lei, Ole-Christoffer Granmo, and Shidhartha Das. Data Boolcanization for Energy Efficient On-Chip Learning Using Logic Driven AI. In International Symposium on the Tsetlin Machine (ISTM), pp. 29-36, 2022.
Raihan Seraj. Jivitesh Sharma, and Ole Christoffer Granmo. Tsetlin Machine for Solving Contextual Bandit Problems. NeurIPS, 2022.
Jivitesh Sharma, Rohan Yadav, Ole-Christoffer Granmo, and Lei Jiao. Drop Clause: Enhancing Performance, Robustness and Pattern Recognition Capabilities of the Tsetlin Machine. In AAAI, 2023.
Michael Lvovitch Tsetlin, On Behaviour of Finite Automata in Random Medium. Avtomat. i Tele- mekh, 13450313455 1961.
Svein Anders Tunheim, Lei Jiao, Rishad Shafik, Alex Yakovlev, and Ole-Christoffer Granmo. Con- volutional Tsetlin Machine- based Training and Inference Accelerator for 2-D Pattern Classifica- tion. Microprocsssors and Microsystems, 103:104949 2023.
12

---

Published as a conference paper at ICLR 2026
Svein Anders Tunheim, Lei Jiao, Rishad Shafik, Alex Yakovlev, and Ole-Chrte Chershhittoffer Granmo. Tsetlin Machine- Based Image Classification FPGA Accelerator with On-Device Training. IEEE Trans. Circuits Syst. I, Reg. Papers, 72(2):830-843, 2025a
Svein Anders Tunheim, Yujin Zheng, Lei Jiao, Rishad Shafik, Alex Yakovlev, and Ole-Christoffer Granmo. An All-digital 8.6-nJ/frame 65-nm Tsetlin Machine Image Classification Accelerator. IEEE Trans. Circuits Syst. I. Reg. Papers, accepted. 2025b.
Leslie Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134 134 1142, 1984.
Rohan Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. Enhancing Interpretable Clauses Semantically Using Pretrained Word Representation. In the 4th BlackboxNLPP Workshop Analyzing and Interpreting Neural Networks for NLP, 2021a.
Rohan Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. Human-Level Interpretable Learning for Aspect-Based Sentiment Analysis. In AAAI, 2021b.
Rohan Yadav, Lei Jiao, Ole-Christoffer Granmo, and Morten Goodwin. Interpretability in Word
Sense Disambiguation Using Tsetlin Machine. In ICAART, pp. 402-409, 2021c
Rohan Kumar Yadav, Lei Jiao, Ole Christoffer Granmo, and Morten Goodwin. Robust Interpretable Text Classification against Spurious Correlations Using AND-rules with Negation. In IJCAI, 2022.
Anis Yazidi, Xuan Zhang, Lei Jiao, and B John Oommen. The Hierarchical Continuous Pursuit Learning Automation: Novel Scheme for Environments with Large Numbers of Actions. IEEE Trans. Neural Netw. Learn. Sys., 31(2):112-526 2019.
Xuan Zhang, Lei Jiao, B John Oommen, and Ole-Christoffer Granmo. A Conclusive Analysis of the Finite-time Behavior of the Discretized Pursuit Learning Automaton. IEEE Transactions on Neural Networks and Learning Systems, 31(1):284-299) 2020.
Xuan Zhang, Lei Jiao, Ole-Chrisee Cle-Christoffer Granmo, and Morten Goodwin. On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):6345-6359, 2022.
13

---

Published as a conference paper at ICLR 2026
A BRIEF OVERVIEW OF THE TM
We present the basics of TM here. Those who already are familiar with the concept and notations of TM can ignore this appendix.
A.1 BASIC CONCEPT OF THE TM
The input to TM is denoted by X [ ......., where 24 E {0, for k: 1,2...... .,,,, and denotes the number of input features. For each input Ih, two literals are defined: the literal Tu and its negation -rk. Consequently, each clause is associated with a total of 2o literals. A clause is defined as a conjunction of subset of these literals, to be explained later.
Each literal is controlled by an associated TA. The TA is a two-action learning automaton that decides whether its corresponding literal should be included in or excluded from the clause. This decision is determined by the current internal state the TA. Figure illustrates illustraaes the structure of TA with 2N states, where N is the number of states for each action. This study considers N as finite number, which practical for real-worle applications. When the TA is in any state between O to N - 1, the action "Include" is selected. The action becomes "Exclude" when the TA is in any state between penalty that the TA receives from the environment, which, in this case, is determined by different types of feedback defined in the TM (to be explained later). A larger N expands the depth of the TA's action-state space, enhancing its robustness. This benefit, however, comes at the cost of longer convergence times to innermost states and greater memory requirements.
to 2N - The transitions among the states are triggered by reward or
A clause is associated with 2o TAs, forming TA team. A TA team is denoted in general gj {TA |1 < k' < 2o). where k' is the index of the TA, j is the index of the TA team/clause (multiple TA teams form TM), and the index of the TM/class to be identified (A TM identifies class, multiple TMs identify multiple classes).
Suppose we are investigating the hth TM whose job is to identify class i, and that the TM composed of m TA teams. Then Cjj(X, (X) can be used to denote the output of the jth TA team, which is conjunctive clause. For training:
(
A NEEJ
A
-ik
for Cj, g / 0,
(12)
KEES
for Sj. 2 0.
For inference:
(X)
A KEEJ
I&
A
A KEEy
for Ej. { 0,
(13)
for 5j. { 0.
In Eqs. 12 and 13
E) and E) are defined as the sets of indexes for the literals that have been included in the clause. E} contains the indexes of included original (non-negated) inputs, dR. whereas ? contains the indexes of included negated inputs, -Wk. e)- E 0 means not a single literal (a feature or its negation) is included in the clause. Note that in propositional logic, an empty clause typically defined having a value of However, empirical results indicate that TMs generally achieve higher test accuracy new data when empty clauses are O-valued. Therefore, during TM
Include
Exclade
Reword :R) Prnnlty (P)
Figure 3: A two-action Tsetlin automaton with 2N states (Jio et al. 2023
14

---

Published as a conference paper at ICLR 2026
Inputs
Literals
TA team
TA decisions
Output
TA
(xx) B(x1)
T
1(~x)) or E(-z1)
32
T
* ((22) or B(zz)
22
-22
TAP
1(-0z) or B(-o2)
C A
[ecission of TA
TA
(xxo) or Exxo)
20-1
No
-20
TA
1(-ur)) or E(-roo
Figure 4: A TA team Gý consisting of 2o TAs (Zhagg et al. 2022). Here [(x1) means "include 21
and E(x1) means "exclude z1".
TA team
C((X)
TA team
Ci(X)
Σ Cx(X)
TA team m
C Cm-1(X)
TA team
C (X)
Figure 5: TM voting architecture (Jiao et al. 2023
training, an "empty" clause outputs to encourage the TAs to include literals, following the feedback mechanisms of the TM. In contrast, during TM inference, an "empty" clause outputs O, indicating that it does not influence the final classification decision since it does not represent any specific sub-pattern.
Figure 4 illustrates the structure of clause and its relationship to its literals. Here, for ease of notation, define [(x) = x, I(-zz) =x, and E(x) = E(-x) in the analysis the training procedure, with the latter meaning that an excluded literal does not contribute to the output.
Multiple clauses, i.c., the TA teams, each of which in conjunctive form, are assembled into a com- plete TM. There are two architectures for clause assembling: Disjunctive Normal Form Architecture and Voting Architecture. this study, we focus on the latter one, as shown Figure The voting consists of summing the outputs of the clauses:
m
= CC())
(14)
j=1
where (=(X) is the set of trained clauses for class i.
15

---

Published as a conference paper at ICLR 2026
The output of the TM, in turn, is decided by the unit step function:
0 for (x)( Th, i for (x(((())) 2 Th,
(15)
where Th is predefined threshold for classification. For example,, the classifier (x) A Ax22 + (-r) A (22) captures the XOR-relation given Th = meaning if any sub-pattern is satisfied, the input will be identified as following the XOR logic.
Note that for the voting architecture, the TM can assign polarity to each TA team (Granmo 2018). Specifically, TA teams with odd indices have positive polarity, learning from training samples with label I, while those with even indices have negative polarity, learning from training samples with label O. The only difference between these polarities is that the output of a clause associated with an even-indexed TA team will be flipped to its negative. The voting consists of summing the polarized clause outputs, and the threshold Th is set to zero. For example, for the XOR operator with four clauses, the learned clauses with positive polarity can be C1 31 A T2 and C3 -01 A 22, while the ones with negative polarity can be C2 I1 A 22 and C4 =i A -2 In this case, when the testing sample [z] = 1, .22 = 0] arrives, the sum of the clause values is 1. On the contrary, when the testing sample [x1 0, 22 0) arrives, the sum of the clause values is -1. In this way, with Th = 0, the system's 's decision range and tolerance is expected to be larger.
In this study, consider only rositive-polarity clauses for two reasons. First, the learning and reasoning process of the T'M can be completely explained from the perspective of learning patterns that output 1, and regative-polarity clauses, which learn patterns that output 0, follow the same procedure. Second, this simplification offers easier analysis and better understanding.
A.2 TRAINING PROCESS OF THE TM
The training process is built on letting all the TAs take part a decentralized game. Training data (X = [x1, T2. ..... Nol ) is obtained from a data set S, distributed according to the probability distribution P(X, 3" )¹) In the game, each TA is guided by Type I Feedback and Type II Feedback defined in Table 3 and Table respectively. Type I Feedback is triggered when the training sample has positive label, i.e., y² 1, meaning that the sample belongs to class i. When the training sample is labeled not belonging class i.e., y O, Type II Feedback is utilized for generating feedback. Examples demonstrating TA state transitions per feedback tables can be found in Section 3.1 in (Zhang al. 2022). In brief, Type feedback is to reinforce true positive and Type II feedback is to fight against false negative.
The hyperparameter s controls the granularity of the clauses and larger encourages more literals to be included in each clause, which also accelerates convergence and improves stability, but at the cost of an increased risk of overfitting in practice. Smaller generally leads shorter clauses and slower convergence in practice. A more detailed analysis on hyperparameters and N can be found in (Zhang et al., 2022).
Value of the clause (X Value of the Literal xal-IR -rk
0
0
P P(Reward)
NA
O
Include Literal
P P(Inaction)
NA
8-1
8-1
P (Penalty)
NA
P Reward)
0
1
Exclude Literal
P (Inaction)
s=1
P(Penalty)
Table 3: Type I Feedback Feedback upon receiving sample with label y = for single TA to decide whether to Include or Exclude a given literal ze/ into Cj. NA means not applica- ble GGrnnmo 2018).
16

---

Published as a conference paper at ICLR 2026
Value of the clause Cj (X)
0
Value of the Literal Ts/ -ak
0
P(Reward)
NA
0
0
Include Literal
P[Inaction
1.0
NA
1.0
1.0
P(Penalty)
NA
0
0
P(Reward)
0
0
Exclude Literal
P P(Inaction)
1.
0
1.0
1.0
P(Penalty)
1.0
0
0
Table Type Feedback Feedback upon receiving a sample with label y = O, for a single TA to decide whether to Include or Exclude given literal /g/-0z into Cj. NA means not applica- ble Granmo 2018).
To avoid the situation that a majority of the TA teams learn only one sub-pattern (or subset of sub-patterns) while ignore other sub-patterns, forming an incomplete representation the hyperpa- rameter T' used regulate the resource allocation. for certain sub-pattern X already reach a total I or more, neither rewards nor penalties are pro- vided the TAs when more training samples of this particular sub-pattern are given. this way, we can ensure that each specific sub-pattern can be captured by limited number, i.e., T, of available clauses, allowing sparse sub-pattern representations among competing sub-patterns. Formally, the strategy works follows:
the votes, i.c., the summation fz (X)),,
Generating Type Feedback. the label of the training sample is y 1, we generate, in probability, Type Feedbuck to each clause C₁ E C.. The probability of generating Type Feedback Granmo 2018):
T max( --T, min(T, (x,())
U1
(16)
2T
Generating Type II Feedback. If the lable of the training sample X is y 0. we generate, again, probability, Type Feedback to each clause Cj E C.. The probability is Granmo 2018):
T + www.n-ax--- ((("
U2
(17)
2T
After Type Feedback or Type II Feedback is generated for a clause, each individual TA within each clause is given neward/penalty/inadee according to the probability defined in the Type and Type II feedback tables, and then the state of the corresponding TA updated.
For example, for the OR operator, one should avoid the situation that majority of TA teams converge to -1 A J2 represent the sub-pattern of [0, 1], and ignore the other sub-pattern [1, 0j and [1, 1). making the learning outcome biased/ubhalanced. proper configuration of T avoid this situation.
17

---

Published as a conference paper at ICLR 2026
B DETAILED PROOF OF THE CONVERGENCE OF THE AND OPERATOR
Proof: In this Appendix, we will prove Theorem 1 The condition u1 > 0 and 12 > 0 guarantees that all types of samples for AND operator, following Eq. (18), are always given and no specific type is blocked during training. The goal of the proof is to show that the system transitions will guarantee the actions of TA1, TA2, TAg, and TA₁ to be E, I, E, and these actions correspond the unique absorbing state of the system.
( = 1[ 1, = 1) =
(18)
P (y 0 0, 1)
(y = 0 1,02 = 0) =
P (ιy 0 0, 22 0)
In Subsections B. we will describe the transitions of the system an exhaustive manner. There- after, in the Subsection B.2 we summarize the transitions Subsection B. and reveal the absorbing state of the system, which is the intended AND operator.
B. THE TRANSITIONS OF THE TAS
In order to analyze the transitions of the system, we freeze the transition the two TAs for the first bit of the imput and study the transition of the second bit of input. Clearly, there are four cases for the first bit, 31, as:
Case 1: TA1 = E, TA2 = i.e., include -11
Case 2: TA1 = I, TA2 E, i.c., include ø1.
Case TA1 E, 'A2 E, i.c. exclude both Tı and -I1.
Case 4: TA, I, TA2 i.e., include both xy and -Z
In what follows, will analyze the transition of the TAs for D2, given the TAs of #1 frozen in the above four distinct cases, one by one.
B.1.1 CASE INCLUDE -
In this subsection, we assume that the TAs for first bit frozen as TA, = and TAg = and thus the overall joint actions of TAs for the first bit give "-æi"". ". In this case, we have 4 situations to study, detailed below:
Situation We study the transition TAg when has "Include" as its current action, given different actions of TA, (i.e., when the action of TA, is frozen "Include" or "Exclude"),
Situation 2: We study the transition of TA3 when it has "Exclude" as its current action, given different actions of TA2 (i.e., when the action of TA, is frozen "Include" or "Exclude").
Situation We study the transition of TA, when it has "Include" as its current action, given different actions of TAg (i.e., when the action of TA3 is frozen "Include" or "Exclude").
Situation 4: We study the transition of TA4 when it has "Exclude" as its current action, given different actions of TA3 (i.e., when the action of TAg is frozen as "Include" or "Exclude").
In what follows, we will go through, exhaustively, the four situations.
B.I.I.I Study TAg with Action Include
Here study the transitions of TA₃ when its current action is Include, given different actions of TA4 and input samples. For ease expressions, the self-loops of the transitions are not depicted in the transition diagram. Clearly, this situation has eight instances, depending the variations of
18

---

0, 0, Published as a conference paper at ICLR 2026
the training samples and the status of TA4, where the first four correspond to the instances with TA, while the remaining four represent the instances with TA, = I.
Now study the first instance, with #1 1, 22 1, y 1, and TA1 E. Clearly, this training sample will trigger Type feedback because = Together with the current status the other TAs, the clause is determined be C -1 x22 0 and the literal is 22 = 1. From Table know that the penalty probability is and the inaction probability is = To indicate the transitions, have plotted the diagram, with the transitions for penalty below. Note that the overall transition probability is /n J. where u1 is defined in Eq. 3 Here, we have assumed # > 0.
Condition: 21 TA4 = E.
x2 1, y =
Thus, Type 22 1,
C' = 1 A 12 = O.
E
Penalty O
Reword
We here continue with analyzing another example shown below. this instance, it covers the training samples: 21 1, 22
O, and TA, E. Clearly, the training sample will trigger Type II feedback because y = 0. The clause output becomes C3 = -2 A 22 = Because we now study TA3, the corresponding literal is x2 Based on the information above, we can check from Table[aand and find the probability of "Inaction" is For this reason, the transition diagram does not have any arrow, indicating that there is "No transition" for TAg.
Condition: 21 TA, = E.
22
0, y
O.
Thus, Type II, 82 = O.
C' = -1h A 12 =0.
Penolty
No transition
Reward
The same analytical principle applies the other instances, and we therefore will not explain them in detail. Instead, we just list the transition diagrams.
Condition: 31 TA4 =F.
0, 22 1, y O.
Thus, Type II, x2 1,
C' 1 A 12 = 1.
Penully
No transition
Reword
O
Condition:
22
TA4 =F.
Thus, Type II, x2 = 0,
C' - A x2 = 0.
Perully
No transition
Reward
O
0
0
19

---

Published as a conference paper at ICLR 2026
Condition:
1, = 1, 1, Thus, Type 1,22 = 1,
TA, =1.
C -21 A D2 A 22 = 0.
21
Penolty
Reward
Condition:
32
0, 0,
TA4 I.
Thus, Type II,
22 0,
C' 1
A
12
A
22 0.
Penolty
0
No transition
Reward
O
O O
Condition:
1, y 0, 21
0, 22
TA I.
Thus, Type
II, F2 = 1,
C -
12
0.
Pernlly
No transition
Reward
Condition:
0, 22 = 0, O,
TA4 I.
Thus, Type II, Σ2 = 0,
C = 1
22
22 0.
5
Penelty
No transition
Reward
B.1.1.2 Study TAg with Action Exclude
Here we study the transitions of TAg when its current action is Exclude, given different actions of TA, and imput samples. This situation has eight instances, depending on the variations of the training samples and the status of TA In this subsection and the following subsections, we will not plot the transition diagrams for "No transition".
Condition: 21 = 1, 22 = 1, 1
=
TA4 E.
Thus, Type
x2 = 1,
C - 0.
Peintiy
Reward
0
20

---

Published as a conference paper at ICLR 2026
Condition:
0, = 0, 0,
TA, E. Thus, Type II, T2 0, C =111
11
1.
Penolty
Reward
Condition:
1, 32
1,
TA4 I. Thus, Type 222 1,
C' 1 A 2 = 0.
Penolty
O
Reward
O
O
'OP O
Condition: 21 0, 22
0, y
0,
TA4 I.
Thus, Type II, x2 = O,
C = m1
7d2 = 1.
to x
Pemully
Reward
B.I.1.3 Study TA4 with Action Include
Here we list the transitions for TA4 when its current action is Include.
Condition: D1 = 1, 32 = 1, = 1, TA₃ E.
Thus, Type -82 = O,
C = -1 -82 0.
5
m
Peinity
Reward
Condition:
I1 = 1, x2 = 1, 1.
TAa I.
Thus, Type I, -82 =0, 0,
C 131
- 0.
Penalty
Reward
B.1.1.4 Study TA4 with Action Exclude
Here list the transitions for TA4 when its current action is Exclude.
21

---

Published as a conference paper at ICLR 2026
Condition: 1, = 1, 1, TA3 E. Thus, Type -02 = 0, 11
C =11 = 0.
Penolty
Reward
Op
"i
Condition: 31 TAg = E.
0, 32
1, 0.
Thus, Type II. -2 = 0, C 1 = 1.
Penully O
Reward
Condition: 21 TAg I.
22
1, y
Thus, Type -22 = 0,
C = 11 12 = 0.
Pemully
Reward
O
Op "1
Condition: T1
0, 22 = 1, = 0.
TAg I.
Thus, Type II, -82 = 0,
C -3h 122 = 1.
5
Peinliy
Reward
1.2 CASE 2: INCLUDE ø1
For Case 2, we assume that the actions of the TAs for the first bit are frozen as TA₃ I and TA2 E, and thus the overall joint action for the first bit is "x1". Similar to Case also have four situations.
B.1.2.1 Study TA3 with Action Include
Condition:
1. x2 1, 1,
TA, = E.
Thus, Type 12 = 1,
C = In A x2=1.
Penalty
Reward
22

---

Published as a conference paper at ICLR 2026
Condition: TA, I.
1, = 1, 1, 22 1
Thus, Type
C = I1 A 22
A 22 = 0.
m1 0
Penolty
Reward
B.1.2.2 Study TA2 with Action Exclude
Condition: 1, 1. 1.
TA4 E.
Thus, Type 22 = 1, I1 1.
Penulty
Reward
Condition:
1, 0, 0,
TA, E. Thus, Type II, 02 0, C xi = 1.
u2
Pennlty
Reward
Condition: I1
32
1, y
TA, I.
Thus, Type x2 1,
C= rı A -2 = 0.
Penolty
O
Reward
O
Op "n
Condition: 31 1, 32 = 0, y 0.
TA4 I.
Thus, Type II, x2 = 0, C = -2 = 1.
1
Penelty
Reward
B.1.2.3 Study TA1 with Action Include
Condition: F1
x2 1, y
TA3 E. Thus, Type -32 = 0, C = A -2 0.
23

---

Published as a conference paper at ICLR 2026
E
Perully
Reward
O
Condition: 21 = 1, 22 = 1, = 1,
TA3 I.
Thus, Type
-2 = 0, C I1 22
22 O.
E
p1
Penully
Reward
O
B.1.2.4 Study TA4 with Action Exclude
Condition: I1 1, 22 = 1, 1,
TA3 E. Thus, Type I, D2 = O, C xi 1.
Prinnity
Reward
OTP "OP
"1
Condition: 31 = 1, 42 = 1, = 1.
TA3 I. Thus, Type I, -2 = 0,
C 31 A 82 1.
Penolty O
0
Reward
O
B.1.3 CASE 3: EXCLUDE BOTH T1 AND
For Case 3, we assume that the actions of TAs for the first bit are frozen as TA = E and TA2 = E, with four situations. Note that in the training process, when all literals excluded, C is assigned to 1.
B.1.3.1 Study TAg with Action Include
Condition:
1, = 1, 1.
TA₃ E.
Thus, Type 22 1. C' x2 L.
Perully
Reward
Condition: TA. I.
1, 1,
Thus, Type 1. 1,
C = 0.
24

---

Published as a conference paper at ICLR 2026
E
Pi
Perully
Reward
O
B.1.3.2 Study TA3 with Action Exclude
Condition: 21 1, 22 1, y TA4 = E.
Thus, Type 22 = 1. C=1.
Penolty
Reward
Condition:
1,
0, 0,
TA2 = E. Thus, Type II, x2 O, C' ==11. 1.
E
Penullt
Reward
Condition:
0, 22 = 0, = 0,
TA4 E. Thus, Type II, 22 = O, C 1
x
Pemuliy
Reward
Condition: F1 1, 32 = 1,
TA, I. Thus, Type C 0.
822 = 1,
Preuniy
Reward
OP "1;
Condition:
22
0, 0,
TA, I.
Thus, Type II, x2 0, C=1
Penalty O
Reward O
25

---

Published as a conference paper at ICLR 2026
Condition:
0, = 0, 0,
TA, =
Thus, Type II, x2 O, C c=1.
E
Penelty
Reward
B.1.3.3 Study TA4 with Action Include
Condition: I1 = 1, 22 = 1, = 1. TA3 E.
Thus, Type - = 0, C = -22 = 0.
E
Penelty
Reward
Condition: 31 = 1, 32 = 1, = 1, TA3
Thus, Type I, 12 = 0,
C - 12 0.
E
Penalty
Reward
O
B.1.3.4 Study TA4 with Action Exclude
Condition: 21 = 1, 22 = 1, = 1, TAg E.
Thus, Type I, -22 = 0, C=1.
Penolty
Reward
Op u1
Condition: F1 0, 22
1, y
TA₃ = E. Thus, Type II, -82 = 0. -=1.
Perully
Reward
Condition:
1. Ø2
1, 1,
TA3 I.
Thus, Type - 0,
C ==
26

---

Published as a conference paper at ICLR 2026
Perullyy O
Reward
O
Condition: 21 = 0, 22 = 1, = 0.
TA3 =I.
Thus, Type II, 02 = 0, ==1.
n2 x OOOTT
Penolty O
Reward
O
B.1.4 CASE 4: INCLUDE BOTH L1 AND
For Case 4, we assume that the actions of TAs for the first bit are frozen as TA, and TA2
and thus C = 0 always. Similarly, we also have four situations, detailed below.
B.1.4.1 Study TAş with Action Include
Condition:
32 1, y
TA4 = E.
Thus, Type 322 = 1, C== 0.
Penolty
Reward O
Condition:
1, 22 = 1, 1,
TA4 I.
Thus, Type 22 1,
C' ==00
E
Pemuily
Reward
B.1.4.2 Study TAg with Action Exclude
Condition: D1 1, x2 1, y
TA E.
Thus, Type Ø2 = 1. C C=0 0.
Perully
Reward O
Opp !n
Condition:
1, D2
1,
TA. =
Thus, Type .2 1,
C = 0.
27

---

Published as a conference paper at ICLR 2026
Perully
O
Reward
C
B.1.4.3 Study TA4 with Action Include
Condition: 21 1, 32 = 1, y
TA3 = E.
Thus, Type -22 = O, C= 0.
Penalty
Reward
Condition:
1, 1,
TAg I. Thus, Type -22 0, C=
E
Penalty
Reward
O
B.1.4.4 Study TA4 with Action Exclude
Condition: 21 = 1, 22 = 1, = 1,
TA3 E.
Thus, Type I, -02 = 0, C =.0. 0.
Penolty
Reward
Op u13
Condition:
22
1, y
TA3 I. Thus, Type -82 = 0, C=0. 0.
Perullty
Reward
So far, have gone through, exhaustively, the transitions of TAg and TA, for all the cases (all pos- sible training samples and system states). Hereafter, we can summarize the direction of transitions and study the convergence properties of the system for the given training samples, to be detailed in the next subsection.
B.2 SUMMARIZE OF THE DIRECTIONS OF TRANSITIONS IN DIFFERENT CASES
Based on the analysis above, we summarize here what happens to TAg and TA4, given different status (Cases) of TA, and TA2, More specifically, we will summarize here the directions of the
28

---

TA3 E or I. Published as a conference paper at ICLR 2026
transitions for the TAs. For example, "TA3 = E" means that TA3 will move towards the action "Exclude", while "TA, = or I" means TA4 transits towards either "Exclude" or "Include".
Scenario 1: Study TA3 I and TA1 =.
Case 1, we have:
Case 3, have:
TA4 TA3 = E.
TA3 + E.
TA4 E.
Case 2. we have:
Case 4, we have:
TA3
TA3 + E.
TA4 = E.
TA4 + E.
From the facts presented above, we can confirm that regardless the state of TA, and TA2, if TAg I and TA4 I, they (TA3 and TA4) will eventually move out of their states.
Scenario 2: Study TA3 and TA₁ = E.
Case 1, we have:
Case 3, we have:
TA3 =
TA3 +
TA4 = E I.
TA4 + E or I.
Case 2, we have:
Case we have:
TA3 = L.
TA3 E.
TA1 =
TA1 + E.
For Scenario 2 Case 2, we can observe that If'; = I, E, TA, = I, and TA2 E, TA, will move deeper to "include" and TA4 will go deeper to "exclude". It not difficult derive also that TA1 will move deeper to "include" and TA2 will transfer deeper to "exclude" in this circumstance. This tells us that the TAs in states TA3 = I, TAA = E, TA, = I, and TA2 = reinforce each other to move deeper to their corresponding directions and they therefore construct an absorbing state of the system. it is the only absorbing state, we can conclude that the TM converge to the intended "AND" operation.
In Scenario 2, we can observe for Cases 1, 3, and 4, the actions for TAg and TA4 are not ab- sorbing because the TAs will not be reinforced move monotonically deeper the states of the corresponding actions for difference cases.
For Scenario 2, Case 3, TA2 has two possible directions to transit, or E, depending the input of the training sample. For action exclude, it will reinforced when training sample x1 = 1 and given, based Type I feedback. However, TA4 will transit towards "include" side when training sample transition for TA, is E, depending on the training samples. In the following paragraphs, when "or" appears in the transition direction, the same concept applies.
32 = 1
and 22 = is given, due to Type II feedback. Therefore, the direction of the
Scenario Study TA3 = and TA,
Case 1, we have:
Case 3, we have:
TA3 or
TA4 = E.
TA4 + E.
Case 2, we have:
Case we have:
TA3 = E or
TAg = E.
TA4 =
TA4 + E.
In Scenario 3, we can see that the actions for TA3 = and TA4 = are not absorbing because the TAs will not be reinforced move deeper to the states of the corresponding actions.
Scenario 4: Study TAg E and TA4 E.
29

---

Published as a conference paper at ICLR 2026
Case 1, we have:
Case 3, have:
TA3 = orrl E.
TA3 +
TA4 = I or E.
TA4 Tor E.
Case 2, we have:
Case 4, we have:
TA3 I.
TA3 E.
TA4 + E.
TA4 + E.
In Scenario 4, we see that, the actions for TA3 E and TA4 E seem to be absorbing state, because the states of TAs will move deeper in Case After a revisit the condition for Case i.c. include both 1 and 21, understand that this condition is not absorbing. In fact, when TA, and TA2 both have "Include" as their actions, they monotonically move towards "Exclude". Therefore, from the overall system's 's perspective, the system state TA, I, TA₃ = I, TA₃ E, and TA2 E not absorbing. For the other cases in this scenario, there is no absorbing state.
Based the above analysis, understand that there is only absorbing condition in the system, namely, TA, = TA₃ = E, TA3 = I, and TA, = E, for the given training samples with AND) logic. The same conclusion applies when freeze the transition of the two TAs for the second bit of the input and study behavior of the first bit of input. Therefore, we can conclude that the TM with clause can learn be the intended AND operator, almost surely, in infinite time horizon. We thus complete the proof of Theorem
30

---

Published as a conference paper at ICLR 2026
C PROOF OF LEMMA
The probability of the training samples for the noise-free OR operator can be presented by the following equations.
P = 1 = 1,42 = 1) = 1,
(19)
[y 1|21 0,
P (y 1 1, = 0) = 1,
( 0 0, J2 0)
Clearly, there are three sub-patterns of z1 and 22 that will give = 1, i.c. [x] = 1, x2 = 1], 1]. More specifically, Eq. (9 can be split into three cases, [x] = 1, 22 0], and [æ] 0, #2 corresponding to the three sub-patterns.
P (v 1/ 1, 1) 1)=1 1,
(20)
P [y 0 02 0) =
P (y 1/21 = 0, = 1) = 1,
(21)
[y 0 0, = 0)
and
P (y 1/21 = 1,32 = 0) = 1,
(22)
P (yy 0 0, 02 0)
In what follows, we will show the convergence of each of the three sub-patterns, i.e., Lemma
The convergence analyses of the above three sub-pattems be derived by reusing the analyses of the sub-patterns of the XOR operator plus the AND operator. For the sub-pattern described by Eq. (20),
confirm that the TAs will indeed converge TA; I, TA2 E, TA3 and TA E, by studying the transition diagrams in Subsection B when input samples of [æ]] = O, r2 = 1] and [x] 1, Z2 0] are removed. In this case, the directions of the transitions for different scenarios are summarized below.
Scenario Study TA3 I and TA4 I.
Case 1, we have:
TA3 + E.
TA, =
Case 2, we have:
TAg =
TA4 = E.
Case 3, we have:
TAg = E.
TA, E.
Case 4, we have:
TAa
TA4 + E.
Scenario Study TAg I and TA4 E.
Case 1, we have:
TA₃ = E.
TA, =
Case 2, we have:
TAg + I.
TA4 E.
31

---

TA3 = E I. Published as a conference paper at ICLR 2026
Case 3. we have:
TA3 = I.
TA4 = E.
Case 4, we have:
TA3 E.
TA4 + E.
Scenario 3: Study TA3 E and TA, = I.
Case 1, we have:
TA3 = E I.
TA4
Case 2, we have:
TA3 =
TA. = E.
Case 3, we have:
TA4 = E.
Case 4, we have:
TA3 = E.
TA4 +
Scenario 4: Study TA3 and TA,- = E.
Case 1, we have:
TA3 = or E.
TA4 = E.
Case 2, we have:
TA3 I.
TA4 =
Case 3, we have:
TA3 = I.
TA4 = E.
Case 4, we have:
TA3 + E.
TA4 =
Comparing the analysis with the one in Subsection B.2 there is apparently another possible ab- sorbing case, which be observed in Scenario 2, Case 3, where TA, and TA, = E, given TA, = and TA2 = E. However, given TAg = I and TA, = E, the TAs for the first bit, i.e., TA1 E and TA2 E, will not move only towards Exclude. Therefore, they do not reinforce each other to move to deeper states for their current actions. For this reason, the system in TAg I, TA4 TA, E, and TA2 E, is not in an absorbing state. In addition, given TAg and TA E, TA1 and TA2 with actions E and will transit towards and E, encouraging the overall system move towards I, I, and E. Consequently, the system state with TA, I, TA2 E, TA3 = I, and TA, = E is still the only absorbing case for the given training samples following
Eq. 20
For Eq. 21 similar to the proof of in Lemma in (Jiao et al. 2023). we can derive that the TAs will converge in TA, E, TA2 II, I, TA3 = I, and TA, E. The transition diagrams for the samples of Eq. 21 are in fact subset of the ones presented in Subsection 3.2.1 and Appendix 2 of (Jiao ct al. 2023). when the input samples of [x] 1 and 22 1] are removed. summarize below only the directions of transitions.
The directions of the transitions of the TAs for the second input bit, i.c., 02/-02, when the TAs for the first input bit are frozen, summarized follows (based on the subset of the transition diagrams in Subsection 3.2.1 of (Jiao et al. 2023
Scenario 1: Study TAg and TA, I
32

---

Published as a conference paper at ICLR 2026
Case 1: have
TA3 + E
TA4 - E
Case 2: we have
TA3 E
TA4 - E
Case 3: we have
TA3 E
TA1 + E
Case 4: have
TÀ3 + E
TA4 E
Scenario 2: Study TA3 = and TA, = E.
Case 1: have
TA3 I
TA4 + E
Case 2: we have
TA3 E
TA4 + E
Case 3: we have
TA3 +1
TA1 +E E
Case 4: have
TA3 + E
TA4 E
Scenario 3: Study TA3 = E and TA4 I.
Case 1: have
TA3 + I, or
TA4 + E
Case 2: we have
TA3 E
TA4 E
Case 3: we have
TA₃ + or
TA4 + E
Case 4: we have
TA3 + E
TA1 E
Scenario 4: Study TAg and TA, = E.
Case 1:
have
TA3 II
TA1 + E
Case 2: we have
TA₃ E
TA4 + E
Case 3: we have
TA2 +I
TA4 + E
Case 4: we have
TAg + E
TA, + E
33

---

Published as a conference paper at ICLR 2026
The directions of the transitions of the TAs for the first input bit, i.e. 21/-11, when the TÀs for the second input bit are frozen, are summarized as follows (based on the subset of the transition diagrams in Appendix 2 of (Jiao et al. (023)).
Scenario Study TA1 = and TA2 =1. I.
Case 1: we have
TA1 E
TA2 + E
Case 2: have
TA1 + E
TA2 E
Case 3: we have
TA1 + E
TA + E
Case 4: we have
TA1 + E
TA2 + E
Scenario 2: Study TA, = and TA2
Case 1: we have
TA1 E
TA2 + E
Case 2: we have
TA1 + E
TA2 E E
Case 3: we have
TA1 +E
TA2 + E
Case 4: we have
TA1 + E
TA2 + E
Scenario 3: Study TA, = and TA2 I.
Case 1: we have
TA1 -+I, I, or
TA2 + E
Case 2: we have
TA1 + E
TA2 I
Case 3: we have
TA1 II
TA2 II
Case 4: we have
TA1 + E
TA2 + E
Scenario 4: Study TA, = E and TA2 E.
Case 1: we have
TA: + I. or
TA2 + E
Case 2: we have
TA1 + E
TA +
34

---

Published as a conference paper at ICLR 2026
Case 3: have
TA1 + E
TA2 + E
Case 4: we have
TAi E
TA2 + E
By analyzing the transitions of TAs for the input bits with samples following Eq. (21 we can conclude that TA1 = E, TA2 = I, TA3 = I, and TA, = E is an absorbing state, as the actions of TA1-TA, reinforce each other to transit to deeper states for the current actions upon various input samples. There are few other cases in different scenarios that seem to be absorbing, but in fact and TA,
not. For example, the status TAg i.e, when TA, E and TA2 E hold. However, to make TA; E and TA2 E absorbing, the condition TA3 = I and TA, I, or TA3 = and TA2 E. Clearly, the status TA3 = and TA, I is not absorbing. For TA3 E and TA; E to be absorbing. is required to have TA1 = I and TA₃ = I to absorbing. or TA, = and TA2 E to absorbing, which are not true. Therefore, all those absorbing- like states not absorbing. In fact, when TA₃ TA4 E, TA1 = E. and TA2 = E hold, the condition TA₃ = I, TA4 = E will reinforce TA1 and TA2 towards E. which the absorbing state of the system. Based the above analysis the transition directions, we can thus confirm the convergence of TM when training samples from Eq. (2 are given.
seems also absorbing Scenario Case 3,
Following the same principle, we can also confirm that the TAs will converge to TA1 = I, TA, = E, TA3 and TA4 when training samples from Eq. (22) are given, according the proof of Lemma 2 in (Jiao et al., 2023).
35

---

Published as a conference paper at ICLR 2026
D PROOF OF LEMMA 2
Proof of Lemma 2 To show the non-absorbing property when samples following Eq. ( are given,
need show that the absorbing states for Eq. (6) disappear when ([r) 1, 0 y 1)
given in addition, and the same applies to Eq. when ([z) 1, = 11 y = 1) is given.
We first show that the absorbing state of TA
TA2 E, TA3 I, TA, E, for sub- sub-pattern
([21 = 1, 22 = 1]. y = 1) as shown in Eq. ( disappears when sub-pattern (2x1 = 1, = 0] =
1) is given in addition. Indeed, TA3 will move toward E when ([x1 1, 0] y 1) given,
because penalty is given to TAg as shown in Fig.
Ponaity
Reward
Figure 6: Transition of TAA3 when its current action is Include, TA1, TA2, and TA4's actions Include, Exclude, and Exclude, respectively, upon a training sample ([æ1 = 1, I2 = 0). 1).
Clearly, when (22 1,02 = 0J.y 1) is given addition, TAg has non-zero probability to move towards "Exclude". Therefore, "Include" is not the only direction that TA3 moves to upon the new input. other words, ([r1 = 1, 22 = 0).2 y = 1) will make the state TA1 = I, TA2 = E, TA3 = I, TA4 E, not absorbing any longer. For other states, the newly added training sample will not remove any transition from the previous case. For this reason, the system will not have any new absorbing state. Therefore, when ([æ) 1, 22 0], y 1) is given in addition, the absorbing state disappears and the system will not have any new absorbing state.
Following the same concept, we show that the absorbing state for (Ix1 1, = 0j.y 1) shown in Eq. (8) i.e., TA, = I, TA2 = E. TA3 = E, TA4 = I, disappears when sub-pattern (I1 1, 11,y is given in addition. Indeed, TA4 will also move towards E when (ạ1 = 1, 1], 1) is given, as shown in Fig.
Ponalty
Reward
Figure 7: Transition of TA4 when its current action is Include, TA1, TA2, and TAg's actions Include, Exclude, and Exclude, respectively, upon a training sample (x) = 1, 22 = 1, y = 1).
Understandably, because of the newly added sub-patterns. the absorbing states in Eqs. and (8) disappear and no new absorbing states are generated. In other words, the TM trained based on samples from Eq. (9) becomes non-absorbing.
Following the same concept, we can show that the system becomes non-absorbin non-abborbing for Eqs. 10 and (TT) well. For the sake of conciseness, we will not provide the details here. In general. any newly added sub-pattern will involve a probability for the leamt sub-pattern to move outside the learnt state, making the system non-absorbing.
36

---

Note that the samples corresponding to the not- not-yet-blocked sub-pattern will encourage the learnt Published as a conference paper at ICLR 2026
E PROOF OF LEMMA 3
Proof of Lemma 3 In Lemma 2 the TM is non-absorbing if the functionality of is disabled (i.e.. when > 0, W2 always hold). Therefore, for the OR operator to converge, the functionality of T critical block any feedback in order form an absorbing state.
By design, TM will either be updated via Type I feedback or Type II feedback. We show via (1) the condition when Type feedback is blocked and then show via (2) when any update from Type II feedback is not triggered. When both happen, the system will not be updated anymore and thus absorbed.
To prove (1) in Lemma 3 we show that the system is not absorbed when 0 or intended sub-pattern blocked by T. When intended sub-patterns are blocked, the system will guide the clauses to learn the remaining intended sub-pattern. Only when all 3 intended sub-patterns are blocked by T, the system will stop updating based on Type I feedback.
Clearly, when no intended sub-pattern is blocked by T", the training samples provided to the system follow Eq. (5) In other words, no samples corresponding to a specific sub-pattern are blocked. Under such training conditions, as shown in Lemma 2 the TM is non-absorbing. When only intended sub-pattern is blocked by T. the system is updated based on samples following Eqs. (9) (TO). or which is also non non-absorbing.
We look at the cases when two intended uub-patterns are blocked by T but the third one is not blocked. In other words, the number of clauses for each of the two intended sub-patterns reaches at least T, and the number of clauses for the remaining sub- uub-pattern is less than T. In this case, only one type of samples from Eqs. (6) or ( or () will be provided to the TM Based Lemma I we understand that all clauses, including the ones that have learnt the two blocked sub-patterns, will be forced learn the not-yet-blocked blocked sub-pau sub-pattern. This is due the fact that only the samples following the -ot-yyetblocked sub-pattern are triggering the update for the TM. In this circumstance, as soon as the not-yet- blocked sub-pattern also has T clauses, i.e., when all three sub-patterns are blocked by T at the same time, Type I feedback are blocked completely.
clauses (i.e., the clauses for the blocked sub-patterns) to move out from the learnt sub-patterms and this may cause the number of clauses for the blocked sub-pattern being lower than (thus unblocked), again. If this happens before the number of clauses for the not-yet-blocked sub-pattern reaches T, at least two uub-pas will be in the non-blocked state, and the system becomes one of the three cases described by Eqs. 9 110 or (IT). In other words, even if absorbing state exists after two intended sub-patterns are blocked by T, the system may not monotonically move towards the absorbing state. Nevertheless, as soon as all three intended sub-patterns are blocked by reaching T clauses, the Type I feedback will be blocked.
Here we prove (2) in Lemma 3 Type II feedback is only triggered by training sample ([x1 O. 22 = 0]. y = 0) in the OR operator. For Type II feedback, based on Table 2 transition is triggered only when penalty occurs, i.e., when the excluded literal has value of 0 and the clause evaluates to 1. Specifically for the OR operation, this only happens when C' = - A -22 or C' = - or C' = -z2. For C 1 -x2. based on the Type II feedback, the TA with the action "excluding ar"" and the TA with the action "excluding 2:2" will be penalized. In other words, the actions of the two TAs for xi and 22 will be encouraged to move from exclude to include side. As soon as one of the TAs (or occasionally both of them) becomes include, the clause will become C' = I A A A-22 or C = -1 A Ø2 A -x2 (or occasionally C = x A -x A 22 A -22). In this case, input [x] = O, r2 = 0] will always result in 0 as the clause value and then the Type II feedback will not update the system any longer. Following the same concept, for C = -22, the Type II feedback will encourage the excluded 21 to be included so that the clause becomes C' 21 A -I2. The same applies to
C = -1 which will eventually become C = -1 A 22 upon Type II feedback. When all clauses in C 22 or C -wn also updated C x u2 C' - A X2, Type II feedback is triggered up any input sample.
We summarize the requirements for an absorbing state:
'More precisely speaking, all samples will be fed into the TM, but only samples corresponding to the not- yet-blocked sub-patter will be used by the TM for training purpose.
37

---

Published as a conference paper at ICLR 2026
For any sample X following sub-pattern [21 1,2g 11. or [11 1,32 0].
[r1 = 0, = 1], the number clauses for that sub-patte sub-pattem, i.c. (X)) must be at least T, matter in which form the clauses are constructed. This will block Type I feedback.
There are no clauses with literal(s) only negated form, such as = -1 or C 222 or C' =1 A 22. This guarantees that transition will happen upon any Type II feedback.
38

---

Published as a conference paper at ICLR 2026
F ANALYSIS OF THE TM WITH WRONG TRAINING LABELS
In this appendix, we analyze the transition properties of the TM when training samples contain wrong labels.
There two types of wrong labels:
Inputs labeled O, which should be 1.
Inputs labeled as 1, which should be O.
We begin by examining the first type of wrong label, followed by the second type, and then address the general case.
F.1 THE AND OPERATOR WITH THE FIRST TYPE OF WRONG LABELS
To formally define training samples with the first type of wrong label, we use the following formulas:
P (y 1 [
1, 1) a, (0, P ( 0 0,
(23)
P ( 0 1,22 = 1) -
1) 1,
P (y 0 [1 = 1,22
0) = =1,
P (y [1 0, 0)
In this case, the label for training samples representing the intended logic [x] = 1, = 1] is y = with probability and y with probability a. In other words, in addition to the training samples detailed in Subsection B new training sample will appear to the system, namely
([z, 1, 1], y 0).
Lemma 6. The TM exhibits non-absorbing for the training samples defined in Eq. 23
To prove this lemma, we analyze the TM's transitions as follows. First, we examine the transitions assuming U1 > 0 and W2 0, similar to the analysis in Subsection B, as detailed in Subsection F.I.I] Next, we study the impact of to determine whether it leads to convergence (absorption), as discussed in Subsection F.1.2)
Proof:
F.1.1 TRANSITION OF TM WITH AND OPERATOR GIVEN #1 > O AND U2 > 0
Following the approach in Subsection B examine the transitions of TA3 and TA4 when the additional training sample ([x1 = 1, 222 1].3 y 0) is introduced, considering Cases to as defined in Subsection B Since y 0 for this sample, only Type II feedback can be triggered to cause transitions. As TA3 is responsible for the literal ø2, which is always for this sample, Type feedback does not trigger any transitions for TA3. Therefore, focus studying the potential transitions of TA4 in the four cases defined in Subsection B.I
In Case where TA, E and TA2 the clause value will always be O for the training sample because - is included in the clause, regardless of the action TA4 takes. According to the Type II feedback transition table, transition occurs when C 0, so no transitions are triggered for TA4, Similarly, in Case 4, where TA, = I and TA, = I, the clause value will always be 0 due to the presence of x1 A -r1 in the clause. As a result, there are no transitions for TA4-
In Case 2, where TA1 = I and TA, E, the literal 21 will always appear in the clause When TA, = the clause includes the literal -22, which results in a clause value of Therefore, no transition is triggered. However, when TA, E, the literal will always appear in the clause, and the value of x2 1, making the clause value regardless of TAgss 's action (whether it includes or excludes 22). According to the Type II feedback table, with the literal value of -r2 being 0 and the clause value being 1, the transition for TA, is:
Condition: I 1, 322 1, 0. Thus, Type II, -2 0,
==1.
39

---

TA4 = I or E. Published as a conference paper at ICLR 2026
x
Perullty
Reward
In Case 3, where TA, = E and TA2 = E, the clause value is fully determined by TA3 and TA When TA4's action is to include, the clause value is 0 for this sample because it includes the literal m22, resulting in no transition for 4A However, when TA4's 's action is to exclude, the clause value always regardless of TA3's action. Specifically, when TA3 includes 22, the clause value is 1, as the literal value of 22 is 1. When it is exclude, all literals are excluded and then the clause value becomes by definition. By examining the transitions of TA4, we can summarize the following graph:
Condition: 1, 1, 0.
Thus, Type II, -2 = 0,
==1
Penolty
Reward
We summarize the directions of the transitions when the wrongly labeled sample is added, with the newly added actions highlighted in red.
Scenario 1: Study TA3 I and TA4
Case 1, we have:
Case
have;
TAg = E.
TAg = E.
TA4 =
TA4 = E.
Case 2, we have:
Case 4, we have:
TA3 =
TAg + E.
TA4 + E.
TA4 E.
Scenario Study TAg = I and TA4 = E.
Case 1, we have:
Case 3, we have:
TA3
TA3 I.
TA2 = E I.
TA4 = E or I.
Case 2, we have:
Case we have:
TAa + I.
TA3 E.
TA4 = or
TA4 + E.
Scenario 3: Study TA2 E and TA4- I.
Case 1, we have:
Case have:
TA3 + oo
TA3 + or I.
TA4 +
TA4 E.
Case 2, we have:
Case 4, we have:
TA3 E or
TAg E.
TA4 = E.
TA = E.
Scenario Study TAg and TA4 E.
Case 1. we have:
Case 3, we have:
TAg = oor E.
TA₃ = I.
TA4 = or
Case 2, we have:
Case have:
TA3 + I.
TA3 + E.
TA4 or
TA4 E.
40

---

Published as a conference paper at ICLR 2026
Clearly, the only absorbing state (IA3 = I and TA, E) becomes non-absorbing due to the newly added transition (the red for TA2). As a result, the system is non-absorbing when us > 0 and U2 >> 0.
F.1.2 TRANSITION OF TM WITH AND OPERATOR WHEN T CAN BLOCK TYPE I FEEDBACK
Based on the above analysis, we understand that the system is non-absorbing when u1 > 0 and
u2 > O. Next, we examine whether it is possible for the system to become absorbing when T can block Type I feedback.
When T clauses have learned the intended pattern x= [2] T, then 21 0 holds, and Type I feedback is blocked. In this situation, only Type II feedback can oceur. Due to the presence of the wrong label, i.e., ([z) feedback triggers transitions in the TAs that have already learned the intended logic ([[2) 1, 32
1, 222 = 11, i.e., when f3 (=(C(
1,32 = 1
0), Type
1. = 1).. For example, Type II feedback will cause a transition in TAs of a Iearned clause C' zι A z2, making the clause deviate from its learned state (c.g., changing from 21 A 22 to I1 A
22). Once this happens, 21 > 0 holds, and Type I feedback is triggered by samples of ([ = 1, 1]. y = 1), encouraging TAs in this clause to move back toward the action Exclude. Thus, even when blocks all Type I feedback samples (setting 41 = 0), the system remains non- absorbing due the wrong label and Type feedback. Notably, value of (z((Ct() (X)) can make both # and d2 simultaneously Therefore, Type and Type II feedhack cannot be blocked simultaneously, ensuring the system is non-absorbing.
F.2 THE AND OPERATOR WITH THE SECOND TYPE OF WRONG LABELS
To properly define the training samples with the second type of wrong label, we employ the follow- ing formulas:
( 1 || = 1,02 = 1) = 1, 0) a, (0,
(24)
P (y 0|
1,22
P 1|x1
1,32
= 0) 1 - a,
P P .1 0, 1) 1,
( 00 0, 0) 1.
In this case, clearly, label of the training samples [xg = 1, x2 = 0] are wrongly labeled as 1 with probability 1 1-a In other words, in addition to the training samples detailed in Subsection B new
type (wrongly labeled) of training sample will appear to the system, namely ([z, = 1, 00. y= 1).
Lemma 7. The TM is non non-absorbing for the training samples given by Eq. 24
Proof: Similar to the proof of Lemma 6 we first consider the transitions of TM with > 0 and U2 > 0, and then examine the impact of T for the system transition.
When #1 > 0 and w2 O, there is non-zero probability in which the training sample ([z) 1,32 = 0). y = 1) will appear to the system. The appearance of this sample will involve transition of TA3 moving from action Include toward Exclude, as shown in Fig. 6 making the system non- absorbing.
When T clauses have learned the intended pattern X = [x] 1, 22 1], i.e. (X) = T, then ū, = 0, and thus Type feedback is blocked for this training sample. In this situation, the TM can only see the training samples of the following:
P ( 0) 1, = 0) = a, E 10
(25)
P ( [1 1,52
0) a,
P (y 0 0, 1) 1,
P (y 0 α 0, 0) 1.
'In this study, we focus only on positive polarity thus U2 > always holds. When negative polarity is enabled (i.e., when a set of clauses learns sub-patterns with label 0), u2 becomes 0 when 7 clauses leam a sample with y = O. However, it remains true that no value of fz (x))) can make both in and ug equal to 0 simultancously.
41

---

Published as a conference paper at ICLR 2026
Following the same concept as the proof of Lemma conclude that the TM is non-absorbing for the samples in Eq. (25). Clearly, the system is non-absorbing. regardless of the value of u1-
Therefore, we conclude that the TM is non-absorbing for the training samples described in Eq. (24).
Following the same principle, can also prove that the TM is non-absorbing when other training samples, i.e., [z] = 0, 22 = 1], and [a] = 0, 22 = 0]. or their combinations, have wrong labels. We thus can conclude that the TM is non-absorbing for the second type of wrong labels.
So far, we have proven that the TM is non-absorbing when only one type of wrong label exists for the AND operator. It is straightforward conclude that the TM remains non-absorbing when both types of wrong labels are present. The key reason is that adding both types of wrong labels does not climinate any transitions between system states non-absorbing systems. Therefore, the TM is non-absorbing for training samples with general wrong labels for the AND operator. Using the same reasoning. we can extend this conclusion the XOR and OR operators. Thus, the following theorem holds.
Theorem 10. The TM is non-absorbing given training samples with wrong labels for the AND, OR, and XOR operators.
The primary reason for the non-absorbing behavior the TM when wrong labels present is the introduction of statistically conflicting labels for the same input samples. These incon- sistency causes the TAs within clause learn conflicting oulcomes for the same input due the corresponding Type and Type II feedback for label I and O respectively. When a clause learns to evaluate an input as I based on Type feedback, samples with a label of 0 for the same input prompt it to learn the input as 0 through Type II feedback. This conftict in labels confuses the TM, leading to back-and-forth learning.
Remark 7.
Remark 8. Note that although wrong labels will make the TM not converge (not absorbing with 100% accuracy for the intended logic), via simulations, we find that the TM can still learn the operators efficiently, which has been demonstrated Section J especially when the probability of wrong label is small. Interestingly, when the probability of the second type of wrong label is large, TM will consider it as a sub- patter, and learn it, which aligns with the nature of learning.
42

---

Published as a conference paper at ICLR 2026
G ANALYSIS OF THE TM WITH AN IRRELEVANT INPUT VARIABLE
In this appendix, we examine the impact of irrelevant input noise on the TM. Irrelevant noise refers to an input bit with random value that does not affect the classification result. For instance, in the AND operator, a third input bit, I3. may appear in the training sample with random I and 0 values, but its value does not influence the output of the AND operator. In other words, the output is entirely determined by the values of Φ and 22. Formally, we have:
P (vV = 1 = 1,02 = 1, 33 = 0 or 1) 1,
(26)
P (y 0/z] 1, 0, 33 0 or 1) 1,
P (v = 0[z] = 0, = 1, 23 = 0 or 1) 1,
P (リ 0|z[ 0, 22 0, T3 = 0 1) 1.
Here I3 = 0 or 1 means P(z3- = 0) = ( = 1) = 1 a, a E (0, 1).
G.1 CONVERGENCE ANALYSIS OF THE AND OPERATOR WITH IRRELEVANT VARIABLE
Theorem 11. The clauses in a TM can almost surely learn the AND logic given training samples in Eq. (26 in infinite time, when T S m.
Proof: The proof of Theorem II consists of two steps: (1) Identifying a set of absorbing conditions and confirming that the T'M, when in these conditions, satisfies the requirements of the AND opera- tor. (2) Demonstrating that any state of the TM that deviates from the conditions defined in step (1) is not absorbing.
The TM will be absorbed when the following conditions fulfill:
1. Condition to block Type I feedback: For any input sample X [x] = 1, 1, regardless of whether F3 = 1 or 0, the TM has at least T clauses that output 1.
2. Conditions to guarantee no action upon Type II feedback:
(a) When 33 or -Ty appears in clause in the TM: The literals that are included in the clause for the first two input variables must result in a clause value of for the input samples X = [z1 = 0, 1, 13]. X = [x] 1, Z² = 0, 233 and X [z]
0, 32- = 0, =a). This ensures that = 0 for these input samples, regardless of the value of æ3. thereby preventing transitions caused by any Type II feedback. The portion of the clause involving the first two input variables can be, c.g., Ø1 A 22 or 21 A 21 A 22, while the overall clauses can be, c.g., C = I1 Axg 13, or C' = z1 A - A x2 -33 as long as the resulted clause value is 0 for those input samples.
(b) When I3 or 7T does NOT appear in a clause in the TM: There is no clause that is in the form of C I1, C I2, C A 22 C -1 22, C = -11 C 22 or
C -=-ua 11 A D2
Clearly, when the above conditions fulfill, the system has absorbed because no feedback appears to the system. Additionally, this absorbing state follows AND operator. Based on the statement of the condition to block Type I feedback, there are least T clauses that output 1 for input sample 1, 13... regardless 2:3 or O. Studying the conditions for Type II feedback, we
X [m1 = 1,
can conclude that the clause outputs 0 for all input samples X = [x] 1, T2 0, 23). X {a1 =
0, = 13), or X [x] = 0, x2 = 0, æ3). We can then setup the Th- T to confirm the AND logic.
The next step is to show that any state of the TM deviating from the above conditions is not absorb- ing. To demonstrate this, we can simply confirm that transitions, which might change the current actions of the TAs, will occur due to updates from Type or Type II feedback.
When literal I3 or literal -z3 is included as a part of the clause, the probability for C' = 0 is non- zero due the randomness of input variable 23. As result, Type I Feedback will encourage the TA for the included literal Fy or -2y to move away from its current action, thus preventing the system from becoming absorbing.
For the case where literal 23 or literal -zg is not included in the clause, the system operates purely based the first two input variables, namely 21 and Ø2. According our previous analysis for
43

---

Published as a conference paper at ICLR 2026
the noise free AND case (Theorem I there is only absorbing status, which is C 21 A 2--- However, this absorbing state disappears because Type I feedback will encourage the excluded literal 23 to be included when 23 1, and similarly encourage the excluded literal -2g to be included when 23 = 0. Once either I3 or mgg is included, the analysis in the previous paragraph applies, and thus the system is not absorbing.
From the above discussion, non-absorbing cases. If Typpe feedback is not blocked, the system cannot reach an absorbing state. Therefore, blocking Type feedback is critical for achieving convergence. The condition T < m to guarantee that T should not be greater than the total number of clauses, making it feasible to block Type I feedback.
clear that Type I feedback is the key driver of action changes in
Remark 9. Due the existence of the irrelevant input x3, the system requires the functionality of to block Type I feedback in order to converge. This contrasts with the noise-free case, where the TM will almost surely converge to the AND operator even when Type feedback is consistently present
(un3 > 0).
G.2 CONVERGENCE ANALYSIS OF THE OR OPERATOR WITH IRRELEVANT VARIABLE
For the OR case, we have
P (y 1/21 1,22 1, or 1) 1,
(27)
P (y = 1[2 = 1,32 = -0,33 = 0 1) = 1,
P (y 1|2 0, -1, 0 1) =1,
P (y = 0|21 = 0, = 0, = =0 1) 1.
Theorem 12. The clauses in a TM can almost surely learn the OR logic given training samples in Eq. (27 in infinite time, when T < mm/2].
Proof: The proof of Theorem 12 follows a similar structure to that of the AND case and involves two steps: (1) Identifying set of absorbing conditions and verifying that, under these conditions, the TM satisfies the requirements of the OR operator. (2) demonstrating that any state of the TM deviating from these conditions is not absorbing.
1. Condition to block Type I feedback: For any input sample X = [a] = 1, = 1, zz]. X = [2]] 1, 22 0, .3). and X [ari 0, 12 1, regardless of whether 2ig 1 or
0, the TM has at least T clauses that output 1.
2. Conditions to guarantee no action upon Type II feedback:
(a) When I3 or -23 appears in a clause in the TM: The literals included in the clause for the first two input variables must ensure a clause value of for the input samples X = [ 0, Z2 0, æz). This is to guarantee that C 0 for those input samples, irrespective of the value of F3, thereby preventing any transitions caused by Type II feedback. The portion of the clause involving the first two input variables can take the form such as X1, 31 A T22 31 A.2,, 21 A -0 A.2 Correspondingly, the overall clauses take the form such C xı A -33, = 31 A -22 A 33, C 31 T2 23, or C' = I1 A -1 A 2 A Wa, as long as the resulted clause value is 0 for those input samples.
(b) When 13 or -a does not appear in a clause in the TM: There are clauses with literal(s) in only negated form, such as C = -1, C' -2 or C' = II A -22-
Clearly, when the above conditions fulfill, the system is absorbing because no feedback triggers state transitions in the system. Additionally, this absorbing state adheres to the OR operator. Based on the condition required to block Type feedback, there are least clauses that output for input sample X [x] 1, 1, 23). X [2] 1, 22 0, x>3] X [x] 0, 1, 2z] regardless of whether Ø3 = 1 or O. Analyzing the conditions for Type II feedback, we find that the clause outputs for all input samples X [x] 22 0, .ry.. We can then setup the Th. T to confirm the OR logic.
The next step is to demonstrate that any state of the TM that deviates from the above conditions outlined above is not absorbing. To do this, we can confirm that transitions which may alter the current actions of the TAs will occur due to updates from Type and Type feedback.
44

---

Published as a conference paper at ICLR 2026
When literal 2y literal m2 is included in the clause, there is due to the randomness of the input variable T3. In this case, Type Feedback will move the included literal 23 m. towards action Exclude, preventing the system from being absorbing.
probability for C' =
For the case where literal F3 or literal -2 is not included as part of the clause, the system operates purely based on the first two input variables, namely I1 and ø2- Based our previous analysis for the noise free OR case shown in Lemma [
the system is non-absorbing. This non-absorbing behavior can also lead the system to a state where the excluded literal, either I3 or -ag, encour- aged to be included. For example, if the TM has a clause C = Ii A T2, upon training sample X [2] 1,32 1, 23 0], the Type feedback will encourage the excluded literal mx to be included. Once one of the excluded literal, Z3 or -2,, is included, the analysis in the previous paragraph applies, meaning the system not absorbing.
Clearly, if Type feedback is not blocked, the system will not be absorbing. As blocking Type I feedback is critical, condition Σ [m/2] necessary, refer Lemma
When T clauses have learned the intended sub- sub-patterns of OR operation, the Type feedback will be blocked. At the same time, Type feedback will eliminate all clauses that output for input sample following X [a1 0, 0, 0, zz3), removing false positives. At this point, the system has converged. The presence of r3 does not change the convergence feature, adds more dynamics to the TM.
G.3 CONVERGENCE ANALYSIS OF THE XOR OPERATOR WITH IRRELEVANT VARIABLE
Theorem 13. The clauses in a TM can almost surely learn the XOR logic given training samples in Eq. (28 in infinite time, when T < 1m/2].
( = 0/2] = 1,22 1, = 0 or 1)
(28)
( 1/21 1, 0, 0 or 1) 1,
( = 1/21 = 0, = -1,33 = 0r 1) 1,
P ( = 0/z = 0, 0, T3 or 1)
The proof for XOR follows the same principles as the AND and OR cases, and therefore, we do not present explicitly here.
G.4 CONVERGENCE ANALYSIS OF THE OPERATORS WITH MULTIPLE IRRELEVANT VARIABLES
In the previous subsections, we demonstrated that if single irrelevant bit is present in the training samples, the system will almost surely converge to the intended operators. This conclusion can be readily extended to scenarios involving multiple irrelevant variables. Here, "multiple irrelevant variables" refers to the presence of additional variables, beyond æz, in the training samples that do not contribute to classification.
Theorem 14. The clauses in TM can almost surely learn the 2-bit AND logic given training samples with q irrelevant input variables in infinite time, q >> O, when T S m.
Theorem 15. The clauses in TM can almost surely learn the 2-bit XOR and OR logic given training samples with q irrelevant input variables in infinite time, q 0, when T |m/2].
Proof: The proofs of Theorems 14 and 15 are straightforward. suffices to verify whether the conditions for blocking Type I and Type IT feedback remain valid when multiple irrelevant variables are present.
The condition for blocking Type I feedback remains valid because Type I feedback is only deter- mined by the first two input bits and not function of the irrelevant variables. For Type II feedback, its effect depends where the literals the irrelevant bits are not included in the clause, the analysis holds, as those literals are absent. When the literals of the irrelevant bits included, their number does not impact the analysis. This is because the clause value entirely determined by the first two bits, and the clause value remains C 0, regardless of the number of irrelevant variables.
whether the literals for the irrelevant inputs are present in the clause. In cases
45

---

Published as a conference paper at ICLR 2026
H CONVERGENCE ANALYSIS OF TM IN k-BIT CASES
H.1 PROOF OF THEOREM 6
Proof: In this setting, the training samples are noise-free, and there exists exactly one intended sub- pub--patern to be learned among the 2* possible combinations. The conditions > 0 and > 0 ensure that has no effect. In particular, training samples are always presented to the TM, and no sample type is suppressed.
To establish Theorem 6 we avoid enumerating all possible states literal level and instead group the clause forms into the following three categories:
(1) Exact match:
The clause matches the intended sub-pattern exactly (c.g., C = I1 A 22 in the 2-bit AND case). Such clause outputs when the intended sub-pattern presented.
(2) Partial match: The clause matches strict subset of the intended sub-pattern (e.g., C in the 2-bit AND case). Such clauses also output 1 when the intended sub-pattern is presented.
(3) Non-match: The clause matches neither the intended sub- patter any of its subsets (e.g., C' = = in the 2-bit AND case). Such clauses output O when the intended sub- pattern is presented.
We show that clauses of type (1) absorbing, whereas clauses of types (2) and (3) non- absorbing. Consequently, the system possesses unique absorbing clause form corresponding to the intended sub-pattern.
Type (1): Exact match is absorbing.
A clause of type (1) is absorbing because once it matches the intended sub sub-pattern, transition can alter its form. Under Type feedback (i.e., when the unique positive sample with y = 1 is and all excluded literals evaluate
presented), the clause outputs All included literals evaluate to 0. The Type feedback table prescribes reward for both included and excluded literals in this situation, meaning that no TA changes its action. Therefore, the clause remains unchanged.
Under Type II feedback (i.e., when samples with y = O are presented), the clause outputs 0, since it matches the positive sub-pattern exactly and thus rejects all negative samples. According the Type II feedback rules, no updates are applied when the clause output is O.
Thus, neither Type I nor Type feedback modify the clause. Type (1) clauses are therefore absorbing.
Type (2): Partial match non-absorbing.
We next show that clauses of type (2) are non-absorbing. Under Type feedback, such clauses output 1. Any literal that should be part of the exact match but is currently the exclude action receives penalty (Type I table, case C = 1, literal value = 1 on the excluded side), encouraging a transition from exclude include. Thus the clause will eventually change its form.
To prove mon-absorbency, it suffices to exhibit a single transition with non-zero probability, Never- theless, we also examine Type feedback for completeness. transition under Type II feedback occurs whenever the clause outputs 1 and an excluded literal has value O. Such literals receive penalty and are encouraged to shift from exclude to include. This situation can arise for partial- match clauses. For example, in the 2-bit AND case, the clause C outputs 1 for the negative sample 21 = 1, Ø2 = 0 (with = 0). The excluded literal corresponding to 22 takes value 0, so Type II feedback encourages it to transition to include. The clause therefore moves toward xι 22-
A special instance this category is the empty clause, where literals are in the exclude action. Such clause outputs 1 for all samples by definition in the training process. Under Type I feedback, all literals belonging to the intended sub-pattern are encouraged to move from exclude to include. Under Type feedback, every literal with value 0 is likewise encouraged transition from exclude to include. Hence the empty clause cannot remain unchanged.
Thus, clauses of type (2) are non-absorbing.
46

---

Published as a conference paper at ICLR 2026
Type (3): Non-match is non-absorbing.
Finally, clauses of type (3) are also non-absorbing. Such clauses output for the intended sub- pattern. Under Type I feedback, when C' = 0, the Type I transition table prescribes penalties for all included literals, encouraging them to move from include to exclude. Hence the clause cannot remain in its current form.
Under Type II feedback, depending on the clause, it is possible for the clause to output 1 for some negative sample. When this occurs, any excluded literal with value 0 receives penalty and is encouraged to shift from exclude to include. For example, in the 2-bit AND case, the clause C = - outputs 1 the sample æ1 22 0 (with y = 0). Type II feedback then penalizes both excluded literals, pushing them toward inclusion. The clause therefore changes form. Thus, clauses of type (3) are non-absorbing.
Although the clause space grows combinatorially, grouping clauses into the three categories above reveals that absorbing/non--bsoone abboorbin behavior is identical within each category, regardless of the specific form of a clause. Since type (1) clauses are absorbing whereas types (2) and (3) are non- absorbing, the TM has a unique absorbing state: the exact match of the intended sub-pattern. Con- sequently, convergence is guaranteed given infinite time.
H.2 PROOF OF THEOREM 7
The proof of Theorem 7 follows the same structure as the proof of Theorem 2 We show that when two or more sub-patterns appear in the training samples, the absorbing clauses that exist in the single-sub-patters setting disappear. In other words, the system no longer possesses any absorbing state as the single sub-pattern case. To restore an absorbing state, the role of the threshold T becomes critical. Analogous to the OR proof, we first show that the system becomes non-absorbing when multiple sub-patterns are present, and then show how to configure T so that convergence guaranteed.
We begin by showing that two or more sub-patten sub-patterns occur in the training samples, the system is non-absorbing. In the k-bit setting, the existence of multiple sub- wub-patterns implies that there is at least one bit whose value differs across sub-patterns. That is, the bit in one sub-pattern but in another. For example, in the 2-bit OR case, between the sub-patterns (1, 0) and (1, 1), 22 is conflicting bit: it is in the former sub-pattern and 1 the latter. We refer to such bits as conflicting bits. Because conflicting bits are present, the absorbing clauses that existed in the single-sub- pattee setting can no longer remain absorbing. The core argument is to show that any clause that was absorbing in the single-sub-patee sub-pattern case ceases to be absorbing once additional sub-patterns, and thus conflicting bits, appear.
Without loss of generality, assume that the third bit is the conflicting bit in the multiple-sub-pane pattern setting. Suppose the clause has reached the absorbing form
(Ir: +, I3 0], y 1).
where i E {1.....k} To show that the system is non non-absorbing we must demonstrate that this clause loses its absorbing property once additional sub-pattern
k} \ (3), and "*" denotes arbitrary assignment to the non-conffictigg bits.
([x; +, I3 = 1),
is introduced.
In the absorbing form, the clause must include the literal -r3 in order to match the sub-patters exactly. However, when training samples corresponding to
([x:
11, 1)
appear, the clause will output ( due to the conflicting bit .33 1. Consequently, Type feedback will reinforce the exclusion of the currently included literals, regardless of their literal value. This process breaks the absorbing condition, meaning the clause is no longer absorbing.
By the same reasoning, the absorbing sub-pattern were
([=: *, 33 1), y 1),
47

---

Published as a conference paper at ICLR 2026
then introducing samples of
([2, = *, 23 = 0j, 1)
would likewise eliminate the absorbing property. Therefore, the specific literal value (0 1) of the conflicting bit the original absorbing state does not matter. Moreover, as additional sub- patterns introduce more conflicting bits, the clauses remain non-absorbing. This clearly indicates that when #1 > and V2 > 0, the clauses are non-absorbing in the presence of multiple sub- patterns. Consequently, the functionality of 'I' must be enabled to ensure that the clauses become absorbing, by preventing Type I feedback from being triggered.
Similar to Lemma we obtain the following result.
Lemma 8. The system is absorbed if and only if (1) the number of clauses for each sub-pattern reaches T, and (2) no clause oulputs for training samples with label O, i.e, no false positives occur.
The proof of Lemma 8 is immediate. Condition (1) blocks all Type I feedback, and the argument follows directly from Lemma Condition (2) ensures that no transitions are triggered by Type feedback. When Type I feedback is blocked and Type II feedback induces no further transitions, the system is absorbing.
To establish Theorem it remains to verify that the condition T S is sufficient to guarantee that all sub-patterns are covered by at least T clauses. Since e denotes the number of sub-patter clusters, that is, the number of clusters in which all sub-patterns share one or more bits in common, we may represent each such cluster with a single clause. Thus, if < m J. then at least T clauses can be assigned to each cluster. Therefore, the convergence requirement in condition (I) is satisfied. We can now prove Theorem
Proof: From the above arguments, we observe that if
T
holds, then Type feedback will eventually be completely blocked, and Type II feedback will even- tually produce only "inaction" responses. In this situation, no further state transitions occur, and the system reaches an absorbing state. Prior to absorption, the system may move back and forth among intermediate states, but it will not become absorbed until the above condition is met.
Once absorbed, every sub- pattepat with label will have at least T clauses assigned it, while the sub-pattern with label 0 will have none. This means that the TM can almost surely learn the intended multiple sub-patterns in infinite time. Once learnt, inference, it can classify the class by setting the threshold Th T. This completes the proof.
H.3 PROOF OF THBOREM AND THEOREM
Proof of Theorem g+ The proof of Theorem 8 consists of two steps: (1) Identifying a set of ab- sorbing conditions and confirming that the TM, when in these conditions, satisfics the require- ments of the intended unique sub-pattern. (2) Demonstrating that any state of the TM that de- viates from the conditions defined in step (1) is not absorbing. Without lose of generality, we consider general
input Boolean vector with k-bit useful bits plus g bit irrelevant bits, as X [ 22, FR, Fh+1: Zz+gg-
The TM will be absorbed when the following conditions satisfied:
Condition to block Type feedback: For any input sample belonging the intended sub- pattern, and for any bits xi E {0, with j E [k: + 1, & g). the TM must have at least T clauses that output 1.
2. Condition to guarantee no transitions under Type II feedback: No clause outputs 1 for training samples with label 0. That is, no false positives occur.
Clearly, when the above conditions are satisfied, the system is absorbed, since no further feedback is produced. Moreover, this absorbing state corresponds to the intended sub- nub-pattern. It is worth noting that the irrelevant bits do not induce any transitions under Type II feedback once clause outputs
48

---

Published as a conference paper at ICLR 2026
for training samples with label 0, i.e., once false positives occur. This is because the absence of false positives implies that all samples labeled O produce a clause output of 0, fully determined by the learned sub sub-patterns from the k useful bits. Since the irrelevant bits do not influence the label, they likewise do not affect the clause output once learning has converged. In other words, regardless of the values of the irrelevant bits, the clause output already determined by the k-bit useful pattern, giving O in this case. Hence, the randomness of the irrelevant bits cannot change the clause output from According the Type feedback table, no transitions occur when C' 0.
The next step is to show that any state of the TM that violates these conditions is not absorbing. To establish this, suffices to confirm that such states will trigger transitions, arising from either Type I or Type II feedback, that modify the current form of the clauses.
We begin with Type feedback. Before this feedback blocked by the threshold T, the random irrelevant bits make the system non-absorbing. The reason is analogous to the conflict-bit argument presented in Subsection HH.2 The conflict bits take the value for some sub-patterns and for others. pushing the system to learn in inconsistent directions. The random irrelevant bits behave in exactly the same manner. Therefore, the mechanism provided by is essential. The condition T < guarantees that T does not exceed the total number of clauses, ensuring that blocking Type I feedback is feasible.
For Type II feedback, any false positive will trigger transitions that move literals with value 0 (and currently excluded) toward the include side until all false positives have been eliminated. As long as false positives remain, Type II feedback continues to update the system, and thus the state is not absorbing.
Based on the above discussion, it follows that any violation of the listed conditions prevents the system from being absorbing. Therefore, only the listed conditions fulfill the absorbing states, which covers the intended sub-pattern.
Proof of Theorem 9) The proof of Theorem follows the same structure and reasoning as the proof of Theorem 8 In particular, we identify two conditions that ensure the system absorbing.
1. Condition to block Type feedback: For any input samples of fixed length n, containing multiple intended sub-patterns where the i-th sub- sub-pattern consists of k; informative bits and
n k; irrelevant bits (with the positions of both bit types arbitrary), the TM must have at
least 7 clauses that output for each intended sub-pattern
2. Condition to prevent transitions under Type II feedback: No clause outputs 1 for train- ing samples with label 0, i.c., no false positives occur.
Different from the condition < m in Theorem 8 here we require T < mm/e]. The arguments showing that these conditions lead to an absorbing state, as well as the arguments establishing that any other clause configuration is non-absorbing, are identical to those presented in the proof of Theorem g We therefore omit the details to avoid repetition.
49

---

Published as a conference paper at ICLR 2026
I EXPERIMENT RESULTS OF 2-BIT CASES WITH NOISE-FREE TRAINING SAMPLES
To validate the theoretical analyses, we here present the experiment results for both the AND and the OR operators.
The number updates The number of clauses
[x x2] = [0,
K
Dx. X2] = [0, 1]
Dx X2] = [1,
Dx X2] = [1, 1]
40-
30
10-
10
12
14
Epochs
Figure 8: The convergence of TM with 7 clauses when = 5 for the AND operator.
Figure shows the convergence of TM for the AND operator when m = 7, T = 5, 8 = 4, and plot the
N 50 (N is the number of states for each action in each TA). More specifically, 1, and the number of system updates function of epochs. From these figures, we can clearly see that after a few epochs, the TM has 5 clauses that learn the AND operator and then the system stops updating because no update is triggered anymore. Note that if we control so that #1 O always holds, all clauses will converge to the AND operator, which has been validated via experiments. These observations Although the theorem says may require infinite time principle, the actual convergence can be much faster.
number of clauses that learn the AND operator, namely, 21
confirm Theorem [
The number of updates The number of clauses
[x xx 0]
5-
X
X
[x x2] = [0, 1]
4-
[X,, X2] [1. 0]
[X1, X2] = [1, 1]
80
60
40
0-
10
12
Epochs
Figure 9: The convergence of a TM with 7 clauses when T = 3 for the OR operator:
6The code for validating the convergence can be found at https: whub.ccm/.aaneei im/ Convergence-of-Tlee inle-ne--ee Machi ne- for-the- www.-chhe-AD--------errraa----
50

---

Published as a conference paper at ICLR 2026
The number COURSS
DG, xyl - [0,
DG, xyl
The number of updattes
26
16
Epochs
Figure 10: The behavior of a TM with clauses when T for the OR operator.
In Fig. we illustrate the number of clauses in distinct sub-patterss when we employ m 3, 4, and N 50 for the OR operator. Based on the analytical result, i.e., Theorem 2 the system will be absorbed, where each sub-pattery will have at least clauses and no update will happen afterwards. From the figure, we can clearly observe that after few epochs, the system becomes indeed absorbed as no updates are observed. When absorbed, the three intended sub- patterns have 3, 4, 5 clauses to represent them respectively, while the unintended sub-pattern has clause, which is consistent with the theorem. Indeed, the list of the converged clauses are: C₁ 21, C2 = 21. C3 = 22, C4 = I1 A 72 Cs = I1 A 22, Cs = I2, and C, = -1 A 22, explaining the number of converged clauses in different sub-pat cub-patterns shown in the figure. Clearly, in this example, some clauses, i.e., C1, C2, C3 and Cr. can each cover multiple sub-patterns. This indicates that in real world applications, if distinct sub-pait hobb-paterns have certain bits common, which can be used to differentiate it from other classes, it is possible for TM to learn those bits as joint features, confirming the efficiency of the TM.
Note that there are many other possible absorbing states that are different from the shown example, which have been observed when run multiple instances of the experiments. As long as each intended sub-pattern is represented by at least 7 clauses in the OR operator, the system converges.
In Fig. 10 the configuration identical that Fig. except that T In this case, as stated in Remark 2 the system will not become absorbing, but will still cover the intended sub-pattern with high probability. From this figure, we can observe that each intended sub-pattern is represented by at least two clauses, and that the unintended sub-pattern has zero clause. At the same time, the TAs do not stop updating their states, which can be seen in the bottom figure. It worth mentioning that we have occasionally observed in other rounds of experiments, that one intended sub-pattern is covered by only 1 clause. In this case, it is still possible to set up Th 2 to have successful classification. Nevertheless, there is no guarantee that each intended sub-pattern will be represented by at least one (or Th) clause(s) in this configuration, thus no guaranteed successful classification.
51

---

Published as a conference paper at ICLR 2026
J EXPERIMENT RESULTS OF 2-BIT CASES WITH NOISY TRAINING SAMPLES
We present the experimental results for the operators under noisy conditions. First, show the results when incorrect labels are present, followed by the results involving irrelevant variables. The final subsection addresses case where both incorrect labels and irrelevant variables are present.
J.1 EXPERIMENT RESULTS FOR WRONG LABELS
To evaluate the performance of the TM when exposed to mislabeled samples, we introduced incor- rectly labeled data into the system. The key observation is that the TM does not converge to the intended logic, meaning it does not absorb into a state where the correct logic consistently repre- sented. However, with carefully chosen hyperparameters, the TM can still learn the intended logic with high probability.
To demonstrate the TM's behavior, we first conduct experiments the AND operator, which satis- fies the following equation:
P = 1|r1 = 1, = 1) = 95%,
(29)
(y 0 1,22 0) 1,
( = 0| = 1, = 0) = 1,
( 0 0, 02 = 0)
In this scenario, 5% of the input samples that should be labeled were incorrectly labeled as 0. To train the TM and evaluate its performance, we used the following hyperparameters: m = 7, 4, Th 2, s = and N 100. The experimental results indicate that the TM does not converge, as the number of updates does not approach zero, which is consistent with our theoretical findings. However, an analysis of the learned clauses shows that in most runs the TM still able to capture the AND operator after training, since at least two clauses conform to the AND pattern, even though the convergence is not achieved.
Here also conduct experiments on the OR operator, which satisfies the following equation:
Pyy 1 1|, 1, 1) 90%,
(30)
( = 1 1mm = 1, = 0) = 90%, P 1| -1,02 0) = 90%,
P = 0/z = 0, x2 = 0) = 1.
In this scenario, 10% of the input samples that should be labeled as were incorrectly labeled as O. To train the TM and evaluate its performance, we used the following hyperparameters:
7, = 4, Th = 2, s 3, and N = 100. Fig. T1 shows the number of updates and the number of clauses that learn distinct sub-patterns,
function of epochs. As shown in Fig. II] the number of updates is big, and thus the system did not converge. Nevertheless, when examining the number of clauses associated with each sub-pattern, we observed that each sub-pattern was covered by least two clauses, ensuring that the OR operator remained valid. Similar results were observed in experiments conducted on the XOR operators.
Interestingly and understandably, when the proportion of mislabeled samples increases to an extreme level, where inputs that should be labeled as 0 are instead labeled 1, the TM begins treat the noise sub- nub-pattemn. For instance, consider the AND operator with input X [2] = 0, 1). which mislabeled as 90% of the cases, as shown in Eq. (3I). Using the hyperparameters 3, 3.0, and N 100, we observed from experiments that the TM generates three clauses with an output of for X = [2] = 0, 1] and another three clauses with an output of 1 for X [aq 1, 1]. This behavior indicates that the TM has incorporated the noise learned sub-pattern. Such outcomes align with the TM's underlying principle of learning, where identifies and models sub-patterns associated with the label 1.
T. 7,
52

---

Published as a conference paper at ICLR 2026
The number of clauses
[0,
[x, X2] [0, 1]
[x x2] (1,
Di, Xz] [1,
1000
The number of updates
5800
5600
4800
200
400
600
800
1000
Epochs
Figure 11: The behavior of TM when m 7,7 for the OR operator with wrong training labels.
P = 1/21 = 1, = 1) 1,
(31)
( 0 1,3g
0) 1,
( = 0 = 0, Ø2 = 1) = 10%
( 0 x2 0)
J.2 EXPERIMENT RESULTS FOR IRRELEVANT VARIABLE
To confirm the convergence property of TM with irrelevant variable, setup the experiments for the AND, OR, and XOR operators when one irrelevant variable, namely, Iz, exists. The probability of 23 being 1 in the training and testing samples is 50%.
For the AND operator, we use the hyperparameters m 5, T = 2, == 3, Th = 2, and 100. Fig. 12 illustrates the convergence of TM for the AND operator in the presence of an irrelevant bit. The results confirm that the TM can correctly learn the AND operator without uncertainty, validating the correctness of Theorem
Interestingly,
upon convergence, the form of the included literals varies. For instance, with the aforementioned hyperparameters,
observe that the converged TM includes clauses of the form 21 A 22 A I3 and another two clauses of the form A A -Z3. This suggests that, instead of excluding the irrelevant bit Ø3, the TM includes at least T clauses containing I3 and at least T clauses containing -I3, which ensures correct classification regardless of the value of Zz. However, when the hyperparameters are set to m 1, single clause exists in the TM, the converged clause takes the form A 22, excluding the literals 33 and -E3.
3, Th and N 100, where only
As T increases (T > m/22,, we observe that convergence becomes challenging. This difficulty arises because the TM cannot simultaneously learn T clauses containing 23 and another T clauses containing 3Z. In such cases, the TM must rely on T clauses in the form D2 to achieve convergence, which can be particularly demanding.
For the OR operator,
the hyperparameters Figure 13 illustratss the convergence of the TM for the OR operator in the presence of an irrelevant bit. The results confirm that TM successfully learns the OR operator without ambiguity, validating the correctness of Theorem [2 The results also confirm that the TM is capable of presenting two sub-patterns jointly.
5, T 2 3, 2, and N 100.
53

---

Published as a conference paper at ICLR 2026
The number of clauses
Dx. 0]
[x,. X2] = [0, 1]
[x, x2] [1. 0]
[x X2]
[1. 1]
The number of updates
30
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
Epochs
Figure 12: Convergence of TM when m 5, T for the AND operator with irrelevant label.
The number of updates The number of clauses
[x,, X21 = [0, 0]
[x x2] [0, 1]
[x x²] = [1. 0]
Di. 1]
0.0
2.5
5.0
7.5
10.0
12.5
15,0
17.5
30
20
12.5
Epochs
Figure 13: Convergence of TM when 5, T for the OR operator with irrelevant label.
Indeed, the OR operator has multiple absorbing states, corresponding multiple clause forms. Some clause forms may include Ø3 or -33, depending on the hyperparameter configuration. Re- gardless of the value of Ø3, as long as the vote sum of the clauses greater than or equal T', the correct classification can be guaranteed.
We have also studied the XOR operator. The convergence instance is shown in Fig. 14 confirming
Theorem [3 Here we use m = T 2, 3, Th = 2.
J.3 EXPERIMENT RESULTS FOR BOTH WRONG LABELS AND IRRELEVANT VARIABLES
In this experiment, we assess the performance of the TM in the presence both mislabeled data and irrelevant variables. Specifically, we evaluate the TM's ability to learn the XOR operator when 40%
54

---

Published as a conference paper at ICLR 2026
The number of clauses
[0,
[x, x2] = [0, 1]
[x, x2] [1.
Dx, Xz] = (1,
The number of updates
250
200
150
100
50
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
Epochs
Figure 14: Convergence of TM when m 7, T = for the XOR operator with irrelevant label.
of the samples are incorrectly labeled, and 10 irrelevant variables added. The input comprises 12 bits, with only the first two bits determining the output based on the XOR logic.
The hyperparameters are configured as follows: polarity enabled. Experimental results reveal that the TM successfully learns the XOR operator in 99% of 200 independent runs. These findings demonstrate the robustness of the TM training in noisy environments.
20. T 15, 3.9, and N 100 with
In another experiment, configured the TM to learn noisy XOR function with 2 useful input bits and 18 irrelevant input bits (hyper parameters: = 128, m = 20, T = 10, s = 3, label noise 0.1). Remarkably, the TM was still able learn the XOR operator with 100% accuracy using just 5000 training samples. If all possible input combinations were required in the training samples, it would require 2 1048576 samples. Clearly, the TM does not rely on the entire combinatorial input space to learn effectively.
When many variables are irrelevant, the training may not cover all possible input combina- tions due to the exponential size of the input space. Although not yet theoretically established, polynomial-sized training sets appear sufficient for the TM, as confirmed by experiments. This is because each TA within a clause updates independently once the clause value and the literal value are determined by sample. The resulting Type and Type II transitions are then fully specified. Con- sequently, the TM does not need to observe every combination of irrelevant inputs. It only requires enough samples to reveal their statistical irrelevance, which triggers the appropriate TA transitions. Furthermore, the influence of irrelevant bits can be neutralized when T clauses capture their negated form and 7 clauses capture their original form for the same sub-pattern. Together, these properties allow the TM to learn effectively without exhaustive coverage of the input space.
55

---

Published as a conference paper at ICLR 2026
K EXPERIMENT RESULTS FOR THE k-BIT CASES
K.1 EXPERIMENT RESULTS FOR NOISE FREE CASE
In this experimen | we tested the TM on 5-bit scenario using both single sub-pattern and multiple sub sub-patterns. For the single sub-pattern case, the pattern (1, 0, 1, 0. 1) was used with parameters m T 5, 8 3. Th 3, and N 100. Here we configure T m deliberately to make Mi 0 always true. For the multiple sub-patterns case, the pattern (1, O, 1, O, 0) was added in addition with m = 5, convergence to the correct intended sub- patt-pattmmsss,, demonstrating its reliable learning capability in the noise-free case.
2, = 3, Th = 2, and 100. In all cases, the TM achieved 100%
K.2 EXPERIMENT RESULTS WITH IRRELEVANT BITS
We first evaluated convergence in the single-sub-patten case, where each sample contains 8 bits and includes one intended sub-pattern (1, O. I, O, x, x, x. x), with x denoting irrelevant bits. The hyperparameters for this experiment were configured as m 3. T 2, s 3, Th 2, and N 100.
For the multiple-sin muutiple-subbpattee sub-pattern case, we first introduced an additional intended sub- sub-pattern, (x, x, x, x, 0, 1, 0, 1), and used the configuration m 5. T = 2, s = 3, Th = 2, and N = 100. Thereafter, in order to test when informative bits are unbalanced in numbers among sub-patterns, we replaced (x, X, X, x. O, 1, O, 1) by (x, X, X, 1,0, 1).
experiments demonstrated 100% convergence the correct intended sub-pattern()), confirming that the TM consistently identifies and converges the desired patterns. These results highlight the robustness of the TM for samples with irrelevant bits.
K.3 EXPERIMENT RESULTS FOR BOTH WRONG LABELS AND IRRELEVANT BITS
To illustrate the performance of the TM in this case, we directly use the Noisy XOR problem and take its results from the literature (Tunheim et al. (023). The Two-dimensional (2D) Noisy XOR dataset consists of 4 4 single-channel Boolean images. Figure shows the patterns for Class (blue) and Class 0 (orange), positioned in the middle of the two upper rows, with x representing random Boolean values. The dataset is balanced, with equal numbers of examples for each class and sub-pattern. Class 1 corresponds to a diagonal line, while Class 0 represents either horizontal or vertical line. Each image contains 4 informative bits and 12 irrelevant bits. To test robustness against label noise, 40% of the training labels are randomly inverted.
Using 2,500 training samples and 8. test samples, the TM implementation achieves a mean test accuracy of 99.99% (Tunheim et al. 2023), demonstrating strong robustness in the presence of noisy labels and irrelevant features.
X
X
X
X
X
X
X
X
X
X
X
X
X
0
X
X
X
X
Figure 15: Patterns representing Class 1 (blue) and Class (Orange) for the 2D Noisy XOR dataset TTnhhem al. 2023).
The code for validating the convergence be found httptttt://// / wtw...com/Jaaeiiii im/ Convergence-of ineo ne- the WANN---O---ppattrrrt
HHere Convolutional TM (CTM) is employed, where the learning principle is identical to the TM used in
this work. The difference that CTM processes 2-D images through patches.
56

---

open bench- Published as a conference paper at ICLR 2026
L APPLICATION EXAMPLES OF TM
Although our manuscript focuses on the theoretical properties of TMs, it is important to note that TMs have already demonstrated strong empirical performance across a broad range of real-world applications. Published results in these areas demonstrate that TMs can serve as competitive, inter- pretable, and resource-effiieet alternatiees neural networks. Below we provide a few examples of real-world experiments from recent literature.
Low-Power and Edge Computing A substantial line of research has explored TM deployments on constrained hardware platforms. The REDRESS framework (Maheshwari et al. 2023) demonstrates that TM- models outperform binarized neural networks across multiple datasets while offering 5 3-5700x speed and energy gains on microcontroller hardware. Dedicated TM accelerators have achieved state-of-the-art energy efficiency, including a 65mm implementation requiring only 8.6mJ MNIST frame (Tunheim et al., 2025b), currently the lowest reported for MNIST inference in digital circuits. TM-based end to end keyword spotting system, TsetlinKWS (Lin et al., 2025), operates at merely 16.58pW while maintaining high accuracy, enabled by compression techniques, convolutional TMM variants, and custom low-power hardware for Google Speech Commands Dataset.
Contextual Decision Making TMM have also been successfully integrated into sequential decision- making settings. By framing the classification task as a contextual multi-armed bandit problem, the TM-Thompson sampling method outperforms other algorithms, including neural network- ap- proaches, on eight of the nine benchmark environments (Iris, Breast Cancer, MNIST, Adult, Cover- type, MovieLens, Statlog, Noisy XOR, and Simulated Article) (Seraj al. 2022).
Federated Learning Recent work has explored TMs in privacy-preserving distributed training. FedTMOS QQ al. 2025) introduces a one-shot federated learning (OFL) framework that replaces conventional knowledge distillation with a TM-based, data-free mechanism. It significantly out- performs its ensemble counterpart by an average of 6.16%, and the leading state-of-the-an art OFL baselines by 7.22% across various OFL settings. In addition, it results in significantly lower com- plexity, reduced storage requirements, and improved computational and communication efficiency, while retaining strong accuracy and scalability.
Image Recognition and Classification TMs have been applied to standard benchmarks such as MNIST (Tunheim et al. 2025b) and CIFAR-10 (Grenningsater et al., 2024), well as domain- specific visual tasks. Recent work demonstrates that TM-based models can match or surpass neural network performance while operating at significantly lower computational cost. For example, Mix- CTME (Teeru et al.] 2025b) achieves robust classification GPS jamming signals in spectrogram data, outperforming conventional deep learning approaches (99.46% vs. 95.72%
mark dataset).
Natural Language Processing. In NLP, TMs offer interpretable alternatives dense neural em- beddings and opaque text classifiers. TM Embeddings (Bhattarai et al., 2024) demonstrate that word semantics can be captured using compact, human-readable logical clauses rather than latent vectors. Other studies highlight the advantages of TM-based reasoning for interpretable and robust text clas- sification Yaadav al., 2022) as well as fake news detection (Bhattarai al., 2022), where TMs match or surpass prior baselines while providing transparent, clause-level explanations for their predictions. Their performance has been consistently validated on widely used open benchmark datasets.
57


Reviews:
[{"review_id": "88ZMkv4AhU", "reviewer": "Reviewer_aVVF", "summary": "This paper studies the convergence behavior of Tsetlin Machines (TM) on basic Boolean operators. It proves almost-sure convergence for AND and OR under noise-free data, clarifies how the resource parameter T is necessary for OR (due to recurrent dynamics without it), and revisits XOR to contrast why clauses must include both literals there. The paper then analyzes learning under two noise models, mislabeled samples (non-convergence / recurrence) and irrelevant input variables (preserving almost-sure convergence with suitable T). Experiments on synthetic setups illustrate the theorems and qualitative behaviors.", "questions": "1.\tCan you provide high-level bounds (even loose) on expected time to absorption under noise-free AND/OR as a function of m,T,s,N and input distribution?\n\n2.\tWhich steps in the proofs rely critically on the 2-bit structure? Do you foresee analogous absorbing-state conditions for k-bit conjunctions/disjunctions and for multi-clause compositions? Any obstacles beyond combinatorial explosion?\n\n3.\tCan you add guidance on the qualitative effect of s (granularity) and N (TA states per action) on convergence speed/stability?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper has good theoretical novelty: Clear separation of behaviors for AND vs. OR vs. XOR, including why OR needs 𝑇 to exit recurrence, and why XOR forces inclusion of both literals (Type II feedback pressure).\n\n2.\tIt has rigorous clause/TA-state analyses leading to a unique absorbing state for AND and a family of absorbing conditions for OR. The use of absorbing-state arguments vs. stationary distributions is a neat angle.", "weaknesses": "1.\tThe theory focuses on 1–2-bit settings. While justified as foundational, readers may want a clear roadmap for extending these techniques to higher-arity clauses and multi-bit operators beyond AND/OR/XOR, or to real datasets with structured features. (Some remarks suggest feasibility, but formal generalizations are not provided.)\n\n2.\tConvergence is asymptotic (“infinite time”). Finite-time/sample complexity bounds or rates (even coarse) would materially strengthen the results and their practical import. The empirical section shows good convergence in practice, but theory doesn’t quantify this.\n\n3.\tExperiments are primarily synthetic and ablation-style. Comparisons to classical concept learning or bandit baselines learning conjunctions/disjunctions (more related work) would better support the empirical importance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GAUqs8Qd51", "reviewer": "Reviewer_PyEi", "summary": "This work provides detailed proofs on the convergence properties of Tsetlin Machines (TMs). Given that existing literature only discussed TMs convergence in 1-bit settings for the Identity/NOT operator and in 2-bit settings for the XOR operator only, it extends the current theoretical understanding of TMs by providing (1) a noise-free (almost surely) convergence proof for the AND operator in a 2-bit setting, (2) a noise-free (almost surely) convergence proof for the OR operator in a 2-bit setting, (3) (almost surely) convergence/recurrence analysis of AND, OR, XOR operators in a 2-bit setting with noisy data (under two random noise types: mislabeled samples and irrelevant input variables).", "questions": "Q1: The definition of the hyper-parameter \"T\" does not seem to be well presented. It was not clear to the reader what type of values it takes (it was briefly mentioned in one of the proofs that T is an integer, but no formal definition for T is found in the notation section) and what is its range. It would be nice if the authors can present the definition of T better in revisions as it is heavily used in the proofs.\n\nQ2: as discussed in W1, can the authors explains a bit more on how this work influence the practical usage of TMs? Any insights that we can draw from these analysis to be applied to real world scenarios?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: strong motivation is given for improving the theoretical ground of TMs properties, with a clear identification of the gap (what was already shown in the literature, and what was missing).\n\nS2: self-contained notation for setting up the TM functionalities, consistent notations used throughout proofs.\n\nS3: a complete proof provided for (1), and high level proof sketches provided for (2,3) where complex reasoning involves (proof details are presented in the appendix). Figure 2 helps the reader understand the proof structure.\n\nS4: key findings on the OR operator where it is shown to be able to learn joint sub-patterns, which is novel.\n\nS5: the convergence analysis on TM's behaviour with noisy data is particularly valuable as real-world data is more than often quite noisy.", "weaknesses": "W1: limited scope - this work explores the 2-bit settings, however, it is missing the discussion of how this work may contribute to analysis of TMs behaviours at a larger scale (in the real deployment of TMs, it is often at a much larger scale). Or more generally, missing discussion on how the theoretical improvements relates to practical usage of TMs.\n\nW2: Section 6 seems to be weaker than section 3&4, partially due to the defer of (almost all) proof details to the appendix and only leaving the statements in the main text. The key rationales behind these findings could be partially included to enhance the strengths of these statements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sLpGe4oeBk", "reviewer": "Reviewer_ThEH", "summary": "A theoretical study of the probabilistic training convergence of Tsetlin Machines for basic logical operators with and without noise.", "questions": "How about some experimental results on substantive real data sets? \nHow can you convince the audience that Tsetlin machines may be practical alternatives to deep neural networks?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Paper is reasonably clear although the presentation could be improved in parts. For example, a figure would shorten and clarify the setup in Section 2.   It would help to explicitly state that Tables 1 and 2 are transition probabilities to bring along readers who are not already familiar with the material.", "weaknesses": "The paper, plus 30 pages of appendix, is a detailed treatise on the convergence of Tsetlin machines for basic logical operators.  It is impossible to estimate the validity of the theorems without a deep study of the lengthy appendix.\n\nWhile the results are of theoretical interest,  we cannot arrive at any conclusions on practical significance without experiments on real-world data sets.   In the absence of such experiments, the paper might be better suited for a refereed journal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)