Text-Enhanced Mask Probability Optimization for Long-Horizon Span-to-Span Attribution

Auditing language models that answer from text far earlier in the sequence requires tracing a generated span to the earlier text it depends on, which may lie in a long prompt or in the response itself, far from the span being explained. We formulate this as long-horizon span-to-span attribution: the effect of intervening on selected source spans on a fixed later target span, with all other recorded text held unchanged. Propagation-based methods score sources from internal computation and need differentiable or architecture-specific access, while perturbation-based methods measure the target directly but face a combinatorial search whose cost grows with the source. We propose TEMPO (Text-Enhanced Mask Probability Optimization), a black-box method that optimizes a probabilistic mask over source units against the target's likelihood under sampled interventions and decodes the result into a complete ranking across deletion budgets. The decoder uses word and clause structure together with the learned mask probabilities, preserves the best searched set at the search budget, and issues no further model queries, so the number of forward passes is fixed regardless of input length or source–target distance. On four task families spanning retrieval, multi-hop reasoning, mathematical continuation with injected errors and counterfactual multiple choice, TEMPO attains the highest deletion AUC on every task and leads all macro-average faithfulness metrics against seven baselines, at lower cost than the strongest of them. The experiments also show that faithfulness and recovery of annotated evidence diverge: the recall leader changes by task, and a query-matching variant of our pipeline raises reference recall while lowering deletion AUC, indicating that behavioral dependence and annotation agreement must be evaluated separately.