PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ankit Kumar, Utkarsh Raj, Rishad Shafik, Sudip Roy

arXiv:2609.06133v1cs.LG

TL;DR

RTM clause feedback provides temporal context but widens the next-step input as clause banks grow. This study folds clause outputs into a fixed-width, two-timescale binary state and tests it on Boolean FSMs; folding changes raw-feedback accuracy by less than one percentage point while using one-tenth the recurrent width.

  • Problem

    RTM clause feedback carries temporal context, but larger clause banks widen the recurrent state and the next TM input.

    Source: §I · p. 1

  • Method

    The paper replaces raw clause feedback with XOR-folded bits tracked at fast and slow timescales, then thresholds them into binary state for evaluation on Boolean FSMs.

    Source: §I · p. 1

  • Results

    Folding changes raw-feedback accuracy by less than one percentage point while reducing recurrent state from 960 to 96 bits; the no-feedback control is slightly more accurate.

    Source: §I · p. 1, §VII · p. 6

  • Takeaways & Limitations

    On these deterministic FSM tasks, clause-derived context is not strictly necessary, while XOR folding offers a narrower interface when recurrence is required.

    Source: §VII · p. 6

    The conclusions are bounded by the evaluated tasks; noisy real-world temporal sequences and direct accelerator energy and latency measurements remain future work.

    Source: §IX · p. 7, §X · p. 8

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses the scaling of recurrent Tsetlin Machines by compressing clause feedback into a fixed-width binary interface. It pairs that design with a reproducible Boolean-FSM benchmark and controls that distinguish clause recurrence from input history and ensemble effects.

I. INTRODUCTION

  • RTMs carry current clause activity forward as Boolean context, unlike conventional Tsetlin Machines that process samples independently.The introduction contrasts this with neural sequence models that carry real-valued hidden states and may incur costly dense arithmetic on small devices.Source: §I · p. 1
  • Clause feedback supplies temporal memory but widens the next-step input as the clause bank grows, motivating a fixed-width summary.The summary XOR-folds clause outputs, applies fast and slow moving averages, then thresholds the result back to a binary state.Source: §I · p. 1
  • The benchmark uses FSMs with hidden transition rules and specifies its generator, outputs, input distribution, sequence lengths, splits, and seeds.Multiple circuit and training seeds address variation because state count alone does not determine task difficulty.Source: §I · p. 1
  • The proposed interface XOR-folds 480 clause activations into 48 bits and retains them at two timescales.The paper also contributes a Boolean-FSM benchmark artifact and a matched evaluation including neural baselines, component ablations, raw feedback, no-feedback controls, and probes.Source: §I · p. 1
  • Across the six circuits, folding changes raw-feedback accuracy by less than one percentage point, while the no-feedback control is slightly more accurate.The authors interpret this as compressed feedback reproducing raw-feedback performance without wide recurrent buses, while short input histories provide substantial temporal context.Source: §I · pp. 1–2

II. RELATED WORK

Related work situates the study among logic-based Tsetlin learning, edge implementations, and neural sequence models. It distinguishes compression of the recurrent interface from compression of the learned model and motivates controls that isolate the value of recurrence.

A. Tsetlin Learning and Model Variants

  • Prior Tsetlin work develops readable propositional rules and variants for images, regression, weighting, multigranularity, robustness, parallelism, and convergence, but not time-varying clause feedback.The section frames the paper's focus as what happens when clause activity becomes an RTM input over time.Source: A. Tsetlin Learning and Model Variants · p. 2

B. Edge Realization and Temporal Context

  • Edge systems reduce or accelerate fixed trained models, whereas RTMs incur a dynamic cost because clause outputs change each step and return as temporal context.The paper reduces that dynamic interface; it does not propose a new accelerator or claim to shrink the stored TM.Source: B. Edge Realization and Temporal Context · p. 2
  • Recurrent-interface compression shrinks the data returned between decisions, while static TM compression reduces the learned model; the clause bank can remain unchanged.The study makes no claim about parameter compression.Source: B. Edge Realization and Temporal Context · p. 2
  • The evaluation pairs raw feedback with a no-feedback control that retains the same two-symbol history and previous prediction, separating recurrence from observed input-window effects.Neural comparisons are accuracy references, but capacity and optimization differences prevent a universal ranking; state probes should test decoding rather than merely count feedback patterns.Source: B. Edge Realization and Temporal Context · p. 2

III. COMPRESSED RTM

The compressed RTM receives observed features and prior binary context, evaluates its clauses, and returns a prediction and clause activations. It folds those activations, retains fast and slow activity traces, and thresholds them into the next-step state.

III. COMPRESSED RTM

  • The RTM combines observed features with prior binary context, then produces a prediction and clause activations.The model has 240 clauses per class, and compression applies to the activity returned at the next step rather than changing the learned clause bank.Source: §III · p. 2

A. Binary Input and Feedback

  • Each input symbol is expanded into Boolean views, and the observed input also includes the previous symbol and previous prediction.The views include binary digits, thermometer thresholds, one-hot identity bits, and pairwise XOR bits.Source: A. Binary Input and Feedback · p. 2
  • A seeded fixed assignment maps clause activations into 48 bins, where XOR folds the assigned activations.XOR is selected to keep the computation Boolean; the paper notes that OR tends to saturate and AND tends to vanish for active clause banks.Source: A. Binary Input and Feedback · p. 2
  • Two exponential moving averages retain activity at different speeds, and thresholding converts the averages back to Boolean values.The figure depicts clause activations being folded, retained through fast and slow averages, and thresholded before returning at the next step; XOR trees map directly to digital XOR operations.Source: A. Binary Input and Feedback · p. 3, Figure 1 · p. 3
  • The two memories form a 96-bit recurrent state, compared with 960 recurrent bits in the raw-feedback model.Five members use different training orders and fold assignments, and their predictions are combined by majority vote.Source: A. Binary Input and Feedback · p. 3

B. Causal Update Order and Interface Accounting

The update order keeps prediction causal: each step uses current data and prior state, then creates feedback for the next step. The design also distinguishes per-member interface widths for compressed and raw feedback.

B. Causal Update Order and Interface Accounting

  • At step t, each member predicts from current input and prior state before its clause activations create feedback for step t + 1.Training follows the same order, so the current prediction cannot use the target or state derived after observing it.Source: B. Causal Update Order and Interface… · p. 3
  • The compressed configuration has per-member recurrent and total input widths of 96 and 182, versus 960 and 1046 for raw feedback.The reported widths are interface dimensions, not trainable floating-point parameter counts; five-member voting does not concatenate member states.Source: B. Causal Update Order and Interface… · p. 3

C. Fold Semantics and Collision Behavior

The method folds clause activity into fixed bins with XOR and retains two timescales, while the benchmark supplies known hidden-state transition rules for testing prediction and state recovery.

C. Fold Semantics and Collision Behavior

  • Each of 480 clause positions maps to one fixed bin, where an odd number of active clauses produces a one and an even number cancels.The two EMA memories act on the same 48 folded bits, adding temporal persistence rather than additional evidence channels.Source: C. Fold Semantics and Collision Behavior · p. 3
  • The fold bounds recurrent-interface width independently of clause-bank size, but does not compress learned automata or reduce the TM’s trainable state.Different ensemble members use different fixed assignments; the evaluation includes 32-bit, single-member, and raw-feedback variants.Source: C. Fold Semantics and Collision Behavior · p. 3

IV. REPRODUCIBLE BOOLEAN-FSM BENCHMARK

  • An FSM has a hidden state and fixed input-conditioned transition rule, making its true memory known to the experimenter but hidden from the learner.The benchmark uses 6- and 8-bit states, with at most 64 and 256 states; these widths do not define task difficulty.Source: §IV · p. 3
  • For each step, four input bits join the current state as transition sources, all state bits update simultaneously, and the label is the updated state’s parity.Circuit seeds fix transition rules, while dataset seeds sample initial states and observed input sequences.Source: §IV · pp. 3–4, Figure 2 · p. 4
  • Each circuit has 1000 training, 300 validation, and 500 test sequences, and exported artifacts include transition tables, arrays, output maps, and file hashes.Structural measures are computed over every state/input pair; circuit-specific majority baselines reflect output balance, and initial hidden states are not model inputs.Source: §IV · p. 4

V. EXPERIMENTAL SETUP

This section introduces the evaluation’s model configurations, baselines, ablations, and uncertainty protocols.

V. EXPERIMENTAL SETUP

  • The section covers hyperparameter configurations, neural baselines, ablation variants, and statistical uncertainty protocols.Source: §V · p. 4

A. Model Configurations and Baselines

The setup compares RTM configurations and causal neural baselines on common data, with matched ablations and paired uncertainty estimates. The results section presents accuracy summaries and paired changes, while the supplied passages do not state their plotted values.

A. Model Configurations and Baselines

  • The RTM uses 480 clauses, threshold T = 120, specificity s = 6.0, and eight training passes, with 144 runs across circuit and training seeds.The study reports mean and sample SD; paired ablation differences use unadjusted 95% Student-t intervals, and host wall time is not a hardware benchmark.Source: A. Model Configurations and Baselines · p. 4
  • Five causal neural baselines use the same arrays and seeds: an eight-symbol-window MLP, simple RNN, GRU, LSTM, and Transformer.The comparisons concern stated implementations, not equal parameter counts or optimization budgets.Source: A. Model Configurations and Baselines · pp. 4–5
  • The eight RTM variants include full compressed, raw-feedback, and no-feedback comparisons plus five component ablations.The no-feedback control still receives two observed symbols and the previous prediction, removing clause-derived state rather than all temporal information.Source: A. Model Configurations and Baselines · p. 5
  • The nearest-centroid probe tests whether feedback signatures identify hidden FSM states, using Hamming distance to rank candidate states.Its split is within test time points from the first circuit member, not held-out-sequence generalization.Source: A. Model Configurations and Baselines · p. 5

B. Paired Comparisons and Uncertainty

  • Ablation effects are paired accuracy changes from the full model across the same nine circuit/training-seed combinations.The intervals summarize within-design variation and are not adjusted across ablations; with three circuit seeds, they do not characterize the full generator distribution.Source: B. Paired Comparisons and Uncertainty · p. 5

VI. RESULTS

  • The results section covers neural-baseline comparisons, component ablations, compression trade-offs, and state-probe fidelity; Fig. 3 summarizes mean test accuracy over nine matched runs.Fig. 3 error bars are sample SD combining circuit and training variation, not confidence intervals; Fig. 4 shows paired accuracy changes from the full model with 95% t intervals.Source: §VI · p. 5, Figure 3 · p. 5, Figure 4 · p. 5

A. Comparison with Neural Baselines

The full RTM beats each circuit-specific majority predictor, while GRU and LSTM have the highest family means. Ablations show ensemble voting helps most, whereas removing clause feedback slightly improves both families.

B. Ablation Results

  • Reducing the ensemble to one member changes accuracy by −1.77 pp (95% CI [−2.42, −1.11]) and −2.29 pp ([−3.72, −0.86]).Removing thermometer features changes accuracy by −0.23 pp ([−0.52, 0.07]) and −0.68 pp ([−1.15, −0.22]).Source: B. Ablation Results · p. 5
  • 0.43 pp ([0.09, 0.78]) and 0.89 pp ([0.34, 1.44]): removing clause feedback improves both family means.One-timescale and instantaneous feedback also improve both families; ensemble voting provides the clearest benefit.Source: B. Ablation Results · pp. 5–6

A. Comparison with Neural Baselines

  • 3.45–20.95 points: full RTM exceeds each circuit-specific majority predictor; GRU and LSTM have the highest means in both families.The per-circuit results show rankings vary with circuit structure, including cases where RTM beats GRU or MLP.Source: A. Comparison with Neural Baselines · p. 5, Table I · p. 6

C. Compressed Versus Uncompressed Feedback

Folding yields a much narrower interface with mean accuracy close to raw feedback, but compressed feedback signatures do not reliably identify hidden FSM states. On these deterministic tasks, no-feedback models retaining short input history are comparable or slightly more accurate.

D. Hidden-State Recovery

  • Compressed top-1 and top-5 state recovery fall below matched random references in both families, despite nearly unique signatures.The compressed codes are almost unique (11,696/12,500 and 14,203/15,000 test steps), but most are rare.Source: D. Hidden-State Recovery · p. 6

C. Compressed Versus Uncompressed Feedback

  • 960 to 96 bits: folding reduces recurrent width 10× and input dimension 5.75×; raw feedback raises mean accuracy by 0.72/0.58 pp, with both paired intervals including zero.Mean host time falls from 72.7 to 16.6 minutes and 73.2 to 19.7 minutes; gated neural models remain more accurate at the family level.Source: §VII · p. 6, C. Compressed Versus Uncompressed… · p. 6

VII. DISCUSSION

  • On these deterministic FSM tasks, short input history makes explicit recurrence not strictly necessary; no-feedback controls are comparable or slightly more accurate.The discussion says the short input history already contains substantial predictive information.Source: §VII · p. 6
  • When clause-derived recurrence is required but raw feedback makes the interface too wide, XOR folding offers a practical, scalable mechanism.Fold width, timescale count, and ensemble size should be evaluated jointly; circuit variation means nominal state count alone is not an adequate difficulty label.Source: §VII · p. 6
  • Nearly unique compressed signatures do not reliably identify hidden state, so predictive utility should not be mistaken for symbolic interpretation.The discussion treats this as a separate caution from predictive accuracy.Source: §VII · p. 6

VIII. ARTIFACT AND REPRODUCTION

The artifact provides the benchmark data and files used for the paper’s tables and figures, with separate paths for rapid regeneration and full retraining. The following section introduces threats to validity and methodological boundaries.

VIII. ARTIFACT AND REPRODUCTION

  • The artifact includes experiment runners, RTM, neural, and probe records, plus circuit manifests, data arrays, transition tables, output maps, and hashes.The files support independent label checks and confirm matched models used identical data.Source: §VIII · p. 6
  • Archived records can regenerate the tables and figures in seconds without retraining.The analysis mode of the RTM experiment runner performs this regeneration.Source: §VIII · p. 6
  • Table III reports per-circuit test accuracy averaged over three training seeds, with neural and RTM models using identical generated arrays.The table identifies Transformer as the attention-based baseline.Source: Table III · p. 7
  • Table IV reports ablation mean accuracy and standard deviation over nine runs.Source: Table IV · p. 7
  • Table V compares compressed with raw feedback and defines Δ as raw minus compressed accuracy.Source: Table V · p. 7
  • The full pipeline reruns the 144-run RTM suite across all seeds using the paper’s ablation schedule.The runners save completed runs individually and resume from a unique run key.Source: §VIII · pp. 6–7

A. Internal and Statistical Validity

The study finds that compressed feedback preserves measured behavior within small empirical margins, but its conclusions are bounded by the small circuit sample, synthetic benchmark, and lack of device-level measurements. It also cautions that predictive feedback patterns do not reliably identify hidden state.

A. Internal and Statistical Validity

  • Three circuit seeds and three training seeds provide a small sample; intervals describe variation within this design, not uncertainty over all Boolean circuits.An interval containing zero does not establish formal equivalence; that would require a predeclared non-inferiority margin and a larger circuit sample.Source: A. Internal and Statistical Validity · p. 7
  • The neural comparison is descriptive rather than a controlled claim of algorithmic superiority because validation selection, model capacities, parameter counts, and optimization budgets differ.Source: A. Internal and Statistical Validity · p. 7
  • Host-time ratios describe this software implementation, not device latency or energy, because timing varies with system load and no repeated device-level protocol was used.An independent implementation would provide a stronger check than rerunning the same code.Source: A. Internal and Statistical Validity · p. 7

B. Construct and External Validity

  • The width calculation covers recurrent state and resulting model input, not automata storage, buffers, data layout, or accelerator packing; folding compresses only the between-step interface.The no-feedback control retains two observed symbols and the previous prediction, so its result does not show that all temporal context is unnecessary.Source: B. Construct and External Validity · p. 7
  • The nearest-centroid probe uses a random time-point split from one ensemble member, while the synthetic, noiseless, stationary FSM benchmark excludes sensor noise, drift, long horizons, continuous inputs, and real-world streams.A positive probe result would require held-out-sequence, held-out-circuit, and control-task confirmation; the negative compressed result weighs against direct hidden-state identification.Source: B. Construct and External Validity · p. 7
  • General deployment claims require evaluation on real-world edge workloads and direct hardware measurements; reproducibility files do not remove these limits.Source: B. Construct and External Validity · p. 8

X. CONCLUSION

  • On evaluated tasks, the compact summary preserves full-feedback behavior within small empirical margins, while the strongest neural learner remains more accurate and short observed history can be as useful as clause feedback.The compressed summary does not reliably reveal hidden machine state.Source: §X · p. 8
Loading 2609.06133v1…