# Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling

arXiv: https://arxiv.org/abs/2009.04861 · HTML: https://mlsanity.com/paper/2009.04861/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2020.

## Built on by (most cited first, 20 of 20)

- [Explainable Tsetlin Machine framework for fake news detection with credibility score assessment](https://mlsanity.com/paper/2105.09114/) (2021)
- [Coalesced Multi-Output Tsetlin Machines with Clause Sharing](https://mlsanity.com/paper/2108.07594/) (2021)
- [Building Concise Logical Patterns by Constraining Tsetlin Machine Clause Size](https://mlsanity.com/paper/2301.08190/) (2023)
- [Word-level Human Interpretable Scoring Mechanism for Novel Text Detection Using Tsetlin Machines](https://mlsanity.com/paper/2105.04708/) (2021)
- [Tsetlin Machine for Solving Contextual Bandit Problems](https://mlsanity.com/paper/2202.01914/) (2022)
- [Exploring Effects of Hyperdimensional Vectors for Tsetlin Machines](https://mlsanity.com/paper/2406.02648/) (2024)
- [Adversarial Attacks on AI-Generated Text Detection Models: A Token Probability-Based Approach Using Embeddings](https://mlsanity.com/paper/2501.18998/) (2025)
- [On the Convergence of Tsetlin Machines for the AND and the OR Operators](https://mlsanity.com/paper/2109.09488/) (2021)
- [Interpretable Tsetlin Machine-based Premature Ventricular Contraction Identification](https://mlsanity.com/paper/2301.10181/) (2023)
- [A Comparison Between Tsetlin Machines and Deep Neural Networks in the Context of Recommendation Systems](https://mlsanity.com/paper/2212.10136/) (2022)
- [The Probabilistic Tsetlin Machine: A Novel Approach to Uncertainty Quantification](https://mlsanity.com/paper/2410.17851/) (2024)
- [Scalable Multi-phase Word Embedding Using Conjunctive Propositional Clauses](https://mlsanity.com/paper/2501.19018/) (2025)
- [Logic-based AI for Interpretable Board Game Winner Prediction with Tsetlin Machine](https://mlsanity.com/paper/2203.04378/) (2022)
- [Contracting Tsetlin Machine with Absorbing Automata](https://mlsanity.com/paper/2310.11481/) (2023)
- [Omni TM-AE: A Scalable and Interpretable Embedding Model Using the Full Tsetlin Machine State Space](https://mlsanity.com/paper/2505.16386/) (2025)
- [Uncertainty Quantification in the Tsetlin Machine](https://mlsanity.com/paper/2507.04175/) (2025)
- [Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic Approach to Concept Learning](https://mlsanity.com/paper/2310.02005/) (2023)
- [A Methodology for Transparent Logic-Based Classification Using a Multi-Task Convolutional Tsetlin Machine](https://mlsanity.com/paper/2510.01906/) (2025)
- [FastOmniTMAE: Parallel Clause Learning for Scalable and Hardware-Efficient Tsetlin Embeddings](https://mlsanity.com/paper/2605.06982/) (2026)
- [Compressed Recurrent Feedback in Tsetlin Machines: A Reproducible Boolean-FSM Study](https://mlsanity.com/paper/2609.06133/) (2026)

## Abstract (arXiv)

Using logical clauses to represent patterns, Tsetlin Machines (TMs) have recently obtained competitive performance in terms of accuracy, memory footprint, energy, and learning speed on several benchmarks. Each TM clause votes for or against a particular class, with classification resolved using a majority vote. While the evaluation of clauses is fast, being based on binary operators, the voting makes it necessary to synchronize the clause evaluation, impeding parallelization. In this paper, we propose a novel scheme for desynchronizing the evaluation of clauses, eliminating the voting bottleneck. In brief, every clause runs in its own thread for massive native parallelism. For each training example, we keep track of the class votes obtained from the clauses in local voting tallies. The local voting tallies allow us to detach the processing of each clause from the rest of the clauses, supporting decentralized learning. This means that the TM most of the time will operate on outdated voting tallies. We evaluated the proposed parallelization across diverse learning tasks and it turns out that our decentralized TM learning algorithm copes well with working on outdated data, resulting in no significant loss in learning accuracy. Furthermore, we show that the proposed approach provides up to 50 times faster learning. Finally, learning time is almost constant for reasonable clause amounts (employing from 20 to 7,000 clauses on a Tesla V100 GPU). For sufficiently large clause numbers, computation time increases approximately proportionally. Our parallel and asynchronous architecture thus allows processing of massive datasets and operating with more clauses for higher accuracy.