PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.03296v1cs.AIcs.LG

TL;DR

Complex reasoning systems must choose among heterogeneous LLMs when subtask quality is unknown and execution alone does not reveal correctness. JOVE jointly allocates executors and paid verification online; across reasoning datasets, it matches the strongest baseline’s average accuracy with substantially lower cost and latency.

  • Problem

    Existing routing and graph-aware allocation methods typically learn from offline data or assume free quality feedback, motivating joint executor and verification choices under cost and latency constraints.

    Source: §1 · p. 1

  • Method

    JOVE jointly selects executor LLMs and node outputs to verify through per-query MILPs, using online quality estimates and an information-gain bonus for future allocations.

    Source: §1 · p. 2

  • Results

    Across multiple reasoning datasets, JOVE achieves average accuracy comparable to the strongest baseline, with 3.7–16.3× lower cost and 8.3–17.0× lower latency.

    Source: §1 · p. 2

  • Takeaways & Limitations

    JOVE provides a foundation for efficient multi-step LLM systems in resource-constrained environments.

    Source: §5 · p. 9

    JOVE assumes verification proceeds asynchronously without delaying graph execution or response delivery, although verification cost counts toward the API budget.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

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.

1 INTRODUCTION

Complex reasoning can be represented as a task graph, allowing heterogeneous LLMs to handle subtasks and independent branches to run in parallel. JOVE addresses the challenge of choosing executors and paid verification under resource constraints when model quality is initially unknown.

1 INTRODUCTION

  • Graph-based inference decomposes queries into DAG subtasks whose dependencies shape the final response, while independent branches can run in parallel.Source: §1 · p. 1
  • Existing routing and graph-aware allocation methods typically rely on offline data or assume free quality feedback, whereas JOVE considers paid, selective verification to improve future allocations.Source: §1 · p. 1
  • The problem couples spending across queries through an average API-cost budget and couples executor choices within each graph through per-query deadlines.A slower executor at one node can restrict feasible downstream choices even when locally favorable in quality and cost.Source: §1 · pp. 1–2
  • JOVE uses per-query mixed-integer linear programs with online model-quality estimates and an information-gain bonus that values verification feedback for future allocations.The framework jointly chooses executor LLMs and outputs to verify under system resource constraints.Source: §1 · p. 2
  • The formulation jointly chooses executor LLMs and node outputs to verify despite initially unknown quality, cost, and latency, under a long-term cost budget and per-query latency chance constraint.Source: §1 · p. 2
  • Across multiple reasoning datasets, JOVE achieves average accuracy comparable to the strongest baseline, with 3.7–16.3× lower cost and 8.3–17.0× lower latency.Source: §1 · p. 2

2 RELATED WORK

Prior work studies graph-structured reasoning, LLM routing, and graph-aware coordination, but commonly relies on fixed models, offline learning, or free quality feedback. JOVE combines online executor allocation with selective node-level verification under shared budget and latency constraints.

2 RELATED WORK

  • Graph-structured decoding exposes reasoning structure or parallelism (Ning et al., 2024; Jin et al., 2025a), while graph-aware workflow systems coordinate models and tools (Kim et al., 2023).Source: §2 · p. 3
  • LLM routing selects models by predicted quality, difficulty, or preference (Chen et al., 2023), while many online methods assume quality feedback is free.Source: §2 · p. 3
  • AutoMix verifies an initial output on every query, adding verification cost and delay, while HybridFlow uses offline training and restricts routing to edge or cloud models.Source: §2 · p. 3
  • JOVE learns executor allocation online while selectively verifying node outputs, extending costly-observation bandits to DAG decisions under shared execution-verification budgets and per-query latency constraints.Source: §2 · p. 3

3 METHOD

JOVE formulates joint execution and verification, derives an oracle per-query MILP, then replaces unknown statistics with online estimates and analyzes quality-learning regret.

3 METHOD

  • JOVE’s method moves from joint problem formulation to an oracle MILP, an online allocation policy, and a quality-learning regret analysis.This is the method’s stated sequence of components.Source: §3 · p. 3

3.1 PROBLEM FORMULATION

  • The objective maximizes the long-run average fraction of correctly executed nodes under a long-run API-cost budget and per-query deadline violation tolerance.The budget can shift spending across queries, whereas latency is constrained per query because one fast response cannot compensate for another missed deadline.Source: §3.1 · p. 4

3.2 ORACLE MILP FORMULATION

  • With known executor statistics, the oracle MILP encodes assignment and dependency-aware finish times; its policy uses no verification because quality is already known.Latency feasibility is enforced through path-length constraints, and the dynamic price penalizes API spending relative to the budget.Source: §3.2 · pp. 4–5

3.3 ONLINE ESTIMATION AND VERIFICATION-AWARE ALLOCATION

  • The online policy replaces oracle coefficients with estimates and adds a verification information-gain bonus, favoring feedback that can improve future executor selection.The D-optimal gain is larger for feature directions with limited prior observations.Source: §3.3 · p. 6

3.4 REGRET ANALYSIS

  • Under the stated assumptions, JOVE’s quality-learning regret is O(T^2/3[log(1 + T)]^5/6), with a sufficient verification-weight interval that is not claimed to be optimal.The lower bound promotes verification of uncertain task-model pairs, while the upper bound keeps the cumulative bonus sublinear.Source: §3.4 · p. 7

4 EXPERIMENTS

Across four reasoning benchmarks, JOVE delivers comparable accuracy to inference baselines with lower average cost and latency. Results also examine resource-aware alternatives, verification behavior, and constraint satisfaction.

4 EXPERIMENTS

  • The evaluation covers Bamboogle, MMLU-Pro, GPQA, and LiveBench-Reasoning, compares inference and resource-aware baselines, and repeats experiments over three randomized query orders.The API-cost budget and deadline are calibrated from direct Qwen3-32B calls on Bamboogle.Source: §4 · p. 7

4.1 EXPERIMENTAL RESULTS

  • 49.5% average accuracy, 2.24 × 10^-4 USD cost, and 7.09 s latency per query; versus CoT, SoT, and Plato, JOVE uses 3.7–16.3× less cost and 8.3–17.0× less latency.Table 1 reports mean ± standard deviation over three random seeds.Source: Table 1 · p. 8, §4.1 · p. 8
  • WR-Online reaches 43.8% average accuracy but has 2.7× JOVE’s latency; Knapsack-ascend and -descend achieve 40.1% and 40.3%, respectively, 9.5 and 9.2 points below JOVE.WR-Online does not enforce a latency constraint; the constrained heuristics use comparable resources to JOVE.Source: §4.1 · p. 8
  • JOVE single-node is cheapest and fastest at 1.68 × 10^-4 USD and 2.08 s per query, but has the lowest average accuracy at 36.8%.It omits task decomposition and receives at most one verification label per query, potentially limiting accuracy and slowing policy learning.Source: §4.1 · p. 8
  • Figure 2 compares the four-dataset accuracy–latency–cost trade-off: inference baselines generally have substantially greater latency and cost, while constrained heuristics use comparable resources but achieve lower accuracy.The prose attributes the heuristic accuracy gap to the value of learning task-dependent executor quality.Source: §4.1 · p. 8, Figure 2 · p. 8
  • In Figure 3a, final-answer accuracy falls monotonically as verifier-labeled incorrect nodes increase for each verified-node count; at fixed error count, accuracy is generally higher with more verified nodes.With five verified nodes all labeled correct, final-answer accuracy is 87.3%, not 100%.Source: §4.1 · p. 9, Figure 3 · p. 9
  • Figure 3b shows GPQA accuracy improving and remaining stable for verification weights kv from 2 to 6, while accuracy declines above 6 as a growing share of executed nodes is verified.Below 1.5, verification is infrequent and accuracy remains relatively low.Source: §4.1 · p. 9, Figure 3 · p. 9
  • As learning progresses, interval-average costs move toward or below budget and deadline hit rates improve, reaching at least 96% on every dataset in the final interval against a 90% target.The practical policy’s constraint satisfaction depends on resource-estimation accuracy and budget-price adaptation.Source: §4.1 · p. 9

5 CONCLUSION

JOVE jointly manages LLM routing and selective paid verification for task-graph reasoning. It achieves competitive accuracy with reduced cost and latency relative to baselines, with sublinear quality-learning regret under stated assumptions.

5 CONCLUSION

  • JOVE jointly manages LLM routing and selective paid verification via per-query MILPs, balancing immediate accuracy with feedback acquisition for future allocations.The paper establishes sublinear quality-learning regret under its stated assumptions and reports empirical budget and deadline control.Source: §5 · p. 9

A.1 ORACLE MILP FORMULATION

The oracle MILP formulation assumes known expected LLM performance, invocation cost, and latency. In this setting, verification adds cost but no quality-estimation benefit.

A.1 ORACLE MILP FORMULATION

  • The oracle MILP optimizes executor selection and verification nodes assuming known expected LLM performance, invocation cost, and latency; verification then adds cost without improving API-quality estimates.The passage identifies the estimates as expected performance and invocation cost, alongside the oracle setting’s known model statistics.Source: §A.1 · p. 12

A.2 THEORETICAL ANALYSIS

The notation convention distinguishes random quantities from their realized values.

A.2 THEORETICAL ANALYSIS

  • Uppercase letters denote random quantities, while lowercase letters denote their realizations.Source: §A.2 · p. 13

A.2.1 SUFFICIENT CONDITION OF THE LATENCY CONSTRAINT

The lemma gives a sufficient condition under which Eq. 6 implies the latency chance constraint in Eq. 2c. Its union-bound argument does not require independent node latencies.

A.2.1 SUFFICIENT CONDITION OF THE LATENCY CONSTRAINT

  • Eq. 6 is sufficient to imply the latency chance constraint in Eq. 2c.The lemma is explicitly framed as a sufficient condition.Source: §A.2.1 · p. 13
  • The proof bounds the event that any node exceeds its assigned latency quantile, then considers the maximum over paths.It uses the conditional union bound to obtain the chance-constraint condition.Source: §A.2.1 · p. 13
  • The union bound applies even when node-latency events are dependent, so no independence assumption is needed.Source: §A.2.1 · p. 13

A.2.2 AVERAGE-BUDGET GUARANTEE

Under stated context, cost, and feasibility assumptions, the proposition establishes long-term budget feasibility for the oracle policy. The proof relies on independent, identically distributed query contexts and a conservative feasible set.

A.2.2 AVERAGE-BUDGET GUARANTEE

  • Query contexts are independent and identically distributed, with node risk shares set by a fixed rule from each context.Source: §A.2.2 · p. 13
  • The guarantee assumes budget feasibility within the oracle’s conservative feasible set, which may exclude some chance-feasible allocations.The cost and latency distributions are time-invariant conditional on context and allocation, and costs are bounded.Source: §A.2.2 · pp. 13–14
  • The proposition establishes long-term budget feasibility when each query optimizes the priced objective using true expected costs and qualities.It also states that E[λT+1]/T tends to zero.Source: §A.2.2 · p. 14

A.2.3 LLM QUALITY LEARNING ANALYSIS

The analysis uses confidence bounds for quality estimates and bounds uncertainty accumulated from verified task–model pairs. It establishes sublinear quality-learning regret under sufficient conditions, while noting that the theorem’s horizon and verification-weight conditions are conservative.

A.2.3 LLM QUALITY LEARNING ANALYSIS

  • The confidence radius makes the uncertainty bonus an upper bound on true model quality with high probability; a larger constant bonus can encourage excessive exploration.As verified observations accumulate, uncertainty falls in the feature directions they cover.Source: §A.2.3 · p. 15
  • The analysis bounds cumulative uncertainty for verified task–model pairs despite selecting verification decisions in batches within each query.The batched uncertainty bound accounts for a shared information matrix within a query.Source: §A.2.3 · pp. 15–16
  • The sufficient horizon condition is T ≥ 8d log(8nmax); smaller feature dimension may ease the horizon requirement but restrict feature expressivity.The passage cautions that reduced expressivity may degrade model-quality estimation.Source: §A.2.3 · p. 22
  • The theorem establishes sublinear quality-learning regret under its formal assumptions, but its sufficient horizon condition can exceed some experimental sequence lengths.For 384-dimensional features and nmax = 5, the stated sufficient horizon can exceed some experiments; those experiments fall outside the theorem’s conservative regime.Source: §A.2.3 · p. 22

A.3.1 JOVE PROCEDURE

This section describes JOVE’s task-graph execution and allocation procedure, including feedback-informed executor and verification choices, and introduces notation for quality-learning regret. It also reports checks on learning-sequence design, resource constraints, verification strategy, and latency-risk allocation.

A.3.1 JOVE PROCEDURE

  • JOVE generates a DAG, forms task–model features, computes quality UCBs, solves a per-query MILP, executes dependencies, launches selected verifications asynchronously, and updates quality and resource histories.The planner prompt requests small executable tasks with minimal acyclic dependencies and specified output formats; the verifier judges factual correctness given the original prompt and dependencies, treating uncertain outputs as incorrect.Source: §A.3.1 · p. 22, §A.3.2 · p. 23

A.3.3 EMBEDDING MODEL

  • JOVE uses a compact 384-dimensional all-MiniLM-L6-v2 embedding and feature-similarity-weighted histories to estimate execution costs and latency quantiles, with baselines for sparse histories.Verification-cost estimates are updated analogously from completed verifications.Source: §A.3.3 · p. 23, §A.3.4 · pp. 23–24

A.4 ADDITIONAL EXPERIMENTAL DETAILS

  • The experiments set γ = 2.0 × 10−4 USD/query and µt = 16 s from direct Qwen3-32B results on Bamboogle, making these constraints tighter than averages across all four datasets.Calls to larger models are charged in full, so expensive assignments must be offset by cheaper assignments elsewhere.Source: §A.4 · p. 24

A.4.1 DISCUSSION ON THE LEARNING SEQUENCE

  • 55.8% accuracy in the one-graph MMLU-Pro setting compares with 54.8% in the four-graph setting, suggesting performance does not depend on repeated queries.Each query appears only once in the one-graph sequence; graphs execute independently, and verification labels update a shared task–model quality estimator rather than reusing outputs or answers.Source: Table 2 · p. 25, §A.4.1 · p. 25

A.4.2 SATISFACTION OF THE CONSTRAINTS

  • At the final interval, every dataset reaches at least 96.0% deadline hit rate, while interval-average costs decline toward the budget as JOVE adjusts allocations.Early cost overspending and below-target hit rates are attributed to the initially small budget multiplier and sparse resource histories; the empirical results do not establish a conditional deadline guarantee for every query.Source: §A.4.2 · pp. 25–26, Table 3 · p. 26, Table 4 · p. 26

A.4.3 ADDITIONAL ABLATIONS

  • Increasing the cost budget or relaxing the latency deadline generally improves GPQA accuracy, while tighter deadlines favor faster executors and modestly reduce accuracy.The cost and latency constraints act as direct controls over the accuracy–resource trade-off.Source: §A.4.3 · p. 27, Figure 4 · p. 27

A.4.4 COMPARISON WITH RANDOM VERIFICATION

  • JOVE improves Bamboogle accuracy by 7.0 percentage points over the best random-verification baseline (p = 0.8), supporting information-gain- and cost-based verification selection.The experimental verifier’s conditionally unbiased feedback assumption is not established; nevertheless, final-answer accuracy decreases as verifier-labeled incorrect nodes increase, suggesting the feedback carries useful quality information.Source: Table 5 · p. 27, §A.4.4 · pp. 27–28

A.5.1 JOINT OPTIMIZATION OF NODE RISK ALLOCATION

  • An extended JOVE jointly allocates node-level latency risk with executor and verification decisions, concentrating tolerance on bottleneck paths to obtain generally tighter latency bounds than uniform allocation.The extension remains a MILP, adding a discrete risk grid and one global risk-budget constraint.Source: §A.5.1 · pp. 28–29

A.6 NOTATION

  • RT denotes quality-learning regret.The passage also refers to a comparator objective with true qualities and its maximizer, but the notation is truncated.Source: §A.6 · p. 31
Loading 2610.03296v1…