BeelineBench

How efficiently do decision models navigate multi-step problems?

Results · Method · Domains · Quick start · Documentation · Citation

BeelineBench measures how well a decision model plans ahead when it solves a multi-step problem. A model that explores fewer unnecessary intermediate states "beelines" directly to the solution, and gets a higher score. Navigating directly to the solution through fewer steps could be interpreted as evidence that the model did some form of internal planning ahead.

• 7 domains: sliding puzzles, planning, arithmetic, word games, and link navigation on Wikipedia.
• Baselines: the classic heuristic of each domain, random choice, and an oracle that knows the true distance to the goal.
• Seeded and portable: each trial, option order, and dropped state comes from seeded draws, so a trial is the same on each machine.
• Intervals on all scores: each score is a geometric mean over 100 trials, with a 95% bootstrap interval.
• Open harness: configuration-driven, with a container image. Any model that uses the Jev protocol or OpenAI's Decisions API can run. Integrate BeelineBench with your evaluation suite.

Results

Benchmark 1.0.0. The overall score is the geometric mean of the domain scores.

Commentary on benchmark 1.0.0.

* or †: at least one model (*) or heuristic (†) run did not solve within 2,500 nodes, so the true score is lower.

All benchmark versions and their figures

Sensitivity studies

Three studies measure how much the score of pplx-decider 1.1 changes on one problem:

• Representation sensitivity
• Order sensitivity
• Repeatability

Method

BeelineBench uses the model as the ranker of the frontier in a best-first search. At each step, the search sends all open states to the model in one request. The search stops when it finds the goal.

A beeline score of 1.0 is perfect: the model navigated to the solution in a minimum number of steps. A score of 0.1 means that the model explored ten times as many nodes as necessary. The score of a domain is the geometric mean over its trials, with a 95% interval over 100 random trials from the problem domain.

The score is the number of nodes in the shortest path to the solution divided by the number of nodes that the model explores:

score = (shortest path + 1) / nodes explored with the model

Before the search, a breadth-first search finds a shortest path to the goal.

BeelineBench also gives other measures on the same trials:

All benchmark evaluations are capped at 2,500 explored nodes. Model-based runs that did not find a solution within 2,500 explored nodes are marked with an asterisk (*) on the score. Heuristic-based runs that did not find a solution within 2,500 explored nodes are marked with an obelus (†) on the heuristic score. A capped run counts as 2,500 explored nodes.

Aggregated statistics that contain at least one run that did not complete within the 2,500 node limit are marked with these symbols, and a matching footnote contains the number of trials that exceeded the limit.

The frontier holds a maximum of 255 states. If it holds more, the search drops states at random. The frontier limit of 255 states gives the details.

Domains

• 8-puzzle (Wikipedia): the player slides eight numbered tiles on a 3 × 3 board, through one gap, until the tiles are in order.
• Blocksworld (Wikipedia): a robot hand moves blocks, one at a time, until the blocks make the goal towers.
• Countdown (Wikipedia): the player combines four numbers with addition, subtraction, multiplication, and division to make a target number.
• Word ladder (Wikipedia): the player changes one letter at a time to get from a start word to a target word, and each step must be a word.
• Wikispeedia (SNAP): the player clicks links from one Wikipedia article to the next, until the player gets to the target article.
• Rush Hour (Wikipedia): the player slides cars and trucks on a 6 × 6 board until the red car can leave through the exit. A vehicle moves only along its own direction, and other vehicles block the path of the red car. So the player must often move a vehicle out of the way first, and sometimes move a third vehicle to make space for it. The model gets the board as six rows of letters and dots, divided by |. BeelineBench makes these boards at random, and each one has a solution.
• Keys and doors: the player walks through the rooms of a building to the exit. Each door has a color, and the key of the same color opens it. The keys are in the rooms, and a key can be behind a different door. So the player must sometimes go into a side room for a key, and then go back. The model gets the building as a list of statements in a random order, for example "The red key is behind the blue door." BeelineBench makes these buildings at random, and each one has a solution.

Settings of benchmark 1.0.0

All scores use the same scale, where 1.0 is perfect. But some domains are harder than others, so compare scores from two different domains with care.

benchmarks.toml holds the exact settings of each version.

Data sources: Wikispeedia (West and Leskovec), and the word list of Knuth's Stanford GraphBase.

Quick start

Run the mini benchmark: the first 20 trials of each domain with pplx-decider 1.1 and pplx-decider 1.0. It needs one key, PERPLEXITY_API_KEY, in .env. Price estimates gives its price.

git clone https://github.com/kyle-pena-nlp/beelinebench && cd beelinebench
uv sync --extra plot
uv run python -m beelinebench baseline      # the heuristic and the oracle alone; sends no requests
uv run python -m beelinebench run --mini    # sends paid requests
uv run python -m beelinebench report

Usage gives the full steps, the configuration, and the commands.

Documentation

Limitations

BeelineBench has four known limitations. Each one can change a score.

The frontier limit of 255 states

A Jev question holds a maximum of 255 options. The search sends the full frontier as one question, so the frontier holds a maximum of 255 states. When the frontier holds more than 255 states, the search drops states at random until 255 states remain.

The heuristic arm, the oracle arm, and the model arm use the same rule. Each arm has its own seeded draws, so a trial drops the same states on each machine. The search forgets a dropped state, so it can find that state again later.

A long search fills the frontier. A Wikipedia article with many links also fills it quickly. For example, "United States" has 294 links. When the limit drops a state of the shortest path, a perfect chooser explores more states. The oracle score shows this effect. In benchmark 1.0.0, the oracle score is 1.000 for each domain except wikispeedia, where it is 0.987.

OpenAI's Decisions API accepted a question with 255 options in a test on 2026-10-09. Its documentation gives no limit. BeelineBench uses the limit of 255 for all models, so that all models get the same questions.

Decision models are sensitive to the presentation

A decision model can give a different answer when it gets the same options in a different form. Two examples are known:

• The order of the options. Jev prefers options near the start of a list. Thus, the chooser puts the options in a new random order for each question. The order comes from seeded draws for each trial and model, so the order is the same on each machine.
• The text of the options. JevChat uses Jev to write text one symbol at a time. Its author found that Jev chooses much better when each option is the full text so far, not the next symbol alone.

BeelineBench writes the states of a domain in one fixed form. A different form, for example a board as a grid and not as one line, can give a different score. Thus, a score measures a model together with the form of the states, not the model alone. Representation sensitivity and order sensitivity measure these effects on one problem.

Some APIs have no seed

The Jev protocol accepts only the fields model, state, and questions. It rejects all other fields, for example seed or temperature. Jev, pplx-decider, Clef, and the models on OpenRouter use this protocol. BeelineBench also sends no seed to OpenAI's Decisions API.

Identical requests can give different probabilities. In one test, the top option of Jev got 0.78, 0.78, and 0.83 in three calls. A different choice early in a search changes the remainder of the search. Thus, a second run of the same trial can give a different score.

BeelineBench fixes its own random values: the trials, the option order, and the dropped states. It cannot fix the answers of the model, so the results are not fully deterministic. The 95% interval does not include this variation. Repeatability measures it on one problem.

The models and their APIs have quirks

Some behavior of the models and their APIs can change a score. Model quirks describes each behavior, and the rule that BeelineBench uses for it: the served model, refusals, dated model names, a short context, models that BeelineBench cannot use, and errors from the APIs.

Related benchmarks

These benchmarks also measure decision models. Each one asks single questions. BeelineBench asks a sequence of questions, in which each choice changes the next question.

• Decision Index (code, Cloudflare's copy): more than 70 decision models, on single questions and games.
• S1MB (code, leaderboard): 137 benchmarks of yes-or-no, choice and score questions, from NLP datasets. A Borda ranking combines them.
• AIM-Decision (AIMultiple): 1,655 classification questions, and 50 browser tasks. It compares decision models with general LLMs.
• OpenRouter decision model rankings: the number of requests to each model. It does not measure accuracy.

Contributing

How to contribute tells you how to add a model, a problem, a protocol, or a benchmark version. AI-assisted code is okay, but a person must write the description of a pull request, and it must match the contents of the pull request in all material ways.

Citation

If you use BeelineBench, cite it as follows. Give the benchmark version that you used, because the code and the benchmarks have separate versions.

@software{pena2026beelinebench,
  author  = {Pena, Kyle},
  title   = {{BeelineBench}: How Efficiently Do Decision Models Navigate Multi-Step Problems?},
  year    = {2026},
  version = {1.0.0},
  note    = {Benchmark 1.0.0},
  url     = {https://github.com/kyle-pena-nlp/beelinebench}
}

If you publish results on the Wikispeedia domain, also cite the two papers of its dataset: West and Leskovec, "Human Wayfinding in Information Networks" (WWW 2012), and West, Pineau, and Precup, "Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts" (IJCAI 2009).

License

BeelineBench is licensed under the Apache License, Version 2.0. NOTICE lists the third-party data and its terms:

• The word list of the word ladder domain is from Donald E. Knuth's Stanford GraphBase, which is in the public domain.
• The Wikispeedia data is from the Stanford Network Analysis Project. SNAP gives no license for it. Thus, BeelineBench and its Docker image do not include it. A run fetches it from SNAP when it needs it.

Support BeelineBench

Each run of a hosted model costs money. The full runs of the six models in 1.0.0 cost about $120 in API fees. The pilots and the sensitivity studies cost about $30 more. The local Clef runs need a rented GPU. To pay for more models and new versions of the benchmark, sponsor BeelineBench on GitHub.