Security-Constrained Prompt Optimization Under Partial Observation

This paper develops a fixed-budget best-prompt identification algorithm for selecting the highest quality prompt of a given task for large language models (LLMs), under the constraints of various quality and security measures. Specifically, the selected prompt needs to satisfy a security constraint against attacks such as indirect prompt injection, which inserts malicious instructions in documents to redirect a language model away from its intended task. The inclusion of the security constraint fundamentally changes prompt evaluation, as an attacked response does not estimate clean-task performance, and a clean response provides no evidence of security. Thus each pull reveals only part of the objective vector. The resulting security-induced partial observation differs from conventional best-arm identification, where each pull reveals all objectives. We formulate this setting as a fixed-budget best-feasible prompt identification problem, and solve it by using a new Guaranteed-Floor Constrained Successive Rejects (GF-CSR) algorithm. GF-CSR adopts a reward-independent two-phase schedule that front-loads attacked pulls until surviving prompts obtain a prescribed security-evidence floor, then shifts sampling toward clean objectives. Under bounded independent rewards and explicit separation conditions, we prove that GF-CSR identifies the unique best feasible prompt with high probability while accounting for bias from incomplete cycles through the attack suite. Experiment results on real-world datasets with indirect prompt injection attacks demonstrate that GF-CSR outperforms baseline algorithms such as partial observation CSR (PO-CSR) and the Uniform algorithm.