Abstract

Current research on the \textit{Decompose-Then-Verify} paradigm forevaluating the factuality of long-form text typically treats decomposition andverification in isolation, overlooking their interactions and potentialmisalignment. We find that existing decomposition policies, typicallyhand-crafted demonstrations, do not align well with downstream verifiers interms of atomicity -- a novel metric quantifying information density -- leadingto suboptimal verification results. We formulate finding the optimaldecomposition policy for optimal verification as a bilevel optimizationproblem. To approximate a solution for this strongly NP-hard problem, wepropose dynamic decomposition, a reinforcement learning framework thatleverages verifier feedback to learn a policy for dynamically decomposingclaims to verifier-preferred atomicity. Experimental results show that dynamicdecomposition outperforms existing decomposition policies, improvingverification confidence by 0.07 and accuracy by 0.12 (on a 0-1 scale) onaverage across varying verifiers, datasets, and atomcities of input claims.