cs.CLOct 31, 2026

From Apparent Search Gains to Selection Failures: Auditing Test-Time Inference in Structured Workflow Planning

Authors: Zhitong Chen, Weifeng Zhang, Kai Yin, Zhiyuan Wang, Ali Mostafavi, James Caverlee

Organizations: Texas A&M University

Abstract

Test-time search can improve structured planning, but when methods differ in prompts, post-processing, and selection, it is unclear what an observed gain should be attributed to. We study this question on DisasterBench, where models compose typed multi-tool workflows, by decomposing inference into three observable stages: whether a correct workflow is discovered, whether it survives structural validation, and whether it is finally selected. Comparing independent sampling, a nominal tree-search configuration, and multi-operator search under controlled inference budgets on two model families, we find that (i) the nominal tree-search configuration realizes non-adaptive complete-workflow sampling, and independent sampling with its expansion prompt reproduces its candidate discovery without constructing a tree; (ii) structural validation never removes the last correct workflow in our evaluated candidate pools, whereas majority voting leaves a discovered correct workflow unselected on 10-19% of tasks per pool, with an audit confirming substantive tool-choice or information-flow errors in 57 of 60 examined cases; and (iii) a tool-specification-aware verifier recovers some of these losses but overturns more correct decisions than it fixes. Our results motivate auditing realized rather than nominal inference pipelines, and reporting discovery, validity, and selection separately.

Figures & tables

Appendix figures & tables31 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Selection-Aware Stress Testing for Interactive Agents

    Aug 31, 2026Yang Xu, Chenang Li, Jiefu Zhang +3AI Agent EvaluationMultiple Hypothesis Testing

  2. DisasterBench: Benchmarking LLM Planning under Typed Tool Interface Constraints

    May 27, 2026Zhitong Chen, Kai Yin, Weifeng Zhang +7Tool-Use PlanningAI Agent Benchmarks