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

Ankit Kumar; Utkarsh Raj; Rishad Shafik; Sudip Roy

cs.LGSep 5, 2026

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

Authors: Ankit Kumar, Utkarsh Raj, Rishad Shafik, Sudip Roy

Organizations: Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, India · Microsystems Research Group, Newcastle University, Newcastle upon Tyne, UK

Abstract

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 \pm 6.74\%$ and $62.94 \pm 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\times$ and $3.71\times$ . 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.

Figures & tables

Fig. 1: Compressed RTM data flow. Clause activations are folded, retained through fast and slow exponential moving averages, and thresholded before returning at the next step. Five independently seeded members vote on the output.

Fig. 2: Boolean-FSM generator. Circuit seeds fix the hidden transition rule; dataset seeds sample initial states and observed input sequences. The label is the parity of the updated hidden state.

Family	Circuit seed	Nominal states	Distinct next	Mean out-degree	Mean bit flips	Majority baseline	Full RTM
6-bit	42	64	48	9.12	2.75	50.45%	61.38%
6-bit	43	64	48	4.50	3.25	61.74%	69.29%
6-bit	44	64	64	6.00	3.00	50.30%	53.74%
8-bit	42	256	108	6.31	4.12	55.17%	76.12%
8-bit	43	256	164	11.81	4.12	53.56%	55.42%
8-bit	44	256	192	9.69	4.00	51.51%	57.29%

TABLE I: Circuit structure, test baseline, and full-RTM accuracy (three training seeds).

Study	Factorization	Runs
RTM variants	2 families $\times$ 3 circuits $\times$ 3 seeds $\times$ 8 variants	144
Neural baselines	2 families $\times$ 3 circuits $\times$ 3 seeds $\times$ 5 models	90
State probes	first member of all RTM variant runs	144

TABLE II: Evaluation matrix.

Fig. 3: Mean test accuracy over nine matched circuit/training-seed runs. Error bars show sample SD across those runs, combining circuit and training variation; they are not confidence intervals.

Fig. 4: Paired accuracy change from the full model over nine runs; bars show 95% $t$ intervals.

Family	Seed	Majority	MLP	RNN	GRU	LSTM	Transformer	Compressed RTM
6-bit	42	50.45	60.37	63.95	65.60	64.42	56.79	61.38
6-bit	43	61.74	73.58	71.43	77.36	76.93	61.49	69.29
6-bit	44	50.30	53.11	55.26	56.52	54.86	52.38	53.74
8-bit	42	55.17	83.68	85.91	88.32	87.81	63.51	76.12
8-bit	43	53.56	55.37	55.21	54.83	54.91	54.71	55.42
8-bit	44	51.51	60.32	63.43	65.39	65.35	54.11	57.29

TABLE III: Per-circuit test accuracy (%): mean over three training seeds. The neural and RTM columns use identical generated arrays (’Transformer’ denotes the attention-based baseline).

Variant	6-bit accuracy	8-bit accuracy
Full compressed	61.47 $\pm$ 6.74%	62.94 $\pm$ 9.92%
No clause feedback	61.91 $\pm$ 6.49%	63.83 $\pm$ 9.89%
Single member	59.70 $\pm$ 6.63%	60.65 $\pm$ 8.79%
32-bit fold	61.47 $\pm$ 6.51%	63.31 $\pm$ 9.96%
No thermometer	61.25 $\pm$ 6.79%	62.26 $\pm$ 9.46%
Single timescale	62.18 $\pm$ 6.26%	63.78 $\pm$ 10.00%

TABLE IV: Ablations: mean accuracy

\pm

SD over nine runs.

Measure	6-bit	8-bit
Compressed accuracy	61.47%	62.94%
Uncompressed accuracy	62.19%	63.52%
Paired $\Delta$ (95% CI)	$+0.72$ [ $-0.22,1.65$ ]	$+0.58$ [ $-0.48,1.63$ ]
Feedback-state bits	$96\to 960$	$96\to 960$
Total input dimension	$182\to 1046$	$182\to 1046$
Mean run time (min)	$16.6\to 72.7$	$19.7\to 73.2$

TABLE V: Compressed versus raw feedback;

\Delta

is raw minus compressed accuracy.

Family	Feedback	Top-1	U-Top-1	Top-5	U-Top-5
6-bit	Compressed	1.08 $\pm$ 0.85%	1.92%	6.35 $\pm$ 3.81%	9.62%
6-bit	Uncompressed	15.40 $\pm$ 9.71%	1.92%	38.30 $\pm$ 18.66%	9.62%
8-bit	Compressed	0.086 $\pm$ 0.057%	0.73%	0.51 $\pm$ 0.17%	3.63%
8-bit	Uncompressed	8.01 $\pm$ 7.34%	0.73%	25.86 $\pm$ 16.63%	3.63%

TABLE VI: Probe accuracy (mean

\pm

SD) and matched uniform references (mean), nine runs.

Sequence Modeling

Sequence modeling studies how to represent, predict, classify, and generate ordered data such as text, time series, events, and biological sequences.

See all 253 papers

Dynamic Compression in Recurrent Networks
Aug 18, 2026Jyothish Pari, Ryan Bahlous-Boldi, Pulkit AgrawalRecurrent Neural Networks Model Compression
Improbable AI Lab, Massachusetts Institute of Technology
Steering Recurrent Reasoners at Inference Time with Readout Feedback
Aug 25, 2026Shunsuke Kamiya, Masanori Koyama, Seongcheol Jeong +5Inference-Time Guidance Recurrent Neural Networks
Graduate School of Engineering, The University of Tokyo
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
Jul 7, 2026Nikola Zubić, Qian Li, Yuyi Wang +1Recurrent Neural Networks Neural Network Expressivity
Robotics and Perception Group, University of Zurich · Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data · Tengen Intelligence Institute, CRRC Zhuzhou Institute

Aug 18, 2026J/K move · Enter open · S save

Dynamic Compression in Recurrent Networks

Jyothish Pari, Ryan Bahlous-Boldi, Pulkit Agrawal

Improbable AI Lab, Massachusetts Institute of Technology

Recurrent Neural Networks Model Compression

Open paper AskPDF arXiv

Recurrent models process long contexts efficiently by compressing their history into a fixed-size state, but modern architectures typically do so in a single causal pass over the sequence. Each input must therefore be compressed before the model knows how it will later be used, forcing a limited state to compromise across possible future demands. We introduce dynamic compression, which allows a recurrent model to selectively revisit past tokens and revise its fixed-size state through additional recurrent updates. The model need not preserve every part of the history at uniformly high fidelity in its recurrent state, because lower-fidelity information can be revisited from the retained raw sequence when it becomes relevant. We study this in a controlled setting where the model first learns multiple functions in-context and, later in the same sequence, encounters a series of few-shot tasks that each require it to identify and reuse one of those functions. A single-pass model must preserve every function at sufficient fidelity for any future task, whereas selective re-scanning allows the model to revisit and refine only the function currently needed. We find that dynamic compression substantially reduces the recurrent state required for accurate reuse and scales more favorably as the number of stored functions grows. These results demonstrate a computation--memory tradeoff in which recurrent models can spend more computation revisiting their history to make more effective use of a fixed-size state.

Abstract

Sequence Modeling

Explore similar work

Dynamic Compression in Recurrent Networks

Steering Recurrent Reasoners at Inference Time with Readout Feedback

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?