OoO-Spec: Out-of-Order Semantic Speculation for Fast Tool Calling
Zhiheng Zhang, Mujie Xu, Feiyu Sun, Zhixin Zhang
cs.CL
2026-08-02
A frozen 0.6B sidecar predicts a tool call's function and arguments in one parallel wave. OoO-Spec is fastest in all 21 target-benchmark cells, averaging 3.89x over autoregressive decoding.
Every time an LLM agent makes a tool call, it has to emit a structured function invocation: which function, and what value goes in each argument. Mainstream models still write this JSON one token at a time, autoregressively, and that is wasteful. The function choice and most argument values can be read off from the user's request and the tool schema without token-by-token generation.
ToolSpec, the prior work this builds on, captures the schema half: it reuses the tokens fixed by the schema and retrieves fragments from earlier calls to speed things up. Its ceiling is that it can only reuse what already exists. When a user says "remind me to meet John at 3pm", the values 3pm, John, and meet appear neither in the schema nor in any prior call, so ToolSpec offers nothing and the target model still has to write them out by hand.
The key observation: tool calls are committed in textual order, but their semantics do not have to be computed that way. The function choice and the argument slots are mutually independent and can be filled in parallel.
OoO-Spec (Out-of-Order) attaches a small sidecar model next to the target: Qwen3-0.6B with a single LoRA adapter, trained once on call traces produced by a Qwen2.5-32B teacher, then frozen. When a request arrives, the sidecar predicts the function index and every schema-defined argument slot in a single parallel vLLM batch (at most 32 tokens per slot). It joins the values into a structured object and renders it as plain JSON, Markdown, or XML (for Qwen3), producing a "semantic hint."
Meanwhile the target runs its own ToolSpec decoding loop as usual. At each candidate-construction boundary it makes a nonblocking readiness check; if the hint is ready, it re-tokenizes it with the target's own tokenizer and feeds it into the candidate pool as a draft. The design choice that matters: the sidecar only produces text and never touches the target's internal state, so the two share no model dimensions, token IDs, or hidden states. That is exactly why one sidecar serves Qwen2.5, Qwen3, and Llama targets with no per-target retraining, and it is what separates OoO-Spec from drafters like EAGLE that must read the target's internals. The target stays the sole verifier and committer: it checks greedily, accepts the longest matching prefix, and rejects the rest, so a wrong hint never corrupts the output.
Across seven targets and three benchmarks, all 21 cells, OoO-Spec is the fastest. Versus plain autoregressive decoding it reaches 2.46x to 5.34x speedup, an unweighted mean of 3.89x against 2.95x for ToolSpec.
| Target | OoO-Spec overall | ToolSpec overall |
| Qwen3-4B | 4.46x | 3.51x |
| Qwen3-8B | 4.73x | 3.61x |
| Qwen3-14B | 4.55x | 3.23x |
| Qwen3-32B | 4.75x | 3.46x |
With the same frozen sidecar, scaling the target from 4B to 32B beats ToolSpec by 27.1%, 31.0%, 40.9%, and 37.3%, averaging 34.1%. The relative gain grows with target size, because each verification step costs more for a larger model, so displacing one step saves more. Against released learned drafters (EAGLE-3, PARD-2, DFlash), OoO-Spec also leads in every comparable cell.
On latency, the target path takes 309.5 ms per request and the sidecar 85.0 ms, but they run concurrently, so end-to-end is only 2.4 ms above the target alone. 65.2% of hints are ready before the first candidate construction, 98.6% before the target finishes, and 94.6% are eventually used. The semantic payload averages just 85 bytes per request.
Almost every step an agent takes is a structured tool call, so tool calling is the cost bottleneck for agent inference. A speedup near 4x means roughly 4x as many agent steps per GPU-second.
The bigger engineering point is "one sidecar, every target." Learned drafters like EAGLE either need per-target training or access to the target's hidden states, which raises the deployment bar. OoO-Spec's sidecar exchanges only text, is 0.6B parameters, and is trained once and frozen, so adding a new target model requires no drafter retraining. The price it pays is decoupling when a hint is generated from when it is used: the sidecar can be a little slow, and as long as it finishes before some target candidate-construction boundary, the hint still helps.
The main engineering constraint is that it wants a separate GPU. When the ablation colocates sidecar and target on one card, overall speedup drops to 3.32x to 3.54x, only about 0.11x above ToolSpec, and Qwen3-32B cannot fit both models on a single 80GB card. The headline near-4x assumes you have a spare GPU for the sidecar.
The evaluation is also narrow. Every number comes from greedy decoding at batch size one. Real online serving almost always uses dynamic batching and sampling, and speculative methods often behave differently under batching, which the paper does not test. The sidecar is trained only on API-Bank and ToolAlpaca, with a Qwen2.5-32B teacher, so whether the hit rate holds for tool ecosystems with very different schemas is not directly shown. The authors themselves flag heterogeneous hardware, multi-target serving, and edge deployment as future work. Finally, this is a tool-calling-specific speedup, not a general decoding speedup.