🤖 machine learning

Predicting Task Difficulty Without Rollouts

This paper proposes a method for predicting task difficulty directly from task descriptions without executing costly rollouts across 17 diverse agentic benchmarks, demonstrating that token-level entropy serves as a reliable predictive signal while exposing limitations in traditional metrics like AUC and revealing hidden environment flaws.

Original authors: Stefan Krsteski, Charlotte Meyer

Published 2026-08-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stefan Krsteski, Charlotte Meyer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Crystal Ball Problem for Robot Brains

Imagine you are building a video game. Before you let players loose on a new, tricky level, you want to know: is this level too easy, too hard, or just right? In the world of artificial intelligence, specifically with "AI agents" (smart computer programs that can take actions like writing code or navigating websites), this question is a massive headache. Usually, to find out how hard a task is, you have to let the AI try it hundreds of times. This is like testing a new rollercoaster by riding it a thousand times just to see if it's too scary. It takes forever, costs a fortune in computer power, and slows down progress.

This paper lives in the corner of computer science where researchers try to predict how difficult a task will be before the AI even tries it. They are looking for a way to read the "recipe" of a task and guess the difficulty, rather than waiting for the AI to burn its fingers on the stove. The key idea they play with is entropy, which sounds fancy but is basically a measure of "surprise" or "confusion." If a computer reading a task description gets very confused and doesn't know what word to say next, that task might be hard. If it flows smoothly, the task might be easy. The researchers wanted to know: Can we use this "confusion meter" to predict difficulty without running the expensive tests?

The "No-Run" Crystal Ball

The authors, Stefan Krsteski and Charlotte Meyer from Andromede AI, decided to test if they could build a crystal ball for task difficulty. Instead of waiting for an AI to struggle through 17 different types of challenges—ranging from solving math problems to navigating the web—they tried to guess the difficulty just by looking at the text description of the task.

They gathered a massive dataset of over 5,000 tasks and watched how 497 different AI agents performed on them. First, they calculated the "real" difficulty by seeing how often the agents succeeded or failed. Then, they tried to predict that difficulty using only the task's text.

The Big Surprise: The "Confusion" Meter Works (Sort Of)
The team found that the best way to guess difficulty wasn't just counting how long the task description was or using a standard AI summary. Instead, the winner was token-level entropy. Imagine an AI reading a task sentence by sentence. At every single word, the AI has to guess what comes next. If the AI is very sure, it's easy. If the AI is torn between many possibilities and feels "uncertain," that's high entropy.

The researchers found that if they tracked this uncertainty as the AI read the task, they could predict difficulty with surprising accuracy. When they tested this on tasks similar to what they had seen before, their predictions matched the real difficulty about 40% of the time (a correlation of 0.399). That's not perfect, but it's a huge leap from random guessing. However, when they tried to predict the difficulty of brand new types of tasks they had never seen, the accuracy dropped to about 22%. It's like a student who aced the practice test but stumbled a bit on the real exam; the method works, but it hasn't mastered the art of generalizing to the unknown yet.

The "AUC" Trap
One of the paper's most important warnings is about a popular way of measuring success called "AUC." The authors show that AUC can be a liar. They explain that AUC can look very high even if your difficulty predictions are terrible, as long as you can tell the difference between a smart AI and a dumb AI. It's like grading a test where you get a high score just for knowing who is smart, without actually knowing which questions are hard. The paper argues we need to stop using AUC for this specific job and use ranking methods instead, which actually tell us if we can order tasks from easy to hard correctly.

Finding Hidden Flaws
The most playful and useful part of their discovery is what happens when the prediction doesn't match reality. The authors call this the "residual."

If the AI predicts a task is easy, but the agents fail miserably, the task might be broken or impossible (like a math problem with a typo that makes it unsolvable).
If the AI predicts a task is hard, but the agents breeze through it, the task might be contaminated (meaning the AI has seen the answer before, such as prior exposure to the solution).

By looking at the gap between what they expected and what actually happened, they found they could spot these hidden issues. For example, they looked at a specific coding task that was supposed to be hard but was actually easy because the answer was leaked; their method flagged it immediately.

The Bottom Line
This paper suggests that we can indeed peek into the future of AI difficulty without running expensive simulations, using the "confusion" level of the AI as our guide. It's not a magic wand that solves everything perfectly, especially for totally new types of problems, but it's a powerful tool. It allows designers to spot broken tasks or opportunities for prior exposure before they waste millions of dollars on testing. As AI gets smarter and tasks get longer and more complex, having a way to guess the difficulty upfront might be the only way to keep the whole system from getting stuck in a loop of endless, expensive trial-and-error.

Technical Summary: Predicting Task Difficulty Without Rollouts

Problem Statement

As Large Language Model (LLM) agents advance, the frontier of evaluation shifts toward complex, long-horizon domains where empirical validation via "rollouts" (simulated agent interactions) becomes a severe computational and logistical bottleneck. Designing and calibrating benchmarks for these environments requires extensive trial-and-error, which is increasingly prohibitive. While prior work has explored using model uncertainty to detect data contamination in static benchmarks, there is a lack of research on ex ante difficulty prediction—estimating whether a task is likely to be hard based solely on its description before executing costly simulations. Existing approaches are often limited to static coding tasks, rely on narrow features, and use evaluation metrics (like AUC) that may not accurately reflect task-level difficulty estimation.

Methodology

Dataset Construction

The authors constructed a multi-benchmark corpus comprising 415,470 agent-task outcomes across 17 agentic benchmarks spanning coding, mathematics, machine learning, web navigation, function calling, and cybersecurity. The dataset includes 5,230 unique tasks evaluated by 497 agent configurations (combinations of 216 models and 90 scaffolds).

Difficulty Target Estimation (IRT)

To establish a ground-truth difficulty metric, the authors employ Item Response Theory (IRT), specifically the one-parameter logistic (1PL) Rasch model.

Model: The probability of an agent $a$ succeeding on task $t$ is modeled as $P(Y_{a,t}=1) = \sigma(\theta_a - \beta_t)$ , where $\theta_a$ represents agent capability and $\beta_t$ represents task difficulty.
Training: The model is trained via stochastic variational inference (SVI) on observed binary outcomes (success/failure).
Target: The resulting scalar $\beta_t$ serves as the difficulty target. To handle variance across different benchmarks, these values are standardized within each benchmark to produce $z(\beta_t)$ .

Feature Engineering

The prediction pipeline attempts to estimate $\beta_t$ using only pre-rollout information. The authors define five feature families derived from the task context ( $C_t$ ) and a reasoning trace ( $R_t$ ) generated by an LLM:

Random Control: Gaussian noise.
Baseline: Log-transformed context length.
Embeddings: PCA-reduced embeddings of the reasoning trace (using bge-base-en-v1.5).
Entropy: Token-level Shannon entropy computed over the reasoning trace using open-weight scorer models (e.g., Qwen3-8B-Base). This captures the model's uncertainty at each token position.
Full Set: A concatenation of entropy summaries (mean, spread, shape, gaps), cross-scorer disagreement, benchmark metadata, structural properties, and embeddings.

Evaluation Metrics

The authors critique the use of Area Under the Curve (AUC) for this task, demonstrating that AUC can remain high even if the predictor assigns a constant difficulty to all tasks (as it conflates agent ability with task difficulty). Instead, they prioritize:

Spearman's $\rho$ : Rank correlation between predicted and IRT-estimated difficulties.
Pairwise Accuracy (pAcc): The fraction of task pairs within a benchmark where the predicted ordering matches the true ordering.
Evaluation Splits: K-fold (in-distribution) and Leave-One-Benchmark-Out (LOBO, out-of-distribution).

Key Results

1. Predictability of Difficulty

Task features contain a meaningful signal for difficulty prediction, but performance varies by distribution:

In-Distribution (K-fold): The Full feature set achieves a Spearman $\rho$ of 0.399 ( $p < 0.001$ vs. baseline). The Entropy features alone are the strongest single family ( $\rho = 0.193$ ), outperforming embeddings and length baselines.
Out-of-Distribution (LOBO): Performance drops but remains significant, with the Full set reaching $\rho = 0.225$ . This indicates that while features encode difficulty, generalization to unseen benchmark families is limited.

2. The Limitations of AUC

The paper demonstrates that AUC is misleading for difficulty prediction. A "constant difficulty" predictor (assigning the same value to all tasks) yields an AUC of 0.715, and a "benchmark average" predictor yields 0.806, despite having zero ability to rank tasks within a benchmark (pAcc = 0.000). This confirms that AUC primarily measures the separation of agent abilities rather than the accuracy of task difficulty estimation.

3. Entropy Trajectories

Ablation studies reveal that the shape of the entropy trajectory (local discrepancies, slope, and variance) is more informative than global mean statistics. Aggregating entropy across multiple scorer models improves in-distribution performance but does not consistently improve out-of-distribution transfer, suggesting potential overfitting to benchmark-specific phrasing.

4. Residual Diagnostics

The authors propose using the residual $r_t = z(\beta_t) - \hat{z}_t$ (observed minus predicted difficulty) to diagnose hidden task factors:

Positive Residuals ( $r_t > 0$ ): Tasks are harder than predicted. This signals potential feasibility issues or evaluator failures (e.g., the django-14725 task had a residual of +1.41 and a 9% success rate).
Negative Residuals ( $r_t < 0$ ): Tasks are easier than predicted. This signals familiarity or data contamination (e.g., the django-11451 task had a residual of -0.56 and a 71.8% success rate).

Significance and Claims

The paper argues that ex ante difficulty prediction is a viable, though imperfect, tool for proactive environment design. Its primary contributions are:

Methodological Shift: Moving from post-hoc empirical validation to pre-rollout estimation, potentially saving significant compute resources in long-horizon domains.
Diagnostic Utility: Demonstrating that the gap between predicted and observed difficulty can serve as a filter to identify benchmark flaws, such as contamination or infeasible tasks, before committing to full evaluation.
Feature Insight: Establishing token-level entropy as a superior predictive signal compared to static embeddings or simple length metrics.
Evaluation Rigor: Highlighting the inadequacy of AUC for difficulty estimation and advocating for rank-based metrics (Spearman $\rho$ , pAcc) to avoid conflating agent capability with task difficulty.

The authors remain modest regarding the current state of the field, noting that while in-distribution ranking is reliable, cross-benchmark generalization remains an open problem. They suggest future work should focus on modeling entropy as a time series and developing mechanistic predictors for task familiarity and feasibility.