Risk-Sensitive Agent Compositions¶

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Formal DAG model composing specialized agents with risk-sensitive workflow guarantees

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper formalizes agentic workflows as directed acyclic graphs (agent graphs) and addresses the problem of selecting agent compositions that minimize tail-risk measures—value-at-risk ($\text{VaR}_\alpha$) and conditional value-at-risk ($\text{CVaR}_\alpha$)—over safety, fairness, and privacy loss functions. The authors introduce BucketedVaR, a polynomial-time dynamic programming algorithm that allocates a risk budget across agents using a union bound, and prove it is asymptotically near-optimal under agent independence. Experiments on compositional RL benchmarks confirm tight approximations of both risk measures.

Problem¶

Existing agentic workflow literature optimizes expected task success, ignoring low-probability, high-consequence (tail) behaviors that arise from composing stochastic agents. Prior risk-sensitive planning work minimizes cumulative loss in MDPs, but for safety/fairness/privacy the relevant quantity is the maximum loss across agents in a composition—a structurally different objective. Naively enumerating all paths in an agent graph is exponential in the number of agents, making direct search intractable.

Method¶

Agent graph formalism: A directed acyclic graph $G = (V, E, \mathcal{X}, \mathcal{T}, F, L, s, t, D_s)$ where edges represent agents and paths represent feasible sequential compositions. The composed loss over a path $p = (e_1, \ldots, e_m)$ is: $$L_p(t_1,\ldots,t_m) := \max_i \{L_{e_i}(t_i)\}$$ The objective (RMAG) is $\arg\min_{p \in P}\, \rho[L_p(Z_p)]$ for $\rho \in \{\text{VaR}_\alpha, \text{CVaR}_\alpha\}$.

BucketedVaR algorithm: A dynamic programming algorithm that processes vertices in topological order. At each vertex $v$ and discretized risk budget $\bar\alpha \in B = \{0, \tfrac{\alpha}{d}, \tfrac{2\alpha}{d}, \ldots, \alpha\}$, it finds the predecessor $v'$ and budget split $\alpha'$ minimizing: $$\text{pathVaR} = \max(\text{VaR}[v', \alpha'],\; \text{quantile}(\text{losses}_{v'\to v},\, 1 - (\bar\alpha - \alpha')))$$ This exploits the union bound: $\text{VaR}_\alpha[\max(R_1,\ldots,R_m)] \leq \max_i \text{VaR}_{\alpha_i}[R_i]$ when $\sum_i \alpha_i = \alpha$.

CVaR recovery: $\text{CVaR}_\alpha \approx \frac{1}{d}\sum_{k=1}^d \text{VaR}_{k\alpha/d}$, recovered as a byproduct from the buckets already computed.

Time complexity: $O(n(d+1)^2|V|^2)$ where $n$ is sample size and $d$ is discretization factor.

Key Contributions¶

Formal definition of the RMAG objective: minimize VaR/CVaR of the maximum agent loss over feasible compositions in an agent graph.
BucketedVaR: a polynomial-time DP algorithm with union-bound-based quantile estimation and optimal risk-budget allocation over $d+1$ discretized levels.
Theorem 1 (validity): With probability $\geq 1-\delta$, the returned estimate $q \geq \text{quantile}(L_p(Z_p), 1-\alpha-\gamma)$ with $\gamma = O(|V|/\sqrt{n})$ vanishing as $n \to \infty$.
Theorem 2 (near-optimality): Under agent loss independence, asymptotically $q \leq \text{quantile}(L_{p^*}(Z_{p^*}), 1 - \alpha + \alpha^2/2)$—suboptimal by an additive $\alpha^2/2$ in quantile level.
CVaR approximation as a free byproduct of the VaR computation.
Empirical validation on compositional RL benchmarks (16-Rooms navigation, Fetch manipulation, BoxRelay resource consumption).

Results¶

BucketedVaR produces tight approximations of $\text{VaR}_\alpha$ on all benchmarks; absolute quantile difference between estimated and true VaR is small (specific percentages are in Figure 2, which is truncated in the provided text).
The algorithm successfully identifies the optimal agent composition on safety-critical navigation (16-Rooms, DroneNav variant) and fair resource consumption (BoxRelay) tasks.
CVaR approximations recovered from the same computation are similarly tight.
Algorithm is robust to a "reasonable amount of correlation" between agent losses, despite the independence assumption in the theoretical guarantee.

Limitations¶

Independence assumption required for near-optimality (Theorem 2) may not hold when agents share environment state or when one agent's output distribution depends on another's trace quality.
Risk budget discretization introduces an approximation gap controlled by $d$; larger $d$ improves accuracy but increases runtime quadratically.
Experiments are limited to RL control benchmarks; performance on LLM-agent pipelines with stochastic, high-dimensional trace spaces is not empirically validated.
The union bound is generally loose; near-optimality guarantee is asymptotic and the finite-sample suboptimality bound ($\alpha^2/2$) may be vacuous for large $\alpha$.
Assumes black-box sampling access to agents at inference time, which may be costly for large LLMs.

Relevance to Agentic AI / LLM Agents¶

This work provides a formal, theoretically grounded framework for safe agent orchestration—a critical gap as multi-agent LLM systems (software dev pipelines, retrieval chains, robot control) are deployed in high-stakes settings where tail failures in safety, fairness, or privacy matter more than average-case performance. The agent graph abstraction is directly applicable to LLM pipelines: edges can represent LLM agents with hallucination or privacy-leakage loss functions, as illustrated by the information retrieval example. The shift from expected-loss to VaR/CVaR optimization addresses a known blind spot of RLHF-trained agents, which optimize expected reward and can exhibit catastrophic low-probability behaviors. For researchers building or evaluating agentic systems, BucketedVaR offers a practical, polynomial-time selection algorithm that requires only black-box sampling—compatible with closed-source LLM APIs.