Fine-Grained Credit Assignment for Agent Architecture Search

We address the problem of agent architecture search, which constructs query-specific agent architectures from a set of candidate operators. Existing approaches optimize a controller using an architecture-level reward or advantage, assigning the same learning signal to all operator decisions within a sampled architecture, regardless of their individual contributions to the final outcome. Such coarse credit assignment can reinforce ineffective or redundant operator decisions. To address this, we present fine-grained credit assignment (FCA), which augments the architecture-level advantage with operation-level advantages for individual operator decisions. To this end, we propose state-conditioned relative advantage (SRA), which assigns operation-level rewards according to intermediate correctness and computational cost, and compares them under similar reasoning states, while placing larger weights on more similar states. We further introduce operator distribution projection (ODP), which maintains the diverse operator choices required for informative relative comparisons. Extensive experiments on diverse benchmarks using Qwen3-8B and GPT-4o-mini demonstrate the effectiveness and efficiency of FCA. We will release our code upon acceptance.