$λ_A$: A Typed Lambda Calculus for LLM Agent Composition

• URL: http://arxiv.org/abs/2604.11767v2
• Date: Tue, 14 Apr 2026 17:27:56 GMT
• Title: $λ_A$: A Typed Lambda Calculus for LLM Agent Composition
• Abstract summary: We present $_A$, a calculus for agent composition that extends the simply-typed calculus with oracle calls, bounded fixpoints, and mutable environments.<n>We derive a lint tool that detects structural configuration errors directly from the operational semantics.<n>We show that $_A$ embeds typed $_A$ fragments, establishing $_A$ as a unifying calculus for LLM agent composition.
• Score: 2.1900658889606097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $λ_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 full Coq mechanization (1,519 lines, 42 theorems, 0 Admitted). 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 $λ_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 $λ_A$ fragments, establishing $λ_A$ as a unifying calculus for LLM agent composition.

Related papers

• SemVerBench: Benchmarking LLM Comprehension of Version-Constraint Resolution Semantics [15.233613140316791]
  SemVerBench is the first benchmark of version-constraint resolution semantics across three ecosystems.<n>We evaluate six frontier models and find no statistically significant self-favoritism.<n>Because the task is verifiable and a free, 100%-correct resolver exists, tool delegation reaches 100%.
  arXiv  Detail & Related papers  (2026-09-10T07:34:44Z)
• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  We develop a query-independent 16-entry codebook that ranks the top decoded candidates in a single batched forward pass.<n>With no iterative search and no message passing at test time, Codebook Agent is the most accurate method on all six benchmarks.
  arXiv  Detail & Related papers  (2026-09-02T08:10:22Z)
• Code2UML: Agentic LLMs with context engineering for scalable software visualization [7.069738194755401]
  This paper introduces an agentic architecture with context engineering for automated diagram generation from source code repositories.<n>It employs a hierarchy of five specialized agents: PlannerAgent, Analyzer DiagramAgent, CorrectorAgent and DependencyAnalyzerAgent, built on the Claude Agent SDK.<n>A deterministic, importance-weighted IR compaction layer transforms full project IRs into diagram-specific views guaranteed to fit within token constraints.
  arXiv  Detail & Related papers  (2026-05-23T08:01:26Z)
• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• A Preliminary Agentic Framework for Matrix Deflation [2.6140509675507384]
  We propose an agentic approach to matrix deflation in which a solver generates rank-1 updates and decides when to stop.<n>We evaluate on Digits ($8times8$), CIFAR-10 ($32times32$ grayscale), and synthetic ($16times16$) matrices with and without Gaussian noise.<n>Across all settings, our agent achieves competitive results, suggesting that fully agentic, threshold-free deflation is a viable alternative to classical numerical algorithms.
  arXiv  Detail & Related papers  (2026-01-06T23:59:18Z)
• LLM-Guided Probabilistic Fusion for Label-Efficient Document Layout Analysis [6.908972852063454]
  Document layout understanding remains data-intensive despite advances in semi-supervised learning.<n>We present a framework that enhances semi-supervised detection by fusing visual predictions with structural priors.<n>Our method demonstrates consistent gains across model scales.
  arXiv  Detail & Related papers  (2025-11-12T02:25:58Z)
• Co-Designing Quantum Codes with Transversal Diagonal Gates via Multi-Agent Systems [1.5948632947109136]
  We present a multi-agent, human-in-the-loop workflow that co-designs quantum codes with prescribed diagonal gates.<n>The workflow is powered by GPT-5 and implemented within RA (https://texra.ai)-a multi-agent research assistant platform.
  arXiv  Detail & Related papers  (2025-10-23T16:45:39Z)
• $\texttt{SEM-CTRL}$: Semantically Controlled Decoding [53.86639808659575]
  $texttSEM-CTRL$ is a unified approach that enforces rich context-sensitive constraints and task- and instance-specific semantics directly on an LLM decoder.<n>texttSEM-CTRL$ allows small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models.
  arXiv  Detail & Related papers  (2025-03-03T18:33:46Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  We introduce EquiBench, a new benchmark for evaluating large language models (LLMs)<n>This task directly tests a model's ability to reason about program semantics.<n>We evaluate 19 state-of-the-art LLMs and find that in the most challenging categories, the best accuracies are 63.8% and 76.2%, only modestly above the 50% random baseline.
  arXiv  Detail & Related papers  (2025-02-18T02:54:25Z)
• Semantic Operators: A Declarative Model for Rich, AI-based Data Processing [27.294714926492187]
  We introduce semantic operators, the first formalism for declarative and general-purpose AI-based transformations.<n>We propose several novel optimizations to accelerate semantic filtering, joining, group-by and top-k operations by up to $1,000times$.<n>We show that the semantic operator model is expressive, capturing state-of-the-art AI pipelines in a few operator calls.
  arXiv  Detail & Related papers  (2024-07-16T06:19:14Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
  Markov Games (MG) is an important model for Multi-Agent Reinforcement Learning (MARL) This paper first refines the AVLPR framework by Wang et al. (2023), with an insight of designing pessimistic estimation of the sub-optimality gap. We give the first algorithm that tackles the curse of multi-agents, attains the optimal $O(T-1/2) convergence rate, and avoids $textpoly(A_max)$ dependency simultaneously.
  arXiv  Detail & Related papers  (2024-02-11T01:51:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.