PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Harness Search: Building Multi-Agent Systems Per-Query via Prediction

Som Sagar, Shasha Li, Hejie Cui, Ransalu Senanayake, Sercan Ö. Arık

arXiv:2610.04137v1cs.LG

TL;DR

Evaluating alternative harness designs for each query is costly, even though the useful agent, instruction, and tool choices depend on the query. SHIFT uses a learned architect and utility predictor to search for a harness before execution, and achieves the highest mean accuracy across six benchmarks among 17 baselines.

  • Problem

    Harness components interact and their value depends on the query and the rest of the design, while evaluating alternatives through execution adds cost.

    Source: §1 · p. 1

  • Method

    SHIFT uses a local architect to propose harness-building actions and predict utility, while Monte Carlo tree search constructs a query-specific harness without executing candidates.

    Source: §1 · p. 2

  • Results

    79.9% mean accuracy makes SHIFT-search the highest-accuracy method across six benchmarks, exceeding the strongest baseline by 7.2 percentage points.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Jointly choosing agents, instructions, and tools beats choosing any one alone, and learned value selection identifies accurate, low-cost harnesses.

    Source: §1 · p. 2

Abstract

from arXiv · show

Agent harnesses specify the roles, instructions, tools, and communication structure used to solve a task, and the right harness depends on the query. Because the value of each design choice is observable only through execution, tailoring a harness to each query has required either executing alternatives at inference time or costly manual design. We introduce SHIFT, which moves execution out of the per-query search loop. A local LLM architect learns a policy over harness-building actions from search, and a value function that predicts, from measured executions, a utility balancing accuracy against execution cost. For each query, Monte Carlo tree search uses these predictions to construct a harness. Across 9,193 tasks in six benchmarks, from math to document and general-assistant tasks, with a Gemini 3.5 Flash executor, SHIFT attains the highest mean accuracy, about 80%, outperforming 17 baselines that span prompting, prompt optimization, and workflow search, and exceeding the strongest baseline by 7.2 percentage points. A cheaper mode of SHIFT also attains a higher mean accuracy than every baseline while using 32% fewer execution tokens than the strongest baseline. We further show that choosing structure, instructions, and tools jointly beats choosing only instructions or only tools by up to 9.1 percentage points, and that learned value selection identifies more accurate harnesses with lower execution cost from candidate pools.

1. Introduction

Harness design must adapt to each query while balancing task capability against execution cost. SHIFT searches query-specific designs before execution, and its benchmark evaluation reports higher mean accuracy than the baselines.

1. Introduction

  • Harness choices interact, making component value depend on both the query and the rest of the design, while evaluating alternatives through execution adds cost.Existing methods optimize reusable workflows, instructions within fixed programs, or query-adaptive compositions and routing.Source: §1 · pp. 1–2
  • A fixed Reader and Solver can waste structure on a simple lookup and still miss calculations, while query-tailored harnesses answer all three illustrated requests correctly.The examples use a single reader for lookup, a reader with a verifier loop for a total, and a reader and verifier with Python for growth rate.Source: Figure 1 · p. 2
  • SHIFT uses a local architect and Monte Carlo tree search to construct each query’s harness without executing candidate designs during search.The architect proposes harness-building actions and predicts utility balancing accuracy against execution cost; only the selected harness is executed at inference.Source: §1 · p. 2
  • 79.9% mean accuracy makes SHIFT-search the top method across six benchmarks, exceeding the strongest baseline by 7.2 percentage points.The largest gains are on OfficeQA and GAIA, at 30.0 and 15.0 percentage points over that baseline, respectively.Source: §1 · p. 2
  • 74.5% mean accuracy lets SHIFT-value exceed every baseline while using 32% fewer execution tokens than the strongest baseline.SHIFT-value selects harnesses using predicted utility.Source: §1 · p. 2
  • Jointly choosing agent structure, instructions, and tools beats choosing any one alone, and the learned architect selects accurate, low-cost harnesses that transfer to harder tasks.The evaluation spans six benchmarks and uses a shared executor against 17 baselines.Source: §1 · p. 2

2. Related Work

Related work improves agent reasoning and prompts, optimizes workflows, and adapts composition or routing to queries. SHIFT distinguishes itself by jointly searching harness choices with learned utility estimates before executing candidates.

Reasoning and prompt optimization

  • Reasoning methods organize tool use, feedback, or intermediate solutions, while prompt optimization tunes instructions within a fixed program; SHIFT searches the harness’s interacting choices jointly.The reviewed approaches include ReAct, Self-Refine, Tree of Thoughts, Graph of Thoughts, and prompt optimizers such as DSPy, MIPRO, and GEPA.Source: §2 · p. 3

Workflow optimization and surrogate evaluation

  • Workflow optimization uses execution feedback to revise designs, while SHIFT trains a local utility predictor on executed harnesses to guide per-query tree search without executing candidates at inference.AgentSquare uses an LLM performance predictor for module recombinations, but newly evolved modules are still evaluated by execution in the task environment Shang et al. (2025).Source: §2 · p. 3

Query-adaptive composition and routing

  • Routers and controllers adapt model or workflow choices to queries; SHIFT adds lookahead over agent, instruction, and tool choices using a learned action policy and utility predictor.Lookahead considers how an action affects the harness built by subsequent actions.Source: §2 · p. 3

3. Methodology

SHIFT constructs a query-specific executable harness by searching over agent, instruction, and tool actions with learned architect predictions, then executes only the selected design.

3. Methodology

  • SHIFT uses architect policy and utility predictions to guide MCTS over harness-building actions, then executes only the selected harness.The architect learns from search decisions and measured execution outcomes during training.Source: §3 · p. 3, Figure 2 · p. 4

3.1. Harnesses as Executable Graphs

  • Harnesses are executable directed graphs of agents, directives, permitted tools, and handoffs, letting one search space cover workflows while excluding invalid structures.Actions can add agents, feedback edges, directives, or tool permissions; their benefits vary across tasks, with financial-document questions favoring larger harnesses and arithmetic showing little accuracy gain despite higher token use.Source: §3.1 · p. 4

3.2. The Policy–Value Architect

  • The architect’s policy guides exploration, while its value function predicts utility balancing task success and resource use without running the harness.The policy and value predictions are both available without executing the candidate harness.Source: §3.2 · p. 5

3.3. Searching over Harnesses

  • MCTS uses deterministic harness transitions and architect predictions to evaluate interacting choices without executor calls; SHIFT-search selects the most-visited path, while SHIFT-value selects the highest-predicted-utility candidate.SHIFT-value can search again with a larger budget when the selected candidate’s predicted value is low.Source: §3.3 · pp. 5–6

3.4. Learning from Execution

  • Training updates policy from search visit distributions and value from measured, cost-aware utility of executed harnesses; a pairwise ranking loss teaches utility ordering.The reward accounts for execution tokens, latency, timeouts, and additional tools and agents.Source: §3.4 · pp. 6–7

4. Experimental Results

Across six benchmarks, SHIFT’s learned architect searches harness designs per query without executing candidates during the search. SHIFT-search leads the baselines in mean accuracy, while SHIFT-value offers a lower-cost alternative and the learned value also helps select harnesses and transfer to harder tasks.

4.1. Evaluation Setup

  • Across 9,193 tasks, the evaluation covers six benchmarks, 17 baselines, and a shared Gemini 3.5 Flash executor.The benchmarks span math, multi-hop and document question answering, code, spreadsheet manipulation, and general-purpose assistance; the six-benchmark mean weights benchmarks equally.Source: §4.1 · p. 7

4.2. RQ1: Does Query-Specific Construction Improve Accuracy?

  • SHIFT-search attains the highest six-benchmark mean accuracy at 79.9%, 7.2% above the strongest baseline, Trace (72.7%).The paired task-bootstrap 95% confidence interval for the improvement runs from 4.42% to 9.88%.Source: §4.2 · pp. 7–8
  • Full search reaches 69.4% HotpotQA accuracy, versus 67.9% with tool delegation alone and 60.3% with instruction additions alone.Restricted variants start from a single Coder and cannot add roles; the comparison tests the full construction space against choosing tools or instructions alone.Source: §4.2 · pp. 8–9, Figure 6 · p. 9

4.3. RQ2: How Does Harness Selection Balance Accuracy and Cost?

  • 74.5% mean accuracy lets SHIFT-value exceed every baseline while using 32% fewer execution tokens than Trace.Both SHIFT variants lie on the six-benchmark accuracy–cost Pareto frontier; SHIFT-value sizes harnesses to the query, using larger harnesses and more tool calls for long-horizon tasks.Source: §4.3 · p. 9, Figure 5 · p. 9, Figure 7 · p. 9
  • 79.9% mean accuracy for search nearly matches greedy’s 79.8%, with about 30% fewer execution tokens and under a second to construct a harness.Value-greedy is cheaper but reaches 60.2% because one-step lookahead cannot credit an agent whose benefit appears only after later actions.Source: §4.3 · pp. 9–10, Table 2 · p. 9, Figure 9 · p. 10

4.4. RQ3: How Effectively Does Learned Value Guide Harness Selection?

  • 10.5% higher HotpotQA accuracy and 2.9% higher GSM8K accuracy come from value selection over identical candidate pools, using half and one fifth the execution tokens, respectively.The top-ranked candidate beats the second-ranked one by 11.9% on HotpotQA, and the benefit grows as more candidates are considered.Source: §4.4 · p. 10, Table 3 · p. 10, Figure 10 · p. 10

4.5. RQ4: Does the Architect Transfer to Harder Tasks?

  • 83.6% MATH-500 accuracy transfers from an architect trained only on GSM8K, versus 81.2% for a fixed single Coder.On difficulty levels 4–5, SHIFT reaches 75.6% versus 71.0%, with both its learned policy and learned value contributing.Source: Table 4 · p. 10, §4.5 · p. 11

5. Conclusion

SHIFT learns from executed harnesses to predict which designs will succeed and at what cost, then constructs query-specific harnesses without executing candidates during search. The conclusion reports stronger accuracy than 17 baselines across six benchmarks, with value-based selection offering a lower-cost alternative.

5. Conclusion

  • SHIFT builds more accurate harnesses than 17 baselines across six benchmarks, with its largest gains on long, tool-intensive tasks; SHIFT-value achieves higher mean accuracy than every baseline at lower cost than the strongest.The conclusion also reports that these gains concentrate where structure matters and existing designs fall short, and carry over to harder problems without retraining.Source: §5 · p. 11
  • SHIFT constructs a harness for each query with a small local model in under a second on one GPU and executes only the selected harness.The conclusion says training separate architects per benchmark incurs an upfront compute cost; future work could pursue generalization across datasets and executors and improve value estimates using outcomes averaged over executions.Source: §5 · p. 11

A.1. Action space

  • Harness construction starts from one Coder without tools and adds up to ten actions from a shared vocabulary, defining about 1.5 × 10^7 possible designs.Actions add agents or feedback loops, append directives, grant tools, or stop; only feasible actions that keep the harness executable are allowed.Source: §A.1 · p. 15

A.2. Architect, search, and reward

  • The architect conditions action choices on the query, benchmark and tools, feasible actions, and a serialization of the current harness graph.Inputs are limited to 2,048 tokens, retaining the beginning and end of long queries.Source: §A.2 · p. 16
  • Batched search evaluates up to eight leaves per architect call and uses virtual loss to steer parallel descents away from the same promising branch.Pending virtual visits are removed once true values are backed up.Source: §A.2 · pp. 16–17
  • The value head predicts utility that rewards task success and penalizes execution resources, favoring the least expensive harness that solves the query.Penalties cover tokens, latency, granted tool types, agents beyond the first, and timeouts; success always outweighs penalties, and cheaper successful harnesses are preferred.Source: §A.2 · p. 17

A.3. Training

Training alternates between tree search, execution, and architect updates using observed utilities and search decisions. Across training, the policy loss falls on every benchmark, while the kinds of harnesses built shift by benchmark.

A.3. Training

  • Each training query is searched from the initial harness; a sampled construction path and up to five other distinct harnesses are executed to supervise the policy and value heads.Same-query executed harness pairs also support the ranking objective, and replay prioritizes states whose values are mispredicted.Source: §A.3 · pp. 17–18
  • By the final epoch, Planners appear in most harnesses on every benchmark, while Researchers are largely dropped on MBPP, SpreadsheetBench, and OfficeQA and Reasoners become common on GAIA.Figure 11 reports final-epoch role shares and their changes since the first epoch.Source: §A.3 · p. 18, Figure 11 · p. 19
  • Training one architect costs about as much as answering 440 OfficeQA to 6,200 HotpotQA test questions with SHIFT-search, but this benchmark-and-executor cost is amortized over later queries.Each architect trains for four epochs; total training executions range from 1,092 on OfficeQA to about 9,400 each on GSM8K and HotpotQA.Source: §A.3 · p. 18
  • The policy loss falls by 35% to 52% on every benchmark, as the architect increasingly anticipates the outcome of its own search.Figure 12 plots mean policy loss over four training epochs, averaging records with nonzero total loss.Source: §A.3 · pp. 18–19, Figure 12 · p. 19

B. Harness Selection Strategies

The section compares harness-decoding strategies that use the trained architect’s policy, value, or both with lookahead. Search preserves greedy construction’s accuracy while reducing execution tokens, and the section also measures per-query savings and architect overhead.

B. Harness Selection Strategies

  • The five strategies share one trained architect and differ in whether policy or value selects actions and whether selection uses lookahead.SHIFT-search uses 64 simulations; SHIFT-value ranks up to five complete harnesses and adds 192 simulations if the best predicted utility is below 0.55.Source: B. Harness Selection Strategies · pp. 19–20
  • Search matches greedy construction’s accuracy while using 30% fewer execution tokens, whereas value-greedy is cheapest but loses about 20% in mean accuracy.Value is most effective with lookahead or when ranking complete harnesses, rather than choosing only one-step changes.Source: B. Harness Selection Strategies · p. 20

B.1. Cost savings across questions

  • Search uses fewer tokens than greedy construction on 60% to 98% of questions, and SHIFT-value does so on 77.5% to 100%, depending on the benchmark.Mean-token savings reach 46% on OfficeQA and 41% on GAIA; Figure 13 compares strategies question by question.Source: §B.1 · p. 20, Figure 13 · p. 20
  • SHIFT-value uses markedly less than SHIFT-search on short-horizon benchmarks, with harness sizes varying by query: it mostly selects four or more agents on SpreadsheetBench and GAIA.It uses one or two agents on almost every GSM8K and MBPP query, two or three on HotpotQA, and splits between one and three or four agents on OfficeQA.Source: §B.1 · p. 20, Figure 14 · p. 21

B.2. Architect overhead

  • At 64 simulations, harness construction takes a median 0.81 seconds on HotpotQA and 0.73 seconds on GSM8K, compared with 0.26 seconds for greedy construction.Figure 15 reports construction time and time per simulation; SHIFT-value takes 0.86 and 0.78 seconds on HotpotQA and GSM8K, respectively, including its occasional second search.Source: §B.2 · p. 21, Figure 15 · p. 21
  • At budgets of 64 or more, each simulation costs 10 to 14 milliseconds, and construction time reaches 2.6 to 3.6 seconds at 256 simulations.The measured design cost stays below one second per query at the default budget, while executing a harness on OfficeQA or GAIA consumes roughly one to eight million executor tokens.Source: §B.2 · pp. 21–22

C. Benchmarks and Evaluation Protocol

The evaluation spans six benchmarks chosen to range from short, self-contained problems to tool-intensive tasks where harness structure may matter. The protocol specifies disjoint data splits and measures both accuracy and executor-token cost.

C. Benchmarks and Evaluation Protocol

  • The six benchmarks span short, self-contained tasks and file-, document-, or web-intensive tasks, testing whether SHIFT adds structure where it helps and withholds it where it does not.The set includes GSM8K, HotpotQA, MBPP, SpreadsheetBench, OfficeQA, and GAIA.Source: C. Benchmarks and Evaluation Protocol · p. 22
  • SpreadsheetBench, OfficeQA Pro, and GAIA are randomly split 55%/15%/30% into training, validation, and test sets, with test questions excluded from training and model selection.GSM8K and HotpotQA use official test or development sets; MBPP keeps its official splits.Source: C. Benchmarks and Evaluation Protocol · p. 22, Table 9 · p. 22
  • Accuracy averages each benchmark’s success criterion across three test runs, failures and timeouts count as incorrect, and the reported mean weights benchmarks equally.Execution cost counts executor tokens across all agents and is aggregated by geometric mean; architect computation is reported separately.Source: C. Benchmarks and Evaluation Protocol · p. 22

D. Baselines

Baselines differ in whether they fix or optimize harness components, while observed structure–success relationships vary across benchmarks and action types.

D. Baselines

  • Prompting and fixed-harness baselines contrast with prompt-optimized and workflow-search methods; SHIFT jointly constructs structure, instructions, and tool access per query.All methods share the Gemini 3.5 Flash executor, test sets, and answer checking; text-only methods score zero on SpreadsheetBench because they do not produce the required workbook.Source: D. Baselines · p. 23

E. Additional Results on Harness Accuracy

  • The appendix examines whether structure benefits differ by benchmark, whether gains over Trace hold question by question, and which action types contribute.The premise for per-query construction is that the right amount of structure may differ across tasks.Source: E. Additional Results on Harness… · p. 23, §E.1 · p. 23

E.1. Structure sensitivity

  • Structure–success contrasts range from none on GSM8K to 50% on OfficeQA, with tools mattering most on SpreadsheetBench and agents on OfficeQA.All nine contrasts on SpreadsheetBench, GAIA, and OfficeQA are significant (two-sided Fisher exact test, p≤0.016), while none on GSM8K; the comparison is observational because search chose the harnesses.Source: §E.1 · p. 23, Table 10 · p. 24

E.2. Paired comparison with Trace

SHIFT-search’s advantage over Trace is broad but concentrated in OfficeQA and GAIA; restricting the action space lowers HotpotQA accuracy.

E.2. Paired comparison with Trace

  • 7.2% mean improvement over Trace (95% interval [4.4, 9.9]) comes from OfficeQA (+30.1%, [17.1, 43.1]) and GAIA (+15.0%, [5.9, 24.8]); the other four are within about 1%.The comparison averages three runs per question and resamples questions with replacement, weighting the six benchmarks equally.Source: §E.2 · p. 24
  • Across three runs, SHIFT-search wins more questions than Trace on OfficeQA (24 vs 4) and GAIA (19 vs 7); SHIFT-value also wins on both.SHIFT-search solves five OfficeQA and three GAIA questions in every run where Trace fails in every run, with no reverse cases.Source: §E.2 · p. 24
  • Excluding SpreadsheetBench, SHIFT-search scores 78.3% versus Trace’s 69.6%; excluding OfficeQA, SHIFT-search still leads at 84.0%.SHIFT-value scores 73.0% when SpreadsheetBench is excluded.Source: §E.2 · p. 24

E.3. Action-space restrictions

  • On HotpotQA, directives alone lower accuracy by 9.1% and tool grants alone by 1.5%; only the full action space also permits adding agents.Both paired 95% bootstrap intervals exclude zero; tools recover most accuracy on this retrieval-heavy benchmark, but the full action space reaches the best result.Source: §E.3 · p. 25

F. Learned Value for Harness Selection

F.1. Candidate ranking

The value head selects harnesses that are more accurate and cheaper than uniform choices, with accuracy improving as more candidates are available.

F.1. Candidate ranking

  • Each question’s four or five candidates came from several construction strategies; selectors were compared on identical pools and outcomes, with uniform selection computed in expectation.Each candidate was executed twice with a Gemma 3 27B executor.Source: §F.1 · p. 25
  • 10.5% on HotpotQA and 2.9% on GSM8K: value selection beats uniform while choosing harnesses costing 9.5k vs 19.5k and 1.8k vs 8.8k tokens, respectively.The value head is trained on utility that rewards success and charges for execution cost.Source: §F.1 · p. 25, Figure 17 · p. 26
  • Value-selection accuracy rises with pool size: HotpotQA goes from 39.1% with one candidate to 48.9% with four, and GSM8K from 89.7% to 92.4%.Uniform selection has the same expected accuracy for every pool size, so the rise reflects better choices rather than easier questions.Source: §F.1 · pp. 25–26

G. Transfer to Harder Tasks

Without retraining, the GSM8K architect transfers to MATH-500, with gains concentrated on the hardest problems; the complete architect performs best among tested configurations.

G. Transfer to Harder Tasks

Related papers

Loading 2610.04137v1…