Action-Space Shaping for LLM Agents: Measuring and Mitigating Tool-Schema Bias

TL;DR: A tool schema — the JSON blob of function names, arguments, and descriptions you hand an LLM agent — is not the agent's action space. It is one of many equivalent encodings of that action space. This paper builds a framework that mechanically rewrites a schema into 32 verified-equivalent variants (same executable actions, same reachable states, same tasks) and finds that agent success rates swing from 0% to 97% depending on nothing but the encoding. Every model family breaks on different variants, closed models included. Cheap probes can't predict which schema will hurt; you have to run ~100 real task queries. And training repairs only the exact schema changes it was trained on — RL does it without collateral damage, SFT doesn't, but neither generalizes to genuinely new kinds of schema change. It's a careful diagnosis with a sobering non-cure.

A tool schema is a coordinate system, not a territory

Every agent benchmark, every RL training environment, and every deployed tool-calling system makes a quiet assumption: the tool schema is the environment. τ-bench picks one parameterization of its airline domain; AppWorld groups 457 APIs into application classes one particular way; MCP servers expose tools however their authors felt like factoring them. We score agents against these schemas as if the score measured task competence.

But consider modify_order(order_id, field, value). The same underlying executable action can be exposed as:

• one giant execute(operation=..., ...) dispatcher covering the whole domain,
• a dozen tiny tools like modify_order__status_shipped(order_id) with argument values baked into the names,
• a transactional protocol: begin(), then one write per argument, then commit(txn_id),
• the native tool with arguments nested, renamed, or reordered.

All of these admit a mechanical, invertible translation back to the same native action and reach the same final environment state. An agent that has actually learned the task — rather than memorized one serialization of it — should perform identically across all of them. This is the same observation RL researchers made long ago about action-space design (discretization, factorization, temporal abstraction all change learning difficulty), transplanted to tool-calling LLMs, where nobody had measured it systematically.

The paper's term for performance variation across equivalent encodings is schema bias, and the core engineering contribution is making "equivalent" checkable: an execution adapter decodes every variant-schema call back to native actions, and a validator confirms each variant executes the same actions and reaches the same states as the native schema on reference traces (~50,000 checks; it caught three implementation bugs before any model was evaluated). Scoring is schema-independent — an episode succeeds iff the multiset of decoded native actions exactly matches the gold set — so any performance gap is attributable to the interface alone.

Qwen3-4B success: .77 / .36 / .76 / .28 (same tasks, same scorer)

The transformation space, briefly

Nine operators fall into three families, ordered by how much they perturb:

Per-tool surface — nest arguments into an object, rename tools (namespaced or opaque identifiers), strip descriptions, reorder arguments. One native action is still one call.

Tool-set partitioning — merge several functions into one dispatcher (the chosen function becomes an argument value), or split one function into many (argument values move into tool names). Still one call per action, but tool boundaries move.

Cross-call protocols — one native action becomes several dependent calls: a begin/write/commit transaction, a reference resolution step (resolve a value to a handle, then pass the handle), or schema discovery (list a class's methods at runtime before invoking — essentially the MCP pattern).

The testbed: 12 synthetic domains, 168 native operations, 2,748 queries; eleven models (nine open-weight across Qwen2.5/Qwen3/Qwen3.5, Llama-3.1, Gemma-4, plus two closed models via API); up to 32 schema variants each. Validation on τ²-bench and BFCL with the same operators.

What they found: large, structured, model-specific

The headline grid (Figure 2 of the paper) shows success ranging from 0% to 97% with everything but the schema fixed. The structure of the variation is the interesting part:

Merging hurts; splitting mostly doesn't. Along a granularity ladder from 0.07× to 10.6× the native function count, splitting roughly preserves native performance while fully merging costs a median of 19 points. Intuition: splitting bakes decisions into names the model reads directly; merging forces the model to route through a dispatcher and remember namespaced argument conventions. And how the merged tool takes its arguments matters enormously — no encoding is safe for everyone:

Note the irony in that chart: the nested structure, which is exactly how JSON-RPC and MCP package arguments, is the worst structure for most models, dropping even the robust Qwen3.5 generation from ~.84 to ~.20.

Cross-call protocols are the hardest — but not inherently. Transactions and schema discovery collapse most earlier-generation models to near zero. Yet reference resolution, also a multi-call protocol, often scores at or above native. So multi-step interaction per se isn't the problem; whether a model follows a particular protocol is idiosyncratic to the model.

Closed models aren't immune. gpt-6-luna and GLM-5.3-Flash both move 32 points across equivalent schemas — though their weak spots are large catalogs (class dispatch, namespaced names) rather than the protocols that break open models.

It replicates on real benchmarks, with a twist. On τ²-bench, best-vs-worst schema gaps run 16–52 points per model. On the airline domain, most earlier models actually do better under some alternative schema than the benchmark's native one — meaning leaderboard scores partly measure fit to an arbitrary interface choice. On retail, fully merged collapses everyone to ≤.09.

Failures follow the variant. A seven-mode automatic failure taxonomy shows that a given schema breaks different models the same way: fully merged produces rejected-and-stuck loops (models keep calling the old native names — a "schema-form failure" where the intent is right but the encoding is wrong; re-scoring those as successes recovers up to 69 points for Qwen3-30B-A3B), transactions produce broken begin/write/commit handles, schema discovery produces silently wrong arguments. The kind of failure is a property of the interface; the magnitude is a property of the model.

You can't predict schema difficulty without running tasks

RQ3 asks whether a designer can rank candidate schemas cheaply. Two query-free probes — log-likelihood of correct call sequences, and a compliance probe on simple schema-derived instructions — rank a model's variants at only \rho = 0.52 and 0.57 (Spearman correlation with full-evaluation success). The failure is instructive: models often follow a protocol perfectly on isolated calls yet collapse inside multi-turn tasks. Qwen3-4B complies with the transaction protocol 97% of the time in isolation but scores .28 on actual tasks; Qwen2.5-32B fails the isolated probe (.00) yet scores .77 on transaction tasks. Difficulty is a joint property of model × schema × task distribution.

Sampling real target queries fixes it: 36 queries reach \rho = 0.72, ~100 reach 0.81, 800 reach 0.92. Since 36 queries match the probes' budget, the probes fail because they omit the tasks, not because they're small. And rankings don't transfer across task distributions (synthetic → τ²-bench correlations are near zero or negative), so you must sample from your environment's distribution.

Training repairs what it sees — and only that

RQ4 compares four mitigations on Qwen3-4B, all with the same 2,000 training queries, evaluated on twelve representative variants including held-out domains:

The pattern is clean and a little deflating:

• Training-free tricks fix one-sentence habits. A single instruction describing the calling convention adds +45 points on schema discovery; constrained decoding on the first call rescues fully merged (Gemma: 0 → .50). Nothing else moves.
• SFT repairs trained variants but taxes untrained ones, dropping already-robust variants by up to 10 points (and native by 8). The tax depends on phrasing more than volume.
• On-policy GRPO repairs trained variants with no tax, keeping every variant at or above baseline. The ablations (Appendix G.3) identify three necessary conditions: the variant must be in the training data, the KL penalty must be zero (KL=0.01 caps schema discovery at .25 vs .75), and the environment must reject invalid calls — with rejections silently executed instead, the learning signal vanishes (.49 → .08 on a transfer variant).
• Transfer is narrow. Gains carry to new combinations of trained changes (+8.8) and stronger versions of them (+11.2), but new operator types get −2.4. On real benchmarks, trained models improve only where the rewrite matches a trained variant (+10.5 on τ²-bench retail under the transaction rewrite); overall τ²-bench and BFCL scores barely move.

So schema robustness, as currently trainable, is not a general capability — it's a union of memorized interface conventions. Training cannot fix schema bias once and for all.

What this changes, and what to doubt

If this holds, three practices need revision. Benchmarking: a single-schema score confounds task competence with interface fit — the authors' proposal to report performance over a small set of verified-equivalent schemas is cheap and reasonable. RL environment design: your choice of action factorization is a hyperparameter with 19+ point swings, and there's no model-agnostic safe choice. Deployment: an engineering refactor of your tool catalog (merging tools, adopting MCP-style nested args or runtime discovery) can silently crater a specific model while leaving your eval suite — run on the old schema — green. The practical takeaway is concrete: before committing to an interface, run ~100 real queries per candidate schema per model.

Reasons for skepticism. Most measurement is in a synthetic environment with templated-then-rephrased queries, all-required arguments, and 66% enumerated values — properties that make merge/split operators well-defined but may exaggerate their effects; the τ²-bench validation is real but covers only six schemas and two domains, with the model under test also serving as user simulator and judge. Exact-multiset scoring is strict; some "failures" may be benign alternate paths (though the schema-form analysis partially addresses this). The mitigation section is thin relative to the measurement: one 4B model, one training budget, and the honest conclusion is essentially negative — nobody has shown how to train general schema robustness, only variant-specific repair. And the operator space, as the authors note, omits whole axes (how results and errors are reported, how state is exposed), so 32 variants is a lower bound on the problem.

The most illuminating read is Section 5 with Figure 2 (the model × schema grid — the whole phenomenon at a glance), followed by Appendix G.3 if you train agents: the three-condition recipe for RL repair (variant in data, no KL penalty, hard rejections) is the most actionable finding in the paper, and the ablation showing that the rejection signal itself — not its wording — drives learning is a genuinely useful piece of mechanism.