On Turn-Level Best-of-N Sampling for Scaling LLM Agents

Jalaj Bhandari, Dhawal Gupta, Hongli Zhan, Zhenting Wang, Varad Pimpalkhute, Zhengzhong Liu, Eric Xing, Rupesh SrivastavaarXiv 2026 · arXiv

This paper from the Institute of Foundation Models (MBZUAI Labs) explores a practical way to make Large Language Model (LLM) agents more reliable. While "scaling laws" usually refer to training bigger models, this work focuses on inference-time scaling—using more compute during execution to get better results.

TL;DR

The authors propose Turn-level Best-of-N (Turn-BoN), a method where an agent generates $N$ candidate actions at every step, and a separate "selector" LLM picks the best one to execute. This simple change improves task success by 5–10%, makes agents significantly more consistent, and surprisingly reduces the total number of turns needed to solve a task by nearly half.

What Problem Does This Paper Address?

LLM agents are notoriously inconsistent. An agent might solve a complex software engineering task on one attempt but fail on the next simply because it sampled a suboptimal action at a critical juncture.

Existing ways to fix this are often impractical:

  1. Trajectory-level Best-of-N: Generating $N$ complete, independent attempts and picking the best one. This requires $N$ parallel environments (sandboxes), which is resource-heavy and impossible if the "environment" is a user's actual machine.
  2. Search (MCTS/DFS): These require "checkpointing" and "restoring" environment states to explore different branches, which is technically difficult in complex, real-world systems.

The authors ask: Can we improve agent performance by scaling compute at the turn level, without needing multiple sandboxes or state rollbacks?

Methods

The authors use a Generator-Selector framework:

  • Generator: At each turn $t$, a base LLM generates $N$ candidate actions (shell commands, file edits, etc.).
  • Selector: An off-the-shelf, high-capability LLM (acting as a "generative critic") receives the full conversation history and the $N$ candidates. It is prompted to select the action most likely to make genuine progress.
  • Execution: Only the selected action is executed in the environment. The result is appended to the history, and the loop repeats.
Figure 1: An illustration of the Turn-BoN method. At each turn the generator proposes N candidate actions; the selector picks the “best” action, which is executed in the environment, and the resulting observation (along with the action) is appended to the context for the next turn.

The authors used a listwise scoring approach, where the selector sees all candidates at once and picks the best index. This is computationally cheaper than pairwise tournaments but more effective than simple pointwise scoring.

Datasets

The approach was evaluated on Terminal-Bench v2.1, a benchmark consisting of 89 hard, realistic command-line tasks. They used the mini-SWE-agent harness to facilitate the agent's interaction with the terminal.

Models used:

  • Generators: Qwen3.6-35B and K2-Horizon-375B.
  • Selectors: Kimi-K3 and DeepSeek-v4.1-Flash.

Key Insights and Ideas

  • One-Step Policy Improvement: The authors theoretically ground Turn-BoN as a sampled version of the "Policy Improvement" operator from Reinforcement Learning. Even an "imperfect" selector can guarantee policy improvement if its selection error is smaller than the potential gain from sampling multiple actions.
  • Doing vs. Looking: A major finding is that Turn-BoN shifts agent behavior. Baseline agents often get stuck in "observation loops" (repeatedly reading files). The selector biases the agent toward "active" behaviors: editing files, running tests, and installing packages.
  • Efficiency through Quality: While Turn-BoN uses more tokens per turn, it results in 40-50% fewer turns per trajectory. By picking better actions, the agent avoids "doom loops" and unproductive exploration, often reaching the solution much faster.
  • Robustness to "Reward Hacking": The authors verified that the performance gains weren't due to the selector finding "cheats" (like reading the reference solution). The improvements stem from legitimate task progress.

Key Results

  • Success Rates: Turn-BoN improved Pass@1 accuracy by 5–10% across different model configurations.
  • Consistency: The "Consistency@4" metric (the percentage of tasks solved correctly in all 4 attempts) saw a significant boost, indicating that the agent becomes much more reliable.
  • Trajectory Length: As seen in Figure 3, the median number of turns dropped from ~45-48 to ~23-29 when using $N=8$.
Figure 2: Pass rates under Turn-BoN. Subfigures (a) and (c) show mean pass rate improvements.
Figure 3: Efficiency and consistency. Subfigures (a) and (c) show the dramatic reduction in turns per task.

Limitations and Future Work

  • Token Cost: Turn-BoN is expensive. It requires 3x to 8x more tokens than a standard run. While it saves on "sandbox" infrastructure, the LLM API costs are higher.
  • Selector Capability: The study primarily used selectors that were more capable than the generators. It remains to be seen how much a weaker or equal-strength selector helps.
  • Future Directions: The authors suggest exploring "Selective Turn-BoN"—only invoking the selector at turns where the generator is uncertain—to reduce costs while maintaining performance gains. They also suggest that training specialized, smaller critic models could make this approach more production-ready.

Summary updated

Abstract

In this work, we evaluate a simple inference-time scaling approach based on \textit{turn-level best-of-N sampling} (\method) for large language model (LLM) agents on complex, long-horizon tasks. We instantiate this using a \textit{generator-selector} framework with two LLMs; at each turn, a \emph{generator} model generates $N$ candidate actions and a \emph{selector} model selects one of them, which is then executed in the environment. This paper is closely related to the work of \cite{zainullina2025guided} who used critic models for guided search at inference time. Different from their work, we evaluate if off-the-shelf, open-weight LLMs can be effective at comparing different candidate actions directly. Experiments on long-horizon terminal tasks show that \method can lead to significant performance improvements, both in terms of accuracy (5--10\%) and consistency across repeated attempts. Analysis of agent trajectories reveal a shift in agent behaviour towards desirable patterns such as reduction in number of attempts to solve the task, improved task instruction following, debugging and testing.
BibTeX
@misc{bhandari2026turn,
  author = {Jalaj Bhandari and Dhawal Gupta and Hongli Zhan and Zhenting Wang and Varad Pimpalkhute and Zhengzhong Liu and Eric Xing and Rupesh Srivastava},
  title = {{On Turn-Level Best-of-N Sampling for Scaling LLM Agents}},
  year = {2026},
  eprint = {2611.06868},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06868},
}
Figure