acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLMs, graph-based inference, optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_eniiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies how to decompose complex reasoning problems into task graphs and execute them with different LLMs under resource constraints. The paper proposes JOVE, in which a planner LLM first decomposes each problem into a DAG of subtasks, and then, for each node, JOVE jointly decides two things, (i) which executor LLM to use, and (ii) whether to call a verifier LLM to check the node's output. The verification results do not affect answer generation and are only used to update the estimates of each model's quality, so as to improve future allocations. JOVE formulates the decisions for each query as a mixed-integer linear program that maximizes the average node correctness under a long-term average budget and a per-query latency constraint, where model quality is estimated online with LinUCB, the value of verification is measured by information gain, and the budget is controlled by dynamic pricing. The paper proves sublinear quality-learning regret under certain assumptions and conducts experiments on Bamboogle, MMLU-Pro, GPQA, and LiveBench-Reasoning, claiming substantially lower cost and latency with accuracy comparable to the baselines.

Critical strengths

The contribution of the paper is an optimization framework with theoretical guarantees, which jointly models executor selection and verification decisions, considers both a long-term budget and a per-query latency constraint, and provides a sublinear regret bound.

Critical weaknesses
  1. The proposed idea of using a planner to decompose a problem into subtasks and then selecting an executor for each node is not necessarily general or reasonable for all tasks, and the paper does not discuss its scope of applicability. (i) Some problems cannot be decomposed into subtasks, or the resulting subtasks are rather abstract. However, the number of nodes in the main experiments is manually fixed at 2–5 (only the appendix tries letting the planner decide on MMLU-Pro), so problems that are hard to decompose must still be decomposed, which may not be the most appropriate approach. (ii) Selecting an executor for each node makes almost no use of language understanding. It only encodes the node description with a very small sentence-embedding model (MiniLM) and scores it with a linear model, so the more abstract the subtask, the less reliable the selection. (iii) The paper shows no actually generated task graphs and does not evaluate the quality of the decomposition. This framework may only be suitable for multi-step tasks that can be naturally decomposed.

  2. The planner used in the experiments appears too strong for the evaluated benchmarks, and the paper provides no further experiments comparing different planners. The planner in the experiments is Gemini 2.5 Flash-Lite, which is already a capable commercial model (relative to the evaluated benchmarks). Since the proposed method has to call it once for every question anyway, why not let the planner answer the question directly? Then neither the executors nor the verifier would be needed. The converse question is whether the planner needs to be a strong model at all. Would a smaller planner still achieve this performance? The paper conducts no experiments on these questions, so it is unclear whether the decomposition is reasonable and whether the whole pipeline is necessary.

  3. The baseline comparison is insufficient, and the baselines are rather weak. (i) The inference-level baselines use only a single model, Qwen3-32B, while JOVE can choose from a pool that includes stronger models such as GPT-OSS-120B and Llama-3.3-70B. The paper does not compare with the strongest single model in the pool answering directly, or with query-level routing over the same pool under the same budget. (ii) Among the resource-aware baselines, WR-Online is the only external method, and the two Knapsack variants are heuristics. (iii) The paper cites many related methods, e.g., in Paragraph 2 of Section 2, but does not compare with most of them.

Questions for authors
  1. Does the proposed framework rely on a strong planner? Would a smaller planner still achieve this performance? If the planner answers the question directly without decomposition, what are the accuracy, cost, and latency? If the planner were not an LLM but a random or rule-based decomposition (the authors are free to choose the rules, e.g., splitting by commas or by syntax), what would the accuracy be?
  2. What happens when problems that cannot be naturally decomposed are forced into 2-5 nodes? Could the authors show examples of actually generated task graphs and evaluate the quality of the decomposition?
  3. What are the results if the strongest single model in the pool (e.g., GPT-OSS-120B) answers directly, or if query-level routing is performed over the same pool under the same budget? And could the authors also provide a broader comparison with other SOTA baselines?
8 comments

We thank the reviewer for their feedback and address each concern below. We have also highlighted the corresponding revisions in blue in the updated paper.


W1 and Q2 Clarification on the applicability of JOVE

We have added examples of planner-generated task graphs to the revised paper (see Appendix A.3.3). These examples illustrate how the planner identifies intermediate reasoning steps and dependencies not explicitly stated in the query. We have also revised Figure 1 (https://anonymous.4open.science/r/JOVE/overview_revised.pdf) to better illustrate task decomposition when the intermediate reasoning steps are not explicitly stated in the query. JOVE is designed for problems where decomposition yields useful, executable subtasks. For simple queries, or those that do not benefit from decomposition, JOVE’s planner may generate a single-node graph that reduces JOVE to query-level routing with optional verification, under the same resource constraints. We acknowledge that vague or poorly decomposed subtasks can degrade performance. We have clarified this in the revised paper (see Remark 3.4).

Quality predictor: We use MiniLM embeddings of node and candidate-model descriptions with a linear predictor to limit allocation overhead and support the regret analysis (Theorem 3.7). JOVE’s MILP can also use scores from other quality predictors, although the current regret guarantee relies on the stated linear model assumptions.


W1 Task graph sizes

We agree that fixing a graph size can introduce unnecessary work when a query admits a simpler plan. In the main experiments (Table 1), we generated four graphs per query (2-5 nodes) to increase the number of online learning rounds, particularly on smaller datasets.

Planner-selected graph sizes: We have evaluated one planner-selected graph per query across all four datasets in Appendix A.4.1 (Table 2, https://anonymous.4open.science/r/JOVE/Table2.png). JOVE achieves 49.3% mean accuracy, compared with 49.5% when using four graphs per query, suggesting that fixing multiple graph sizes is not necessary to maintain accuracy. On a mixed workload with one graph per query, JOVE achieves the highest accuracy among the considered resource-aware methods (50.5%, see Table 3, https://anonymous.4open.science/r/JOVE/mixed.png). Appendix A.3.3 also illustrates that, for a naturally two-hop question, requesting additional nodes produces finer-grained retrieval and answer extraction steps rather than necessarily introducing vague subtasks.


W2 and Q1 Planner ablation

We thank the reviewer for suggesting these comparisons. We chose Gemini 2.5 Flash-Lite for its low cost, fast inference, and reliable adherence to the task-graph JSON schema. We evaluated three alternative planners (Table 7, https://anonymous.4open.science/r/JOVE/ablation-planner.png): Llama 3.1 8B Instruct, Gemma 3 4B-IT, and a rule-based planner that splits queries at punctuation and conjunctions. Gemini 2.5 Flash-Lite achieves the highest accuracy on all four datasets, with Llama 3.1 8B Instruct as the closest alternative. Gemma 3 4B-IT achieves 6.25 percentage points lower mean accuracy and produces invalid task graphs for 5.1% of queries (scored as incorrect). The rule-based planner achieves only 11-29% accuracy across the four datasets, suggesting that simply splitting the question into parts often fails to capture the reasoning needed to solve it.

Why not let the planner answer the question directly? Table 7 (see the link above) shows that JOVE achieves 11.0 percentage points higher mean accuracy than direct calls to Gemini 2.5 Flash-Lite across the four datasets. Alongside this accuracy gain, JOVE gives the system greater control over end-to-end latency and API cost.

W3 and Q3 Extra baselines

Direct answers from stronger models: We have additionally evaluated GPT-OSS-120B and Llama-3.3-70B-Instruct from JOVE’s executor pool as single-call baselines. As shown in Table 7 (link above), GPT-OSS-120B achieves higher accuracy but at 2.47-8.78 times JOVE’s API cost and 1.88-3.74 times its latency. Llama-3.3-70B-Instruct exceeds JOVE’s accuracy only on MMLU-Pro and incurs higher costs on all four datasets.

Query-level routing: We added two online routing baselines beyond WR-Online: B.A. LinUCB [1] and LimBanFeed [2] (Table 1, https://anonymous.4open.science/r/JOVE/Table1.png). Across the four benchmarks, JOVE achieves higher accuracy and lower latency than both, with costs moderately higher than B.A. LinUCB but substantially lower than LimBanFeed.

Interpretation: B.A. LinUCB uses successive routing attempts and free answer-level feedback, while JOVE learns from paid node-level verification and can execute independent subtasks in parallel. LimBanFeed selects verifications after execution, whereas JOVE jointly optimizes both decisions under cost and latency constraints.

[1] Online Multi-LLM Selection via Contextual Bandits Under Unstructured Context Evolution, AAAI 2026

[2] Online Learning with LLM Experts from Limited Feedback, preprint Sept 2026


We thank the reviewer again for their time and feedback and would be happy to answer any further questions.

Thank you once again for your valuable comments on our submission. As the author-reviewer discussion period is approaching its end, we would like to kindly confirm whether we have sufficiently addressed your concerns. If any questions remain, please let us know, and we would be happy to clarify. If you are satisfied with our responses, we would greatly appreciate your consideration in adjusting the evaluation scores accordingly. We sincerely look forward to your feedback.

Reviewer_QexTOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes JOVE, which jointly selects executor LLMs and intermediate outputs for paid verification in task graphs under a long-term cost budget and per-query latency constraints. Verification improves future allocations without changing the current response. The method combines online quality estimation, an information-gain bonus, and per-query MILP optimization. Under stated assumptions, the paper establishes sublinear quality-learning regret and evaluates four reasoning benchmarks, reporting comparable average accuracy with much lower cost and latency than fixed-model inference baselines.

Critical strengths
  1. The joint formulation addresses a critical trade-off between allocating resources to current execution and investing in feedback to improve future decision-making. Including task dependencies and resource constraints makes this a substantive systems problem.
  2. Evaluation across four benchmarks shows a good balance between accuracy and resource use. Comparisons with random verification and decomposition ablation further confirm that the proposed design choices enhance performance.
Critical weaknesses
  1. The specific benefit of joint execution–verification optimization is not clearly isolated. The most significant efficiency gains are reported relative to fixed-model baselines, while JOVE uses a heterogeneous model pool. Although the random-verification comparison offers some insight, it is limited to Bamboogle and does not show superiority over an informed policy that prioritizes executor selection before verification allocation. Consequently, evidence supporting the paper’s central contribution remains limited.
  2. The theoretical guarantees offer limited support for practical resource compliance. The regret comparator uses the same resource estimates and budget prices as JOVE. The analysis does not demonstrate constraint satisfaction when considering estimated costs and latency quantiles. Early deadline violations and budget overspending within a finite horizon highlight the practical significance of this limitation, despite the paper’s acknowledgment of the issue.
Questions for authors
  1. How does JOVE perform compared to a policy that first selects executors and then allocates verification based on uncertainty and cost? Both use the same task graphs, model pool, estimator, and similar total spending. This comparison would clarify the specific benefits of joint optimization.
  2. What happens when estimated latency constraints are infeasible or MILP solving exceeds the reserved allocation time? How often do these situations arise in the reported experiments?
6 comments

We thank the reviewer for the constructive comments, which we address in detail below. We have also highlighted the corresponding revisions in blue in the updated paper.


W1 and Q1 Joint optimization vs execute-then-verify

We thank the reviewer for suggesting a comparison to isolate the benefits of joint optimization. Following the reviewer’s advice, we have added an execute-then-verify baseline that firstly selects executors and then decides nodes for verification. The baseline uses the same API budget as the original JOVE and matches JOVE’s average spending split by allocating 88% for execution, 12% for verification. Specifically, execute-then-verify firstly assigns executors using JOVE’s per-query MILP without the information-gain bonus. With the executor allocations fixed, it then solves a second MILP to select nodes for verification. The second MILP maximizes information gain minus a verification-cost penalty weighted by a separate Lagrange multiplier (Appendix A.4.5). This two-step baseline provides a direct comparison for assessing the benefit of optimizing execution and verification jointly. As shown in the updated Table 6 (https://anonymous.4open.science/r/JOVE/ablation-verify.png), JOVE outperforms this baseline across all four datasets.

Interpretation: The two-step baseline selects executors based on predicted node-executor quality and cost. Its verification step is then restricted to those fixed node-executor pairs only. For comparison, joint optimization (JOVE) allows verification value to directly influence executor selection: JOVE can favour a node-model pair whose verification is highly informative, even when its current predicted quality is lower. This provides learning opportunities that the two-step baseline may miss and potentially benefits policy learning. We have included this baseline and clarified the distinction in the revised manuscript (Appendix A.4.5).


W1 Extra routing baselines & verification ablation

We thank the reviewer for suggesting additional routing baselines. We have added B.A. LinUCB [1] and LimBanFeed [2], with results in the updated Table 1 (https://anonymous.4open.science/r/JOVE/Table1.png). Across all four datasets, JOVE achieves higher accuracy and lower latency than both baselines, with costs comparable to B.A. LinUCB and lower than LimBanFeed.

Interpretation: JOVE learns from selectively paid node-level verifications, without requiring final-answer correctness feedback, and allocates verification and execution within the API budget. Compared with JOVE’s setting, B.A. LinUCB allows successive routing attempts, incorporates previous outputs into next turn’s routing, and requests response evaluation after each turn, which is similar to forming a fully sequential task graph, incurring a much higher latency compared to JOVE with parallel executions. For LimBanFeed, it controls feedback frequency under a verification budget and selects certain responses for evaluation, without execution-side budget constraints. Its verification selection operates on past executions, which makes it also as an execute-then-verify baseline but without task decomposition and system constraints on latency and execution cost. Their disjoint optimization makes it suboptimal compared to JOVE.

We have also included verification ablation results on the other three datasets in the updated Table 6 (https://anonymous.4open.science/r/JOVE/ablation-verify.png). The new results further support the effectiveness of JOVE’s selective verification (over random verification) and joint optimization (over execute-then-verify).

[1] Online Multi-LLM Selection via Contextual Bandits Under Unstructured Context Evolution, AAAI 2026

[2] Online Learning with LLM Experts from Limited Feedback, preprint Sept 2026

W2 Scope of the theoretical guarantees

We agree that resource compliance under online resource estimates is not guaranteed by the current analysis. Theorem 3.7 establishes sublinear quality-learning regret for a sufficient range of verification weights (kvk_v), relative to a benchmark that uses the same resource estimates and budget prices as JOVE. The theorem does not account for resource-estimation errors and therefore does not establish constraint satisfaction for the online policy.

Separately, we establish resource-constrained guarantees in the oracle setting. Proposition A.3 (Appendix A.2.2) establishes long-run budget feasibility for the oracle policy with the dynamic multiplier update under the stated assumptions. Lemma A.1 (Appendix A.2.1) shows that an allocation satisfies the per-query latency chance constraint when the critical-path bound computed using true node-level quantiles fits within the deadline (Eq. 6). We have clarified the scope of these guarantees in the revised paper (page 7, line 363-371).

Early latency violation and cost overspending: Early deadline violations may result from inaccurate latency estimates, while initial overspending also reflects the time needed for the budget multiplier to adapt. The budget constraint (Eq. 2b) is asymptotic and permits temporary overspending, although the reported finite-horizon average costs remain above the budget. Appendix A.4.3 (Tables 4 and 5) show that, after the first 200 queries, all four datasets achieve deadline hit rates of at least 96% (against a 90% target) and interval-average costs below the budget of 2×10−42 \times 10^{-4} USD per query.

For applications that require constraint compliance from the first query, JOVE can use offline-calibrated cost and latency estimators while continuing to learn model quality online. Such estimators may reduce early constraint violations, although satisfying the per-query latency chance constraint requires sufficiently conservative estimates of the true latency quantiles. We have noted these points in the revised paper (page 10, line 507-512).


Q2 Infeasible latency and solver runtime

MILP solver runtime: We reserve 0.1s of the 16s end-to-end latency deadline for solving the MILP. If the solver exceeds this allowance, less time remains for execution, potentially causing a deadline violation. In our main experiments, the mean solve time was 32.8 ms and the maximum was 45.8 ms, so all MILPs were solved within the reserved time.

Further interpretation: Larger task graphs may increase MILP complexity and solve time. However, we observed no consistent increase in solve time across graphs with one to five nodes. To test a larger instance, we combined existing task graphs into synthetic 20-node graphs. The mean solve time was 33.1 ms, comparable to that observed for the smaller graphs.

Infeasible latency constraint: In our experiments, all MILP instances were feasible under the specified latency constraints. In practice, a requested deadline can make the MILP infeasible if it is shorter than the minimum achievable latency under the available executor assignments. Accordingly, Remark 3.2 assumes that the deadline is provisioned to ensure MILP feasibility. For practical applications, JOVE can compute the minimum feasible deadline after generating the task graph by minimizing the estimated critical-path latency over available executor assignments, accounting for planning and allocation overhead. If the requested deadline is below this minimum, JOVE can report the earliest feasible deadline. Alternatively, it can solve a relaxed MILP by extending the deadline to this minimum or removing the latency constraint while retaining the cost-aware objective. We have clarified these points in the revised paper (Remark 3.2 and page 10, line 513-522).


We are happy to answer any further questions. Thank you again for your time and commitment!

Thank you once again for your valuable comments on our submission. As the author-reviewer discussion period is approaching its end, we would like to kindly confirm whether we have sufficiently addressed your concerns. If any questions remain, please let us know, and we would be happy to clarify. If you are satisfied with our responses, we would greatly appreciate your consideration in adjusting the evaluation scores accordingly. We sincerely look forward to your feedback.

Reviewer_4UV3OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes JOVE, an online framework that learns a policy for assigning subtasks to corresponding executor LLMs, while jointly considering verification costs with planning and execution. JOVE solves an important problem: automated systems for per-task LLM routing typically require human or LLM judge feedback, yet they assume that verification comes at no cost, limiting their online or practical feasibility. JOVE instead integrates long-term, cross-request verification cost into a shared budget along with planning and task execution. JOVE shows that, under specific assumptions, quality-learning regret grows sublinearly with the number of questions, establishing stable allocation quality over long sequences.

Experiments cover four reasoning benchmarks and a pool of eight models as potential executors per subtask. JOVE achieves the highest task accuracy among resource-aware baselines while delivering strong cost and latency savings. Analysis empirically validates key assumptions, including using aggregated node-level correctness as a proxy for final correctness, constraint satisfaction, and sensitivity to hyperparameter choices.

Critical strengths

S1. The paper makes a novel contribution by jointly integrating planning, execution, and verification costs into one budget for an online optimization problem. This is a promising direction for building self-evolving multi-agent systems with long-term sustainability.

S2. The approach is theoretically grounded in multiple key aspects, notably the sublinear regret analysis and long-term cost feasibility in the appendix.

S3. The paper shows significant empirical gains, achieving the highest accuracy among resource-aware methods and strong cost/latency reductions. Pareto-optimality is demonstrated in Figure 2. Results include statistical error, which is critical for reasoning workloads that involve randomness due to LLM sampling.

S4. Several assumptions are validated empirically. For example, the use of aggregated subtask correctness as a proxy for end-to-end task correctness is justified in Figure 3(a).

Critical weaknesses

W1. A key concern is data leakage, which the authors partly address. Per benchmark, each testing sample is used to generate multiple task graphs. These graphs may contain very similar nodes, as acknowledged by the authors. When a node from an earlier graph is verified, the verification labels are integrated into the quality estimator weights and affect future graphs derived from the same test sample, which might contain a high-similarity node. Table 2 in A.4.1 addresses this but only on one benchmark. A complete analysis of potential data leakage issues across all benchmarks could fully resolve this concern.

W2. In the current evaluation, each sequence of task graphs only includes in-distribution samples, i.e., from the same benchmark set. It is unclear if the online optimizer generalizes to mixed workloads from multiple benchmarks that may differ in feature-to-label relationships.

W3. The paper does not directly show how quickly the online learning algorithm converges. Appendix A.4.2 partly shows how deadline hit rate and cost change with more processed samples, but not accuracy.

Questions for authors

Q1. How fast does JOVE converge (in terms of processed samples), and how does it compare to other online learning solutions such as WR-Online?

3 comments

We thank the reviewer for recognizing the novelty of our proposed joint execution-verification problem and our solution JOVE. We address the raised concerns below.


W1 Repeated queries and the learning sequence

We thank the reviewer for this suggestion and have added one-graph-per-query results for the remaining three datasets, completing this evaluation across all four benchmarks (updated Table 2, https://anonymous.4open.science/r/JOVE/Table2.png). In the main paper Table 1, we generate graphs with 2, 3, 4, and 5 nodes for each query to provide more graph samples for online learning, particularly on smaller datasets (Bamboogle and LiveBench-Reasoning). In the updated Table 2 (each query appears only once), JOVE retains its favourable accuracy-latency-cost trade-off. Its accuracy drops slightly on Bamboogle (from 49.3 to 47.9) and LiveBench-Reasoning (41.3 to 40.9), where these settings provide fewer online learning rounds to converge, while performance remains largely unchanged on MMLU-Pro and GPQA. These results suggest that JOVE’s overall advantage persists without repeated questions. We have further explained this in the updated paper (Appendix A.4.1).


W2 Learning on a mixed workload

We agree with the reviewer’s suggestion. We have conducted a mixed-workload experiment to include queries of all four datasets. The queries are randomly shuffled, with each appearing only once in the online learning sequence. We present the results in Table 3 (https://anonymous.4open.science/r/JOVE/mixed.png). On this mixed workload, JOVE achieves the highest accuracy (50.5%) among the compared resource-aware methods, with mean latency of 6.32 s and mean API cost of 2.14×10−42.14 \times 10^{-4} USD per query.


W3 and Q1 Learning speed

We have added learning curves comparing the cumulative accuracy of JOVE and other online learning baselines under the mixed workload setting (Figure 9, https://anonymous.4open.science/r/JOVE/mixed_curve.png). We notice that the curves fluctuate in the early rounds because each answer carries substantial weight in the running average and the policies have had few opportunities to learn. For LimBanFeed and JOVE, limited verification may make these early fluctuations more pronounced. WR-Online and B.A. LinUCB assume free (but unrealistic) final-answer correctness feedback in every round, yielding more stable learning in the beginning. For further comparison, the three online baselines learn from final-response labels for the original tasks, while JOVE trains its policy on smaller subtasks using node-level labels, which may provide simpler patterns for the policy to learn and converge. As more queries are processed, all curves stabilize. JOVE leads for most of the sequence and finishes with the highest accuracy. We emphasize that JOVE enables online learning by selectively paid verification within the same budget as LLM execution, which is a more practical and challenging setting in this area.


We thank the reviewer again for their support of our work. We also added other experiments and clarifications to address concerns raised by other reviewers. These revisions are highlighted in blue in the revised paper. We would be happy to answer any further questions. Thank you again for your time and support.

Reviewer_4UV3OpenReview ↗

Reviewer's response

Thanks to the authors for the clarification. The updated results on workloads with no repeated queries and from mixed datasets strengthen the evaluation. I also appreciate the discussion on convergence speed. I maintain my positive score.

We are glad that our response has addressed your concerns. We appreciate your suggestions which helped us strengthen the paper. Thank you again for your time and support!

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of rebuttal

Dear Area Chair and reviewers,

Thank you for taking the time to consider our work and for the constructive suggestions. To make the rebuttal easier to follow, we briefly summarize JOVE’s main contribution and explain how the new experiments and clarifications address the points raised in the reviews. We have marked the resulting changes in blue in the revised paper.

JOVE in brief

Given a planner-generated task graph, JOVE jointly chooses which LLM executes each subtask and which subtask outputs to verify for online learning. Independent subtasks can run in parallel to reduce response time. For each query, JOVE solves a mixed-integer linear program (MILP) that uses online estimates of quality, cost, and latency to balance execution quality against resource use (API spending and end-to-end latency). One central trade-off in JOVE is how to split the shared API budget between executing the current query and paying for verification that improves future executor choices. JOVE trains its policy using only subtask-level verification, making it easier to deploy in settings where obtaining correctness labels for final answers is difficult or costly.

Additional experiments

  • Joint execution and verification (QexT, W1/Q1). We added a two-stage baseline that fixes executor assignments before choosing what to verify using information gain (Appendix A.4.5, https://anonymous.4open.science/r/JOVE/ablation-verify.png). With the same experimental setting, JOVE improves final-answer accuracy by 2.8–4.0 percentage points across the four datasets at similar cost and latency. We also extended the random-verification comparison to all four benchmarks.
  • Repeated queries, mixed workloads, and learning curves (4UV3, W1–W3/Q1, and enii, W1). With one graph per query and the planner choosing its size (Appendix A.4.1, https://anonymous.4open.science/r/JOVE/Table2.png), JOVE achieved 49.3% mean accuracy, compared with 49.5% with four graphs per query. On a shuffled stream of distinct queries from all four datasets (Appendix A.4.2, https://anonymous.4open.science/r/JOVE/mixed.png), JOVE led the online baselines in cumulative accuracy with limited cost and latency.
  • Planner ablation (enii, W2/Q1). We tested two smaller LLM planners and a rule-based planner (Appendix A.4.6, https://anonymous.4open.science/r/JOVE/ablation-planner.png). Llama 3.1 8B came closest to Gemini 2.5 Flash-Lite. Using Gemini as JOVE’s planner yielded 11.0 percentage points higher mean accuracy than asking Gemini to answer directly.
  • Stronger baselines (enii, W3/Q3, and QexT, W1). We added direct calls to GPT-OSS-120B and Llama-3.3-70B-Instruct (Appendix A.4.6, https://anonymous.4open.science/r/JOVE/ablation-planner.png), along with two online routers, Budget-Aware LinUCB and LimBanFeed (Section 4, https://anonymous.4open.science/r/JOVE/Table1.png). GPT-OSS-120B achieved higher accuracy than JOVE at higher cost and latency. JOVE was more accurate and faster on average than both query-level routing baselines, with average cost between theirs.

Additional clarifications

  • When decomposition helps (enii, W1/Q2). We added examples of planner-generated graphs (Appendix A.3.3). Remark 3.4 further explains that when decomposition offers little benefit, the planner can return a single-node graph. JOVE then routes the full query to one executor and decides whether to verify the answer under the same resource constraints.
  • Scope of the guarantees (QexT, W2). We clarified that Theorem 3.7 establishes sublinear regret for model quality learning without considering errors in online resource estimates (page 7, line 363-371). We explained that the early latency violation and budget overspending are common in constrained online learning with cold-start, which can be addressed with offline-calibrated estimators to ensure the constraints compliance from the start (page 7, line 371, and page 10, 507-512).
  • Deadline feasibility and solver time (QexT, Q2). We clarified that the MILP assumes a feasible latency constraint. If the requested latency is too short, JOVE can compute the minimum feasible latency and solve a relaxed MILP by either extending the latency requirement to that value or removing the latency constraint while retaining the cost-aware objective. In the main experiments, every MILP solve finished within the reserved 100 ms, with a maximum solve time of 45.8 ms (Remark 3.2 and page 10, line 513–522).

Thank you again for the constructive feedback that helped us improve the paper. We hope the new results and clarifications are helpful as you revisit your assessments. We would be glad to discuss any remaining questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.