PaperlayerView exact revision on arXiv

Source-linked AI summary

Sherlock: Reliable and Efficient Agentic Workflow Execution

Yeonju Ro, Haoran Qiu, Íñigo Goiri, Rodrigo Fonseca, Ricardo Bianchini, Aditya Akella, Zhangyang Wang, Mattan Erez, Esha Choukse

arXiv:2511.00330v1cs.MAcs.SE

TL;DR

Agentic workflows can propagate errors across dependent steps, while broad verification adds latency and cost. Sherlock uses counterfactual vulnerability analysis, cost-aware verifier selection, and speculative execution. It reports higher average accuracy than a non-verifying baseline alongside reductions in execution time and cost.

  • Problem

    Agentic-workflow errors can propagate to final outputs, while identifying vulnerable nodes, choosing cost-effective verifiers, and avoiding verification delays remain challenges.

    Source: §1 · p. 1

  • Method

    Sherlock uses counterfactual fault injection to find vulnerable nodes, learns cost-effective verifier choices, and speculatively executes downstream tasks while verification runs.

    Source: §1 · p. 2

  • Results

    18.3% average accuracy gain over a non-verifying baseline, with up to 48.7% execution time reduction and 26.0% cost reduction.

    Source: §1 · p. 2, §10 · p. 11

  • Takeaways & Limitations

    Sherlock combines fault-aware verification with runtime control to balance reliability and efficiency in agentic workflows.

    Source: §10 · pp. 10–11

    The topology-based policy can be learned for each new domain and must remain independent of workflow-specific features to support dynamic workflows.

    Source: §5.4 · p. 6

Abstract

from arXiv · show

With the increasing adoption of large language models (LLM), agentic workflows, which compose multiple LLM calls with tools, retrieval, and reasoning steps, are increasingly replacing traditional applications. However, such workflows are inherently error-prone: incorrect or partially correct output at one step can propagate or even amplify through subsequent stages, compounding the impact on the final output. Recent work proposes integrating verifiers that validate LLM output or actions, such as self-reflection, debate, or LLM-as-a-judge mechanisms. Yet, verifying every step introduces significant latency and cost overheads. In this work, we seek to answer three key questions: which nodes in a workflow are most error-prone and thus deserve costly verification, how to select the most appropriate verifier for each node, and how to use verification with minimal impact to latency? Our solution, Sherlock, addresses these using counterfactual analysis on agentic workflows to identify error-prone nodes and selectively attaching cost-optimal verifiers only where necessary. At runtime, Sherlock speculatively executes downstream tasks to reduce latency overhead, while verification runs in the background. If verification fails, execution is rolled back to the last verified output. Compared to the non-verifying baseline, Sherlock delivers an 18.3% accuracy gain on average across benchmarks. Sherlock reduces workflow execution time by up to 48.7% over non-speculative execution and lowers verification cost by 26.0% compared to the Monte Carlo search-based method, demonstrating that principled, fault-aware verification effectively balances efficiency and reliability in agentic workflows.

1 INTRODUCTION

Agentic workflows can amplify early errors, while verifying every node adds substantial latency and cost. Sherlock targets verification by analyzing node vulnerability, selecting cost-effective verifiers, and overlapping verification with downstream computation.

1 INTRODUCTION

  • Early-node mistakes can propagate and contaminate final outputs, but verifying only terminal nodes misses early correction and verifying every node compounds overhead.Verification can raise latency and cost substantially, making placement a central challenge.Source: §1 · pp. 1–2
  • Sherlock uses counterfactual fault injection to identify vulnerable nodes, learns cost-effective verifier choices, and applies these policies to dynamically generated workflows.The vulnerability policy is topological rather than workflow-specific.Source: §1 · p. 2
  • Its speculative runtime overlaps verification with computation and rolls back when detected errors require recovery.This is intended to reduce latency while preserving correctness under detected errors.Source: §1 · p. 2
  • 18.3% average accuracy gain over a non-verifying baseline, with up to 48.7% execution time reduction and 26.0% cost reduction.The authors report Sherlock as best in class compared to verifying baselines.Source: §1 · p. 2

2 BACKGROUND

The background frames agentic workflows as graphs of dependent subtasks and reviews verifier approaches that validate or revise LLM outputs.

2.1 Agentic Workflows

  • An agentic workflow is a graph of subtasks, with edges carrying upstream outputs or context to dependent child nodes.Workflows may be statically defined or generated on demand from task descriptions.Source: §2.1 · p. 2

2.2 LLM Verifiers

  • Verifier approaches include self-refinement, self-consistency, LLM-as-a-Judge, and debate, with different ways to critique, compare, or revise outputs.Figure 3 compares verifier performance across task categories, with latency and cost normalized to baseline execution.Source: §2.2 · pp. 2–3, Figure 3 · p. 3

3 VERIFIER CHARACTERISTICS

Verifier overhead is substantial, accuracy-cost tradeoffs vary by task, and verified outputs often remain unchanged—motivating selective, task-aware verification and speculative execution.

3.1 Verifier Overhead

  • Up to 28.9× latency and 53.2× monetary cost overhead can arise from a single verifier on one output, while terminal-only checks miss early correction opportunities.Verifying every intermediate node compounds overhead.Source: §3.1 · p. 3

3.2 Task-Dependent Accuracy-Cost Tradeoff

  • Higher verifier cost does not necessarily improve accuracy, and cost-optimal choices vary even among tasks in the same category.Figure 4 encodes utility as accuracy gain −λ · cost, with higher values indicating better cost effectiveness.Source: §3.2 · p. 3, Figure 4 · p. 3

3.3 Verification Redundancy

  • Most verifiers retain many original outputs, but match rates vary by task; some Tool-category rates fall to 0.10–0.13.This output redundancy motivates running downstream subtasks while verification proceeds.Source: §3.3 · p. 4, Figure 5 · p. 4

4 SHERLOCK OVERVIEW

Sherlock combines learned vulnerability and verifier-selection policies with speculative execution to manage accuracy, latency, and cost in dynamic workflows.

4 SHERLOCK OVERVIEW

  • Sherlock onboards new domains rather than each new workflow, deriving placement and verifier-selection policies from representative execution traces.The traces include prompts, node outputs, and final-output ground truth.Source: §4 · p. 4
  • Online, a vulnerability estimator prioritizes nodes and a verifier selector chooses cost-optimal checks within the user’s cost budget.Speculation proceeds downstream without waiting; low similarity after revision can trigger selective rollback of affected nodes.Source: §4 · p. 4
  • The system exposes tunable reliability-latency-cost tradeoffs, distilling onboarding priors into runtime policies.The overview characterizes these as Pareto-optimal trade-offs.Source: §4 · p. 4

5 IDENTIFYING ERROR-PRONE NODES

Sherlock identifies vulnerable workflow nodes through fault injection and uses their topological properties to guide verification placement. The analysis finds greater vulnerability at terminal and initial nodes and at nodes with more incoming dependencies, informing a budget-aware priority policy.

5.1 Fault Model for Agents

  • Fault injection targets context, prompts, and outputs to model behavioral deviation, context loss, and execution faults, using empirical failure frequencies from prior work.The adopted frequencies are mapped from prior multi-agent workflow traces.Source: §5.1 · p. 5

5.2 Fault Injection in Workflows

  • For each selected node, Sherlock injects a sampled fault, reruns downstream computations, and aggregates final-accuracy deviations into a sensitivity score for verifier placement.Sampling temperature is fixed at 0 during fault injection to control randomness that affects observed failure rates.Source: §5.2 · p. 5

5.3 Topological Error Distribution

  • Terminal nodes are most vulnerable, followed by initial nodes; intermediate nodes contribute least, while higher fan-in correlates with greater vulnerability.Intermediate errors can often be corrected downstream; early misinterpretations can cascade, and terminal nodes lack recovery paths.Source: Figure 8 · p. 5, §5.3 · p. 5
  • Fan-out shows little to no correlation with error magnitude, suggesting that branching alone does not amplify vulnerability.Source: §5.3 · pp. 5–6

5.4 Derived Topology-based Policy

  • The placement policy selects terminal nodes first, then initial nodes, then intermediate nodes in descending fan-in order, subject to the verification budget.The policy can be learned for each new domain and kept independent of workflow-specific features for dynamic workflows.Source: §5.4 · p. 6

6 COST-OPTIMAL VERIFIER SELECTION

Sherlock selects verifiers dynamically because their accuracy–cost trade-offs vary by task. It learns task-conditioned verifier preferences from observed accuracy and cost, then selects the verifier with the highest predicted preference.

6 COST-OPTIMAL VERIFIER SELECTION

  • Because verifier effectiveness and accuracy–cost trade-offs vary across tasks, Sherlock uses a learning-based selector rather than one global configuration or lookup rule.Source: §6 · p. 6

6.1 Verifier Selection Problem

  • Sherlock formulates verifier selection as preference learning over observed accuracy–cost pairs, with λ controlling the trade-off between performance improvement and computational cost.The paper frames this as a Lagrangian relaxation; λ represents willingness to pay for improved performance.Source: §6.1 · p. 6

6.2 Preference-Based Policy Optimization

  • The policy is optimized with GRPO using relative verifier advantages, then selects the candidate with the highest predicted preference for a new task prompt.Source: §6.2 · pp. 6–7

6.3 Training Data and Model

  • Training pairs benchmark prompts with each candidate verifier’s observed accuracy and cost; prompts are encoded with distilbert-base for the policy model.Source: §6.3 · p. 7

7 SPECULATIVE EXECUTION

Sherlock runs downstream work while verification proceeds, then retains or rolls back speculative results according to verification and output similarity. Its run-ahead depth is constrained by verifier latency and compute budget, while task-specific metric results guide selective rollback.

7 SPECULATIVE EXECUTION

  • Sherlock overlaps verification with downstream computation, retaining speculative results when the verifier confirms the output and rolling back dependent work otherwise.If verification fails, corrected output is propagated and invalidated nodes are rescheduled.Source: §7 · p. 7

7.1 When to Run Ahead: Trade-offs and Cost Model

  • Deeper speculation can reduce latency but risks more wasted compute on rollback; a verifier-latency bound and user-set budget constrain eligible work.The feasible region combines verifier latency and the compute budget; the cost model uses verifier–executor match probability to estimate rollback waste.Source: §7.1 · pp. 7–8
  • For parallel downstream nodes, the latency constraint sums the slowest node latency at each depth level to determine eligible speculation.At each depth, nodes may run in parallel; the depth-level constraint refines the latency bound.Source: §7.1 · p. 8

7.2 Selective Rollback

  • ROUGE-L aligns best with answer equivalence on instruction-following and tool-use tasks (ρ ≈0.55, AUC ≈0.85), but metrics are random on code and math (AUC ≈0.5).Sherlock uses a ROUGE-L threshold for instruction-following and tool-use, but defaults to full rollback for code and math; revised outputs judged equivalent can be retained.Source: §7.2 · p. 8

8 EVALUATION

Sherlock is evaluated on generated workflows across three benchmarks, with comparisons covering verifier placement, verifier selection, and speculative execution. The reported results show higher accuracy at lower cost than the compared verifier-selection approaches, alongside latency reductions from speculation.

8.1 Setup and Evaluation Methodology

  • Evaluation uses CoTCollection, OMEGA’s compositional math subset, and LiveCodeBench; accuracy, execution and verification latency, and verifier cost are measured.Flow generates the workflows, and Texec measures completion of execution while Tvrf measures time until the final verified output.Source: §8.1 · pp. 8–9
  • Baselines include even and random placement, static verifier assignments, AFlow, a task-category tabular selector, and an oracle; experiments serve open models on eight A100 GPUs.The tabular selector classifies nodes into four task categories; the reported classifier achieves near 98% task-classification F1.Source: §8.1 · pp. 8–9

8.2 Verifier Placement

  • With the same verifier selection and budget, Sherlock’s topology-aware placement consistently achieves higher final accuracy with less budget than random or even placement.The comparison isolates verifier placement as the variable.Source: Figure 12 · p. 9, §8.2 · p. 9

8.3 Verifier Selection

  • Sherlock follows the accuracy–cost Pareto frontier, achieving higher accuracy at the same cost than static verifier assignments and approaching the oracle.The selector is trained on a microbenchmark and evaluated on accuracy and average cost per task.Source: Figure 13 · p. 9, §8.3 · pp. 9–10
  • Across all tasks, Sherlock delivers higher accuracy and lower cost than AFlow; it also consistently exceeds the tabular approach in accuracy while costing less.Figure 14 presents the end-to-end final-accuracy and total-verification-cost comparison.Source: Figure 14 · p. 10, §8.3 · p. 10

8.4 Speculative Execution

  • 62.9% mean Texec reduction and 48.7% Tvrf reduction occur on LiveCodeBench; CoTCollection and OMEGA also exceed 50% Texec reductions.The reported latency reductions are attributed to overlapping verification with downstream execution.Source: Table 3 · p. 10, §8.4 · p. 10

9 RELATED WORK

Related work addresses workflow generation and optimization, as well as systems for serving agentic workflows. Sherlock is presented as complementary to these efforts, combining verifier selection with speculative execution.

Agentic Workflow Generation and Optimization

  • Workflow-generation research uses iterative search, LLM-based generation, and fine-tuning; Sherlock complements it by adding dynamic verification policies to generated workflows.The paper characterizes Sherlock’s strategy as lightweight, combining heuristics with learned verifier selection for online adaptability.Source: §9 · p. 10

Serving Agentic Workflows

  • Agent-serving work covers planning, scheduling, orchestration, and asynchronous execution; Sherlock focuses on jointly navigating cost, accuracy, and latency through verifier selection and speculation.Sherlock is described as the first framework to explore these trade-offs holistically for agentic workflows.Source: §9 · p. 10

10 CONCLUSION

Sherlock combines counterfactual analysis, dynamic verifier selection, and speculative execution with rollback to balance reliability, latency, and cost.

10 CONCLUSION

  • Sherlock identifies error-prone nodes through counterfactual analysis and selects verifiers dynamically, jointly optimizing latency, cost, and accuracy.It uses speculative execution and rollback to overlap verification with downstream computation while controlling rollback cost.Source: §10 · pp. 10–11
  • Up to 48.7% execution latency reduction and 26.0% cost reduction over baselines are reported for Sherlock.Sherlock exposes user-configurable knobs to trade off reliability, latency, and cost.Source: §10 · p. 11

A.1 Microbenchmarks

  • The microbenchmarks span instruction-following, math, coding, and tool-calling tasks.Examples include HotpotQA, MATH, HumanEval, and GTA.Source: §A.1 · p. 14

A.2 Verifier Cost Calculation

  • Verifier cost is the sum of model and GPU costs; GPU cost depends on the number of GPUs used and duration.The setup uses an 8-GPU server, with resources allocated across executor, judge, and advanced-feedback models.Source: §A.2 · p. 14

A.3 Judge LLM and Majority Answer

Majority-answer generation and selection have task-dependent strengths, while Sherlock’s node-state machine governs speculative execution and rollback.

A.3 Judge LLM and Majority Answer

  • sc-gen smooths superficial answer variations but adds generation cost; sc-select uses one token to choose an existing answer but cannot reconcile divergent responses without overlap.The two approaches’ relative effectiveness varies across tasks, partly due to Judge specialization.Source: §A.3 · p. 15
  • sc-gen with a general-purpose model outperforms Judge-based sc-gen on Tools and Code, while Judge-based sc-select performs better there and comparably on QA.The table compares generation-based and selection-based majority answers.Source: §A.3 · p. 15, Table 4 · p. 15

B SPECULATIVE EXECUTION STATE MACHINE DIAGRAM

C LIGHTWEIGHT SIMILARITY METRICS FOR PRACTICAL ROLLBACK

Lightweight similarity metrics can align with ground-truth answer equivalence in natural-language tasks but are unreliable for code and math, shaping rollback decisions.

C LIGHTWEIGHT SIMILARITY METRICS FOR PRACTICAL ROLLBACK

  • The evaluated lightweight metrics are cosine similarity, Jaccard similarity, ROUGE-L, BLEU, and AST similarity.They are considered as interpretable alternatives to LLM evaluators, which add latency and cost along the critical path.Source: C LIGHTWEIGHT SIMILARITY METRICS FOR… · p. 16
  • ROUGE reaches ρ ≈0.56–0.77 and AUC ≈0.83–0.88 on instruction-following and tool-use, while code/math metrics have ρ < 0.2 and AUC ≈0.5.Table 5 summarizes Spearman correlation and AUC; higher values indicate stronger alignment with ground-truth answer equivalence.Source: C LIGHTWEIGHT SIMILARITY METRICS FOR… · p. 16, Table 5 · p. 16
  • KDE distributions separate matching from non-matching answers for instruction and tool-use tasks but overlap substantially for code and math.Figure 17 plots similarity scores for matching and non-matching outputs by task category.Source: C LIGHTWEIGHT SIMILARITY METRICS FOR… · p. 16, Figure 17 · p. 17
  • Sherlock defaults to rollback for code and math because lightweight metrics do not reliably capture semantic equivalence in those domains.For natural-language tasks, the paper concludes that lightweight metrics can replace LLM judgment.Source: C LIGHTWEIGHT SIMILARITY METRICS FOR… · p. 16

Related papers

Loading 2511.00330v1…