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

We sincerely thank you for your insightful comments and constructive criticisms. Your feedback has been invaluable in improving the quality and clarity of our manuscript. Below, we address the Weaknesses and Essential Reference part.

W1: Motivation behind optimizing query efficiency

The motivation for improving query efficiency is to reduce the monetary cost and practical constraints associated with training federated black-box prompt learning models using cloud-based LLMs. Each query to commercial APIs incurs usage fees and is subject to rate limits, both of which scale with the number of active clients and training iterations in Fed-BDPL. (e.g. GPT-4o is \$2.5/1M input tokens, \\$10/1M output tokens, with rate limits depending on the usage tier.)

Our goal is to make federated black-box prompt tuning cost-effective and scalable in real-world deployments. To that end, our analysis and design focus on the FL framework’s query behavior to cloud-based LLM, rather than how the LLM server handles concurrent API calls.

We will revise the introduction to emphasize the motivation behind optimizing query efficiency.

W2: Experiment on heterogeneity

We provide an additional experiment to demonstrate FedOne’s performance under varying levels of client heterogeneity. Following prior works [1, 2], we simulate heterogeneity using a Dirichlet distribution with concentration parameters $\alpha=0.5$ for medium heterogeneity and $\alpha = 0.1$ for high heterogeneity. Each experiment is run three times independently. The complete results, including three figures corresponding to different heterogeneity levels, are available at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge2-Medium_Hetero.png ).

These experiments further support our theoretical results. Activating a single client per round ($K_*=1$) consistently achieves the highest query efficiency, even in highly heterogeneous settings. This is because the core intuition behind FedOne remains valid under the heterogeneous case: the query cost to the LLM increases linearly with the number of activated clients (since each client issues one query), while increasing K is not able to provide a linear speedup in convergence rate. Our original submission did not include these heterogeneity results because our primary goal was to theoretically identify and validate the optimal query-efficient strategy for Federated Black-box Prompt Learning. Heterogeneity is outside the core scope of this work.

We appreciate the reviewer’s suggestion, and we will add the heterogeneity experiments to the Appendix C.

W3: Fed-X result for Table 1

The corresponding result is provided at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/kF7d_Fed-X_in_table1.jpg ), and it demonstrates that FedOne-X and Fed-X achieve comparable test metrics. We did not include the test metrics for Fed-X in the main text because the primary goal of our research is to improve the query efficiency of Fed-BDPL; optimizing test accuracy is beyond the scope of this work. Our theoretical results also specifically focus on convergence behavior and query efficiency, and do not deal with generalization errors.

We will include the results of Fed-X of Table 1 in Appendix C for completeness.

Essential References: Experiment comparison with FedBPT

Thank you for raising this important point. We would like to clarify that FedBPT is already included in our experiments under the name Fed-BBT. (For context, FedBPT (Sun et al., 2023) applies BBT (Sun et al., 2022) to federated learning, with specific adaptations to enhance performance in FL.) Specifically, our Fed-BBT baseline implements the FedBPT, where the CMA-ES parameters are aggregated across clients, instead of full model parameters.

We chose the name "Fed-BBT" (instead of "FedBPT") to help the reader intuitively compare methods within our framework. The naming convention "Fed-BBT vs. FedOne-BBT" makes it immediately clear that the two methods share the same prompt tuning backbone (BBT) but differ in client activation mechanisms (Fed- vs. FedOne-). In contrast, naming "FedBPT vs. FedOne-BBT" requires additional prior knowledge to recognize that they shared the same backbone.

We will revise Section 4.2 to explicitly state that Fed-BBT is adapted from FedBPT, with BBT as the underlying prompt tuning method.

References

[1] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." NeurIPS 33 (2020): 2351-2363.

[2] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." ICML. PMLR, 2019.

We sincerely thank you for your insightful comments and constructive criticisms. Below, we address the weaknesses.

W1: Rationale of Fed-BDPL

The rationale for employing Black-box Discrete Prompt Learning is grounded in two key real-world constraints:

1. Lack of Access to Model Internals: The white-box federated prompt learning approaches (reference [1–4] you mentioned) assume direct access to model weights or gradients, which is infeasible in realistic scenarios when we want to leverage the most advance commercial, closed-source LLMs (e.g., GPT, Claude), that are only accessible via APIs. Our work specifically targets this black-box setting, where the prompt tuning is conducted without model access—a practical and increasingly common constraint in modern applications.
2. Resource Constraints on FL Clients: In typical FL scenarios, clients are resource-constrained devices (e.g., mobile phones) with limited compute and memory. However, white-box methods ([1-4]) require storing and training on the LLM model locally, which is computationally infeasible for such device. In contrast, black-box prompt tuning offloads the computation to the LLM API, making it scalable and deployable in realistic FL scenario.

We will revise the introduction (par. 3, 4) to make the above rationale more explicit, and ensure that references [1–4] you mentioned are properly cited in the Related Work section.

W2: Motivation of FedOne

The motivation to activate only one client per round is not heuristic, but rather grounded in our theoretical analysis of query efficiency in Fed-BDPL, which includes the convergence of Fed-BDPL (Theorems 3.4, 3.5) and query efficiency (Corollary 3.6). Specifically, Corollary 3.6 demonstrates that setting K=1 achieves optimal query efficiency for reaching an $\epsilon$-solution in the Fed-BDPL framework. The FedOne framework is directly derived from this theoretical result to achieve optimal query efficiency.

The intuition behind FedOne is further elaborated in Remark 3.7: the query cost to the LLM increases linearly with the number of activated clients (since each activated client issues one query), while increasing $K_*$ is not able to provide a linear speedup in convergence rate. Consequently, the marginal gain in convergence rate does not compensate for the linear increase in query cost, making $K_*=1$ the most query-efficient choice under this framework.

We further empirically validate this in Figure 2, where different client selection strategies ($K_*=1,5,10,20,40$) are compared. The results show that activating a single client per round consistently achieves the optimal query efficiency, aligning with our theory.

W3: The Impact of Prompt Length

While prompt length is not the primary focus, we agree that it is an important factor. As shown in Fig. 3, performance remains relatively stable across a moderate range of prompt lengths, with the average accuracy staying in $0.83\pm0.005$. This suggests no statistically significant performance drop when increasing the prompt length.

However, it is worth noting that very short or very long prompts introduce larger variance due to the properties of BDPL.

1. Very short prompts lack sufficient capacity to instruct the LLM effectively.
2. Very long prompts lead to a larger search space and increased training difficulty.

Based on these observations, we selected a prompt length of 20 in our main experiments, as it offers a good trade-off, with the lowest variance. We will clarify this rationale in Appendix C.

W4: Compare with FedBPT

Thank you for raising this important point. We would like to clarify that FedBPT is already included in our experiments under the name "Fed-BBT". (For context, FedBPT (Sun et al. 2023) applies BBT (Sun et al. 2022) to FL, with adaptation designs to enhance its performance in FL.) Specifically, our Fed-BBT baseline implements the FedBPT, where the CMA-ES parameters are aggregated across clients, instead of full model parameters.

We chose the name "Fed-BBT" (instead of "FedBPT") to help the reader compare methods intuitively. E.g., using "Fed-BBT vs. FedOne-BBT" immediately tells that they share the same backbone but differ in client activation mechanisms (Fed- vs. FedOne-). In contrast, naming "FedBPT vs. FedOne-BBT" requires additional prior knowledge to recognize that they are comparable.

We will revise Section 4.2 to explicitly state that Fed-BBT is adapted from FedBPT, with BBT as the underlying prompt tuning method.

W4: The rationale difference between FedBPT and ours

The main rationale difference between FedBPT and our work lies in the research focus: FedBPT focuses on adapting BBT to the federated learning setting, with specific designs to improve optimization performance across clients. In contrast, our work focuses on query efficiency, a crucial and underexplored challenge in federated black-box prompt learning with cloud-based LLMs.

Thank you for your insightful comments and for recognizing the contribution of our work. Your feedback has been invaluable in enhancing the quality and clarity of our manuscript. We reply to the weaknesses and questions.

W1&Q1: Impact of heterogeneity on theoretical analysis

Thanks for pointing that out. We will add more discussion on the heterogeneity in the theoretical analysis.

Regarding the theoretical result under heterogeneity, the conclusion that activating one client per round yields the highest query efficiency in Fed-BDPL still holds. However, the trade-off is a slower convergence rate per round, as fewer clients contribute updates in each iteration.

1. Theorem 3.4, Theorem 3.5, and Corollary 3.6 explicitly consider bounded client heterogeneity, and the result that $K_*=1$ achieves optimal query cost remains valid in this context. This is because the core intuition behind FedOne continues to hold: the query cost to the LLM increases linearly with the number of activated clients (as each client issues one query), while increasing $K_*$ is not able to provide a linear speedup in convergence ([1,2]).
2. The trade-off is that fewer activated clients per round lead to a slower convergence rate (e.g., $O(\frac{1}{\sqrt{K T}})$ convergence in [1]), even though it improves overall query efficiency.

W2&Q2: Experiment on heterogeneity

We have also included an additional experiment to demonstrate FedOne’s performance under varying levels of client heterogeneity, supporting the points discussed in W1&Q1. Following prior works [3, 4], we simulate heterogeneity using a Dirichlet distribution with concentration parameters $\alpha=0.5$ for medium heterogeneity and $\alpha = 0.1$ for high heterogeneity. Each experiment is run three times independently. The complete results, including three figures corresponding to different heterogeneity levels, are available at the following anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge2-Medium_Hetero.png ). We will include the above experiments in Appendix C.

The experiment shows that across all levels of heterogeneity, when the trials converge to a similar stationary point (i.e., approaching the same validation accuracy), activating a single client per round ($K_*=1$) consistently achieves the lowest query cost.

The trade-off is that:

1. Activating fewer clients increases variance in training, which can lead to greater fluctuations.
2. Activating fewer clients also lowers the convergence rate, and conversely, increasing K can speed up convergence at the cost of higher query overhead.

Based on the above trade-off established in our work, practitioners can tune $K_*$ according to their specific system constraints and performance goals.

Despite these trade-offs, the primary objective of our work is to identify the optimal query-efficient strategy within the Fed-BDPL framework that still guarantees convergence. Both our theoretical analysis and empirical results demonstrate that activating a single client per round achieves this goal, providing the best balance in settings constrained by the high cost and rate limits associated with querying cloud-based LLMs.

Other comments

Thank you very much for pointing out these helpful corrections! We have revised them accordingly.

References

[1] Haddadpour, Farzin, and Mehrdad Mahdavi. "On the convergence of local descent methods in federated learning." arXiv preprint arXiv:1910.14425 (2019)

[2] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." ICLR 2020.

[3] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." Advances in neural information processing systems 33 (2020): 2351-2363.

[4] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." International conference on machine learning. PMLR, 2019.

Thank you for your insightful comments and for recognizing the contribution of our work. Your feedback has been invaluable in enhancing the quality and clarity of our manuscript. We reply to the questions and weaknesses.

Q1&W1: Impact of heterogeneity

When the client‘s data distribution is highly heterogeneous, the theoretical result that activating one client per round yields the highest query efficiency in Fed-BDPL still holds. This is because the core intuition behind FedOne remains valid under such conditions: the query cost to the LLM increases linearly with the number of activated clients (since each activated client issues one query), while increasing K is not able to provide a linear speedup in convergence ([1, 2]).

We have also included an additional experiment to evaluate FedOne's performance under highly heterogeneous client distributions. Following prior works [3, 4], we simulated heterogeneity using a Dirichlet distribution with the concentration parameter $\alpha=0.1$, representing a highly non-IID setting. The result demonstrates that, even under highly non-IID conditions, activating a single client per round ($K_*=1$) still achieves the highest query efficiency, which is aligned with the theoretical result. The result figure can be found at this anonymous link ( https://anonymous.4open.science/r/ICML-Rebuttal-FedOne-649F/Converge3-High_Hetero.png )

We will include this experiment in Appendix C.

Q1: Potentially slow convergence

As demonstrated in [2], activating more clients per round under non-IID settings can improve the convergence rate, but it does not yield a linear speedup. By setting $K_*=1$ in FedOne, our approach intentionally trades off this marginal gain in convergence rate in favor of query efficiency.

However, the primary goal of our work is not to maximize convergence rate per round, but to identify an optimal query-efficient strategy within the Fed-BDPL framework that still guarantees convergence. Both our theoretical analysis and empirical results confirm that activating a single client per round achieves this objective, offering the best trade-off when considering the high cost and rate limits associated with querying cloud-based LLMs.

We will add a discussion of this trade-off in the Appendix to provide a more balanced view of the design choice.

Q2&W3: Adaptive strategy of $K_*$

Regarding the adaptive strategy, this work provides two key insights into the trade-off between the number of activated clients $K_*$, convergence speed, and query efficiency:

1. Increasing $K_*$ leads to higher query costs (scaling linearly with $K_*$) while yielding only sublinear improvements in convergence rate.
2. Reducing the number of activated clients K improves query efficiency but may result in slower convergence. Notably, setting $K_*=1$ achieves optimal query efficiency.

Our research provides the above principles for tuning $K_*$, enabling practitioners to adjust $K_*$ according to their specific system constraints and performance objectives.

Q3&W2: Uniform query cost assumption

We acknowledge that query costs may vary in practice due to factors like input length or client-specific characteristics. However, the uniform cost assumption allows us to simplify the theoretical analysis without significantly compromising realism.

Since clients are randomly selected at each round, variations in individual query costs are expected to average out over time. Even if we modeled client query costs as a distribution, the inherent randomness in selection would mitigate the overall impact. Therefore, the uniform cost assumption offers a practical balance between analytical tractability and real-world applicability.

We will add the above discussion to the manuscript.

References

[1] Haddadpour, Farzin, and Mehrdad Mahdavi. "On the convergence of local descent methods in federated learning." arXiv:1910.14425 (2019)

[2] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." ICLR 2020.

[3] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." NeurIPS 33 (2020): 2351-2363.

[4] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." ICML. PMLR, 2019.