Technical Summary: When Independent Sampling Outperforms Agentic Reasoning

Problem Statement

The paper addresses the critical challenge of allocating fixed inference-time compute budgets for Large Language Models (LLMs) solving competitive programming tasks. While prior research has demonstrated the efficacy of both repeated independent sampling (e.g., k-shot, self-consistency) and agentic reasoning (iterative reasoning with tool use, debugging, and environment interaction), there is a lack of systematic understanding regarding their accuracy–cost tradeoffs.

Existing evaluations often assume unbounded resources or report performance at a single operating point without accounting for the monetary cost or the number of model calls. In real-world deployments, where budgets are strictly limited by cost, latency, or query counts, it remains unclear whether investing resources into a single, deep agent trajectory with rich feedback is superior to distributing those same resources across multiple independent, shallow attempts.

Methodology

The authors conduct a rigorous empirical and theoretical evaluation across 216 Codeforces problems spanning Divisions 1–3, ensuring the problems post-date the models' training to prevent data contamination.

Evaluation Strategies

Three distinct inference regimes are compared under matched constraints (monetary budget $c_{max}$ and query count $k_{max}$):

1. k-shot (Independent Sampling): The model generates $k$ independent solutions via single API calls. The best solution is selected based on acceptance by the Codeforces judge.
2. Agent (Single Trajectory): A single SWE-agent trajectory is executed with a full budget ($c_{max}$). The agent has access to a terminal for iterative coding, execution, and debugging, utilizing prompt caching to amortize context costs.
3. Agent-1/3 × 3 (Budget-Partitioned): The total budget is split across three independent SWE-agent runs (each with $c_{max}/3$). This isolates the benefit of multiple independent initializations from the benefits of within-trajectory refinement.

Theoretical Framework

To generalize the findings, the authors model the problem as an integer program aimed at maximizing the final probability of success under a fixed budget $C$. They derive a cost-optimal rule:

• The optimal strategy minimizes the negative log failure likelihood per dollar: $\frac{-\ln(1-p)}{c}$, where $p$ is the success probability and $c$ is the cost.
• They prove that if a single API call (k-shot) has a higher value for this metric than an agent run, the budget should be allocated to repeated independent calls rather than a single long agent trajectory.

Analysis Techniques

• Trajectory Analysis: Unsuccessful agent runs are analyzed using an LLM-as-a-judge (GPT-4.1) to categorize failure modes.
• Scaling Laws: The authors estimate success probability and cost scaling trends for both k-shot and agent runs, fitting power laws to agent costs and analyzing convergence rates.

Key Results

1. Superiority of Independent Sampling

Across all model families and difficulty levels (Divisions 1–3), k-shot inference consistently outperforms agent-based methods when performance is normalized by either monetary cost or the number of model calls.

• Cost Efficiency: For any fixed budget threshold, k-shot solves strictly more problems than a single SWE-agent run or the budget-partitioned agent variant.
• Query Efficiency: Even when controlling for the number of queries (ignoring cost), agents lag behind k-shot, indicating that the inefficiency is not merely due to higher per-call overhead or context length but stems from lower effectiveness per invocation.
• Robustness: The performance gap persists even with prompt caching enabled in the agent framework, ruling out context-length accounting as the primary cause of the disparity.

2. Agent Failure Modes

Trajectory analysis reveals that agents frequently fail due to specific structural weaknesses in competitive programming contexts:

• Algorithmic Inefficiency (19.3%): Failure to design efficient algorithms, resulting in brute-force or high-complexity solutions.
• Iterative Loops (7.4%): Repeated cycling through similar incorrect strategies with minor tweaks without reconsidering the core approach.
• Ineffective Debugging (7.0%): Excessive focus on peripheral issues rather than strategic reassessment.
• Missing Theoretical Insight (6.7%): Failure to identify necessary mathematical or combinatorial properties.

3. Scaling Trends

Empirical scaling analysis (Figure 4) demonstrates that:

• k-shot success probability converges to 1 exponentially with cost, maintaining a constant negative log failure likelihood per dollar.
• Agent success probability converges more slowly. The cost of agent runs grows super-linearly (near-quadratic) with the number of queries due to context growth, causing the "negative log failure likelihood per dollar" to decrease significantly as the budget increases.
• The optimal agent strategy, if one exists, involves a finite, short search length ($q^*$), beyond which independent repetitions of shorter searches are more cost-effective.

Key Contributions

1. Systematic Comparison: A fine-grained empirical comparison of k-shot, single-agent, and budget-partitioned agents across multiple models and difficulty levels, revealing that k-shot dominates in accuracy-cost tradeoffs.
2. Failure Mode Analysis: Identification of recurring agent weaknesses (inefficient iteration, ineffective debugging) that explain their poor cost efficiency in self-contained algorithmic tasks.
3. Principled Metric: Introduction of the negative log failure likelihood per dollar ($\frac{-\ln(1-p)}{c}$) as a theoretically grounded metric for optimizing resource allocation in success-or-fail solvers, moving beyond intuitive or single-point accuracy metrics.
4. Scaling Trends: Rigorous estimation of scaling laws showing that agent costs grow super-linearly while independent sampling offers linear efficiency, providing a mathematical basis for preferring k-shot under tight constraints.

Significance and Claims

The paper argues that for self-contained algorithmic tasks like competitive programming, independent exploration (k-shot) is more cost-effective than deeper agentic reasoning under realistic resource constraints.

• Contextual Nuance: The authors explicitly state that this does not diminish the value of agents in domains requiring complex navigation, file manipulation, and iterative testing (e.g., software engineering benchmarks like SWE-bench). Instead, the findings highlight that inference strategies must be matched to task structure.
• Resource Allocation: The work provides a mathematically principled method for allocating inference budgets, suggesting that when a single API call is more cost-efficient than an agent run, resources should be distributed across independent attempts rather than invested in prolonged deliberation.
• Evaluation Standard: The paper advocates for cost-aware evaluation of inference strategies, urging the community to move beyond single-point accuracy metrics to continuous accuracy-cost trajectories.

The authors conclude that while agentic interaction can theoretically improve performance, the overhead of iterative refinement often outweighs the benefits in competitive programming, where the "correct" solution path can often be discovered early through broad, independent exploration.