CS-pFedTM: Communication-Efficient and Similarity-based Personalization with Tsetlin Machines

Shannon How, Jagmohan Chauhan, Geoff V. Merrett, Jonathon HareOpenReview 2026 · Submission to ICLR 2026 · Rejected · OpenReview

TL;DR

CS-pFedTM is a novel personalized federated learning (pFL) framework that replaces resource-heavy neural networks with logic-based Tsetlin Machines. By using parameter similarity as a proxy for data heterogeneity, it adaptively balances local and global knowledge to slash communication costs by orders of magnitude while outperforming state-of-the-art methods in accuracy.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple devices (clients) to train a model collaboratively without sharing their private data. However, two major "bottlenecks" prevent its widespread use on edge devices like smartphones or IoT sensors:

  1. Data Heterogeneity: Different users have different data (e.g., one person takes photos of cats, another of cars). A single "global" model often fails to perform well for everyone.
  2. Communication Constraints: Sending massive Deep Neural Network (DNN) parameters back and forth between devices and a central server is slow and battery-draining.

While "Personalized FL" (pFL) tries to solve the first problem by letting clients keep some local model parts, most existing methods still rely on DNNs, which are computationally expensive and offer limited control over communication budgets.

Methods

The authors introduce CS-pFedTM, which shifts the paradigm from calculus-based neural networks to logic-based Tsetlin Machines (TMs).

Key Components:

  • Tsetlin Machines: Instead of weights and biases, TMs use propositional logic (AND/OR rules) and finite-state automata. They operate on bits, making them inherently faster and leaner than DNNs.
  • Dual-Model Personalization: Each client maintains two TMs: a Local TM (trained only on local data to capture specific patterns) and a Global TM (shared with the server to benefit from collective knowledge).
  • Similarity-Driven Allocation: This is the core innovation. The server conducts a "reference round" to calculate the Jaccard similarity between clients' models.
  • If clients are very different (high heterogeneity), the system allocates more local clauses to prioritize personalization.
  • If clients are similar, it allocates more global clauses to maximize shared learning.
  • Communication-Awareness: The framework translates a megabyte-based communication budget into a concrete number of "clauses" that can be shared, ensuring the model never exceeds the device's bandwidth limits.
  • Weight Masking: To further boost efficiency, weights for classes not present in a client's local dataset are masked (set to zero), allowing the model to focus only on relevant categories.

Datasets

The authors evaluated the framework across six diverse datasets:

  • Image Datasets: SVHN (street view house numbers), EMNIST (extended handwritten characters), CIFAR-10, CIFAR-100, and Tiny-ImageNet.
  • Audio Dataset: SpeechCommands-12 (SC-12) for keyword spotting.
  • Heterogeneity Simulation: They used a Dirichlet partition to simulate varying levels of "Non-IID" data (data that is not identically distributed across clients).

Key Insights and Ideas

  • Parameters as a Proxy for Data: The most significant "aha moment" is the mathematical and empirical proof that the similarity of Tsetlin Machine parameters (active clauses) is a highly reliable proxy for the similarity of the underlying data distributions. This allows the server to adapt the model architecture without ever seeing the clients' private metadata.
  • The "Sweet Spot" of Personalization: The paper demonstrates that peak performance always occurs at an intermediate split between local and global components. Being "too local" loses the benefit of the group, while being "too global" ignores the individual user's needs.
  • Logic is Leaner: By using bit-based logic rather than floating-point math, the system achieves massive reductions in memory and communication without the "information loss" typically seen when simply compressing or pruning a standard neural network.

Key Results

CS-pFedTM consistently outperformed state-of-the-art (SOTA) personalized FL baselines (like FedPAC, FedRep, and FedSelect):

  • Accuracy: Achieved the highest average performance, outperforming the second-best method by an average of 1.64% and other TM-based methods by up to 32%.
  • Communication Efficiency: Slashed upload costs by 3.6× to 886× and download costs by 5.58× to 107× compared to SOTA baselines.
  • Hardware Efficiency: Improved runtime efficiency by at least 1.17× and reduced storage requirements by 2.17× compared to traditional CNN-based federated learning.

Limitations and Future Work

  • The "TM Ceiling": The authors acknowledge that Tsetlin Machines can sometimes lag behind the absolute highest accuracy of SOTA DNNs in centralized settings due to the "booleanization" of data (converting everything to 0s and 1s).
  • Concept Drift: While the current model handles static data well, the authors suggest that future versions should periodically re-estimate client similarity to handle "concept drift" (when a user's data patterns change over time).
  • Advanced Architectures: Future work will look into integrating "Graph Tsetlin Machines" and "TM Composites" to further close the performance gap with deep learning while maintaining the framework's massive efficiency gains.

Summary updated

Abstract

Federated Learning has become a promising framework for preserving data privacy in collaborative training across decentralized data sources. However, the presence of data heterogeneity remains a significant challenge, impacting both the performance and efficiency of FL systems. To address this, we introduce CS-pFedTM (Communication-Efficient and Similarity-based Personalized Federated Learning with Tsetlin Machine), a method that addresses this challenge by jointly enforcing communication-aware resource allocation and heterogeneity-driven personalization. CS-pFedTM enforces communication budget feasibility through clause allocation and tailor personalization using clients' parameters similarity as a proxy for data heterogeneity. Experiments across multiple datasets show that CS-pFedTM consistently outperforms state-of-the-art personalized FL approaches, achieving at least $3.6\times$ lower upload cost, $5.58\times$ lower download cost, and $1.17\times$ higher runtime efficiency, while maintaining superior accuracy.
BibTeX
@misc{how2026cs,
  author = {Shannon How and Jagmohan Chauhan and Geoff V. Merrett and Jonathon Hare},
  title = {{CS-pFedTM: Communication-Efficient and Similarity-based Personalization with Tsetlin Machines}},
  year = {2026},
  url = {https://openreview.net/forum?id=rcY4qPSXP4},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2026},
}
Figure