The menu is an execution prior, state path tool menus for online agents

The paper I am reviewing here is The Menu Is an Execution Prior: State-Path Tool Menus for Online Agents, released on arXiv as 2609.09395. It argues that a tool menu should be designed as a prior over execution paths rather than as a ranking by similarity to the request sentence. You can find the original linked under the title.

Hello, this is Patrick. I paused at the title for a moment when I first saw it, because the word menu sounded almost too ordinary. In agent research the menu can sound like a small interface detail around search results, yet the authors say that this modest device decides online success and failure. So why did the menu become this important. The fastest way to see it is to start at a restaurant.

The menu makes sense once you see it as a restaurant menu

Imagine a customer walks in and orders a stew. From the kitchen side, the final act alone never completes the dish. Someone has to wash rice and start the cooker, prepare broth, trim ingredients, and manage heat before the stew can arrive at the table. Now suppose the ticket sent to the kitchen shows a large photo of the finished stew but leaves out how to use the rice cooker and the broth pot. The cook knows what to make, yet the hands are tied.

The situation for an online agent is close to that kitchen. The agent may have thousands of tools available, but right before execution the model actually sees only a short ordered subset. The paper calls this the tool menu, with the rule that the agent can call only tools inside this menu. So the menu is not a friendly suggestion list. It is the boundary of action. I liked this definition because it moves search and ranking from an outside information retrieval problem into the middle of execution. What the model sees right before it acts already decides what it can do.

That shift raises the next question right away. Where does the current way of building menus go wrong.

Why picking tools that look like the request leaves work undone

The common construction today lines tools up by relevance to the request. Tools whose names share words with the request, or whose descriptions sit close in meaning, rise to the top. This works well for one step questions. Ask about weather and the weather lookup lands at rank one. The trouble starts when several steps tangle together.

A multistep task never finishes with the final act alone. To complete a payment you may first need to authenticate, to authenticate you may need a reservation number, and to get that number you may need to pull a search record. In other words, earlier tools have to produce results in order so the final action has usable inputs. Relevance ranking usually pushes the final action to the top, because the request sentence mentions payment and the payment tool scores highest. Producer tools such as reservation lookup or identity check look less like the request, so they slide down.

What interests me more is how the authors read this failure. They do not treat it as a scoring problem that better similarity could fix. They treat it as a wrong criterion for ordering. Relevance tells you what to do, but it never tells you what to prepare in which order. So the menu can display the final action in plain view while the agent cannot take the first step. There is no executable entry, and the producers that would create intermediate material are missing. From a systems perspective, this observation stings because the shape of the failure is familiar. When we look at a new AI architecture we look at the shape of failure before the score, and here the shape is one I have seen often. Plenty of tools, yet no tool to start with.

That leaves an interesting question. If resemblance is the wrong ruler, what should order the menu.

What it means to treat the menu as an execution prior

The authors answer that the menu should act as an execution prior. The phrase sounds heavy, but people make the same judgment every day. When you open a map app before a trip, the app first shows routes from your current place to the destination, with gas stations and rest stops along those routes. It does not list every place whose name resembles the destination. Only things on a walkable path appear, and that selection already guesses at execution.

The state path in the paper is close to that road on the map. It is a route drawn before execution, from the observable request state to the desired outcome state. The menu then holds a prior belief over those routes, a sense of which paths are worth trying. The test is no longer whether a tool resembles the request sentence. The test is whether it sits on a path from this state to that state. I think the more important result is behind the number here, because the role of the menu moves from search output to part of the execution plan.

This is where I would be careful not to overread the experiment. A prior does not mean a fixed script that takes freedom from the agent. The menu still only offers candidates, and the agent still chooses during online execution. It only starts with a sketch instead of a blank page, much like the sign at a trailhead. The sign does not climb the mountain for you, but it tells you where to fill water and where to save strength. The menu in this paper does the same work. It does not decide what to do so much as suggest an order of preparation worth trying.

Then how do you actually build such a menu. Would a larger menu solve it by itself.

A bigger menu would not fix this

The intuition says to enlarge the menu. If 32 tools feel short, show 64 or 128 and the missing tool will arrive eventually. The scene reported here points the other way. A well built menu of 32 tools holds more complete chains than an existing style list of 128. A quarter of the size, yet ahead in executable coverage.

The difference matters more than it looks. A larger menu spreads attention, fills context, and raises serving cost. A small menu with the right order lets the agent move at once. It is like cooking from a recipe rather than from a long shopping list. Ten ingredients arranged in order help more than a hundred ingredients piled without sequence. Arrangement does the work, not volume.

I found the source of the gap convincing because it comes from structure rather than luck. A 128 item list ranked by relevance tends to cluster near the final action. The names look alike, but the tools do not connect into an order. A 32 item menu built around state paths connects. It has an entry that can run now, producers that fill missing inputs in the middle, and a closer at the end. I stopped here for a while, because we talk a lot about model size and prompting when agent performance comes up, yet we talk too little about what we place in front of the model and in which order.

So what machine builds a menu that connects like that. It is time to look inside.

A state path is a route drawn before you move

Let me walk through the state path idea more slowly. A request usually arrives as a finished sentence, but from the system side it looks like a start state. Not logged in yet, no lookup results yet, no auth token yet. The desired result sits on the other side. Payment done, booking confirmed, document issued. Between the two states there is a gap, and only tool calls can fill it.

A state path sketches the fill order before acting. It asks together whether a tool can run from the current state, whether its output satisfies the input of a later tool, and whether such orders recur in training paths. The three have to agree. A tool that cannot run now is no use however much it resembles the goal, a middle tool that fills no input breaks the road, and a strange order never seen before is close to a gamble.

What I liked in the authors choice is that they did not use the path only to explain behavior after the fact. Usually we run the agent first and then recover the path from logs. Here the order flips and the path is baked into the menu before execution. The menu itself becomes a draft map. The agent still judges online, but it judges on paper with a sketch rather than on blank paper. If you picture real operations, the difference is large. Even when a schema changes overnight or one tool goes into maintenance in the morning, an agent with a sketch finds the next fork faster.

That sketch needs an eye that reads three signals at once. That eye is the encoder.

Why the encoder has to read three signals together

Talk of an encoder can sound difficult, but the job is simple when described by role. It does not grade each tool alone. It grades each tool by its role on a path. The three signals in the paper each answer a different question. Can this tool run from the current state right now. Does its output actually fill the input of a later tool. Did such an order appear repeatedly in training paths.

The first signal is executability. However good a tool looks, there is little reason to place it early if it cannot be called with current inputs. Calling payment confirmation without a reservation number is an order mistake. The second signal is input output fit. The date format made by an earlier tool has to match the format wanted later, and a user identifier has to carry across steps. Tools chosen only by similar names break exactly here. The third signal is remembered order. Sequences that appeared often across successful training paths carry the weight of tested habit. Frequency alone never proves correctness, but it beats picking with no clue.

I read the combination like a notebook of past mistakes. Each signal alone can mislead, yet overlaid they expose errors. Executability alone gathers only buttons you can press now. Input output fit alone mixes in tools you cannot press yet. Past order alone brings old roads that may not fit the current situation. Only together do they show a road worth trying from here. The overlap also changes the character of the whole menu. The task stops being picking tools one by one and becomes picking a connected road as a whole.

So how does that judgment turn into an assembled menu.

A two stage device that covers entry points and fixes order

The full device moves in two stages, a retriever and a reranker. The names sound grand, but the work is plain when spelled out. First gather candidates that together can walk, then line them up in an order that can execute. Order matters because the menu is ordered. The agent reads from the top when choosing the next act, so if a producer sits below its consumer, the needed material stays out of reach even while visible.

The retriever has to cover three shares. An executable entry, producers that fill missing inputs, and the final action that closes the work. If any share drops out, the chain breaks. Without an entry the agent cannot start, without producers it stalls halfway, without the final action it cannot finish. The goal of retrieval therefore changes from gathering many similar items to gathering a combination that does not break. That change in success criterion, from resemblance to completeness, made me nod. It reframes search as preparation for walking.

The reranker then pulls producers before consumers. Seen from outside it looks like a small sorting change, but in execution flow it is decisive. When the visible order shows the auth token created before the payment call, the agent follows the road naturally. When payment appears first, the agent wanders while holding missing inputs. Same ingredients, different result, the way a shuffled recipe card cooks differently from an ordered one. The device does not change the agent itself. Weights stay the same and prompting stays the same. Only the view right before execution changes, and with that view the online success rate moved. That is the claim to test with numbers, and numbers need their conditions checked before trust.

How to read the scene where 32 beats 128

The ToolBench result reads clearly at first glance. Online success rose from 0.737 to 0.898, ahead of retrieval, reranking, generation, and routing baselines, without changing the agent. The starting point 0.737 was already not low, so a lift above 0.16 points means roughly one extra saved task out of every six failures. In operating terms that shift is not small. When work that succeeded seven times out of ten starts succeeding nine times out of ten, retries and human handoffs fall in a visible way.

The sharper number is the contrast of 32 and 128. The state path menu held more complete chains with 32 tools than the official list held with 128. This part is easy to misread, so care helps. It does not mean 32 always beats 128. It means the selection criterion matters more than the count. A large menu picked by resemblance crowds around similar final actions, while a small menu picked by path covers entry, producers, and finish in balance. It is a choice of where to spend the same budget. Spread wide, or connect tightly.

Counter evidence belongs here too. ToolBench is a representative market for tool use skill, but it cannot stand in for every production setting. Description quality, schema stability, and latency of outside systems remain outside the benchmark. Still, I do not take the result lightly because the shape of the gain stays consistent. It is not a sharp spike on one benchmark but a structural change, more complete chains held and order corrected, followed by numbers. The number is the result. The rearrangement before it is the real story.

Would that rearrangement survive when the model changes.

What questions remain when the agent stays the same

One of the parts I want to follow next is the executor swap test. The authors report that the success gain holds across executor families with different model capacities. If that holds, the meaning is large. It would mean the benefit comes from execution structure rather than from the habits of one model. Smaller models lose the road easily and need maps more, while larger models might seem fine without maps yet still waste steps when order tangles.

From a systems perspective, the next question is obvious. Where is the cheapest place to keep this menu. Should it be computed fresh right before each run, or prepared and refreshed on a schedule. The encoder needs input output specs and past paths at hand to read its three signals, and in a setting where thousands of tools shift and schemas change often, keeping those materials fresh is real work. A better menu that takes too long to build can cancel its online gain. The paper stresses gains from the menu alone with the agent unchanged, and my next sentence would ask who pays for the menu, when, and how much.

The shape of remaining failure also deserves attention. Success at 0.898 still leaves about one failure in ten. Where does the road break. Perhaps an entry was found but a producer output missed the expected format by a small margin. Perhaps a new order never seen in training was needed. No map shows roads under construction. So I hope the next version shows maps of broken chains alongside successful ones. Knowing where paths snap is how the next map gets drawn better.

That brings me to the wider question this study leaves for agent design.

Scenes I want to see in the next study

There is an old question here. Does an agent become smarter by growing the model, or by tidying the world the model sees. This paper votes for the second. Keep the model fixed, rebuild the menu around paths before execution, and online success jumps. When we look at a new AI architecture we do not look at scores alone. We look at what actually changed and what cost structure that change creates in a system. Seen that way, the change here is clear. The criterion for picking tools moved from resemblance to connection, and that moved criterion changed even the order inside the menu.

Then where could this flow break. I will return to that promise here, because the menu is not a cure all. The state path idea shines when the start state reads clearly. When the request is vague and the start itself sits in fog, drawing the route is hard. Tasks where one tool output does not flow neatly into the next input can also weaken the prediction, for example work that pauses for human approval or offline sign off outside the system. Drawing a good map and paving real roads are different jobs.

Even so, I think this paper moved the question in agent research by a useful distance. The question changed from which tool looks most like the request to which order carries execution to the end. The question is good because its answer lands directly on a small device, the menu. No retraining of a giant model is needed, and there is a handle to try tomorrow. What I would watch next is how far that handle holds in harder settings. Tools changing live, input formats shaking often, several agents contesting the same tools, would the path menu still hold its line. On the day that answer arrives, the menu will be called an execution plan rather than a search result. Then what is the role of people. I suspect it moves less toward walking the road and more toward deciding which roads to sketch in advance.