CoCoDA: Co-evolving Compositional DAG for Tool-Augmented Agents

Ziyang Yu 1 Qiyue Li 2 Liang Zhao 1 1 Emory University 2 Beijing Normal-Hong Kong Baptist University · 2026

Read CoCoDA: Co-evolving Compositional DAG for Tool-Augmented Agents by Ziyang Yu 1 Qiyue Li 2 Liang Zhao 1 1 Emory University 2 Beijing Normal-Hong Kong Baptist University (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-08399.txt.

Introduction

Ziyang Yu, Qiyue Li, and Liang Zhao let a tool library and its planner grow up together. Tool-augmented small models gain skills from external code, but as the library grows, retrieval eats the context budget and flat text indexes hide the typed, compositional shape of real code.

CoCoDA stores everything in one compositional code graph: tools are nodes with typed signatures, descriptions, preconditions, and worked examples, and edges record which tools call which. Planner and library co-evolve through that shared structure as new reusable subroutines appear. At run time, typed retrieval prunes candidates by signature matching, so the planner searches a big library without paying a growing prompt tax.

Catalog record

CREATORZiyang Yu 1 Qiyue Li 2 Liang Zhao 1 1 Emory University 2 Beijing Normal-Hong Kong Baptist University
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.08399

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CoCoDA: Co-evolving Compositional DAG for Tool-Augmented Agents Ziyang Yu 1 Qiyue Li 2 Liang Zhao 1 1 Emory University 2 Beijing Normal-Hong Kong Baptist University Abstract Tool-augmented language models can extend small language models with external executable skills, but scaling the tool library creates a coupled challenge: the library must evolve with the planner as new reusable subroutines emerge, while retrieval from the growing library must remain within a fixed context budget. Existing tool-use and skill-library methods typically treat tools as flat or text-indexed memories, causing prompt cost to grow with library size and obscuring the typed, compositional structure of executable code. We propose CoCoDA, a framework that co-evolves the planner and tool library through a single code-native structure: a compositional code DAG. Nodes are primitive or composite tools, edges encode invocation dependencies, and each node stores a typed signature, description, pre/post-condition specification, and worked examples. At inference time, Typed DAG Retrieval prunes candidates by symbolic signature unification, ranks survivors by descriptions, filters them by behavioral specifications, and disambiguates with examples, keeping expensive context materialization on progressively smaller candidate sets. At training time, successful trajectories are folded into validated composite tools, while the planner is updated with a DAG-induced reward that credits composites by their primitive expansion size. We provide theoretical results showing retrieval cost reduction, sublinear retrieval time, compositional advantage under the shaped reward, monotone co-evolution under conservative updates, and DAG well-formedness. Across mathematical reasoning, tabular analysis, and code task benchmarks, CoCoDA enables an 8B student to match or exceed a 32B teacher on GSM8K and MATH and consistently improves over strong tool-use and library-learning baselines. 1 Introduction Tool-augmented language models extend a planner with external executable tools, allowing even small language models to offload computation, symbolic manipulation, and long-horizon procedures to a reusable library. This division of labor is especially attractive for small language models, whose context windows and parametric capacity are limited. In principle, a sufficiently rich tool library can act as an external procedural memory: the planner retrieves a small set of relevant tools, invokes them through an executor, and composes their outputs into a final answer. However, scaling such a library creates a tension. On one hand, the library must evolve with the planner. As the planner explores new tasks, it discovers recurring sub-trajectories that should be abstracted into reusable tools; otherwise, the planner repeatedly reconstructs the same primitive computations. On the other hand, every newly added tool increases the retrieval burden. A flat library makes the planner’s prompt cost grow with the number of tools, eventually exhausting the context budget before the library becomes useful. Thus, tool-library learning for small language models requires solving two coupled problems: how to grow the library with the policy, and how to retrieve from the growing library under a fixed context window. Existing approaches address only parts of this problem. Static tool-use systems assume a fixed inventory and train or prompt the model to call tools from that inventory. Skill-library and agent-memory methods append new skills during exploration, but typically store them as flat text records or natural-language memories, so retrieval cost grows with library size and the internal dependency structure of executable code remains hidden. Hierarchical memory and RAG methods reduce context cost by clustering summaries, but their hierarchies are induced by topical similarity rather than by executable composition. Conversely, code-library learning and program-synthesis methods exploit compositional structure, but they are not designed for LLM planners operating under token-budgeted retrieval. The missing mechanism is a structure that is simultaneously code-aware, retrieval-efficient, and learnable online. Our key observation is that executable tools contain structure that text memories do not. A tool has a typed signature, executable dependencies, behavioral specifications, and concrete input-output examples. These signals can be used not only to organize the library, but also to decide which records must be exposed to the planner. We therefore represent the library as a compositional code DAG. Nodes are primitive or composite tools, edges are invocation dependencies extracted from executable bodies, and each node stores a four-level record: typed signature, description, pre/post-condition specification, and worked examples. This DAG is the single object through which CoCoDA couples library growth and context-bounded retrieval. At inference time, CoCoDA performs Typed DAG Retrieval. Given a query-induced subgoal, retrieval first prunes candidates by symbolic signature unification, then ranks the survivors by descriptions, filters them by pre/post-condition compatibility, and finally uses examples for disambiguation. Because expensive LLM-billed records are materialized only for surviving candidates, the retrieval cost contracts across stages rather than scaling with the full library. Because the hierarchy follows invocation dependencies rather than text similarity, retrieval can surface a composite tool that behaviorally subsumes a primitive sub-trajectory. At training time, CoCoDA co-evolves the planner and the library. Successful trajectories are passed to a fixed teacher abstractor, which proposes composite tools. A proposal is committed only if it preserves acyclicity and satisfies dependency and specification checks. The planner is updated with a DAG-induced reward that credits tools by their primitive expansion size: invoking a composite that represents multiple primitive calls receives positive saved-call credit, while invoking a primitive receives none. Thus, among behavior-equivalent trajectories with the same verified outcome, the planner is encouraged to use reusable composites. The same DAG therefore plays two roles: it keeps retrieval within the context budget and defines the structural signal that trains the planner to exploit newly learned abstractions. We make the following contributions. First, we formulate tool-library learning for small language models as a joint planner-library optimization problem with explicit retrieval-cost and context-window constraints. Second, we propose Typed DAG Retrieval, a code-native retrieval cascade that uses signatures, invocation edges, specifications, and examples to keep prompt cost sublinear in library size. Third, we introduce an online co-evolution procedure that inserts validated composite tools and trains the planner with a DAG-induced saved-call reward. Fourth, we provide theoretical results showing retrieval cost reduction, sublinear retrieval time, compositional advantage under the shaped reward, monotone co-evolution under conservative updates, and DAG well-formedness. Finally, across mathematical reasoning, tabular analysis, and code task benchmarks, CoCoDA enables an 8B student to match or exceed a 32B teacher on GSM8K and MATH and consistently improves over strong tool-use and library-learning baselines. 2 Related Works 2.1 Tool-Augmented Language Models Toolformer ( 24 ) teaches an LLM to self-annotate API calls and interleave them with generation, while ReAct ( 35 ) threads reasoning traces with tool invocations at inference time. ToolLLM ( 22 ) , Gorilla ( 18 ) , and AnyTool ( 7 ) scale tool use to thousands of real-world APIs through instruction tuning and hierarchical API retrieval. ToolAlpaca ( 29 ) and Gorilla ( 18 ) distill tool-use trajectories from a stronger teacher into smaller planners. RLTF ( 12 ) , ToRL ( 11 ) , and ToolRL ( 20 ) train LLMs end-to-end with outcome rewards from execution feedback, and ReTool ( 9 ) and ARTIST ( 27 ) extend the recipe to multi-turn agentic settings on top of GRPO ( 25 ; 6 ) . Across these works, the tool inventory is treated as a static, flat text-indexed resource that the policy optimizes against rather than reshapes, leaving both co-evolution and the per-prompt scaling of retrieval cost unaddressed. 2.2 Skill Library Learning and

Read the complete text