From Apparent Search Gains to Selection Failures: Auditing Test-Time Inference in Structured Workflow Planning
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
| Model / Run | Procedure | Oracle | Selected | Gap | Filter | Vote | Tie | Tokens/task |
| GPT-4o-mini | IS | 139 | 121 | 18 | 0 | 18 | 0 | 238k |
| CoT-tree | 153 | 131 | 22 | 0 | 22 | 0 | 242k | |
| MO-Tree | 146 | 123 | 23 | 0 | 21 | 2 | 239k | |
| Prompt-matched IS † | 154 | 129 | 25 | 0 | 24 | 1 | 242k | |
| Qwen3.5-9B Control | Prompt-matched IS † | 160 | 127 | 33 | 0 | 32 | 1 | 253k |
| Qwen3.5-9B Run 1 | IS | 159 | 129 | 30 | 0 | 28 | 2 | 263k |
| Factor | Evidence in this study | Alignment principle |
|---|---|---|
| Generation scaffold | Prompt-matched independent sampling reaches CoT-tree-level Oracle coverage on GPT-4o-mini (154 versus 153) and Qwen3.5-9B (160 versus 162 and 157). | Match scaffolds or include a scaffold-matched sampling control. |
| Sampling controls | In a matched IS rerun, removing the fixed request seed increases distinct raw responses from 2.03 to 3.96 per task and distinct valid workflows from 1.60 to 2.32; Oracle changes from 133 to 139 ( ). | Apply decoding and seed policies symmetrically and distinguish matched controls from broader sensitivity checks. |
| Post-generation processing | On earlier fixed-seed pools, common normalization reduces CoT-tree invalidity from 27.4% to 2.9% and increases unfiltered-majority correctness from 104 to 118. On primary GPT-4o-mini pools, CoT-tree Oracle coverage increases from 145 to 153, while IS remains at 139. | Use a common audited normalization policy. |
| Backend realization | GPT-4o-mini reduces nominal multi-sample MO-Tree requests to single-sample updates, whereas Qwen realizes local aggregation. | Report realized rather than nominal branching. |
| Resource accounting | A pooled candidate set estimated at 232k tokens/task from its retained subset actually costs 414k once both source runs are counted, approximately the IS budget. | Count all inference contributing to the evaluated pool. |
| Selection interface | Generic and targeted LLM selectors do not reliably improve on majority selection. The targeted Top-3 verifier fixes 90 known errors but breaks 175 majority-correct decisions under unrestricted deployment; vote-margin gating removes most of this harm but yields no reliable gain. | Hold the primary selector fixed, preserve candidate-support information, and report selector sensitivity separately. |
Appendix figures & tables31 assets
Supplementary material from the paper’s appendix.
Appendix
| Model | Procedure | Calls/task | Retained/task | Tokens/task | Max output | Configuration |
|---|---|---|---|---|---|---|
| GPT-4o-mini | IS | 32.0 | 32.0 | 238k | 2048 | baseline prompt, no seed |
| GPT-4o-mini | Prompt-matched IS | 32.0 | 32.0 | 242k | 2048 | CoT-tree prompt, no seed |
| GPT-4o-mini | CoT-tree | 32.0 | 31.5 | 242k | 2048 | non-adaptive CoT expansion, no seed |
| GPT-4o-mini | MO-Tree | 30.5 | 12.7 | 239k | 2048 | five operators, no seed |
| Qwen3.5-9B | IS | 34.0 | 34.0 | 263k | 2048 | |
| Qwen3.5-9B | Prompt-matched IS | 34.0 | 34.0 | 253k | 2048 | CoT-tree prompt |
| Model | Condition | Oracle | Selected | Tokens/task | Unique valid | Winner share |
| GPT-4o-mini | CoT-tree | 153 | 131 | 242,476 | 4.22 | .769 |
| GPT-4o-mini | Prompt-matched | 154 | 129 | 242,193 | 4.09 | .770 |
| Qwen3.5-9B | CoT-tree R1 | 162 | 132 | 252,678 | 3.91 | .733 |
| Qwen3.5-9B | CoT-tree R2 | 157 | 133 | 252,445 | 4.01 | .740 |
| Qwen3.5-9B | Prompt-matched | 160 | 127 | 252,666 | 4.05 | .734 |
| Procedure | Sampling | Oracle | Selected | Retained/task | Unique valid/task | Winner share |
|---|---|---|---|---|---|---|
| IS | fixed seed | 133 | 121 | 32.0 | 1.60 | .925 |
| IS | no seed | 139 | 121 | 32.0 | 2.32 | .881 |
| CoT-tree | fixed seed | 144 | 118 | 23.0 | 3.22 | .806 |
| CoT-tree | no seed | 153 | 131 | 31.5 | 4.22 | .769 |
| MO-Tree | fixed seed | 150 | 117 | 12.8 | 4.82 | .555 |
| MO-Tree | no seed | 146 | 123 | 12.7 | 4.75 | .583 |
| ID | Transformation | Recoverability status | Primary protocol |
|---|---|---|---|
| E1 | Generated-reference canonicalization | Recoverable | Enabled |
| E2a | Dependence fields rebuilt from generated references | Recoverable | Enabled |
| E2b | Multi-predecessor dependency reduction | Information-losing | Disabled |
| E3 | Empty outputs filled from the tool manifest | Recoverable | Enabled |
| E4 | Manifest-assisted output-key correction | Semantic correction | Disabled |
| E5 | Non-object inputs reset to an empty map | Not recoverable; never triggered | Disabled |
| Method | Oracle E2b on | Oracle E2b off | Selected E2b on | Selected E2b off |
|---|---|---|---|---|
| Fixed-seed IS | 132 | 132 | 118 | 117 |
| CoT-tree | 144 | 144 | 120 | 118 |
| MO-Tree | 150 | 150 | 117 | 117 |
| Invalid (%) | Unfiltered Majority | |||
|---|---|---|---|---|
| Method | Original | Common | Original | Common |
| IS | 2.0 | 0.9 | 117 | 117 |
| CoT-tree | 27.4 | 2.9 | 104 | 118 |
| MO-Tree | 25.1 | 6.9 | 100 | 115 |
| Model / Run | Comparison | Metric | tasks | pp [95% CI] | McNemar |
|---|---|---|---|---|---|
| GPT-4o-mini | Prompt-IS IS | Oracle | +15 | +8.2 [+3.8, +13.1] | .0015 |
| GPT-4o-mini | Prompt-IS CoT-tree | Oracle | +1 | +0.5 [-3.3, +4.4] | 1.000 |
| GPT-4o-mini | CoT-tree IS | Oracle | +14 | +7.7 [+3.3, +12.6] | .0026 |
| GPT-4o-mini | MO-Tree IS | Oracle | +7 | +3.8 [-1.1, +8.7] | .210 |
| GPT-4o-mini | Prompt-IS IS | Selected | +8 | +4.4 [-1.1, +9.8] | .169 |
| GPT-4o-mini | Prompt-IS CoT-tree | Selected | -2 | -1.1 [-4.4, +1.6] | .727 |
| Procedure | Oracle | Selected | Oracle | Selected |
|---|---|---|---|---|
| IS | 135 | 117 | – | – |
| CoT-tree | 148 | 127 | +13 (.004) | +10 (.087) |
| MO-Tree | 142 | 119 | +7 (.210) | +2 (.860) |
| Model / Run | Procedure | Retained | Valid | Unique valid WF | Winning share | Ties |
| GPT-4o-mini | IS | 32.0 | 31.7 | 2.32 | .881 | 1 |
| GPT-4o-mini | Prompt-matched IS | 32.0 | 31.1 | 4.09 | .770 | 3 |
| GPT-4o-mini | CoT-tree | 31.5 | 30.6 | 4.22 | .769 | 5 |
| GPT-4o-mini | MO-Tree | 12.7 | 11.9 | 4.75 | .583 | 17 |
| Qwen Control | Prompt-matched IS | 34.0 | 33.5 | 4.05 | .797 | 5 |
| Qwen Run 1 | IS | 34.0 | 28.7 | 4.29 | .776 | 6 |
| MO width | Tokens/task | Calls/task | Retained | Valid | Unique WF | Oracle | Selected |
|---|---|---|---|---|---|---|---|
| Narrow | 285k | 33.6 | 7.3 | 6.2 | 2.67 | 147 | 122 |
| Medium | 376k | 42.7 | 10.1 | 8.6 | 2.90 | 148 | 122 |
| Original | 438k | 48.6 | 11.7 | 9.8 | 2.95 | 150 | 121 |
| Procedure | Oracle | Selected | Gap | Tok./task |
|---|---|---|---|---|
| IS + majority | 35 | 32 | 3 | 989k |
| MO-Tree + Random | 37 | 29 | 8 | 1,064k |
| MO-Tree + Active UCT | 35 | 31 | 4 | 979k |
| Rollout outcome | Active UCT | Random |
|---|---|---|
| No new nodes | 210 (32.8%) | 156 (24.4%) |
| Terminal CoT leaf revisits | 197 (30.8%) | 134 (20.9%) |
| New retained candidates | 310 (48.4%) | 326 (50.9%) |
| Retained candidates/task | 17.8 | 18.7 |
| Model / Run | Procedure | Vote loss | Rank 2 | Rank 3 | Selected | Top-2 | Top-3 | Oracle | |
|---|---|---|---|---|---|---|---|---|---|
| GPT-4o-mini | IS | 18 | 11 | 5 | 2 | 121 | 132 | 137 | 139 |
| CoT-tree | 22 | 10 | 2 | 10 | 131 | 141 | 143 | 153 | |
| MO-Tree | 21 | 13 | 3 | 5 | 123 | 138 | 141 | 146 | |
| Prompt-matched IS † | 24 | 13 | 6 | 5 | 129 | 143 | 149 | 154 | |
| Qwen3.5-9B Control | Prompt-matched IS † | 32 | 17 | 7 | 8 | 127 | 145 | 152 | 160 |
| Qwen3.5-9B Run 1 | IS | 28 | 17 | 7 | 4 | 129 | 148 | 155 | 159 |
| Model / Run | Procedure | Correct share mean | Vote deficit mean | Rank-2 deficit median | vote | votes |
| GPT-4o-mini | IS | .154 | 16.3 | 18 | 0 | 1 |
| CoT-tree | .147 | 8.1 | 5 | 2 | 4 | |
| MO-Tree | .219 | 2.2 | 2 | 7 | 15 | |
| Prompt-matched IS † | .162 | 10.0 | 7 | 1 | 4 | |
| Qwen3.5-9B Control | Prompt-matched IS † | .138 | 13.3 | 16 | 1 | 5 |
| Qwen3.5-9B Run 1 | IS | .169 | 11.0 | 10 | 1 | 1 |
| Type | Case | Selected divergence | Votes |
|---|---|---|---|
| Tool | GPT-4o-mini IS, Task 123 | Building_damage_assessment replaces Change_Mapping_and_Detection ; remaining steps match. | 22–2 |
| Dependency | GPT-4o-mini IS, Task 179 | Three independent image restorations are changed into a sequential restoration chain. | 20–11 |
| Sem. equiv. | Qwen3.5-9B IS, Task 41 | Two independent steps are reordered while preserving tools, arguments, and dependency edges. | 13–6 |
| Error Type | GPT-4o-mini | Qwen | Total |
|---|---|---|---|
| Tool | 17 | 18 | 35 |
| Dependency | 13 | 9 | 22 |
| Semantic Equivalent | 0 | 3 | 3 |
| Total | 30 | 30 | 60 |
| Correct-workflow rank | Tool | Parameter | Dependency | |
|---|---|---|---|---|
| Rank 2 | 151 | 29.8 | 0.0 | 2.6 |
| Rank 3 | 55 | 25.5 | 0.0 | 1.8 |
| Rank | 59 | 23.7 | 0.0 | 1.7 |
| All | 265 | 27.5 | 0.0 | 2.3 |
| Vote-margin group | Tool | Parameter | Dependency | |
|---|---|---|---|---|
| Low margin | 133 | 18.8 | 0.0 | 3.0 |
| High margin | 132 | 36.4 | 0.0 | 1.5 |
| Model / Run | IS–CoT | IS–MO | CoT–MO |
|---|---|---|---|
| GPT-4o-mini | 3/4 | 4/6 | 3/6 |
| Qwen Run 1 | 14/15 | 5/5 | 6/7 |
| Qwen Run 2 | 13/15 | 4/6 | 3/5 |
| Model / Run | Procedure | Primary | Unfiltered | Occurrence | Unique text | First valid | Tie upper bound |
|---|---|---|---|---|---|---|---|
| GPT-4o-mini | IS | 121 | 121 | 121 | 119 | 119 | 121 |
| CoT-tree | 131 | 129 | 130 | 131 | 112 | 131 | |
| MO-Tree | 123 | 122 | 123 | 123 | 104 | 125 | |
| Qwen Run 1 | IS | 129 | 129 | 129 | 128 | 121 | 131 |
| CoT-tree | 132 | 132 | 127 | 132 | 122 | 134 | |
| MO-Tree | 122 | 122 | 127 | 122 | 114 | 128 |
| Model / Run | Procedure | Primary | GPT-4o judge | Tie upper bound | Oracle |
|---|---|---|---|---|---|
| GPT-4o-mini | IS | 121 | 123 | 121 | 139 |
| CoT-tree | 131 | 112 | 131 | 153 | |
| MO-Tree | 123 | 112 | 125 | 146 | |
| Qwen Run 1 | IS | 129 | 110 | 131 | 159 |
| CoT-tree | 132 | 114 | 134 | 162 | |
| MO-Tree | 122 | 128 | 128 | 147 |
| Model / Run | Procedure | Majority | Verifier | Fixed | Broken | Net | McNemar |
|---|---|---|---|---|---|---|---|
| GPT-4o-mini | IS | 121 | 123 | 11 | 9 | +2 | .820 |
| GPT-4o-mini | CoT-tree | 131 | 113 | 3 | 21 | -18 | |
| GPT-4o-mini | MO-Tree | 123 | 108 | 12 | 27 | -15 | .024 |
| Qwen Run 1 | IS | 129 | 116 | 9 | 22 | -13 | .029 |
| Qwen Run 1 | CoT-tree | 132 | 117 | 11 | 26 | -15 | .020 |
| Qwen Run 1 | MO-Tree | 122 | 121 | 12 | 13 | -1 | 1.000 |
| Statistic | Fixes (90) | False overrides (175) |
|---|---|---|
| Median normalized margin | 0.258 | 0.500 |
| Median winner vote share | 0.556 | 0.700 |
| Median valid groups | 3 | 4 |
| Chosen rank 2 | 84.4% | 64.6% |
| Chosen rank 3 | 15.6% | 35.4% |
| More steps than majority | 27.8% | 52.6% |
| Margin bin | Majority correct | Broken | Break rate (%) | Fixed | Net |
|---|---|---|---|---|---|
| 51 | 22 | 43.1 | 21 | -1 | |
| 39 | 9 | 23.1 | 16 | +7 | |
| 60 | 18 | 30.0 | 15 | -3 | |
| 94 | 28 | 29.8 | 20 | -8 | |
| 394 | 98 | 24.9 | 18 | -80 |
| Threshold | Routed | Changed | Fixed | Broken | Net | Selected | McNemar |
|---|---|---|---|---|---|---|---|
| 0 | 92 | 49 | 10 | 9 | +1 | 1142 | 1.000 |
| .05 | 114 | 65 | 13 | 13 | 0 | 1141 | 1.000 |
| .10 | 190 | 118 | 22 | 24 | -2 | 1139 | .880 |
| .15 | 243 | 147 | 31 | 27 | +4 | 1145 | .690 |
| .20 | 321 | 178 | 37 | 34 | +3 | 1144 | .810 |
| .30 | 437 | 231 | 53 | 51 | +2 | 1143 | .920 |
| Pool | Correct votes | Wrong-dep. votes | Result |
|---|---|---|---|
| IS | 7 | 25 | Wrong |
| Prompt-matched IS | 29 | 1 | Correct |
| CoT-tree | 28 | 2 | Correct |
| MO-Tree | 4 | 3 | Correct |
| Factor | How it arises | How to detect it | Observed effect in this study | Alignment principle |
|---|---|---|---|---|
| Generation scaffold | Nominally different inference procedures use different prompts, reasoning instructions, or expansion templates. | Reproduce the generation scaffold with independent sampling while holding decoding, budget, and downstream evaluation fixed. | Prompt-matched IS reaches CoT-tree-level Oracle coverage on GPT-4o-mini (154 versus 153) and lies within the two Qwen CoT-tree runs (160 versus 162 and 157) (Appendix C.1.1 ). | Match scaffolds or include a scaffold-matched sampling control. |
| Sampling controls | Request seeds and other sampling settings can alter response diversity under repeated or identical prompts. | Use matched reruns where possible and distinguish controlled seed effects from broader sampling-sensitivity comparisons. | In a matched IS rerun, removing the fixed request seed increases distinct raw responses from 2.03 to 3.96 and unique valid workflows from 1.60 to 2.32 per task; Oracle changes from 133 to 139 ( ) (Appendix C.6 ). | Apply sampling controls symmetrically and distinguish matched controls from broader sensitivity checks. |
| Post-generation processing | Candidate pools receive different repair, normalization, or semantic-correction rules. | Re-extract raw outputs and reevaluate all procedures through one common transformation pipeline. | On the primary GPT-4o-mini pools, the common recoverable normalization raises CoT-tree Oracle from 145 to 153 while leaving IS unchanged at 139. On earlier fixed-seed pools, procedure-specific processing yields 27.4% CoT-tree invalidity versus 2.9% under the common policy, and unfiltered-majority correctness rises from 104 to 118 (Appendix D ). | Use one audited normalization policy and separate recoverable canonicalization from semantic correction. |
| Backend realization | Serving systems may not realize requested multi-sample or branching parameters. | Audit returned completions and execution logs rather than relying on nominal hyperparameters. | GPT-4o-mini returns one completion for nominal requests, whereas Qwen realizes MO-Tree’s configured local multi-sample aggregation (Appendix C.3 ). | Report realized branching and avoid treating backend differences as model-only effects. |
| Resource accounting | Retained candidates may represent only part of the inference used to construct a trajectory or pooled candidate set. | Sum all model calls and tokens contributing to the evaluated pool, including generations later discarded or aggregated. | An exploratory pooled configuration was initially estimated at approximately 232k tokens per task from its retained subset, but full accounting across its contributing runs yields approximately 414k tokens per task, about the IS budget (Appendix C.5 ). | Account for full realized inference cost rather than retained-pool size. |
| Selection interface | Different selectors observe different multiplicities, subsets, or representations of the candidate pool. | Reevaluate fixed pools with alternative deterministic selectors and explicitly specified verifier interfaces. | Deterministic selector variants are largely stable, but model-based selectors do not reliably improve on majority selection. The targeted Top-3 verifier fixes 90 majority errors while breaking 175 correct majority decisions under unrestricted deployment; vote-margin gating removes most of this degradation but yields no reliable improvement (Appendix G.4 ; Appendix G.5 ). | Hold the selector fixed for primary comparisons, preserve candidate-support information, and report selector sensitivity separately. |
| Work | (a) | (b) | (c) | (d) | (e) | (f) | (g) | (h) |
|---|---|---|---|---|---|---|---|---|
| ToT / RAP / HiAR-style search ( Yao et al., 2023 ; Hao et al., 2023 ; Wu et al., 2024 ) | ||||||||
| Budget-aware reasoning comparison ( Wang et al., 2024 ) | ||||||||
| System-level test-time scaling ( Hariri et al., 2026 ) | ||||||||
| Discriminator-dependent tree search ( Chen et al., 2024 ) | ||||||||
| Repeated-sampling coverage ( Brown et al., 2024 ) | ||||||||
| Candidate generation and verification ( Liu et al., 2025 ) |
Inference-Time Search
Inference-time search uses extra computation at deployment to explore, score, and select candidate reasoning paths or actions without retraining a model.
See all 109 papers