Toward a Principled Framework for Measuring Agent Safety

The paper proposes that agent safety should be measured by search rather than sampling, and presents the BOA framework, which found unsafe trajectories missed by greedy and sampling evaluations on agent safety workloads. The paper states that existing safety evaluations only run greedy or a small number of sampled trajectories and report a single safe or unsafe rate, failing to see long-tail trajectories where low-probability actions may trigger unsafe behavior. Given a deployment configuration (model, decoder, prompt, environment, judge, likelihood budget), BOA searches the trajectory space within the budget and outputs a safety score, i.e., the probability that the agent remains safe under that configuration; the search covers both single-turn LLM internals and the agent-environment interaction tree, and controls computational cost through batched decoding and judging, prefix caching, and chunked tree expansion. BOA can also be used to rank models, defenses, and attacks on the same scale, with controllable GPU cost.