JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

Haoran Zhang; Dongjun Kim; Seohyeon Cha; Kevin S Chan; Ananthram Swami; Gustavo De Veciana; Haris Vikalo

cs.AIOct 2, 2026

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

Authors: Haoran Zhang, Dongjun Kim, Seohyeon Cha, Kevin S Chan, Ananthram Swami, Gustavo De Veciana, Haris Vikalo

Organizations: University of Texas at Austin · DEVCOM Army Research Laboratory

Abstract

Complex reasoning queries can be decomposed into directed acyclic task graphs and distributed across heterogeneous LLMs, reducing latency through parallelism and enabling smaller models to solve complex tasks. In practice, however, the suitability of an LLM for a given subtask may be a priori unknown, and execution alone does not reveal output correctness. We propose JOVE, an online framework that jointly assigns executor LLMs and selects intermediate outputs for paid verification. Verification runs asynchronously and is used to improve future allocations, so the system must balance spending on execution now against learning for later. We study how to optimize this trade-off under a long-term budget and a per-query latency constraint, with stochastic, initially unknown LLM service quality, invocation costs, and execution times. JOVE makes execution and verification decisions by solving a sequence of per-query mixed-integer linear programs. Online learning updates task-dependent estimates of LLM quality based on verification feedback, while an information-gain bonus incorporates the value of learning into allocation decisions. Under a natural set of assumptions, we establish sublinear quality-learning regret for JOVE. Across four reasoning benchmarks, JOVE achieves competitive accuracy against standard inference baselines while reducing average cost and latency by at least 3.17 times.

Figures & tables

Figure 1: Overview of JOVE. A planner decomposes each query into a task graph and identifies candidate executor LLMs for each node. JOVE jointly assigns executors and selects outputs for verification, subject to a long-term execution/verification budget and latency constraints. Verification proceeds asynchronously without delaying the current response, improving model-quality estimates.

(a) Accuracy (%) $\uparrow$
Methods	Bamboogle	MMLU-Pro	LiveBench-Reasoning	GPQA
Inference-level baselines (unconstrained)
Direct (Qwen3-32B)	$47.5\pm 3.2$	$47.3\pm 0.8$	$31.4\pm 1.2$	$45.1\pm 3.8$
CoT ( Wei et al., 2022 )	$\textbf{51.7}\pm 1.2$	$54.1\pm 1.1$	$39.2\pm 0.9$	$54.2\pm 3.6$
SoT ( Ning et al., 2024 )	$48.9\pm 3.4$	$52.0\pm 3.1$	$33.4\pm 2.3$	$50.9\pm 6.8$
Plato ( Jin et al., 2025a )	$46.5\pm 0.9$	$52.8\pm 3.2$	$38.4\pm 1.8$	$\textbf{60.3}\pm 0.1$

Table 1: Accuracy, latency, and API cost per query across four benchmarks. Averaged across benchmarks, JOVE achieves competitive accuracy with substantially lower latency and API cost than the unconstrained inference baselines. Values are mean

\pm

standard deviation over three random seeds.

Figure 2: Accuracy, latency, and cost trade-offs, averaged over four datasets.

Panel of Figure 3 — Figure 3: Verification analysis of JOVE. (a) Final-answer accuracy versus the number of verifier-labeled incorrect nodes $k$ , grouped by the number of verified nodes $n$ , with results pooled across all four datasets. (b) GPQA final-answer accuracy and the fraction of executed nodes verified, split by verifier-labeled correct and incorrect output, as the verification weight $k_{v}$ varies.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Inference-level baselines (unconstrained)
Methods	Accuracy (%) $\uparrow$	Latency (sec.) $\downarrow$	Cost ( $\times 10^{-4}$ USD) $\downarrow$
Direct (Qwen3-32B)	$47.3\pm 0.8$	$45.39{\scriptstyle\,\pm\,2.29}$	$5.34{\scriptstyle\,\pm\,0.38}$
CoT ( Wei et al., 2022 )	$54.1\pm 1.1$	$34.11{\scriptstyle\,\pm\,4.63}$	$5.38{\scriptstyle\,\pm\,0.34}$
SoT ( Ning et al., 2024 )	$52.0\pm 3.1$	$70.17{\scriptstyle\,\pm\,6.27}$	$27.53{\scriptstyle\,\pm\,3.71}$
Plato ( Jin et al., 2025a )	$52.8\pm 3.2$	$104.20{\scriptstyle\,\pm\,5.21}$	$22.23{\scriptstyle\,\pm\,2.02}$
Resource-aware methods (constrained)

Appendix

Table 2: Results on MMLU-Pro. Each query generates one task graph in the learning sequence.

Datasets	$t\in[1,50]$	$t\in[51,100]$	$t\in[101,200]$	$t\in[201,\text{end}]$
Bamboogle	$96.8\pm 4.0$	$98.2\pm 1.6$	$98.1\pm 2.1$	$98.6\pm 1.4$
MMLU-Pro	$75.6\pm 8.8$	$93.4\pm 3.6$	$95.8\pm 1.7$	$98.4\pm 0.4$
LiveBench-Reasoning	$56.9\pm 10.0$	$89.7\pm 4.3$	$94.7\pm 4.0$	$96.0\pm 2.1$
GPQA	$72.9\pm 12.2$	$91.6\pm 5.6$	$95.7\pm 1.3$	$98.7\pm 1.3$

Appendix

Table 3: Deadline hit rate (%) across successive intervals. The target is 90%.

Datasets	$t\in[1,50]$	$t\in[51,100]$	$t\in[101,200]$	$t\in[201,\text{end}]$
Bamboogle	$11.29\pm 3.3$	$1.83\pm 0.3$	$1.38{\pm 0.2}$	$0.98{\pm 0.2}$
MMLU-Pro	$23.09\pm 12.4$	$7.65\pm 4.1$	$3.24\pm 1.2$	$1.99\pm 0.1$
LiveBench-Reasoning	$6.15\pm 2.0$	$2.39\pm 1.3$	$1.97\pm 0.5$	$1.97\pm 0.4$
GPQA	$21.35\pm 4.6$	$8.74\pm 3.2$	$3.05\pm 1.0$	$1.66\pm 0.1$

Appendix

Table 4: Average cost (

\times 10^{-4}

USD) across successive intervals.

\gamma=2\times 10^{-4}

USD.

Panel of Figure 4 — Figure 4: Ablation of the cost and latency constraints on GPQA.

Methods	Accuracy(%)	Latency (s)	Cost ( $\times 10^{-4}$ USD)
$p=0.2$	$33.6\pm 1.7$	$4.23\pm 0.83$	$2.06\pm 0.11$
$p=0.5$	$34.8\pm 1.2$	$3.27\pm 0.35$	$2.42\pm 0.24$
$p=0.8$	$42.3\pm 0.9$	$3.09\pm 0.72$	$2.35\pm 0.14$
$p=0.9$	$37.1\pm 1.4$	$3.02\pm 0.40$	$2.37\pm 0.12$
$p=1.0$	$38.5\pm 1.2$	$4.00\pm 0.39$	$2.09\pm 0.09$
JOVE	$49.3\pm 1.0$	$3.68\pm 0.48$	$2.18\pm 0.18$

Appendix

Table 5: Comparison of verification strategies on Bamboogle.

Symbol	Description
Query and task graph
$t$ , $T$	Query index and horizon (number of queries).
$x_{t}$	The $t$ -th query.
$\mathcal{G}_{t}=(\mathcal{N}_{t},\mathcal{E}_{t})$	Planner-generated task graph (DAG) for query $x_{t}$ .
$\mathcal{N}_{t}$ , $\|\mathcal{N}_{t}\|$	Node (subtask) set and its cardinality.
$\mathcal{E}_{t}$	Edge set; $(j,i)\in\mathcal{E}_{t}$ means node $i$ requires the output of node $j$ .

Appendix

Table 6: Notation for the task graph, decisions, outcomes, and oracle statistics.

Symbol	Description
Online estimation (Section 3.3 )
$\phi_{t}^{i}(a)\in\mathbb{R}^{d}$ , $d$	Feature vector of the task–model pair and its dimension.
$\mathcal{D}_{t-1}$	Feature–label pairs obtained through verification before query $t$ .
$\Upsilon_{t-1}(a)$	Execution records $(\phi,m,d)$ for model $a$ collected before query $t$ .
$w(\phi,\phi_{t}^{i}(a))$	Softmax similarity weight assigned to a past record.
$G_{t-1}$ , $G_{t-1}^{+}$	Ridge information matrix before query $t$ , and after adding one verified observation.

Appendix

Table 7: Notation for online learning, resource control, and the analysis.

LLM Inference Scheduling

Large language model inference scheduling allocates requests, batches, compute, and KV-cache memory to balance latency, throughput, and service-level objectives.

See all 166 papers

Online Verification of Language Model Responses Under Cost Constraints
Oct 2, 2026Erfan Hajihashemi, Yanning ShenLLM Reliability Online Learning
Department of Electrical Engineering & Computer Science University of California, Irvine
LLM-as-Judge on a Budget
Feb 17, 2026Aadirupa Saha, Aniket Wagde, Branislav KvetonLLM Evaluation LLM-as-a-Judge
UIC · Adobe
Logic-Regularized Verifier Elicits Reasoning from LLMs
May 7, 2026Xinyu Wang, Changzhi Sun, Lian Cheng +4LLM Evaluation LLM Answer Verification
Department of Computer Science and Technology, East China Normal University · Institute of Artificial Intelligence (TeleAI), China Telecom

Oct 2, 2026J/K move · Enter open · S save

Online Verification of Language Model Responses Under Cost Constraints

Erfan Hajihashemi, Yanning Shen

Department of Electrical Engineering & Computer Science University of California, Irvine

LLM Reliability Online Learning

Open paper AskPDF arXiv

As large language models are increasingly deployed for multi-step reasoning, verifying the correctness of their outputs has become essential for maintaining reliability at scale. Verifying the correctness of large language model outputs is often done by querying a costly ground-truth oracle, which is impractical to invoke at every step in an online setting. Prior work addresses this by querying a single weak verifier on every step, and using its score to decide whether the costly strong verifier needs to be queried as well, reserving strong verification for only a small fraction of the steps. However, a single fixed weak verifier may not perform consistently well as the subject matter or difficulty of incoming queries changes over time, and committing to one in advance risks either overly costly or inaccurate verification. We introduce OMVV (Online Multi-Verifier Verification), an algorithm that maintains a pool of

K

candidate weak verifiers with differing cost and verification performance, and adaptively routes each round's decision to a verifier selected via an online score combiner and an exponential-weights routing policy. OMVV provides a distribution-free, finite-time guarantee on false-accept and false-reject rates across the full pool of verifiers, and further achieves sublinear regret against the best fixed verifier in hindsight under a combined cost and consistency objective. Experiments on reasoning dataset benchmarks show that OMVV achieves higher accuracy at lower verification cost than any single fixed verifier, across a range of operating budgets.

Abstract

LLM Inference Scheduling

Explore similar work

Online Verification of Language Model Responses Under Cost Constraints

LLM-as-Judge on a Budget

Logic-Regularized Verifier Elicits Reasoning from LLMs