Hcapo Hindsight Credit Assignment

Technique: Hindsight Importance Ratios for Causal Step-Level Credit

Long-horizon tasks suffer from credit assignment myopia: trajectory-level rewards don't reveal which intermediate steps were responsible for success. HCAPO addresses this by using the LLM itself as a post-hoc critic: it conditions on successful outcomes to estimate hindsight importance ratios that amplify credit for causally relevant steps while suppressing less instrumental ones.

Rather than training separate value models, this method leverages self-normalized importance sampling with the base LLM, making it training-free and readily integrated into existing RLVR frameworks like GRPO.

Core Concept

The key innovation is computing hindsight Q-values by:

1. Self-Conditioning on Success: Inject the successful outcome into the LLM's prompt context
2. Importance Ratio Estimation: Measure how step probability changes when conditioned on success
3. Causal Filtering: Steps whose probability increases given success are causally responsible
4. Multi-Scale Integration: Combine macro-level trajectory rewards with micro-level Q-values

This produces step-wise credit signals grounded in the model's own conditional distributions, avoiding external value function errors.

Architecture Overview

• Base LLM policy: Unchanged from baseline RLVR method
• Hindsight conditional: Re-prompt the model with outcome information
• Importance ratio computation: Token-level log-probability deltas
• Self-normalized importance sampling: Aggregate step-level credits
• Multi-scale reward aggregation: Blend trajectory and step signals

Implementation Steps

Step 1: Compute Self-Normalized Importance Ratios

For each step, estimate how probability changes when conditioned on successful outcome.

import torch
import torch.nn.functional as F

def compute_hindsight_importance_ratios(
    model,
    trajectory,
    input_ids,
    successful_outcome
):
    """
    Compute importance ratios ρ for each step in trajectory.

    trajectory: list of (token_id, log_prob) tuples
    input_ids: original input token sequence
    successful_outcome: target outcome to condition on
    """
    trajectory_length = len(trajectory)
    importance_ratios = []

    # Original forward pass (already computed, use cache)
    original_log_probs = torch.tensor(
        [log_prob for _, log_prob in trajectory],
        dtype=torch.float32
    )

    # Hindsight forward pass: condition on successful outcome
    # Prepend outcome to input as conditioning
    hindsight_input = torch.cat([
        input_ids,
        torch.tensor([[model.tokenizer.encode(successful_outcome)]])
    ], dim=1)

    with torch.no_grad():
        hindsight_outputs = model(hindsight_input)
        hindsight_logits = hindsight_outputs.logits

    # Extract log probabilities for trajectory tokens
    hindsight_log_probs = []
    for t, (token_id, _) in enumerate(trajectory):
        logits = hindsight_logits[0, input_ids.shape[1] + t]
        log_prob = F.log_softmax(logits, dim=-1)[token_id]
        hindsight_log_probs.append(log_prob.item())

    hindsight_log_probs = torch.tensor(hindsight_log_probs, dtype=torch.float32)

    # Importance ratio: exp(log_prob_hindsight - log_prob_original)
    # This measures probability boost when conditioned on success
    log_ratios = hindsight_log_probs - original_log_probs
    importance_ratios = torch.exp(torch.clamp(log_ratios, min=-5, max=5))

    return importance_ratios

Step 2: Formulate Hindsight Q-Values

Combine importance ratios with trajectory returns to create step-level credits.

def compute_hindsight_q_values(
    trajectory,
    returns,
    importance_ratios,
    gamma=0.99
):
    """
    Compute Q^H = ρ × G where G is discounted return from each step.

    trajectory: list of steps
    returns: trajectory-level return G
    importance_ratios: tensor of importance ratios per step
    gamma: discount factor
    """
    trajectory_length = len(trajectory)

    # Discounted cumulative return from each step
    q_values = []
    cumulative_return = returns

    for t in range(trajectory_length - 1, -1, -1):
        # Q-value: hindsight importance weighted return
        q_hindsight = importance_ratios[t] * cumulative_return

        q_values.insert(0, q_hindsight)

        # Update cumulative return for previous step
        cumulative_return = cumulative_return / gamma  # Undo discount

    q_values = torch.stack(q_values)

    return q_values

Step 3: Multi-Scale Reward Integration

Blend macro-level trajectory signals (GRPO baseline) with micro-level Q-values.

def compute_multi_scale_returns(
    trajectory_return,
    hindsight_q_values,
    macro_weight=0.6,
    micro_weight=0.4
):
    """
    Combine trajectory-level and step-level signals.

    trajectory_return: scalar return for full trajectory
    hindsight_q_values: tensor of step-level Q-values
    macro_weight, micro_weight: balance between scales
    """
    # Macro signal: repeat trajectory return
    macro_signal = torch.full_like(
        hindsight_q_values,
        trajectory_return
    ) * macro_weight

    # Micro signal: hindsight Q-values normalized
    micro_signal = (
        hindsight_q_values / (hindsight_q_values.std() + 1e-8)
    ) * micro_weight

    # Combined: weighted sum
    multi_scale_returns = macro_signal + micro_signal

    return multi_scale_returns

Step 4: Policy Gradient with Multi-Scale Advantages

Update policy using blended advantage estimates (placeholder for GRPO integration).

def grpo_step_with_hindsight(
    model,
    input_ids,
    trajectory,
    trajectory_return,
    model_optimizer,
    num_reference_samples=4
):
    """
    GRPO training step augmented with hindsight credit assignment.
    """
    # Compute importance ratios from hindsight conditioning
    successful_outcome = "Correct"  # Placeholder
    importance_ratios = compute_hindsight_importance_ratios(
        model,
        trajectory,
        input_ids,
        successful_outcome
    )

    # Compute hindsight Q-values
    hindsight_q_values = compute_hindsight_q_values(
        trajectory,
        trajectory_return,
        importance_ratios
    )

    # Multi-scale integration
    multi_scale_returns = compute_multi_scale_returns(
        trajectory_return,
        hindsight_q_values,
        macro_weight=0.6,
        micro_weight=0.4
    )

    # Forward pass for policy gradient
    outputs = model(input_ids)
    log_probs = F.log_softmax(outputs.logits, dim=-1)

    # Extract log probs for trajectory tokens
    trajectory_log_probs = []
    for t, (token_id, _) in enumerate(trajectory):
        logit = outputs.logits[0, input_ids.shape[1] + t]
        log_prob = F.log_softmax(logit, dim=-1)[token_id]
        trajectory_log_probs.append(log_prob)

    trajectory_log_probs = torch.stack(trajectory_log_probs)

    # Policy gradient: advantage-weighted log probs
    baseline = multi_scale_returns.mean()
    advantages = multi_scale_returns - baseline

    policy_loss = -(trajectory_log_probs * advantages).mean()

    model_optimizer.zero_grad()
    policy_loss.backward()
    model_optimizer.step()

    return {
        'policy_loss': policy_loss.item(),
        'importance_ratio_mean': importance_ratios.mean().item(),
        'advantage_mean': advantages.mean().item()
    }

Practical Guidance

When to Use:

• Long-horizon reasoning tasks (10+ steps)
• Scenarios where trajectory rewards are sparse or weak
• GRPO-based training where step-level credit is bottleneck
• Multi-step problem solving with clear intermediate milestones

When NOT to Use:

• Short horizon tasks (<3 steps) where trajectory signals suffice
• Extreme latency constraints (hindsight pass adds 2-3x inference)
• Tasks without clear success conditions to condition on
• Very large models where re-inference is prohibitively expensive

Hyperparameters:

• macro_weight: 0.5-0.8; increase if trajectory signal is reliable
• micro_weight: 0.2-0.5; complement with macro signal
• importance ratio clipping: [-5, 5] prevents numerical instability
• number of hindsight samples: 1 usually sufficient (could ensemble)

Common Pitfalls:

• Over-relying on micro signal when trajectory supervision is weak
• Importance ratios exploding due to log-probability differences
• Hindsight conditioning conflicting with original input (prompt carefully)
• Forgetting to normalize Q-values before aggregation

Reference

Hindsight Credit Assignment paper on arXiv