QVal: Cheaply Evaluating Dense Supervision Signals for Long-Horizon LLM Agents

🕒 Published (v1): 2026-06-30 17:58 UTC · Source: Arxiv · link

Why this paper was selected

Dense rewards cheaply for long-horizon agents; practical enabler for RL training

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Training dense supervision signals for long-horizon LLM agents is expensive because evaluation requires full downstream RL runs that conflate signal quality with engineering choices. QVAL is a training-free testbed that measures a signal's Q-alignment — how well it rank-orders actions according to reference Q-values — enabling cheap pre-training comparison. Across 21 methods, 4 environments, and 6 backbones (>1.2K experiments), simple direct-prompting baselines consistently outperform recent specialized methods.

Problem

Long-horizon LLM agent trajectories (hundreds to thousands of actions) make outcome-only rewards too sparse to guide learning. Dense supervision methods score intermediate steps, but the only existing evaluation protocol integrates each method into a full post-training pipeline and measures downstream task performance. This is computationally expensive, makes methods from different families (which require incompatible training setups) incomparable, and conflates the intrinsic quality of the learned signal with RL algorithm choice, normalization, loss-integration strategy, and other engineering confounders. No common, direct benchmark exists.

Method

QVAL formalizes the evaluation of dense supervision as measuring Q-alignment: given a reference policy \(\pi\) as close to optimal as the environment allows, a method \(k: \mathcal{S} \times \mathcal{A} \to \mathbb{R}\) is Q-aligned if

\[k(s,a) = \phi\!\left(Q^\pi(s,a)\right) \quad \text{for some strictly increasing } \phi.\]

The testbed pipeline: 1. Collect trajectories in each environment with sub-optimal or mixed policies to ensure diversity of high- and low-value state-action pairs. 2. Label with reference Q-values via Max-Value Monte Carlo (MVMC): restore the environment to state \(s_t\), force action \(a_t\), roll out \(\pi\) several times, and take the maximum discounted return as \(Q^\pi(s_t, a_t)\). Reference policies are scripted optimal controllers (FrozenLake, OpenApps), an expert planner (ALFWorld), or GPT-5.5 with \(k=16\) rollouts (TerminalBench). 3. Score every (s, a) pair with each candidate dense supervision method. 4. Measure Q-alignment by Spearman's \(\rho\) between predicted scores and reference labels. Methods that output permutations over candidate actions use per-state Spearman averaged across states.

QVAL-v1.0 covers four environments (FrozenLake, ALFWorld, OpenApps, TerminalBench) spanning discrete to open-ended action spaces, text and visual observations. Backbones are Qwen3.5 (9B–122B-A10B) and Gemma 4 (26B-A4B, 31B), held fixed across methods within each experiment to isolate signal quality.

Key Contributions

• QVAL framework: training-free, model-fixed evaluation protocol that isolates dense supervision signal quality from downstream training engineering choices.
• QVAL-v1.0 benchmark: datasets of state-action pairs with reference Q-values across 4 environments, evaluating 21 methods from 7 families over 6 open-weight backbones, totaling >1.2K experiments.
• Empirical findings: simple direct-prompting and ranking baselines outperform all more complex alternatives; performance clusters by methodological family; text observations outperform visual ones; added complexity within a family does not improve Q-alignment.
• Extensible infrastructure: new environments require only a data collection and MVMC labeling pass; new methods require only one scalar per (s, a) pair.

Results

• Direct prompting and ranking methods achieve the highest Q-alignment across all environments and backbones, outperforming all seven other families on average.
• Performance clusters strongly by family: methods within the same family produce similar Spearman \(\rho\) ranges, validating the taxonomy.
• Complexity does not help within families: direct-batched/direct-sequential/direct-16 do not clearly outperform direct-single; codegen-avg improves mean \(\rho\) over codegen slightly but does not reduce variance; sdpo-gt (oracle privileged information) does not improve over sdpo.
• Code-based methods show the largest variance and perform well in small, structured environments (FrozenLake) but degrade on open-ended settings (TerminalBench).
• Text observations produce stronger Q-alignment than image observations across the evaluated methods.
• Relative ordering of methods is largely preserved across action-value (\(Q^\pi\)) and state-value (\(V^\pi\)) targets.
• GPT-5.5 reference policy achieves 100% Pass@16 on the TerminalBench subset; results remain consistent when replacing it with Claude Opus 4.7 as backbone.

Limitations

• Reference Q-values in open-ended environments (TerminalBench) depend on MVMC rollouts from a frontier model (GPT-5.5), introducing approximation error when that model is itself imperfect.
• QVAL-v1.0 covers only four environments; generalizability of rankings to other domains (e.g., multi-agent, tool-use with external APIs, very long context) is untested.
• Q-alignment is argued as a proxy for downstream training utility, but the causal link — that high \(\rho\) reliably predicts better RL training outcomes — is not validated experimentally in the paper.
• Visual modality results are weaker overall, and the method taxonomy for vision-centric settings may be less informative than for text.
• Methods requiring internal model states (log-probabilities) require open-weight models, limiting applicability to proprietary APIs.

Relevance to Agentic AI / LLM Agents

QVAL directly addresses a core bottleneck in training long-horizon LLM agents: the absence of cheap, standardized ways to evaluate intermediate-step supervision signals before committing to expensive RL post-training runs. The finding that simple prompting baselines outperform specialized dense supervision methods challenges recent assumptions in the agent RL literature and reorients the research agenda. The Q-alignment metric and MVMC labeling protocol are general tools applicable to any agentic benchmark, making QVAL a likely standard evaluation harness for future dense-reward and process-reward model research in LLM agents. The testbed also supports test-time search (MCTS-style rollouts), broadening its relevance beyond training to inference-time agent planning.