[Fudan & Waterloo] Does RL Expand the Capability Boundary of LLM Agents? A PASS@(k, T) Analysis

TL;DR

Conventional wisdom, based on static math benchmarks, suggests Reinforcement Learning (RL) just makes LLMs "more certain" of what they already know. This paper shatters that myth for LLM Agents. By introducing PASS@(k, T)—a metric that tracks both sampling attempts ($k$) and interaction depth ($T$)—the authors prove that RL genuinely teaches agents new compositional strategies that Supervised Fine-Tuning (SFT) actually destroys.

The "Convergence" Myth in LLM Reasoning

In the world of static reasoning (like MATH-500), recent studies (e.g., Yue et al., 2025) found that as you increase the sampling budget ($k$), the performance of RL-tuned models and base models eventually converges. This led to a pessimistic conclusion: RL doesn't "teach" anything new; it just shifts probability mass towards correct answers the model could already find with enough luck.

But does this hold for agents? Agents don't just "think"; they "act" and "observe." A bridge question like "What is the nationality of the director of Film X?" requires sequential tool use. If your interaction depth $T$ is limited to 1, no amount of re-sampling ($k\to \infty$) will solve it. The capability is gated by the depth of interaction.

Methodology: The PASS@(k, T) Framework

The authors formalize capability as a two-dimensional grid.

1. k-axis (Sampling): How many independent trajectories do we allow?
2. T-axis (Interaction): How many search/tool rounds are allowed per trajectory?

This framework allows us to define:

• Capability Expansion: When RL solves problems that the Base model never solves, even with infinite sampling.
• Efficiency Improvement: When RL simply solves "solvable" problems more consistently.

Results: RL Wins Where SFT Fails

The study compared a Base model (Qwen2.5-7B), an SFT model (expert imitation), and an RL model (trained via GRPO).

1. The Category C Breakthrough

On "Bridge" questions (sequential retrieval), RL showed a widening gap over the Base model at high $k$. Most strikingly, SFT regressed the capability boundary. Even though SFT and RL saw the exact same 200 training problems, SFT's imitation learning caused a "diversity collapse."

2. Strategy Diversity

RL preserves the "creativity" of the base model. While SFT collapsed to only ~15 unique search sequences per problem, RL maintained ~45, similar to the base model. RL isn't inventing "new" search queries; it's learning how to use the information it finds.

3. Perplexity Decomposition

By analyzing per-token surprisal, the authors found that the "novelty" in RL trajectories is concentrated in the Reasoning tokens, not the Search tokens. The agent isn't becoming a better "searcher"; it's becoming a better "thinker" who can bridge the gap between two retrieved facts.

Critical Insights: Why Does This Matter?

1. Reweighting vs. Replacement: SFT tries to replace the model's distribution with a narrow expert path. RL reweights the model's existing vast library of strategies toward those that work.
2. The Agentic Advantage: RL is uniquely suited for agents because the environment provides the "verifiable reward" that allows the model to explore beyond the limits of static imitation.
3. Practical Workflow: On compositional tasks, skip SFT. Use GRPO with a simple task reward. It is more robust and expands the actual problem-solving horizon.

Conclusion & Limitations

This work reconciles the two versions of the RL story: RL is just a re-shaper of probability in static settings, but in agentic settings, that re-shaping unlocks Compositional Capabilities that feel—and function—like brand new skills.

Limitations: The study used a small 7B model and a limited search corpus. Future work must verify if these "capability boundaries" continue to expand as we scale to 70B+ parameters or web-scale tool environments.

Takeaway: If you want a more reliable calculator, use SFT. If you want a more capable agent, use RL.