CS Paper Radar

Prefix Executability: Evaluating Tool-Using Agents Beyond Final Success

Amir H. Rezaeian, Weiyi Sun, Yassine Benajiba, Dan Roth

cs.AI cs.CL ·submitted 2026-10-29 16:58 UTC · v1
top venue

Abstract

Tool-use benchmarks often score agents by final task success, but terminal outcomes can obscure whether the intermediate tool-call trajectory was executable. We propose prefix executability as a trajectory-level evaluation protocol for tool-using agents. The protocol measures whether every prefix of a predicted tool-call sequence remains executable under tool schemas, state preconditions, and data dependencies, and summarizes reliability using Prefix Executability Curves (PEC), First-Error Depth (FED), Trajectory Executability Rate (TER), horizon-normalized AUC-PEC, and Recovery Rate (RR). We instantiate the protocol on stratified samples from BFCL-v3 multi-turn and ToolSandbox, and on the complete Airline/Retail base splits of $τ^3$-bench. We observe that outcome-only and prefix-level rankings diverge: agents whose execution is conditioned on an unverified plan often achieve higher point-estimate final success than non-plan-conditioned baselines while substantially lowering TER and AUC-PEC. These divergences are precisely the failure modes that prefix executability is designed to expose: they reveal whether apparent success rests on an executable trajectory, where invalidity first enters, and whether success follows recovery from an earlier failure. As a validation intervention, explicit pre-execution plan checking can improve executable-prefix survival while maintaining competitive terminal success. These results show that final success alone is insufficient for evaluating tool-use agents and that prefix-level executability provides an actionable reliability signal for comparing agents, diagnosing failures, and assessing validation mechanisms.

Comment
21 pages, 2 figures. Accepted to NeurIPS 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Executable Prefix Values for Locating Agent Failures

cs.AI cs.CL ·2026-10-13 ·Bingyu Shen, Jiaqi Tang, Lan Wei, Yi Sheng, J. Jenny Li +1 more
hot direction similarity 0.69
Abstract · 46 pages, 12 figures, 60 tables

Work on debugging LLM agents treats the "first mistake" marked by a human or LLM judge as ground truth for where a trajectory failed. We ask whether such labels point at causes or symptoms, and make the distinction executable: we restart the agent from reconstructed intermediate states of a failed trajectory and estimate its prefix value V(h_t), the probability of success from each step, with a certified point of no return (PNR) for a failure. On 150 SWE-bench Verified tasks with two frozen open-weight agents, we build such curves for 47 and 60 failed trajectories and probe every step labeled by four frontier judges under the Traverse rubric. We find that the labels do not mark what a controller needs. Judges of different lineages agree on the exact step in only 21/57 cases, and the newest judges flag mistakes in 8/10 and 10/10 successful runs. For 66% of the labels, the agent's success probability does not drop at the labeled step; only 7/188 answers name the decisive step. Restarting at the measured restart point raises expected success from 0.44 to 0.57 offline, and real restarts confirm the advantage, whereas restarting at a judge's label does not (-0.08 to -0.03). We release our code, curves, and labels.

0.50

When Agent Metrics Measure Different Things: An Evidence-Grounded Audit of the Praxa AI Pipeline

cs.SE cs.AI ·2026-09-10 ·Stefan G. Creadore, Peyton Woakz
similarity 0.66
Abstract · 22 pages, 4 figures. Retrospective measurement audit with aggregate data, offline analysis code, and a prospective, unexecuted operator-cove…

Agent evaluations can be numerically correct while measuring a different construct from the one implied by their labels. We present a retrospective measurement audit of selected Praxa AI implementation files, historical evaluation artifacts, and operational records. A 139-case offline routing report contains 112 passes and 27 failures despite zero gating failures, because known gaps are explicitly exempted from the gate. An identifier-free export represents 8,843 tool-attempt rows: 8,395 recorded durations and 448 missing values. Of the durations, 121 equal the signed 32-bit maximum and carry abandoned-client labels; inspected database code clamps elapsed lifecycle age. The pooled recorded 99th percentile is 2,147,483,647 ms, versus 38,118.31 ms among server-observed completed calls. This is a stratum contrast, not a treatment effect. In a documented single-trajectory compaction pilot, the reported follow-up input reduction is 94.39%, but the reduction across the trigger and follow-up calls together is 46.54%. We reproduce the descriptive calculations, verify 91 timing statistics through a separate weighted rational-arithmetic implementation, and execute 13 scoring-function and 12 analysis-verifier tests. Finite-completion bounds show how missing durations limit all-row timing statements without imputing values. The contribution is a source-linked case study and reusable verification package for separating gate policy, lifecycle timing, and request-level accounting from broader agent-performance claims. Historical provider runs and the full current pipeline were not independently reproduced; general capability superiority and population-level statistical significance are not established.

0.35

Measuring the Serving Stack Instead of the Model: Hidden Confounds in Local Tool-Use Evaluation

cs.CL cs.AIcs.SE ·2026-09-22 ·Lijuan Tang, Yuemeng Zheng
similarity 0.65
Abstract · 9 pages, 4 figures, 3 tables. Accepted at the 2nd Workshop for Research on Agent Language Models (REALM) @ EMNLP 2026

A coding agent must emit a valid tool call--a parseable invocation of a tool in the provided schema--before the harness can execute its chosen action. We study how local serving stacks affect this protocol step and show that measured outcomes can depend on the serving layer rather than model behavior alone. In Ollama, the default tools= request is gated per model by a static template flag: some models are accepted and return calls as text, some return native tool_calls, while Phi-3 and Gemma-3 are rejected before inference. In our harness, rejection and retry exhaustion are not preserved as structured failure metadata, so downstream analysis can misclassify them as model non-calls and naively report 0% fidelity. Adding a text tool list while retaining the native channel recovers much of the measured fidelity for accepted models, whereas a uniform text protocol reduces fidelity for Llama-3.2, which has native tool-call support. Cross-stack probes on Ollama, llama.cpp, vLLM, and SGLang show different handling of the same request. Constrained decoding removes parse failures but can induce non-termination, and turn-pooled versus per-instance estimates differ by up to about 55 points. We conclude with a checklist for treating serving behavior as part of the evaluation protocol.

0.55

Agent Harness Awareness: Turning Verified Telemetry into Operational Control for Tool-Using Agents

cs.AI cs.CL ·2026-09-13 ·Manu Agrawal, Shrey Nagpal
benchmark similarity 0.64
Abstract · 9 pages, 3 figures

Tool descriptions tell an agent what an action can do, but they do not necessarily reveal whether that action is healthy or suitable at the moment of use. Execution harnesses often possess this information through monitors, traces, and recent failures while the model choosing the next action does not. We call this gap operational blindness. We introduce Agent Harness Awareness, a trust-separated design in which the host supplies a small, fresh, verified state snapshot before a consequential action while retaining measurement, enforcement, evaluation, and final dispatch authority. We test its tools-and-network instance with ToolRoute, a controlled isolation benchmark that holds the task and candidate semantics constant and varies the operational information available to the model. In a 216-decision ablation across GPT-5.6 Sol, Claude Sonnet 5, and Gemini 3.7 Flash, verified tool-health state reduced mean observable policy regret by 96.9% against a same-shape neutral control (4,252 ms to 131 ms) and raised single-dispatch completion from 69.4% to 95.8%. In a separate 27-decision end-to-end replication with live local TCP/HTTP execution, OpenTelemetry client spans, and Toxiproxy-injected faults, verified state reduced mean regret from 8,956 ms to 0 ms (zero excess observable operational cost) and completed the live action in 9/9 model-by-fault cases versus 5/9 for the neutral control. These studies establish the tools-and-network instance of Agent Harness Awareness: selected host telemetry materially improves pre-dispatch operational choice. Runtime state, hardware pressure, economics, retry-aware recovery, and heterogeneous selection remain open empirical extensions of the same architecture.

0.22

TRACER: Trajectory-Aware Tool Retrieval for LLM Agents

cs.CL cs.AIcs.IR ·2026-10-15 ·Tanish Kher, Sarvesh DK, Abedelkadir Asi, Sparsha Chennarayapatna Sundaresh, Dezhi Hong
similarity 0.64
Abstract · 21 pages, 7 figures, 23 tables

Modern agents select tools from registries, but exposing entire registries incurs high token costs and can impair selection as they grow. We present TRACER, a retrieval front-end that indexes observed tool-call sequences in a trie and ranks continuations using a learned blend of empirical and contextual priors. On a mixed retail-and-telecom $τ^2$ environment, TRACER improves GPT-5.4's tool-selection accuracy by 4.7 points while reducing input tokens per step by 80%, exposing just 5 of 128 tools. In autonomous full-turn execution, it matches GPT-5.4's full-registry task success with 61% fewer input tokens per step. Across six environments and four models, TRACER improves tool-selection accuracy over full-registry selection in 21 of 24 model-environment pairs, with average gains of 6 to 10 points; the three exceptions trail by at most 2.2. We analyze failures in both regimes to identify directions for future work.

0.21

ShadowBench-MCP: Measuring Shadow Invocations in MCP-Style Tool Routing

cs.CR cs.AIcs.MAeess.SY ·2026-11-09 ·Eyhab Al-Masri, Wenjun Yang
publishedbenchmark similarity 0.63
Abstract · Presented at the 35th USENIX Security Symposium (USENIX Security 2026)

LLM agents increasingly act as routers for tools, APIs, and software-supply-chain workflows, making an execution path - rather than generated text alone - a security-relevant model output. We study shadow invocation: a task-preserving request variant that causes an LLM router to select a riskier execution path, potentially skipping validation, provenance, staging, redaction, or audit controls even though the request does not ask for a malicious action. We introduce ShadowBench-MCP, a benchmark and metric suite that separates task preservation (TPSS), operational pressure (OPSS), and route-geometric drift (RGAS), and combines them in the pre-execution SODS score. In a focused policy-ablation study using a Groq-hosted qwen/qwen3-32b router, 120 routing decisions yield 96 original-versus-variant comparisons across six security-sensitive workflows. Efficiency-first routing produces a 29.2% shadow-invocation rate and 26.7% safety-tool skip rate. Policy-aware routing reduces these to 4.2% and 1.7%, respectively, corresponding to an 85.7% relative reduction in shadow invocations. Pre-execution signals distinguish shadow routes with ROC AUC up to 0.94. These results are early, single-router evidence of a policy-dependent routing-layer security effect, not a claim of universal vulnerability.

0.38

Think Before You Act: Decision Gate for LLM Agents

cs.AI ·2026-10-28 ·Iftach Shoham, Yuval David, Offer Akrabi, Erez Bilgory, Ido Levy +3 more
similarity 0.63
Abstract

LLM agents increasingly perform consequential actions through external tools, yet their proposed actions are often executed without independent verification of policy compliance or task completion. We introduce JevAct, a runtime verification framework that intercepts selected agent actions before execution and enables feedback-driven correction. JevAct compiles domain policies into executable state checks and structured questions evaluated by a prefill-only decision model, which produces probability-based judgments without relying on LLM generation. By combining deterministic verification of tool-state facts with probabilistic assessment of conversational context, the framework identifies potentially invalid actions and premature task termination, providing targeted feedback for bounded revision. JevAct operates independently of the underlying agent model and requires no modifications to its parameters or tools. We evaluate JevAct across eleven LLM agents on $τ^2$-bench Airline and Telecom tasks and BFCL. Results show improvements in agent reliability across multiple models and benchmarks, with particularly consistent gains on Telecom and BFCL, while performance on Airline is more mixed. Overall, these findings suggest that combining structured decision models with executable verification can improve the reliability of tool-using LLM agents.

0.10

The Double Measurement Confound in Agent Benchmarks: De-Scaffolding, Ground-Truth Scoring, and Reliability Beyond the Mean

cs.SE cond-mat.mtrl-sci ·2026-09-06 ·Yonghong Zhang, Shadi Motaali, Vu Phong Dinh, Avin Piroutiniya, Jorge E. López de Vergara +4 more
benchmarkhighly cited similarity 0.62
Abstract · 31 pages, 18 figures; supplementary material included as appendix

Agent benchmarks are increasingly used to compare large language models (LLMs) and guide deployment decisions, yet benchmark scores are meaningful only if they measure model capability rather than properties of the evaluation pipeline. We identify a double measurement confound: execution-critical decisions are performed by a fixed scaffold instead of the model, while the scorer evaluates outputs using criteria that may not reflect task correctness. We unify these issues within a measurement-theoretic framework that characterizes when benchmark scores can be interpreted as evidence of model capability, and instantiate it with an audit-and-repair protocol that (i) transfers execution-critical decisions from the scaffold to the model, (ii) replaces shape-based evaluation with seeded ground-truth scoring, and (iii) reports reliability beyond the mean through worst-case and tail-risk metrics. Experiments on ComtradeBench show that the joint intervention transforms a nearly flat leaderboard into a reliability spectrum that distinguishes both average performance and robustness across seeds. Applying the audit to existing benchmarks further shows that scorer validity is benchmark-specific, whereas scaffold ownership is an uncontrolled axis wherever we probed it. Our results suggest that benchmark scores should be interpreted together with their scaffolding level, scoring criterion, and reliability profile, providing a practical framework for more valid evaluation of LLM agents.

0.46