FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning

We sincerely appreciate your insightful comments and constructive feedback, which have been invaluable in improving the quality and clarity of our manuscript. Below, we provide detailed responses to the identified weaknesses and questions.

*W1: Considering that the computational cost on the entire LLM of white-box prompt learning is transfer to the cost on APIs usage of black-box prompt learning, the overall motivation is questionable. More detailed cost-benefit analyses and related facts would explain this well.

1. The statement "the computational cost of the entire LLM in white-box prompt learning is transferred to the cost of API usage in black-box prompt learning" is not universally applicable.. Access to advanced LLMs is typically governed by large organizations, which often restrict white-box access, making fine-tuning or internal modifications unfeasible. This leaves researchers and practitioners with no alternative but black-box prompt tuning to adapt these models for specific tasks. Black-box prompt tuning enables efficient model customization by modifying the inputs (prompts) rather than the model’s internal structure, which is crucial in scenarios where internal access or fine-tuning is prohibited or unavailable.
2. Even if the stated cost-transfer argument were valid, black-box prompt learning offers clear advantages in terms of cost-effectiveness and practicality. White-box fine-tuning of LLMs requires substantial computational resources, such as GPUs or other high-performance hardware, resulting in significant upfront investments and maintenance costs. In contrast, black-box prompt learning shifts this burden to API usage fees, which are often more manageable and scalable, particularly for smaller organizations or individual practitioners. Moreover, in our experiments, the cost of white-box prompt learning (e.g., training on cloud GPUs with RoBERTa-base) was comparable to the cost of black-box prompt learning (e.g., using the OpenAI API for GPT-3.5-turbo). However, black-box methods allowed us to leverage a more advanced model (GPT-3.5-turbo) than would have been feasible in the white-box setting, further underscoring its practicality and efficiency.

*W2: The claim and the proof of Corollary 2, which support the main idea that 1 client is needed, is naive and questionable either. K∗ is related to aggregation and overall variance (e.g., λ in Assumption 3) due to the fact that larger K reduce the aggregation noise in federated learning setting. Even if small stepsize can be used to minimize it, as claimed in Line 269, the training process in slower, leading more global epochs. Thus, the bound, from Line 1519 to 1595, seems vaccum and the claim do not make sense. A more comprehensive analysis could help, which considers the trade-offs between reduced aggregation noise from larger K and the increased number of global epochs.

1. The demonstration of Corollary 2 is rigorous. We analyze the optimal $K_{\ast}$ by balancing convergence complexity and query count, aiming to achieve the fastest convergence with the fewest queries. Specifically, we first fix the convergence accuracy, denoted as $\epsilon$, and determine the number of iterations, $T_{\epsilon}$, required to achieve this accuracy. We then analyze the total number of queries, given by $T_{\epsilon}K_{\ast}=\mathcal{O}(K_{\ast})$. This analysis shows that the combined effect of convergence complexity and the number of queries is directly proportional to $K_{\ast}$. Therefore, to optimize query efficiency—balancing both convergence complexity and query count—it is crucial to minimize $K_{\ast}$. Ideally, setting $K_{\ast}=1$ achieves the most efficient balance, ensuring both theoretical and practical efficiency.
2. You appear to be conflating $K$, $K_{\ast}$ and $\lambda$ in the algorithmic context. To clarify: $K$ represents the total number of clients in the federated learning system; $K_{*}$ denotes the number of clients activated per round. Increasing $K_{\ast}$ reduces the variance introduced by the aggregation of clients, as described in Equation (13); $\lambda$ captures the bias introduced by data heterogeneity, reflecting inconsistencies in client data distributions. These two sources of error—bias from data heterogeneity ($\lambda$) and variance from random client selection ($K_{\ast}$)—are distinct. Additionally, the total number of clients, $K$, remains constant throughout the algorithm's execution, ensuring a stable framework for analysis and implementation.

The response to W1 is reasonable, but the rest of the analysis of One is confusing, the assumptions of the parameters inherently decouple the connections that should exist. The noise from less sampling of clients is not taken into account in the analysis alone, leading to biased conclusions, and therefore does not change my rating.

We have uploaded a revised version addressing some of the issues identified during the discussion (highlighted in blue). Your review and feedback would be greatly appreciated.

We sincerely appreciate your insightful comments and constructive feedback, which have been invaluable in improving the quality and clarity of our manuscript. Below, we provide detailed responses to the identified weaknesses.

*W1: More details on optimizing K∗ from ">1" to "=1" for improving query efficiency in Section 3.2 should be provided, as it is the most important part in the whole paper. According to the current version, the proposed method is too simple and too straightforward. The effect of the value of K∗ on model convergence should be also analyzed in this section.

We carefully analyze the optimal $K_{\ast}$ by balancing convergence complexity and query count, with the goal of achieving the fastest convergence with the fewest queries. Increasing $K_{\ast}$, the number of activated clients, can accelerate convergence by leveraging more data; however, it also increases query overhead, leading to higher communication and computational costs. We rigorously demonstrate that the number of queries required for Fed-BDPL to achieve an $\epsilon$-solution is $\mathcal{O}(K_{\ast})$. This result emphasizes that optimal query efficiency is achieved when only a single client is activated per round.

*W2: The experiment does not contain related baselines to compare with, such as [1],[2]. As a result, it is very hard to evaluate whether the FedOne reflects the SOTA performance.
[1] Black-box Prompt Tuning for Vision-Language Model as a Service. IJCAI 2023.
[2] Fedbpt: Efficient federated black-box prompt tuning for large language models. ICML 2024.

Thank you for your suggestion about the experimental baseline:

1. Reference [1] focuses on visual and language model integration, making it unsuitable for our study. Specifically, the framework in [1] jointly optimizes prompts for different modalities by sharing the intrinsic parameter subspaces of both visual and language modalities, a process that necessitates interaction between these two modalities.
2. Reference [2], cited in Section 4.2 (line #338, Sun et al., 2022), serves as a key baseline in our experimental evaluation. We have adapted this work as the "FedOne-BBT" baseline (line #332), allowing for a direct comparison between our proposed FedOne algorithm and existing state-of-the-art methods.

*W3: It is unclear whether the number of clients has an effect on the performance of FedOne.

In our theoretical analysis, the total number of clients does not impact the performance of FedOne. This is because our analysis accounts for the inherent randomness introduced by client sampling. This randomness, stemming from the stochastic nature of client selection, must be addressed and eliminated, as the $\alpha$ parameter we aim to optimize depends on the contributions of all clients. Consequently, our theoretical framework does not consider the effect of the total number of clients, $K$, on the algorithm's performance. Instead, the key factor influencing convergence is the number of activated clients, $K_{\ast}$. To further investigate the impact of the number of clients, we will conduct experiments focusing on the parameter $K$.

Thank the authors for the explanation. Most of my concerns have been addressed. According to the current version of the paper, I prefer to keep my score.

We have uploaded a revised version addressing some of the issues identified during the discussion (highlighted in blue). Your review and feedback would be greatly appreciated.

We sincerely appreciate your insightful comments and constructive feedback, which have been invaluable in improving the quality and clarity of our manuscript. Below, we provide detailed responses to the identified weaknesses and questions.

W1: The paper builds upon an existing federated BDPL framework.

This article shares similarities with an existing federated BDPL framework; however, we address a distinct problem that has not been explored in previous research:

1. Prior research on federated black-box prompt tuning has largely overlooked the significant query costs associated with cloud-based LLM services and has not provided corresponding theoretical analysis. We are the first to highlight that previous studies have neglected the issue of query efficiency in this context.
2. We conduct a rigorous theoretical analysis, with results showing that by restricting each round of activation to a single client, FedOne achieves optimal query efficiency. Additionally, the corresponding experimental results validate the effectiveness of FedOne, offering an effective paradigm for addressing the black-box problem in scenarios with limited computational resources.
3. We utilize the Gumbel-Softmax technique to reparameterize the categorical distribution of the prompt vocabulary and apply the policy gradient method to approximate gradients in the black-box setting. This enables optimization in the parameter space rather than in label probabilities, thereby mitigating bias. This approach allows for more stable model training while facilitating theoretical analysis based on unbiased gradients, as opposed to biased gradients.

W2: The rationale behind the FedONE algorithm is not adequately explained.

We will provide a detailed explanation of the rationale behind the FedOne algorithm:

1. An intuitive explanation for the effectiveness of FedOne lies in its ability to maximize the utility of each LLM query. By activating only one client per round, FedOne ensures that each query contributes significantly to the global model update. This selective client activation minimizes redundant computations and reduces communication overhead, optimizing the overall query efficiency within federated learning frameworks.
2. We have rigorously demonstrated, through theoretical proof, that the number of queries required for Fed-BDPL to achieve an $\epsilon$-solution is $\mathcal{O}(K_{\ast})$, where $K_{\ast}$ represents the number of activated clients. This result highlights that optimal query efficiency is achieved when only a single client is activated per round, as is the case with FedOne.
3. Experimental results presented in Figure 2 and Table 3 show that by utilizing the minimum number of activated clients—FedOne—the federated learning framework achieves the highest possible query efficiency. This approach maximizes efficiency between clients and the server, leading to a more efficient learning process.

We have uploaded a revised version addressing some of the issues identified during the discussion (highlighted in blue). Your review and feedback would be greatly appreciated.

We sincerely appreciate your insightful comments and constructive feedback, which have been invaluable in improving the quality and clarity of our manuscript. Below, we provide detailed responses to the identified weaknesses.

W1: The proposed method requires each client to store a size of n×N αs. Nowadays, the pretrained embedding layer of an LLM gets larger, e.g., from 32k in LLaMA-2 to 128k in LLaMA-3. Therefore, it costs a large amount of computation and communication overhead.

The parameter $\alpha$, used for generating the discrete prompt, is much smaller than the model parameters. As shown in Table 2, FedOne exhibits significantly low computational and communication overhead, which is a critical factor in its scalability and practical applicability in federated learning scenarios. By minimizing both the computational resources required for processing and the frequency of communication between clients and the server, FedOne ensures efficiency, even in resource-constrained environments.

W2: This paper does not explicitly discuss the effect of n. This should be part of the ablation study.

1. Theoretically, as demonstrated in Theorem 1, a larger value of $n$ leads to a slower convergence rate for Fed-BDPL. This can be intuitively understood, as increasing the prompt length requires more epochs to effectively identify and optimize the most relevant prompt tokens. A larger $n$ adds complexity to the search space for the optimal token configuration, thus prolonging the convergence process.
2. Experimentally, to further investigate the impact of prompt length, we will add an ablation study focusing on the parameter $n$.

W3: The review of FL is insufficient. I see there are a number of works addressing LLM fine-tuning under federated learning. The authors should concretely discuss why the existing works are infeasible.

Thank you for suggesting the inclusion of the LLM fine-tuning baseline. We have incorporated the most relevant work on Federated Prompt Tuning in Section 5.3:

1. Existing research on fine-tuning LLMs in federated learning often assumes that the models are open-source, with full access to their parameters for direct modification. In contrast, our work focuses on black-box learning scenarios, such as those involving commercial large language models. These models offer only inference services, limiting access to their underlying parameters. Users can interact with them by providing inputs and receiving outputs via API calls but cannot modify model weights or apply traditional gradient-based fine-tuning. Consequently, fine-tuning methods are inapplicable in these closed-system settings, where internal parameters remain inaccessible.
2. Additionally, fine-tuning in FL generally assumes that clients have significant computational resources to manage the extensive load required for retraining large models. However, this is often impractical in FL scenarios, where clients are typically resource-constrained devices with limited processing power. Requiring substantial computational capabilities for fine-tuning can lead to scalability issues and limit the applicability of such methods in large-scale, decentralized settings. In contrast, our approach focuses on methods that do not require direct access to the model or heavy client-side computation, making it more suitable for practical deployment in resource-limited environments.

W4: $\eta_{\ast}$ goes to an order of O(T). This sounds really weird. I think the author should justify the reason.

Thank you for pointing out the issue. We identified an error in Equation (12), where an extra $T$ appeared in the denominator due to a substitution error on line #1495. This mistake has been corrected and does not affect the convergence results:

We have uploaded a revised version addressing some of the issues identified during the discussion (highlighted in blue). Your review and feedback would be greatly appreciated.