Search under constraints.

One of the questions puzzling the current AI landscape has been trying to improve the robustness and verifiability of AI agents. We can state this more formally: how do we make sure AI agents do not violate constraints, and still verifiably solve the task they were designed for? This problem likely becomes exploding with multi-task agents and long-horizon tasks. Since LLM based AI agents seem to be the standard in the industry for dealing with multiple tasks such as information retrieval, printing something or sending a message, we need a verifiable and efficient method of tool call sequencing which is constrained by a set of rules.

Let's phrase the problem more formally. We can describe an AI agent performing these tasks as a partially observable Markov decision process. The agent lives in an environment whose true state it cannot see directly; it only ever observes the results of the tool calls it makes. Rather than knowing exactly where it is, the agent maintains a belief state: a probability distribution over the possible states it could occupy, given everything it has observed so far. Every tool call is an action that both changes the underlying state and returns an observation, and from that observation the agent updates its belief. What separates this setting from standard MDP problems is the following. First, not every tool is usable at every step. Some are deactivated or gated by permissions; at each state the agent is choosing from a restricted, state-dependent set of admissible tool calls. Second, every tool call costs something: time, money, API calls, side effects in the world, and the agent has only a finite budget to spend before it must commit. There is a verifier that decides whether the goal was actually met. Now the problem is reduced to the following. Starting from its current belief, the agent must choose a sequence of available tool calls that maximizes the probability of verifiably completing the task, while staying within its budget and never violating its constraints.

Our goal with Perseus is to develop an advisor for AI agents that provides them with much better accuracy and guarantees execution within constraints defined by the user. Of course an easy way to answer this is to just use an LLM here with some trial and error. However there are a couple fundamental drawbacks with just using an LLM, which is focused on trusting its output, which was demonstrated by Anthropic in their paper in 2025 on why LLMs were not to be trusted based on their reasoning outputs which defaulted to largely being issues with CoT. Hence, LLMs for multitask agents have a plethora of caveats that arise due to this notion of robustness, verifiability and constraint based searching.

Here is where Perseus excels, because it is not a black box we implicitly trust, it is an explicit, model-based search over tool-call sequences. Using Perseus for this task of identifying the correct sequence of tool calls enables the following outcomes: First, the constraints become guarantees, so staying within the rules is a property of the method itself. Second, every recommendation is grounded in an estimated probability of verified completion and an estimated cost. So when Perseus proposes a path, we can see why it was chosen and how confident it is, rather than accepting a fluent sentence on its ability to reason about it. This is precisely why the LLM-only approach cannot be answered. Third, because Perseus only advises, it hands the agent strongly-suggested sequences and lets the agent's own reasoning execute them it stays small and cheap while still doing the expensive deliberation the LLM skips.

Let's dig deeper into explaining the ideas behind how this transition of Perseus from code retrieval to being an advisor for a multi-task agentic framework works. We frame the user's requirements as a single object, Phi. It has three components namely: the set of forbidden tools, the ceilings on each resource such as a cap on dollars or latency or the number of calls, and a set of soft weights, one per resource, that say how aggressively to minimize each resource while it stays under its ceiling. A resource can appear in Phi twice, once as a ceiling it must never cross and once as a soft weight saying that, below that ceiling, less is better. Taken in order, the agent is doing this: maximize the probability that the verifier accepts the result first, then among the trajectories that survive, minimize the weighted resource spend, all while staying under every ceiling and only ever calling tools that are admissible at the current belief.

The problem with this definition is in implementation, it is unreasonable to expect the user to define Phi well. Sometimes Phi is sharp, the user states it outright and we condition on exactly that. Just as often we hold only a distribution over Phi, because the spec is vague, or because we are serving a population whose preferences we have sampled rather than enumerated, or because we sit upstream of the request and want a policy that is good in expectation before the exact requirements arrive. The cleaner way to see these two cases is that the sharp one is just the degenerate limit of the distributional one, the distribution collapsed onto a single point. So we do not treat them as two problems. We work in terms of the distribution and let a known Phi be the special case where that distribution is a spike.

What follows from this framing is that the value that we learn is conditioned on Phi rather than tied to any one setting of it, and it is learned across the distribution over Phi rather than refit for each request. This is the multi-objective reinforcement learning idea of capturing the entire Pareto distribution (scaling laws exponential) inside one model instead of solving a single scalarization at a time, and it is what frees us from retraining per user. When a request pins Phi down we evaluate at that point. When it does not, we reason under the prior, either committing to an action under the expectation over the distribution, or holding a posterior over Phi and letting it sharpen as the user's behavior reveals which region of preference space they actually occupy. The remaining budget belongs in the same condition for the same reason: the value of an expensive call depends on how much budget is left, so a value that ignores the remaining budget is simply misspecified.

The hard part of Phi, the forbidden tools and the ceilings, stays outside all of this on purpose. We enforce them structurally rather than learn them. The set of candidate tools is masked to the admissible set before anything is scored, and any branch that would cross a ceiling is cut before it is ever expanded, which is sound because resource spend only grows as a trajectory lengthens. A forbidden tool is then not a low-scoring choice, it is simply not among the choices, and an overspending branch is gone before it is evaluated at all. The reason for keeping this away from the learned, Phi-conditioned machinery is that the guarantee then holds for every trajectory and for every Phi the distribution puts weight on, no matter how well or badly the value model was trained.

Whether the verifier accepts a result does not depend on what the user was willing to pay. We treat that probability on its own terms and never let the cost objective bleed into it. And we resolve the trade-off between completion and weighted cost by ordering the two rather than summing them, because a single weighted sum fixes one point on the Pareto front and, for some settings of the weights, would give up real success probability to save a marginal amount of cost. That is the trade we refuse, which is the whole reason completion and cost are not placed on a shared axis in the first place.

The payoff from framing it this way shows up at inference. Because the preference lives in how we collapse value, not in the model weights, when a user changes requirements partway through, asking for more speed, less spend, or a newly disabled tool, it does not cost us a refit, only a reread of a search we have already done, because the learned model is evaluated under Phi rather than retrained for Phi. The expensive part, learning a value that is accurate across the whole space of preferences, is paid once and offline, and everything that happens when a request actually comes in is cheap. The same setup holds anywhere an agent has to choose a legal, budgeted sequence of tool calls toward a goal with a verifier, which is most of what we are currently asking LLM agents to do and trusting them to get right. The guarantee carries over unchanged because it never depended on the domain, and only the world model has to learn the new domain. That is what makes a distilled, constraint-aware search worth building underneath these agents, it stays small and cheap, it does the deliberation the LLM skips, and the part that makes it safe is a property of the method and not a thing we are hoping the model learned.