Symbolic Constraint Agents: Mining Tool-Call Constraints from Documentation and Traces

Symbolic constraints, which are programmatic, deterministic checks for tool calls, are commonly framed as a measure for enforcing safety policies on tool-calling agents. However, previous approaches limit their scope to environments with an explicit policy, and have not been shown to improve end-to-end task performance. Hence, we explore what symbolic constraints can be mined from environments without an explicit policy, and whether they can improve agent performance in complex environments. We present Symbolic Constraint Agents (SCA), a framework that mines symbolic constraints from API documentation, refines them against execution traces, and checks the agent's tool calls with an SMT solver at runtime. A violation can trigger either a natural-language warning by default, or an automatic repair when the valid replacement is uniquely determined. On AppWorld, this refinement step raises error-detection F1 from 37.0 to 58.3 on GPT-5.5 traces and from 39.3 to 61.9 on Qwen3.5-27B traces. Symbolic guidance then improves task completion for three models, up to a 4.92pp gain on GPT-5.4-mini. These results show that automatically mined symbolic constraints can improve task completion in large, stateful tool environments.