AdvPlan-Bench: Adversarial Evaluation of Structured Plan-Generation Agents

Technical Summary: AdvPlan-Bench

Problem Formulation
Current evaluations of plan-generation agents often assess a candidate plan in isolation, focusing on whether it produces a plausible final answer, valid tool traces, or executable sequences. However, in adversarial settings, a plan's quality is not intrinsic; it depends on how an opposing agent searches for responses, which constraints are emphasized, and whether the candidate set contains meaningful alternatives. Existing benchmarks (e.g., BIG-bench, HELM, AgentBench) typically evaluate task completion or tool correctness against static answer keys or fixed environments. They often fail to capture the robustness of a plan when subjected to an adaptive opponent or to analyze the structure of the candidate frontier (diversity, Pareto optimality) and the trace-level reasoning behind selection.

Methodology: AdvPlan-Bench
AdvPlan-Bench is an offline, synthetic benchmark designed to evaluate structured plan-generation agents through an adversarial lens. It treats the evaluation object not as a single prompt-response pair, but as a tuple $(s, c_B, C_R, U, D)$, comprising a scenario, a BLUE structured plan, a set of RED adversarial responses, a utility-like advantage signal, and diagnostic traces.

• Representation: Plans are represented as typed action chains with optional conditional branches, role assignments, and tool-call slots. Each plan receives a synthetic quality score $q = w_e e - w_c c - w_r r$ (effectiveness, cost, risk).
• Adversarial Setup:
  • BLUE Policy: Generates a structured candidate plan $c_B$.
  • RED Policy: Generates a set of responses $C_R = \{c^1_R, \dots, c^k_R\}$ conditioned on the scenario and $c_B$.
  • Selection: A selector evaluates candidates using a scoring function $S(b_i)$ that balances rescaled quality ($Q$), constraint alignment ($D$), candidate diversity ($V$), and adversarial pressure ($P$).
• Evaluation Axes: The benchmark tracks six axes rather than a single aggregate score:
  1. Representation Validity: Inspectability of typed plan objects.
  2. Plan Structure: Metrics like path optionality, vertex parsimony, and worldline completion.
  3. Adversarial Robustness: How BLUE quality changes as RED's response budget ($k$) increases.
  4. Frontier Quality: Diversity and Pareto-nondominated alternatives within candidate sets.
  5. Constraint-Sensitive Selection: The trade-off between synthetic quality and qualitative structure.
  6. Trace Reproducibility: The ability to regenerate results from per-scenario artifacts.
• Baselines & Controls: The study compares single-sample RED responses against sampled best-response policies (quality-greedy and constraint-aware), an offline LLM-policy contract baseline, and a two-stage multi-agent council (generate, stress-test, revise, adjudicate).

Key Contributions

1. Formal Adversarial Setup: A framework where structured candidates are evaluated against sampled response sets rather than fixed answer keys.
2. Reproducible Offline Benchmark: A system providing typed plan traces, BLUE/RED policy comparisons, constraint-coherence diagnostics, response-budget curves, and Pareto-frontier analysis.
3. Empirical Evidence: Data from 150 synthetic scenarios across five planning templates (urban stability, maritime interdiction, multi-domain coordination, air-defense suppression, humanitarian evacuation) demonstrating how adversarial sampling and multi-agent critique alter win-rate and plan-quality conclusions.
4. Benchmark Development Finding: A demonstration that scenario framing variables must be wired into generated content to have an effect; otherwise, framing changes result in a "silent no-op."

Results

• Adversarial Impact: Increasing the RED response budget from a single sample ($k=1$) to eight samples ($k=8$) reduces the BLUE advantage from 0.518 to 0.486 and the BLUE win rate from 0.900 to 0.820.
• Candidate Diversity: Sampled RED candidate sets exhibit nontrivial variation, with mean action-type diversity of 0.681 and an average of 2.17 Pareto-optimal candidates per set of eight.
• Baseline Performance:
  • The offline LLM-policy baseline achieves a BLUE advantage of 0.496 and a win rate of 0.700, with RED constraint coherence reaching 1.000.
  • The two-stage multi-agent council improves BLUE performance relative to strong RED search, achieving a BLUE advantage of 0.509 and a win rate of 0.813. In 75.3% of scenarios, the final selected plan comes from the revised set.
• Rubric Sensitivity: A study with three independent raters over 600 records showed a 0.978 inter-rater agreement, indicating the heuristic rubric is not brittle to small scoring perturbations.
• Framing Sensitivity: When the generator was patched to use scenario framing to modify objectives, the measured sensitivity delta became 0.066, confirming that framing must be active in generation to influence outcomes.

Significance and Claims
The paper positions AdvPlan-Bench as a methodological contribution rather than an operational decision architecture or a new self-play learning algorithm. Its significance lies in:

• Granularity: Shifting the evaluation unit from a prompt-response pair to a structured adversarial trace, allowing researchers to inspect the "candidate frontier" and the stability of plans under increased adversarial pressure.
• Reproducibility: Providing a transparent artifact where assumptions (e.g., synthetic quality scores, constraint heuristics) are inspectable before moving to live models or real-world data.
• Diagnostic Capability: Exposing silent failures in benchmark design (e.g., the framing no-op) and distinguishing between genuine repair effects and scoring artifacts in multi-agent systems.

The authors explicitly state that AdvPlan-Bench is not an operational planner, does not use real-world data, and should not be used for real-world decision-making. It serves as a controlled testbed for studying adversarial plan evaluation, response-budget sensitivity, and multi-agent critique-and-revision traces.