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

arXiv: https://arxiv.org/abs/2610.03296 · HTML: https://mlsanity.com/paper/2610.03296/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 33 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 28 of 28)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [LiveBench: A Challenging, Contamination-Limited LLM Benchmark](https://mlsanity.com/paper/2406.19314/) (2024)
- [An LLM Compiler for Parallel Function Calling](https://mlsanity.com/paper/2312.04511/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation](https://mlsanity.com/paper/2307.15337/) (2023)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [Router-R1: Teaching LLMs Multi-Round Routing and Aggregation via Reinforcement Learning](https://mlsanity.com/paper/2506.09033/) (2025)
- [MixLLM: Dynamic Routing in Mixed Large Language Models](https://mlsanity.com/paper/2502.18482/) (2025)
- [Learning to Keep a Promise: Scaling Language Model Decoding Parallelism with Learned Asynchronous Decoding](https://mlsanity.com/paper/2502.11517/) (2025)
- [Adaptive LLM Routing under Budget Constraints](https://mlsanity.com/paper/2508.21141/) (2025)
- [S-DAG: A Subject-Based Directed Acyclic Graph for Multi-Agent Heterogeneous Reasoning](https://mlsanity.com/paper/2511.06727/) (2025)
- [Plato: Plan to Efficiently Decode for Large Language Model Inference](https://mlsanity.com/paper/2402.12280/) (2024)
- [HybridFlow: Resource-Adaptive Subtask Routing for Efficient Edge-Cloud LLM Inference](https://mlsanity.com/paper/2512.22137/) (2025)
- [WISERouter: LLM Routing with Workload Budget Constraint](https://mlsanity.com/paper/2607.23765/) (2026)
- [Neural Bandit Based Optimal LLM Selection for a Pipeline of Subtasks](https://mlsanity.com/paper/2508.09958/) (2025)
- [Serving Agentic Workflows with a Physical-Plan Compiler and Adaptive Runtime](https://mlsanity.com/paper/2607.02942/) (2026)
- [Mind the Delay: Latency-aware Query Routing for Heterogeneous LLM pools](https://mlsanity.com/paper/2607.18253/) (2026)

## Abstract (arXiv)

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.