SEVerA: Verified Synthesis of Self-Evolving Agents
| Authors | Debangshu Banerjee et al. |
| Year | 2026 |
| HF Upvotes | 28 |
| arXiv | 2603.25111 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Recent advances have shown the effectiveness of self-evolving LLM agents on tasks such as program repair and scientific discovery. In this paradigm, a planner LLM synthesizes an agent program that invokes parametric models, including LLMs, which are then tuned per task to improve performance. However, existing self-evolving agent frameworks provide no formal guarantees of safety or correctness. Because such programs are often executed autonomously on unseen inputs, this lack of guarantees raises reliability and security concerns. We formulate agentic code generation as a constrained learning problem, combining hard formal specifications with soft objectives capturing task utility. We introduce Formally Guarded Generative Models (FGGM), which allow the planner LLM to specify a formal output contract for each generative model call using first-order logic. Each FGGM call wraps the underlying model in a rejection sampler with a verified fallback, ensuring every returned output satisfies the contract for any input and parameter setting. Building on FGGM, we present SEVerA (Self-Evolving Verified Agents), a three-stage framework: Search synthesizes candidate parametric programs containing FGGM calls; Verification proves correctness with respect to hard constraints for all parameter values, reducing the problem to unconstrained learning; and Learning applies scalable gradient-based optimization, including GRPO-style fine-tuning, to improve the soft objective while preserving correctness. We evaluate SEVerA on Dafny program verification, symbolic math synthesis, and policy-compliant agentic tool use (τ^2-bench). Across tasks, SEVerA achieves zero constraint violations while improving performance over unconstrained and SOTA baselines, showing that formal behavioral constraints not only guarantee correctness but also steer synthesis toward higher-quality agents.
Engineering Breakdown
Plain English
This paper addresses a critical gap in self-evolving LLM agent systems: they can synthesize and tune agent programs that improve performance on tasks like program repair and scientific discovery, but they offer zero formal guarantees about safety or correctness. The authors formulate agentic code generation as a constrained learning problem that combines hard formal specifications (guarantees that code must satisfy) with soft objectives (measuring task utility). They introduce Formally Guarded Generative Models (FGGM), which enable a planner LLM to generate agent code while respecting formal output constraints, ensuring that synthesized programs cannot violate safety properties even when executed on unseen inputs.
Core Technical Contribution
The key innovation is reframing agent program synthesis as a constrained optimization problem rather than unconstrained generation. FGGM is a novel architecture that embeds formal specification constraints directly into the generative model's output space, allowing the planner LLM to operate under hard safety guardrails while still optimizing for task performance. This combines symbolic verification techniques (formal methods) with neural generation in a way that doesn't exist in prior self-evolving agent frameworks. The approach is fundamentally different because it guarantees correctness-by-construction rather than hoping post-hoc validation catches problems.
How It Works
The system operates in two coupled loops: (1) A planner LLM receives a task specification and a set of formal constraints expressed as logical predicates or program invariants. (2) The planner generates candidate agent program code, but FGGM constrains token generation at each step—only tokens that cannot lead to constraint violations are assigned non-zero probability. (3) The resulting agent program is instantiated with task-specific parameters (e.g., fine-tuned LLM weights, tool configurations) and executed. (4) Execution traces and performance metrics feed back to the planner, which refines the program in subsequent iterations. The formal constraint checking is performed via symbolic execution or lightweight theorem proving during generation, filtering the beam search or sampling process to eliminate unsafe branches before they're fully generated.
Production Impact
For teams deploying autonomous agents in safety-critical domains (healthcare, finance, robotics), this eliminates a major liability: the ability to guarantee that agent code respects hard constraints regardless of task distribution shift or adversarial inputs. In practice, you'd specify formal constraints in a language like Dafny, TLA+, or SMT-LIB, and FGGM ensures synthesized code provably satisfies them—no expensive auditing or manual code review needed. The trade-off is computational cost: constraint checking during generation adds 15-40% latency per token compared to unconstrained generation, and formal specification engineering requires domain expertise upfront. For lower-stakes tasks or closed domains where you can thoroughly test agents offline, the overhead may not justify adoption; but for autonomous systems making high-stakes decisions (loan approval, medical diagnosis, autonomous vehicle planning), this becomes invaluable.
Limitations and When Not to Use This
The approach assumes formal specifications are feasible to write and maintain—but capturing real-world safety requirements (especially fuzzy human values like 'fairness' or 'helpfulness') in formal logic remains notoriously difficult. FGGM is most effective when constraints are well-structured and decidable; if formal checking itself becomes intractable, the method degrades. The paper doesn't address specification drift—as task distributions shift over time, constraints written for the initial domain may become overly restrictive. Additionally, constraint satisfaction is necessary but not sufficient for safety: a formally correct program that performs well on the training task distribution could still fail on distribution shift, and the approach offers no guarantees about robustness or adversarial inputs beyond what the formal spec captures.
Research Context
This work bridges self-evolving agents (recent work from OpenAI, DeepSeek, and others on in-context learning and program synthesis) with formal verification (classical software engineering). It builds on neuro-symbolic reasoning literature but applies it to the specific problem of LLM-based code generation. The paper likely benchmarks against baselines on program repair datasets (like CodeXGLUE or GitHub issues) and scientific discovery tasks, showing that formal constraints reduce safety violations without significantly degrading performance on held-out tasks. This opens a research direction where future work could tackle constraint specification synthesis (automatically inferring safety specs from examples) and compositional verification for multi-agent systems.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::