# Compressed Recurrent Feedback in Tsetlin Machines: A Reproducible Boolean-FSM Study

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 5 Sep 2026.

## Builds on (most cited first, 12 of 12)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Designing and Interpreting Probes with Control Tasks](https://mlsanity.com/paper/1909.03368/) (2019)
- [Efficient Processing of Deep Neural Networks: A Tutorial and Survey](https://mlsanity.com/paper/1703.09039/) (2017)
- [The Tsetlin Machine -- A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic](https://mlsanity.com/paper/1804.01508/) (2018)
- [The Convolutional Tsetlin Machine](https://mlsanity.com/paper/1905.09688/) (2019)
- [On the Convergence of Tsetlin Machines for the IDENTITY- and NOT Operators](https://mlsanity.com/paper/2007.14268/) (2020)
- [Massively Parallel and Asynchronous Tsetlin Machine Architecture Supporting Almost Constant-Time Scaling](https://mlsanity.com/paper/2009.04861/) (2020)
- [A Tsetlin Machine with Multigranular Clauses](https://mlsanity.com/paper/1909.07310/) (2019)
- [The Weighted Tsetlin Machine: Compressed Representations with Weighted Clauses](https://mlsanity.com/paper/1911.12607/) (2019)
- [MATADOR: Automated System-on-Chip Tsetlin Machine Design Generation for Edge Applications](https://mlsanity.com/paper/2403.10538/) (2024)
- [Low-Energy Reduced RISC-V Instruction Subset Processor for Tsetlin Machine Inference at the Edge](https://mlsanity.com/paper/2606.19964/) (2026)

## Abstract (arXiv)

Sequential inference on small devices requires a model to retain useful history without repeatedly processing a long input record. A Recurrent Tsetlin Machine (RTM) provides this memory by returning Boolean clause outputs from one time step as inputs to the next. Direct feedback, however, grows with the clause bank and can make the recurrent input unnecessarily wide. This paper investigates a fixed-width alternative. We combine clause activations by exclusive-OR (XOR) folding, retain the folded bits at two time scales, and threshold them back to a binary state. The resulting design reduces 480 clause activations to 96 recurrent bits. We evaluate the method on a reproducible Boolean finite-state-machine benchmark with explicit transition rules, data splits, and random seeds. Across 144 runs, the compressed model obtains 61.47 ± 6.74% and 62.94 ± 9.92% accuracy on the two task families. Raw clause feedback changes these means by less than one percentage point, while increasing the recurrent width tenfold and measured host execution time by 4.38× and 3.71×. Gated neural models remain more accurate, and a no-feedback control retaining only short input history achieves comparable or slightly higher accuracy. On this benchmark, folding matches raw feedback within small empirical margins at a much narrower interface; these findings also underscore the critical necessity of no-feedback recurrence controls when benchmarking sequence models.