Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The paper introduces $\lambda_A$, a typed lambda calculus designed for formalizing the composition of LLM agents, incorporating features like oracle calls, bounded fixpoints for ReAct loops, probabilistic choice, and mutable environments. By proving type safety, termination of bounded fixpoints, and soundness of lint rules, the authors provide a principled foundation for agent configuration. Empirical evaluation on real-world agent configurations reveals that a significant portion (94.1%) are structurally incomplete under $\lambda_A$, highlighting the semantic entanglement between declarative configuration and imperative code.
A staggering 94% of real-world LLM agent configurations are structurally incomplete, revealing a deep semantic chasm between declarative configuration and imperative code.
Existing LLM agent frameworks lack formal semantics: there is no principled way to determine whether an agent configuration is well-formed or will terminate. We present $\lambda_A$, a typed lambda calculus for agent composition that extends the simply-typed lambda calculus with oracle calls, bounded fixpoints (the ReAct loop), probabilistic choice, and mutable environments. We prove type safety, termination of bounded fixpoints, and soundness of derived lint rules, with partial Coq mechanization (1,567 lines, 43 completed proofs). As a practical application, we derive a lint tool that detects structural configuration errors directly from the operational semantics. An evaluation on 835 real-world GitHub agent configurations shows that 94.1% are structurally incomplete under $\lambda_A$, with YAML-only lint precision at 54%, rising to 96--100% under joint YAML+Python AST analysis on 175 samples. This gap quantifies, for the first time, the degree of semantic entanglement between declarative configuration and imperative code in the agent ecosystem. We further show that five mainstream paradigms (LangGraph, CrewAI, AutoGen, OpenAI SDK, Dify) embed as typed $\lambda_A$ fragments, establishing $\lambda_A$ as a unifying calculus for LLM agent composition.