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

CoCoDA is a novel framework that enables smaller language models to efficiently use large tool libraries by organizing tools as a compositional DAG structure with typed signatures and specifications. The system co-evolves the planner and tool library during training, allowing an 8B model to match or exceed a 32B model's performance on mathematical and coding benchmarks while maintaining sublinear retrieval costs.

CoCoDA addresses a fundamental scalability problem in tool-augmented AI systems: as tool libraries grow, retrieval becomes increasingly expensive and context budgets constrain performance. The framework introduces a compositional code DAG where tools are nodes with typed signatures, dependencies encoded as edges, and behavioral specifications stored at each node. This structure enables hierarchical tool composition rather than treating tools as flat resources, allowing the system to build increasingly complex capabilities from simpler primitives.

The innovation extends beyond architecture to training methodology. During inference, typed DAG retrieval uses symbolic signature unification to prune candidates before ranking by descriptions and filtering by behavioral specifications. This progressive narrowing keeps expensive context materialization focused on relevant candidates. During training, successful tool compositions are validated and integrated back into the library as composite tools, while a DAG-induced reward structure incentivizes the planner to use composites efficiently based on their primitive expansion size.

The results demonstrate substantial practical advantages: an 8B parameter model achieves parity with a 32B baseline on GSM8K and MATH benchmarks through more efficient tool use. Theoretical guarantees on retrieval cost reduction and monotone co-evolution under conservative updates provide confidence in the approach's scalability. For the broader AI industry, this suggests that intelligent tool organization and composition may be more valuable than simply scaling model size, with implications for efficient deployment of language models in production environments where context budgets and computational constraints remain binding.

• →CoCoDA organizes tools as a typed compositional DAG to reduce context costs and enable efficient hierarchical composition
• →An 8B model using CoCoDA matches or exceeds a 32B baseline on mathematical reasoning tasks through improved tool utilization
• →Typed DAG retrieval uses symbolic signature unification and behavioral specifications to progressively narrow candidate sets without full context materialization
• →Co-evolution mechanism validates successful tool compositions during training and credits them by primitive expansion size in reward shaping
• →Framework provides theoretical guarantees on sublinear retrieval time, compositional advantage, and DAG well-formedness under conservative updates