acceptodds
Under review as a conference paper at ICLR 2027

Instances of equal computed difficulty differ in LLM agent success by more than chance

Abstract

Agent benchmarks usually set difficulty by how many models failed a task, building the axis from the systems measured: a fall in success along it is not itself evidence about a model. Does difficulty computed from the task's own structure predict how often an LLM agent wins? An instance is one setup in a small autobattler: the agent buys and places three units, one at a time, against a script. Its 3,240 complete plays can all be listed, and its difficulty d is the fraction that win: larger d means an easier instance. Every unit costs the same and the agent spends its whole budget, so choosing at random at each step draws uniformly from those plays: random play wins with probability exactly d. Two LLM agents, luna and glm, played 126 instances from the range's two ends, as did a third model reported separately, a random player and 21 scripted strategies. An analysis plan fixed four Holm-adjusted tests in advance; all four reject their null hypotheses. Success rises with computed d (p = 0.0004), and luna and glm each beat random play's 0.100 at d = 0.1, one test each. No instance sits at d = 0.1, fixed in advance between the ends, so both come off a fitted curve. The fourth rejects too: instances of equal computed difficulty differ widely in success, beyond what difficulty explains; structure is not all that makes an instance hard for a model. Instance for instance, luna and glm respond to difficulty about as steeply as random play (90% interval 0.92 to 1.30, within the pre-registered range 0.6 to 1.4). That steepness is a slope, 1 for random play by construction. The plan's model assumed one shared slope; the agents' separate fits differ. The slope does not tell you how well a strategy plays: four scripted strategies spanning the design's range of information and search have slopes within about 0.05 of one another and of random play's fitted 1.03. Computed difficulty does predict success, but is no substitute for measuring models: a difficulty-graded suite should report the spread at equal difficulty beside the slope. These results rest on two agents, one game and one prompt.

Primary area:
foundation or frontier models, including LLMs
Keywords:
preregistration, instance difficulty, LLM agents, exhaustive enumeration, sequential decision making, random baseline, generalized linear mixed model, evaluation design

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_qSXCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies whether a model-independent structural difficulty measure predicts LLM-agent success in a small deterministic autobattler. Each instance has 3,240 ordered complete plays; their winning fraction d is also exactly the win probability of uniform random play. Two headline agents and a separately reported third model play 126 instances with ten attempts each, sampled from two separated difficulty ranges. A preregistered common-slope GLMM and four Holm-adjusted tests assess association with difficulty, levels at d=0.1, and overdispersion beyond a simpler difficulty-only model. Twenty-one scripted strategies illustrate that slope is not a capability score. A smaller prompt-intervention experiment reports regret changes when rules and exact move values are supplied.

Critical strengths
  1. The structural measure has an exact and interpretable random baseline. Equal prices, fixed play length, and exhaustive enumeration make P(random win)=d a genuine property of the environment rather than a difficulty label inferred from the models under test. This is a useful controlled setup for studying what difficulty grading can and cannot tell us.

  2. The scripted-policy comparisons make an important distinction between the level of success and its slope with difficulty. The paper also reports substantial limitations rather than hiding them: agent-specific fits, fallbacks, interpolation at an unobserved d, imperfect interval calibration, and the separate intervention arm's unresolved gate verdict. This transparency makes the study easier to assess and its narrower descriptive findings potentially useful.

Critical weaknesses
  1. The central heterogeneity interpretation is not separated from misspecification of the null model. Appendix B.5 defines Q4 as overdispersion against a binomial GLM with model intercepts and one common logit(d) slope. Yet Table 2 reports different agent-specific slopes (1.4429 versus 1.0079), and Appendix B.8 reports different instance-effect SDs (2.3307 versus 1.0889). Rejecting this restricted GLM can reflect agent-specific slopes or an incorrectly specified response curve, as well as residual instance difficulty. It does not by itself isolate differences between instances at equal d. The same issue weakens the pooled claim that the two agents respond about as steeply as random play. A heterogeneity analysis allowing model-specific response functions, or a direct comparison of genuinely matched-d instances, is needed for the title-level conclusion.

  2. Important inferential claims remain dependent on unverified structure. Both level tests use d=0.1, but all sampled instances lie in 0.0164–0.0265 or 0.1735–0.3762, so the estimates depend on an untested interpolation. The model-free suite-average advantage in Appendix B.8 supports an advantage on observed instances, not a rate at 0.1. Separately, Section 7's regret attribution cannot distinguish search from valuation and retains a harness/provider-mismatch verdict without a rerun. The code, logs, and preregistration text are unavailable during review, which prevents checking these consequential analysis choices. I would prefer a narrower paper centered on the exact baseline and robust observed-instance results unless these issues are resolved.

Questions for authors
  1. Does the Q4 heterogeneity result persist when the null permits model-specific slopes and flexible difficulty-response curves? How many distinct exact d values occur, how many have multiple non-mirrored instances, and can those matched groups support a direct within-d test?

  2. Please make the agent-specific fits central to the interpretation. Under a model allowing separate slopes and instance-effect distributions, which claims about random-like steepness and excess instance variation remain supported? The common fit's preregistration does not establish the validity of its assumptions.

  3. Can you replace or supplement the d=0.1 claims with inference on the observed ranges, and provide an anonymous snapshot of the instance suite, outcomes, analysis, and frozen plan? For the intervention arm, would you either resolve the gate defect with a validated rerun or restrict the conclusion to the direct observation that agents select well when exact values are printed? These changes could materially improve my assessment.

Reviewer_JfsqOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether task difficulty computed independently of an agent predicts that agent's success. In a small auto-battler, all 3,240 complete plays can be enumerated, and the fraction of winning plays defines difficulty. Experiments on 126 instances compare two primary LLM agents, an additional model, and scripted policies. A separate intervention study supplies rules and exact action values to examine sources of regret. The main findings concern the relationship between difficulty and success, residual variation across instances, and the distinction between a difficulty-curve slope and policy capability.

Critical strengths
  1. A difficulty measure with a clear operational meaning. Exhaustive enumeration makes the random-policy success probability exact and independent of the tested models. This provides a useful setting for examining what a structural difficulty measure captures, without defining difficulty from the evaluated agents' failures.

  2. The slope counterexamples are informative. The scripted policies show that similar slopes can coexist with substantially different win rates. This is a concrete contribution to interpreting benchmark difficulty curves and remains useful even if the stronger statistical claims need qualification.

Critical weaknesses
  1. The interpretation of Q4 needs a sensitivity check. Appendix B.5 tests a binomial GLM with model-specific intercepts, a shared slope on logit(d), and no instance effect. Rejecting that null establishes lack of fit of this specified model. The broader interpretation—variation between instances beyond what difficulty explains—also depends on the mean curve being adequate. This matters because the separately fitted slopes are 1.4429 and 1.0079. A model with different slopes, or a reasonable nonlinear relationship, could account for part of the lack of fit. The reported instance-effect estimates are suggestive, but their interpretation also depends on the mean specification. The registered parametric test is a legitimate analysis; the unresolved question is how robustly its rejection supports the title's broader wording. Per-instance counts and a sensitivity analysis would make this much easier to assess.

  2. The exact-value intervention changes information and search as well as valuation. L2 supplies optimal continuation values evaluated against the final opponent board, which the acting model does not fully observe. It therefore changes both the information available and the work needed to choose an action. The resulting improvement supports the usefulness of supplied values, but attributing approximately three quarters of regret to computing action values requires additional assumptions about the decision process. Appendix D.5 does not establish that this process remains unchanged across conditions. The main conclusion should explain which attribution survives without that assumption, or describe the result as the total effect of supplying exact values.

Questions for authors
  1. Does the Q4 conclusion persist with model-specific slopes and reasonable nonlinear mean curves? Please clarify the intended scope of the claim and provide the per-instance success counts needed to assess it.
  2. Which components of the proposed regret decomposition remain identifiable when L2 supplies additional opponent information and removes search? Would narrowing the conclusion to the total intervention effect preserve the paper's main takeaway?
Reviewer_RK5MOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces a custom autobattler environment and an associated difficulty metric. Each instance of the environment has a fixed opponent script, and the difficulty score is defined as the fraction of all possible plays that lead to the agent winning. Hence, difficulty is equivalent to the win rate for a uniform random player. The main goal of the paper is to study the relationship between this custom difficulty metric and LLM agent performance, using GPT 5.6 Luna, GLM 5.3 Flash and Gemma 4 31B IT.

The paper assumes that the difficulty metric and the win rate follow a generalised linear mixed model. To fit it, they run the 3 LLM agents and a random play agent against 126 different opponent scripts (instances). From these simulations, they establish that success rises with computed difficulty, and that instances with the same difficulty level show substantial differences in win rates. Both GLM 5.3 Flash and GPT 5.6 Luna beat random performance at d=0.1, and their pooled slope is about as steep as that of random play. This slope, however, when computed for a set of fixed strategies, cannot reliably distinguish between strategies with different levels of available information and search.

The authors attempt to attribute agentic failures to specific causes by running simulations where the LLM agent receives increasing amounts of information: first only the task description, then adding the battle rules, and lastly including the exact final outcomes against the true opponent for each legal move. The authors conclude that failures can be mainly attributed to an inability to evaluate moves.

Critical strengths
  • The evaluation procedure seems rigorous and transparent, with the authors committing to a pipeline before seeing the data, reporting uncertainty adequately, and building controls when required (e.g. building the random play arm to test the harness, and re-fitting the model excluding games where the fallback moves were triggered).
  • The design of the difficulty metric, albeit environment-specific, is well-motivated and intuitive.
Critical weaknesses
  • I found the paper difficult to follow. There is an absence of a clear storyline connecting the motivation, results, and significance, as well as a lack of cohesion across sections and even paragraphs. For instance, the first paragraph of the introduction describes the benefits of defining difficulty metrics that are independent of model performance, and the second paragraph starts by describing an instance of an autobattler, without informing the reader of what an autobattler is, and how it is relevant to the work. Additionally, the manuscript relies on a lot of paper-specific terminology (e.g. rungs, headline, queue, fallback screen), and includes multiple procedural statements (e.g. “Puzzles of equal computed difficulty differ in model success beyond what difficulty explains (φ = 3.2342; s = 1.4059, 90% CI [1.1990, 1.6484]; Wald on log s; coverage not simulated).”), which hurt readability.
  • The authors consider one custom toy environment, 2 different LLMs (and a third one reported separately), and one prompt configuration. There is no evidence or argument that the findings extend beyond this limited setting.
Questions for authors
  • Given the presented findings, what do the authors conclude about the usefulness of the proposed difficulty metric?
  • In Section 7, the regret is calculated against an agent following the optimal strategy assuming access to the opponent’s full board. This confounds capability with privileged information about the opponent’s remaining placements. Could the authors report regret for each of the experiments in comparison to the best possible policy given the available information (e.g. given a state, consider all opponent boards consistent with the units visible so far, and take as the best move the one that yields the highest outcome on average)?
  • Could the authors motivate why the levels are evaluated at d0=0.1d_0=0.1, the instances are sampled from ranges d 0.0164-0.0265 and 0.1735-0.3762, and a common slope fitted to the pooled data from GLM and Luna?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.