Risk-Sensitive Agent Compositions

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

Why this paper was selected

ICLR; formalizes agentic workflows as DAGs; risk-sensitive composition with safety guarantees

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Agentic workflows that compose multiple specialized AI agents must minimize not just task failure but also tail-risk violations of safety, fairness, and privacy requirements. This paper formalizes agent compositions as directed acyclic graphs and introduces BucketedVaR, a dynamic-programming algorithm that finds the risk-optimal composition by efficiently approximating Value-at-Risk (\(\text{VaR}_\alpha\)) via union-bound budget allocation. The algorithm runs in \(O(n(d+1)^2|V|^2)\) time and is proven near-optimal asymptotically under agent-loss independence.

Problem

Existing agentic workflow selection optimizes expected task success but ignores low-probability, high-consequence tail behaviors (safety violations, hallucination spikes, unfair resource use). Naive enumeration of all feasible compositions is intractable—an agent graph can have exponentially many paths. Prior risk-sensitive planning literature addresses cumulative loss in MDPs, not the maximum loss across sequential agents, which is the natural objective for safety/fairness/privacy.

Method

Agent graph formalization. A workflow is a DAG \(G = (V, E, X, T, F, L, s, t, D_s)\) where each edge carries an agent \(f_e\) and a loss function \(L_e\); a path from source \(s\) to target \(t\) is a feasible composition. The composed loss is \(L_p(t_1,\ldots,t_m) := \max_i L_{e_i}(t_i)\) (max, not sum).

RMAG objective. Find \(\arg\min_{p \in P}\, \rho[L_p(Z_p)]\) for \(\rho \in \{\text{VaR}_\alpha, \text{CVaR}_\alpha\}\).

BucketedVaR. The key insight is the union-bound decomposition: $\(\text{VaR}_\alpha[\max(R_1,\ldots,R_m)] \leq \max_i\{\text{VaR}_{\alpha_i}[R_i]\} \quad \text{when } \textstyle\sum_i \alpha_i = \alpha.\)$ The algorithm discretizes the risk budget into \(d+1\) buckets \(B = \{0, \tfrac{\alpha}{d}, \tfrac{2\alpha}{d}, \ldots, \alpha\}\) and processes vertices in topological order. For each vertex \(v\) and budget \(\bar\alpha \in B\), it finds the predecessor \(v'\) and sub-budget \(\alpha' \leq \bar\alpha\) that minimizes \(\max(\text{VaR}[v', \alpha'],\, \text{quantile}(\text{edge losses}, 1-(\bar\alpha-\alpha')))\). CVaR is recovered as a Riemann sum over the stored VaR estimates: \(\text{CVaR}_\alpha \approx \tfrac{1}{d}\sum_{k=1}^d \text{VaR}_{k\alpha/d}\).

Key Contributions

• Formal DAG model of agentic workflows with per-edge loss functions encoding safety/fairness/privacy (decoupled from task accuracy).
• BucketedVaR algorithm: polynomial-time (\(O(n(d+1)^2|V|^2)\)) DP that finds near-optimal VaR-minimizing agent composition.
• Theorem 1: with probability \(\geq 1-\delta\), the estimated VaR lower-bounds the true path quantile at level \(1-\alpha-\gamma\), where \(\gamma \to 0\) as \(n \to \infty\).
• Theorem 2: asymptotically (under agent-loss independence), the returned path is optimal up to an additive \(\alpha^2/2\) shift in quantile level.
• CVaR approximation as a byproduct with no additional sampling cost.
• Empirical validation on RL-based compositional control benchmarks (safety navigation, fair resource consumption).

Results

• BucketedVaR produces tight approximations of both \(\text{VaR}_\alpha\) and \(\text{CVaR}_\alpha\) across all tested benchmarks (16-Rooms, Fetch, BoxRelay).
• The algorithm successfully identifies the optimal agent composition in all benchmarks.
• Algorithm is robust to moderate correlation between agent losses (empirically validated; independence is only required for the asymptotic optimality guarantee, not validity).
• Specific headline numbers are cut off in the provided text (Figure 2 describes absolute quantile difference percentages, but values are truncated).

Limitations

• Independence assumption: near-optimality guarantee (Theorem 2) requires agent losses to be independent random variables; correlated losses weaken the bound.
• Black-box sampling: requires rollout access to each agent, which may be expensive for large LLM-based agents.
• Discretization error: budget bucketing introduces \(O(\alpha/d)\) granularity; finer \(d\) increases runtime quadratically.
• Max-loss composition: the framework assumes the composition loss is the max of individual losses, which suits safety/fairness but not all multi-objective settings.
• RL-only benchmarks: evaluation uses RL-trained control policies; generalization to LLM-agent pipelines is illustrated by example but not empirically benchmarked.

Relevance to Harnesses / Meta-Harnesses

This paper provides a formal foundation for risk-aware meta-harness design: when a harness selects among alternative agent pipelines (e.g., different tool chains, retrieval strategies, or sub-agent orderings), BucketedVaR offers a principled way to choose the composition that minimizes worst-case safety or quality violations rather than just expected performance. The agent-graph abstraction directly mirrors the DAG structure used in modern meta-harnesses to represent workflow alternatives. The result that CVaR is a byproduct of VaR optimization is practically valuable—harness schedulers can obtain both a tail-risk bound and an expected-shortfall estimate with a single pass. The independence-of-losses condition is often approximately satisfied in harnesses where sub-agents operate on disjoint data or tool namespaces, making the optimality guarantee applicable to realistic deployments.