LegoMark: Efficient and Traceable Black-Box Watermarks for Federated Fine-Tuning

Federated fine-tuning (FFT) enables clients to collaboratively adapt a large language model to downstream tasks without sharing their local data, but clients may redistribute the trained adapters without authorization. Existing traceable black-box watermarks identify the source of a leaked model through its outputs, but injecting and verifying a distinct watermark for every client incurs costs that grow linearly with the client population $n$. We propose LegoMark, a watermarking method for FFT that constructs client-specific watermarks by composing shared watermark bases. The server encodes each client's identity with a unique non-zero binary message, learns one watermark base for each bit position, and combines the bases selected by the active positions of the message, reducing both the number of injection procedures per round and the number of watermark datasets queried per suspect model from $\Theta (n)$ to $\Theta (\log n)$. To address interference when independently trained bases are combined, we introduce composition-aware refinement that optimizes each watermark base to survive when combined with other bases. Motivated by an empirical asymmetry in decoding errors that is well approximated by a Z-channel, whereby active bits may be lost while inactive bits are essentially never activated, we adopt a constant-weight codebook in which all messages share the same number of active bits. Under this approximation, a damaged message cannot match any valid one, so active-bit losses lead to withheld attribution rather than misattribution. Extensive experiments show that LegoMark preserves main-task accuracy while achieving a high attribution rate and never misattributes under the evaluated post-processing attacks. At $n=100$, it reduces the wall-clock injection time per round by $4.4\times$ and the verification time per suspect adapter by $12.3\times$ compared to the state-of-the-art method TraMark.