The in-context learning paradigm with LLMs has been instrumental in advancing a wide range of natural language processing tasks. The selection of few-shot examples (exemplars / demonstration samples) is essential for constructing effective prompts under context-length budget constraints. In this paper, we formulate the exemplar selection task as a top-m best arms identification problem. A key challenge in this setup is the exponentially large number of arms that need to be evaluated to identify the m-best arms. We propose CASE (Challenger Arm Sampling for Exemplar selection), a novel sample-efficient selective exploration strategy that maintains a shortlist of “challenger” arms, which are current candidates for the top-m arms. In each iteration, only one of the arms from this shortlist or the current top-m set is pulled, thereby reducing sample complexity and, consequently, the number of LLM evaluations. Furthermore, we model the scores of exemplar subsets (arms) using a parameterized linear scoring function, leading to stochastic linear bandits setting. CASE achieves remarkable efficiency gains of up to 7$\times$ speedup in runtime while requiring 7$\times$ fewer LLM calls (87% reduction) without sacrificing performance compared to state-of-the-art exemplar selection methods. We release our code and data (https://github.com/kiranpurohit/CASE).

Federated Learning systems are increasingly subjected to a multitude of model poisoning attacks from clients. Among these, edge-case attacks that target a small fraction of the input space are nearly impossible to detect using existing defenses, leading to a high attack success rate. We propose an effective defense using an external defense dataset, which provides information about the attack target. The defense dataset contains a mix of poisoned and clean examples, with only a few known to be clean. The proposed method, DataDefense, uses this dataset to learn a poisoned data detector model which marks each example in the defense dataset as poisoned or clean. It also learns a client importance model that estimates the probability of a client update being malicious. The global model is then updated as a weighted average of the client models’ updates. The poisoned data detector and the client importance model parameters are updated using an alternating minimization strategy over the Federated Learning rounds. Extensive experiments on standard attack scenarios demonstrate that DataDefense can defend against model poisoning attacks where other state-of-the-art defenses fail. In particular, DataDefense is able to reduce the attack success rate by at least ∼ 40% on standard attack setups and by more than 80% on some setups. Furthermore, DataDefense requires very few defense examples (as few as five) to achieve a near-optimal reduction in attack success rate.

Kiran Purohit, Venktesh V, Raghuram Devalla, Krishna Mohan Yerragorla, Sourangshu Bhattacharya, Avishek Anand. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.