A History of How We Learned to Evaluate AI Agents

A different history from the one about architecture

A companion piece in this publication traces the history of AI agent architecture — the sequence of mechanisms, from a 1971 symbolic planner to today’s vendor-shipped agent SDKs, that decide what an agent does next. This is a different history, about a narrower and less celebrated question: how did anyone decide whether what the agent did was any good?

The two histories run on separate clocks. An architecture can change overnight — a new prompting pattern, a new SDK release — while a benchmark takes months to build, longer to be trusted, and longer still to be retired once it stops measuring anything real. Evaluation methodology has its own sequence of dated, documented turning points, largely independent of which architecture happened to be under test at the time. This article follows that sequence: from benchmark suites built for game-playing policies, through a separate and much narrower tradition of single-turn language benchmarks, through an execution-based turn that changed what counts as a check, to the environments and tool-use benchmarks built for language agents specifically. Four methodological moves recur across all of it, and naming them is the point of writing the history down.

Borrowed from games: the reinforcement-learning benchmark suites

The earliest benchmark infrastructure recognizable as agent evaluation was not built for anything that used language at all. It was built to compare policies that played games.

Bellemare, Naddaf, Veness, and Bowling introduced the Arcade Learning Environment as an evaluation platform, giving researchers “an interface to hundreds of Atari 2600 game environments,” each one, the paper argues, posing “significant research challenges for reinforcement learning, model learning, model-based planning, imitation learning, transfer learning, and intrinsic motivation” ^[1]. The methodological contribution was not any single game; it was the platform itself, a common interface that let a single agent be scored across a wide, fixed roster of environments its designers had not individually hand-tuned it for. That distinction — general competence across many held tasks, rather than performance on one — is a habit of mind evaluation retained long after the games themselves stopped being the point.

Brockman and colleagues generalized the same idea beyond Atari with OpenAI Gym, described as “a growing collection of benchmark problems that expose a common interface, and a website where people can share their results and compare the performance of algorithms” ^[2]. The phrase worth noticing is “compare the performance of algorithms.” A shared interface plus a shared scoreboard is a specific methodological bet: that evaluation only means something once many independent groups can run the same test the same way and post directly comparable numbers. Every benchmark discussed below inherits that bet, whether or not its authors ever played an Atari game.

What these RL-era suites did not have to solve, because their agents did not produce language, was the problem of grading an answer’s content. A game score is unambiguous by construction — more points is better, a win is a win — so the entire measurement problem collapsed onto reward design and repeated trials across a fixed environment reset. Reading the next thread requires noticing what that convenience concealed: the moment an agent’s output became a sentence rather than a score, the question “did it succeed” stopped being free.

A parallel and much narrower thread: the single-turn benchmark

While game-playing agents were being scored on cumulative reward, a separate and much narrower evaluation tradition was forming around language itself, and for years it had nothing to do with agents at all: a model was handed one input and graded on one output, with no environment, no persistence, and no second turn.

Rajpurkar, Zhang, Lopyrev, and Liang’s SQuAD set the template, a dataset of “100,000+ questions posed by crowdworkers on a set of Wikipedia articles, where the answer to each question is a segment of text from the corresponding reading passage” ^[3]. The paper’s own baseline, a logistic regression model, reached 51.0 percent F1 against a human ceiling of 86.8 percent — a wide, legible gap the authors offered as “a good challenge problem for future research” ^[3]. That gap, not the dataset’s size, is the methodological artifact worth keeping: a benchmark’s usefulness is roughly proportional to how far current systems sit below a credible human reference, and SQuAD was built to make that distance visible and reproducible.

Wang and colleagues then generalized the single-turn approach across tasks rather than within one, arguing that for language understanding “to be maximally useful, both practically and as a scientific object of study, it must be general: it must be able to process language in a way that is not exclusively tailored to any one specific task or dataset” ^[4]. GLUE bundled nine separate tasks — grammatical acceptability, sentiment, paraphrase and similarity judgments, and several varieties of natural-language inference — behind one leaderboard number. That number is worth writing out, because the arithmetic embeds an assumption the field would later revisit:

an unweighted mean of nine task scores $s_t$. Averaging like this treats all nine component tasks as equally important and, implicitly, as equally hard and equally reliably measured — an assumption nothing in the construction actually guarantees. It is a real simplifying assumption, not a neutral summary statistic, and it is exactly the assumption GLUE’s own successor abandoned.

Within roughly a year, Wang and colleagues reported that “performance on the benchmark has recently surpassed the level of non-expert humans, suggesting limited headroom for further research,” and built SuperGLUE specifically to reopen that headroom with “a new set of more difficult language understanding tasks, a software toolkit, and a public leaderboard” ^[5]. The single-turn benchmark tradition, in other words, was already exhibiting a pattern by 2019 that agent benchmarks would later inherit on a shorter cycle: a benchmark is built, it is met, and it is replaced, not repaired.

Kiela and colleagues made the critique of that cycle explicit rather than leaving it implicit in successive leaderboards. Dynabench was built on the observation that models achieving high scores on static benchmarks nonetheless failed on straightforward adversarial examples, and it proposed instead a platform for “human-and-model-in-the-loop dataset creation” where “dataset creation, model development, and model assessment can directly inform each other, leading to more robust and informative benchmarks” ^[9]. Annotators were tasked with writing examples specifically designed to fool the current best model while remaining clear to a human reader — turning benchmark construction into an ongoing adversarial process rather than a one-time snapshot. Static single-turn benchmarks never fully gave way to Dynabench’s dynamic alternative, but the diagnosis it offered — that a fixed test decays the moment its answers become learnable rather than merely correct — reappears, largely unchanged, in the contamination debates that surround agent benchmarks built on public code repositories.

The execution-based turn

The methodological move that mattered most for what followed was not about agents or environments at all. It was a change in what counts as a passing grade.

Chen and colleagues introduced Codex, a GPT model fine-tuned on public GitHub code, alongside HumanEval, a benchmark of hand-written programming problems graded not by comparing generated text to a reference string but by actually running the generated function against unit tests ^[10]. That is a small-sounding change with a large consequence: a string-match grader can be fooled by a plausible-looking wrong answer, while an execution-based grader cannot, because it does not read the answer at all — it runs it. Codex solved 28.8 percent of HumanEval’s problems on a single attempt, against 0 percent for GPT-3 and 11.4 percent for GPT-J, and the paper reports solving 70.2 percent of problems when 100 samples were drawn per problem and any one of them was allowed to pass ^[10].

That last detail forced a genuine statistical problem into agent-adjacent evaluation for the first time: naively estimating the chance that at least one of $k$ sampled attempts succeeds, by drawing exactly $k$ samples and checking, is a high-variance estimator, especially at small $k$. Chen and colleagues instead drew a larger fixed pool of $n$ samples per problem, counted the number $c$ that passed, and computed an unbiased estimate of the pass rate at budget $k$ directly from that pool:

The term inside the brackets is the probability that a random draw of $k$ items from the $n$ samples contains no passing solution, so one minus that quantity is the probability at least one does. The point of writing the estimator this way, rather than simply sampling $k$ times per problem, is to separate two things later agent benchmarks would have to separate again and again: how good a system is, and how much it was allowed to try. Every agent benchmark discussed below that reports a success rate is implicitly answering the question this estimator first made explicit — success at what sampling budget, counted how.

Environments come back, this time built for language

Execution-based grading solved the problem of checking one function against one specification. It did not, by itself, solve the problem of an agent that has to act more than once, against a world that remembers what it did last turn. That problem required environments again — the thing RL-era suites had, and single-turn NLP benchmarks by construction did not.

Côté and colleagues’ TextWorld supplied one route back to a persistent environment for language: “a sandbox learning environment for the training and evaluation of RL agents on text-based games,” a Python library “that handles interactive play-through of text games, as well as backend functions like state tracking and reward assignment” ^[6]. Where Bellemare and colleagues had wrapped an existing library of Atari cartridges, Côté and colleagues generated the games themselves, procedurally, specifically so that an agent’s performance could be tested for generalization across environments it had never seen rather than memorization of a fixed set.

Shridhar and colleagues then connected that text-based tradition directly to embodied tasks with ALFWorld, motivated by the observation that “existing work does not yet provide the infrastructure necessary for both reasoning abstractly and executing concretely” ^[7]. ALFWorld let an agent “learn abstract, text-based policies in TextWorld… and then execute goals from the ALFRED benchmark in a rich visual environment,” and its authors reported that training this way “fosters better agent generalization than training only in the visually grounded environment” ^[7]. Evaluation, in other words, was no longer just asking whether a final answer matched a reference; it was asking whether a policy learned in one representation of a task transferred to another, harder representation of the same task — a question a single-turn benchmark has no vocabulary to even pose.

Yao, Chen, Yang, and Narasimhan pushed the same environment-building instinct toward something closer to a real deployment surface with WebShop, “an e-commerce website environment with 1.18 million real-world products and 12,087 crowd-sourced text instructions” in which an agent has to navigate actual web pages to find and purchase an item matching a description ^[8]. Their best agent reached a 29 percent success rate, against 9.6 percent for a rule-based baseline and 59 percent for a human expert, and — the detail that mattered methodologically — agents trained in the simulated site showed what the paper calls “non-trivial sim-to-real transfer” when tested against real commercial websites ^[8]. That transfer result is the clearest evidence in this history that a built environment, rather than a fixed dataset, had become the object worth constructing: the benchmark’s value lay not in the specific products catalogued but in the interaction surface it reproduced.

Tools, repositories, and users: the current generation

By 2023, language models were being wrapped in loops that called tools, browsed pages, and edited files, and the benchmarks built for single-turn text or for bespoke simulated worlds could not evaluate any of it directly. A new generation of benchmarks answered that gap, and each one made a distinct methodological choice about what, specifically, to check.

Liu and colleagues named the gap explicitly rather than assuming it: “there is an urgent need to quantitatively evaluate LLMs as agents on challenging tasks in interactive environments” ^[11]. AgentBench answered with eight distinct environments spanning operating systems, databases, web shopping, and games under one evaluation harness, and its central finding was as much a diagnosis as a leaderboard: “poor long-term reasoning, decision-making, and instruction following abilities are the main obstacles for developing usable LLM agents” ^[11] — a result about where agents fail, not only how often.

Jimenez and colleagues took execution-based grading, the move Codex had introduced for isolated functions, and applied it at the scale of an entire software repository. SWE-bench evaluates a candidate patch by running the modified repository’s own test suite, over “2,294 software engineering problems drawn from real GitHub issues and corresponding pull requests across 12 popular Python repositories,” motivated by the observation that “language models have outpaced our ability to evaluate them effectively” ^[12]. The paper’s own baseline result is a useful corrective to any assumption that this generation of benchmarks was easy: the best-performing model tested, Claude 2, resolved just 1.96 percent of the issues ^[12]. Where Codex checked one function against unit tests written for that function, SWE-bench checks a multi-file change against a test suite the agent did not write and was never shown in full — execution-based grading, but against a target the agent had to discover the shape of rather than merely satisfy.

Mialon and colleagues took evaluation in the opposite direction on one axis while extending it on another. GAIA returns to single, unambiguous final answers — the SQuAD-era grading discipline — while demanding that reaching them requires “reasoning, multi-modality handling, web browsing, and generally tool-use proficiency” ^[13]. Their headline comparison is stark: “human respondents obtain 92% vs. 15% for GPT-4 equipped with plugins” across 466 questions, a gap the authors read as evidence against extrapolating from language models’ success on narrow professional exams to genuine general assistance ^[13]. GAIA is not a regression to single-turn evaluation; it keeps single-turn grading’s unambiguous checkability while requiring the multi-step process that single-turn benchmarks never had to test.

Yao, Shinn, Razavi, and Narasimhan closed a gap none of the preceding benchmarks addressed: interaction with a user, and consistency across more than one attempt. Tau-bench was built because, as the paper states plainly, “existing benchmarks do not test language agents on their interaction with human users or ability to follow domain-specific rules, both of which are vital for deploying them in real world applications” ^[14]. Its agents converse with a simulated user while consulting API tools and written policy documents, and the reported results carry a second finding beyond raw accuracy: state-of-the-art models “succeed on fewer than 50% of tasks” and show “significant inconsistency across multiple trials” on the same task ^[14]. That second finding is a direct descendant of the pass@k estimator Codex introduced, run in the opposite direction — not asking whether a system can succeed at least once given several tries, but whether it succeeds reliably given exactly one try, repeated.

What actually changed, four times

Read end to end, this is not a story of steadily improving scores. It is a story of the check itself being redesigned, on four separate occasions, each time because the previous check had stopped answering a question anyone still needed answered.

From a fixed dataset to a persistent environment. RL-era suites had this from the start, because a game state persists whether or not anyone measures it. Single-turn NLP benchmarks did not, and could not, until TextWorld, ALFWorld, and WebShop rebuilt the idea of a persistent, resettable world specifically for language-driven agents.

From string comparison to execution. SQuAD, GLUE, and SuperGLUE all graded by comparing generated text to a reference. Codex and HumanEval broke that pattern by running the output instead of reading it, and SWE-bench extended the same discipline to a target — a whole repository’s test suite — the agent never gets to see in full.

From a static snapshot to an acknowledged decay problem. GLUE gave way to SuperGLUE within about a year of publication for exactly the reason Dynabench later made explicit: a benchmark a model can be trained toward stops measuring the capability it was built to measure. SWE-bench, GAIA, and tau-bench all inherit this problem in a sharper form, because their raw material — public repositories, public web pages, public tool documentation — is also training data for the systems being tested on it.

From at-least-once to every-time. Chen and colleagues’ pass@k formalized “did it succeed given several tries” as a statistically honest quantity for exploration. Tau-bench asks the harder operational question — does it succeed the same way twice — and reports that, on its own tasks, the state of the art mostly does not.

Predictions, and what would falsify them

These are forecasts, kept separate from the sourced history above. Horizon: August 2029. Common assumption: no regulatory mandate standardizes agent evaluation reporting before then.

One. Benchmarks built on public code repositories and public websites will increasingly disclose an explicit contamination-audit methodology, in the spirit of Dynabench’s original critique of static datasets, rather than relying solely on a cutoff date. Disconfirmed if the widely cited coding-agent and tool-use benchmarks of 2029 still report headline numbers with no stated procedure for detecting or bounding training-data overlap.

Two. Reliability-at-repeat-count metrics, in the lineage tau-bench opened by inverting pass@k, will become a standard companion figure alongside single-attempt accuracy on agent leaderboards, rather than a niche addition. Disconfirmed if the most-cited agent leaderboards of 2029 still publish a single success rate with no repeated-trial or consistency figure alongside it.

Three. Some benchmark in the direct lineage of GAIA — unambiguous final answers reached through genuinely open-ended tool use — will be judged to have saturated the way SQuAD, GLUE, and SuperGLUE each were, and a harder public successor will be built and adopted within roughly two years of that judgment. Disconfirmed if GAIA or its closest successors remain the field’s primary general-assistant benchmark past 2029 without a documented saturation event and replacement.

None of these predictions requires a capability discontinuity. Each follows from a pattern already visible at least twice in the sourced record above: a check stops answering the question it was built for, and the field replaces the check rather than the question.

What to take away

The history of agent evaluation is not the history of agents. It runs on its own clock, and it has already turned over its central instrument four times: what counts as an environment, what counts as a passing grade, whether a fixed test is trusted to keep meaning what it meant on the day it shipped, and whether success has to hold up once, or every time. Each turn is dated to a specific paper with a stated reason, from an Atari interface built so algorithms could be compared on equal footing, through a leaderboard number that assumed nine unlike tasks could be averaged into one, through a formula built to make repeated sampling statistically honest, to a benchmark that finally asked whether an agent talking to a simulated user would get the same result twice.

The pattern across all four turns is the same one visible in the newest, least settled corner of the field today: a check is trusted until it is gamed or outgrown, and then it is rebuilt, not patched. Reading the history this way is also a way of reading the present — the next time an agent benchmark reports a headline number, the useful question is not only what the number is, but which of these four turns it has, and has not, already taken.