acceptodds
Under review as a conference paper at ICLR 2027

Reading between the Clauses: Data Reconstruction Attack on Federated Training of Tsetlin Machines

Abstract

Tsetlin Machines (TMs) classify binary inputs through learned logical combinations of features. They have recently gained attention because they train without GPUs, run efficiently on edge devices, and are explainable by design: each learned clause is a small pattern that points directly at the input pixels behind a decision. Weighted Convolutional TMs (wCTMs) have even been shown to outperform neural networks on federated image classification under strong data heterogeneity. Federated learning is meant to protect privacy by keeping each client's data on their own device and sharing only the trained model with the server. We show that for wCTMs this protection fails: the same explainability that makes a clause readable also makes it invertible. Under heterogeneous data, many clients hold classes with so few images that their clauses memorize the individual samples. We present the first data reconstruction attack on federated wCTM training. From a single uploaded model, an honest-but-curious server estimates how many images a class was trained on and reassembles the clauses' learned patches to recreate the original images. No auxiliary data and no protocol manipulation are required. Across five benchmarks, the attack reconstructs hundreds to thousands of images, up to 95% of the images each heterogeneous setting leaves exposed.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
tsetlin machines, data reconstruction attack, federated learning, privacy attacks, interpretable models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_jiU8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents the first training data reconstruction attack against federated weighted Convolutional Tsetlin Machines (wCTMs), exploiting their inherent interpretability, and the fact that non-IID federated data leaves many client classes trained on only a handful of samples. From a single uploaded client model, an honest-but-curious server identifies vulnerable client classes, estimates the unknown number of training samples via the maximum clique of a clause conflict graph, assigns clauses to canvases through an integer linear program, and paints each canvas by solving a second ILP that places clauses conflict-free while filling in class-common pixels using a cross-client pixel agreement map. Evaluated on five image-recognition benchmarks (MNIST, F-MNIST, SVHN, GTSRB, CIFAR-10) under Dirichlet non-IID partitions over 100 clients, the attack detects vulnerable classes with F1 between 0.92 and 1.00, estimates sample counts with 86–9986–99% accuracy, and reconstructs up to 95% of exposed samples when M≤5M \leq 5. The work concludes that the very interpretability that makes Tsetlin Machines attractive is what exposes their training data, and that principled defenses such as differential privacy or model-configuration tuning trade utility for privacy.

Critical strengths
  • The paper identifies and exploits a genuine, non-obvious attack surface that existing reconstruction attacks cannot reach.
  • The empirical evaluation is broad, multi-metric, and honestly reports where the attack fails. Attack papers are frequently undermined by cherry-picked settings or single metrics that conflate class-generic reconstruction with sample-specific recovery. This paper's use of Matching F1 specifically separates the two, and its willingness to report SVHN as the hard case and to show degradation curves by true sample count makes the central claim credible.
Critical weaknesses
  • The paper attacks weighted Convolutional Tsetlin Machines (wCTMs), a model family that rarely appears in the main ICLR program. Although Tsetlin Machines have some activity in interpretable logical learning, edge inference, and hardware acceleration communities, they are neither a mainstream ICLR architecture (Transformers, diffusion models, GNNs, state-space models) nor a primary target of the ICLR privacy community (neural networks, language models). Consequently, the paper's central contribution, "the first reconstruction attack against federated wCTMs", lacks direct relevance for most ICLR reviewers and readers.
  • The attack assumes the server obtains the complete internal state of each client's uploaded wCTM, e.g., all clauses, Tsetlin automaton states, integer weights, and valid position sets. This comes from the "single-round upload of the full local model" setting of FedTMOS (S How et al., 2025). The paper does not sufficiently justify the realism of this assumption, nor does it discuss whether the attack still holds if the protocol uploads only aggregate statistics, encrypted states, or gradient approximations.
Questions for authors
  • If the paper could show that "any interpretable model based on conjunctive clauses (decision trees, rule lists, Tsetlin Machines, neuro-symbolic models) leaks under few-sample federated settings," its audience would be much broader. But all experiments are confined to wCTMs, with no cross-model validation.
  • The paper explicitly acknowledges that the attack only works when each client class has 1–5 training samples. Beyond 5, clauses begin to generalize, the conflict graph loses structure, and both sample-count estimation and reconstruction quality degrade sharply. This means the attack's applicability is very narrow, and the paper does not sufficiently argue whether this narrow regime is common in real federated settings.
  • Section 5 discusses defenses, identifies differential privacy (DP) as a "principled defense," and suggests using a discrete Gaussian mechanism to add noise to TA states and clause weights. But the paper performs no DP experiments, reports no figures on how the attack's F1, Jaccard, or Matching F1 degrade under DP noise, and does not report what ϵ\epsilon is needed to render the attack unusable. This leaves the "defense discussion" on paper and weakens the paper's practical guidance.
    • After adding DP noise, does the attack still work? If so, how large an ϵ\epsilon is needed? If ϵ=1\epsilon = 1 suffices to stop the attack, the threat is limited; if even ϵ=10\epsilon = 10 fails to stop it, the attack is severe. The paper provides no such curve.
  • The paper's core technical tools, e.g., maximum clique, integer linear programming (ILP), and SAT solving, are standard tools in combinatorial optimization and operations research, not new methods of interest to the ICLR community.
    • Theorem 1 proves that the maximum clique is a lower bound on the sample count. The observation is clean, but its mathematical depth is limited, essentially a counting argument via an injective map. Does the proof go beyond what is "obvious"? To be specific, Theorem 1 is a lower bound, but it is "obvious" (each conflicting clause must come from a different sample) and not tight (the paper itself says the bound loosens when M>5M > 5).
Reviewer_JA6yOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a reconstruction attack on federated weighted Convolutional Tsetlin Machines (wCTMs). A passive server identifies client classes with few samples, estimates sample counts from clause conflicts, and reconstructs binarized images through integer programming. Experiments on five datasets show substantial leakage in heterogeneous, one-shot federated settings.

Critical strengths
  1. The attack handles challenges specific to convolutional Tsetlin Machines. It combines clause-conflict analysis, sample-count estimation, clause assignment, and spatial placement to exploit the model’s discrete representation. It requires neither gradients nor protocol manipulation. The method goes beyond directly applying an existing reconstruction attack to a different model family.
  2. The experiments support the role of victim-specific clauses in reconstruction. The attack outperforms class prototypes and real same-class test images on the reported metrics. Removing pixel agreement maps still gives high clause agreement and matching scores, suggesting that the reconstructions use information from the victim model rather than relying entirely on common class patterns. Ablations over sample counts, heterogeneity, training epochs, and model configuration help identify the conditions under which leakage occurs.
Critical weaknesses
  1. The recovery rate needs to be distinguished from reconstruction fidelity. Matching F1 assigns each reconstruction to its nearest image in the client’s training set. A match counts as a hit if the image belongs to the target class and has not already been claimed. There is no distance threshold or comparison with nonmember candidates. A hit therefore indicates a unique nearest-image assignment within the training set, but does not necessarily mean that the particular sample was accurately reconstructed.

    The Hamming distances, visual examples, and baseline comparisons provide further evidence of leakage. Still, the headline recovery rate of up to 95% should either include a fidelity requirement or be clearly described as reconstruction-output coverage. This matters especially for the multichannel datasets, where average normalized Hamming distances remain around 0.15–0.17.

  2. The connection between the sample-count bound and the solver fallback is unclear. Theorem 1 establishes the clique lower bound conditional on every retained clause firing on at least one target-class training image. The weight and literal filters only approximate this condition, so the guarantee needs to remain explicitly conditional.

    A maximum clique also does not generally give enough canvases to assign all clauses. Pairwise conflicts can require more groups than the clique number, and higher-order conflicts can require additional groups. Appendix G.2 addresses infeasibility by adding a canvas and retrying, but this step is missing from the main algorithm. It is unclear whether sample-estimation accuracy is measured using the initial clique estimate or the final canvas count, and how retries, timeouts, and failed assignments affect the recovery statistics.

Questions for authors
  1. How does the recovery rate change when a successful reconstruction must satisfy both a unique assignment and a distance threshold? Could adding same-class nonmembers to the candidate set help assess sample-specific identification?
  2. What fraction of retained clauses, after filtering, fail to activate on any target-class training image? Please report how well the assumption in Theorem 1 holds empirically.
  3. How often are additional canvases, SAT refinement, or solver retries needed? Do sample-count accuracy and reconstruction coverage use the initial clique estimate or the final count? Please include failure and timeout handling in the algorithm and explain the denominators used in the reported results.
Reviewer_nx8yOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a reconstruction method and results for federated learning based on Tsetlin Machines. The paper

Critical strengths
  1. it's a nice result to show that under this evaluation setting, the federated learning can still leak the info and have images reconstructed.
  2. Initial results show proof of concept for the proposed method.
Critical weaknesses
  1. It's not clear if the method can be extended to more complex datasets and into more generic federated training settings. There are conditions required and mentioned in the paper to make this method work. However, even with these conditions satisfied, The evaluation was not performed on a much challenging task with more complex images.
  2. This paper proposed a new approach, but at the same time need to compare with other reference or existing methods. It was not very clear in the paper that what is in particular the benefits on using this reconstruction algorithm. The evaluation also seem qualitative to me. it's better to have some quantitative comparison with other SOTA methods.
  3. It seems from the results the reconstruction has systemic issues that are focusing more on edges and gradients. is there any solution to this?
Questions for authors
  1. Is it possible to extend to more evaluation on a higher res image and also a time series data?
  2. Could the attack model be covered more precise? including how the federated system is assumed and how IID data are feed in the training.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.