arXiv AI
Oct 5

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

JOVE is an online framework that jointly assigns large language model (LLM) executors and selects intermediate outputs for paid verification in directed acyclic task graphs. It balances immediate execution costs with future learning by solving per-query mixed‑integer linear programs and updating task‑dependent LLM quality estimates through verification feedback. Experiments on four reasoning benchmarks show that JOVE matches standard inference accuracy while cutting average cost and latency by at least 3.17×.

By Haoran Zhang, Dongjun Kim, Seohyeon Cha, Kevin S Chan, Ananthram Swami, Gustavo De Veciana, Haris Vikalo
arXiv Machine Learning
Oct 5

Online Verification of Language Model Responses Under Cost Constraints

The paper introduces OMVV, an online multi-verifier algorithm that maintains a pool of weak verifiers with varying costs and performance. It adaptively selects a verifier each round using an online score combiner and exponential-weights routing, providing distribution-free guarantees on false-accept and false-reject rates. Experiments on reasoning benchmarks show OMVV achieves higher accuracy at lower verification cost than any single fixed verifier across different budgets.

By Erfan Hajihashemi, Yanning Shen
arXiv AI
Sep 28

Nice Fold or Hero Call: Learning Budget-Efficient Thinking under Policy-Dependent Solvability

The paper introduces Budget‑Efficient Thinking (BET), a two‑stage framework that treats adaptive reasoning as a computational investment, aligning solve‑or‑fold decisions with expected return rather than perceived difficulty. BET learns three distinct behaviors: concise short solves for easy queries, early abstention (nice fold) when further reasoning is unlikely to pay off, and allocating sufficient compute (hero call) for hard‑but‑solvable questions. Experiments on seven benchmarks with three base models show BET cuts reasoning tokens by 54% while boosting accuracy by up to 3.2%, and it transfers effectively to scientific QA and logical reasoning tasks.

By Zhaomeng Zhou, Lan Zhang, Junyang Wang, Mu Yuan, Songlin Liu, Tingzhao Li, Yiqing Hu, Yumeng Zhao