CoCoDA: Co-evolving Compositional DAG for Tool-Augmented Agents
Authors: Ziyang Yu, Qiyue Li, Liang Zhao
Summary
CoCoDA organizes tool-augmented LLM agents using a compositional code DAG (directed acyclic graph) where nodes are primitive or composite tools and edges show invocation dependencies. At inference, it retrieves tools by progressively filtering: first by type signatures, then descriptions, then behavioral specs, then examples—keeping expensive context materialization for only the smallest candidate sets. During training, successful action sequences become new composite tools, and the planner gets credit proportional to how many primitives each composite saves. Results show an 8B model matching a 32B teacher on math benchmarks.
Main takeaways:
- Organizes tools in a typed DAG rather than flat text-indexed memory, exploiting compositional structure
- Retrieval uses a funnel: type-check → semantic rank → spec filter → example disambiguate, progressively shrinking candidates
- Successful trajectories are "folded" into new composite tools; planner reward credits composites by primitive count saved
- Theoretical guarantees: sublinear retrieval cost, monotone improvement under conservative updates, DAG stays well-formed
- 8B student matches 32B teacher on GSM8K and MATH; consistent gains across benchmarks
Relevance
Not directly related to my persona/behavioral installation work. This is about structuring and retrieving reusable code tools for agentic task-solving, which is orthogonal to how personas get installed or leak across contexts. Included because it's a clever approach to scaling tool libraries, but no obvious connection to marker implantation or persona geometry.
Threat model
Potential threat/caveat for clean result "Random obscure Latin 3-grams don't leak Gaperon-1125-1B's hidden pretraining trigger; leakage seen on famous Latin phrases at ~10% doesn't extend to the obscure-vocab neighborhood (MODERATE confidence)": this item discusses benchmark.
Abstract
arXiv:2605.08399v1 Announce Type: new 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.