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

QVal: Training-Free Evaluation of Dense Supervision Signals§

Problem§

LLM agents in long-horizon tasks (e.g., web navigation, robotics) suffer from sparse outcome rewards. Dense supervision methods (e.g., confidence scores, embedding similarities) aim to give intermediate rewards but are expensive to evaluate: downstream training conflates signal quality with engineering choices.

Core Methodology: QVal Score§

QVal measures Q-alignment: how well a dense supervision signal $\mathrm{score}(s,a)$ orders actions according to the Q-values $Q^*(s,a)$ of a strong reference policy.

1. Reference Policy Training: Train a policy (e.g., via PPO or behavior cloning) using outcome-only rewards to obtain Q-values for each state-action pair across collected trajectories. This is done once per environment.
2. Score Extraction: For each evaluated dense supervision method, extract scores for the same state-action pairs.
3. Rank Correlation: Compute Spearman's rank correlation coefficient $\rho$ between the method's scores and the reference Q-values:

$$ \rho = 1 - \frac{6 \sum d_i^2}{n(n^2-1)} $$ where $d_i$ is the difference in ranks of the two scores for pair $i$. Higher $\rho$ indicates better alignment with optimal action ordering.

Implementation Details§

• Environments: 4 diverse tasks (WebShop, ALFWorld, etc.) with trajectory lengths up to hundreds of steps.
• Methods: 21 methods spanning 7 families (e.g., prompting, self-distillation, embedding similarity, intrinsic confidence).
• Backbones: 6 open-weight LLMs (e.g., Llama 2, Mistral).
• Key Finding: Simple prompting baselines (e.g., "rate this action from 0 to 10") often outperform complex learned methods.

Code Snippet§

import numpy as np
from scipy.stats import spearmanr

def qval_score(method_scores: np.ndarray, q_values: np.ndarray) -> float:
    """
    Compute QVal score as Spearman correlation between method scores and Q-values.
    """
    rho, _ = spearmanr(method_scores, q_values)
    return rho

# Example usage:
# reference_policy_q = get_reference_q_values(trajectories)  # precomputed
# method_scores = my_dense_supervision_method(trajectories)
# qval = qval_score(method_scores, reference_policy_q)

Key Results§

• Performance clusters by method family (prompting > self-distillation > embedding similarity).
• Findings are consistent across model sizes and environments.
• QVal requires no training of the evaluated method, reducing cost ~100x compared to full pipeline evaluation.