CARTA: Composing Deep-Search Tasks with Relational Contracts

Training deep-search agents requires tasks whose web evidence jointly constrains the answer: clues chained through intermediate entities (depth), conditions converging on one entity (branching), and distinct paths closing a loop on the same entity pair (coupling). Longer chains need not add the latter two, so composition is a design variable, not a byproduct of length. Yet composition is not enough: in graph-based synthesis, realizing a graph as a question can silently drop a relation or break an identity binding while the answer stays valid, so checking the answer cannot establish whether structure was preserved.We introduce CARTA (Compositional Answer-Rooted Task Assembly), which treats relational structure as a checkable specification. Three operations (Extend, Branch, Couple) compose answer-rooted graphs; the resulting structure compiles into a Relational Contract of relation obligations and identity constraints, against which each realized question is audited, localizing violations for revision. With SFT alone and at matched example count, CARTA data trains stronger agents than recent synthesis corpora across benchmarks at two backbone scales. Further experimental analysis shows that mixing composition levels beats either single level, that contract-guided realization raises whole-query conformance from $72.9$ to $86.3$ and lifts downstream accuracy by $4.1$–$6.6$ points, and that selecting rollouts by contract score beats random selection among equally correct ones. Treating relational structure as something to specify and check, rather than to infer from answer correctness, turns structure into a supervision signal that trains measurably stronger agents.