🤖 machine learning

Barriers to Counterfactual Credit Attribution for Autoregressive Models

This paper investigates the challenges of implementing counterfactual credit attribution (CCA) in autoregressive generative models, demonstrating that CCA fails to compose autoregressively and that retrofitting existing models to satisfy CCA requires query complexity exponential in the output length.

Original authors: Aloni Cohen, Chenhao Zhang

Published 2026-05-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Aloni Cohen, Chenhao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef who just invented a delicious new soup. In the old days, if you used a secret spice from a specific farmer, you would naturally say, "This soup tastes great because of Farmer John's spice." You give credit where it's due.

But now, imagine you have a magical "Soup Bot." You feed it a list of ingredients (a database), and it whips up a soup. The problem is, the Bot is a black box. It mixes everything so thoroughly that you can't tell which specific ingredient made the soup taste the way it does. If you can't tell what influenced the soup, you can't give credit to the farmers. This paper argues that we need a way to force the Bot to say, "I used Farmer John's spice," whenever that spice was actually essential to the recipe.

The authors call this "Counterfactual Credit Attribution" (CCA). It's a fancy way of saying: "If we took Farmer John's spice out of the list, would the soup still taste the same?" If the answer is "No, it would taste different," then the Bot must give credit to Farmer John.

The paper explores two natural ways to build this "Credit-Giving Bot" and finds that both hit a massive wall.

1. The "Step-by-Step" Approach (Autoregressive Models)

Most modern AI (like the one writing this summary) works like a person writing a story one word at a time. It picks a word, then the next, then the next.

The Idea: Maybe we can just teach the Bot to give credit for each individual word it picks. If it picks a word that depends on Farmer John's spice, it credits him. Then, we just string all those words together to make the full soup.

The Problem: The paper proves this doesn't work.

The Analogy: Imagine you are building a tower out of blocks. You have a rule: "Every time you place a block, you must check if it's stable." You follow this rule perfectly for every single block. But when you step back, the whole tower collapses.
The Reality: The authors show that even if the Bot is perfect at giving credit for every single word it generates, the final story (the whole sequence) might still fail to give credit properly. The "credit" gets lost or distorted as the words pile up. It's like trying to build a stable house by only checking the stability of individual bricks; the structure as a whole might still fall apart.

2. The "Retrofit" Approach (Adding Credit Later)

The Idea: What if we already have a Bot that is great at making soup but terrible at giving credit? Can we just put a "wrapper" around it? This wrapper would watch the Bot make soup and, after the fact, decide, "Okay, I'm going to add a note saying 'Credit: Farmer John'."

The Problem: The paper proves this is computationally impossible (or at least, so hard it might as well be impossible).

The Analogy: Imagine you have a locked safe that generates a random 100-digit code. You want to add a label to the safe that says, "This code was influenced by the number 7." To do this, you have to peek inside the safe to see if the number 7 was actually used.
The Reality: The authors show that to figure out if the Bot really needed a specific piece of data (like Farmer John's spice) to generate its output, you would have to ask the Bot to generate the soup trillions upon trillions of times (exponentially many queries) to be sure. It's like trying to find a single specific grain of sand on a beach by digging up every single grain one by one. Even if you just want a "good enough" guess, the math says you still have to dig up almost the whole beach.

The Big Takeaway

The paper concludes that we currently have a major roadblock.

We can't just build credit-giving AI by making it credit-giving at every tiny step (word-by-word).
We can't easily fix existing AI by tacking on a credit-giving layer later without doing an impossible amount of work.

The authors also point out a weird side effect: To satisfy the strict rules of this "Credit System," the Bot might be forced to give credit to ingredients that barely changed the soup at all. It's like being forced to thank a farmer for a single grain of salt that didn't actually change the taste, just because the math says you might have needed it.

In short: Making AI that reliably and efficiently gives credit to its sources is much harder than we thought, and the two most obvious solutions don't work.

Technical Summary: Barriers to Counterfactual Credit Attribution for Autoregressive Models

Problem Statement

Generative AI obscures the link between inputs and outputs, complicating the practice of giving credit to prior work. While Counterfactual Credit Attribution (CCA) was recently introduced by Livni et al. [2024] as a technical condition for learning algorithms (a relaxation of differential privacy requiring stability with respect to non-credited inputs), its application to generative models remains unexplored.

This paper initiates the study of CCA for autoregressive language models. Specifically, it addresses the challenge of attributing credit to a deployment-time dataset (e.g., a RAG database or in-context learning examples) rather than the training dataset. The goal is to design models that output both a generated sequence and a credit set $C \subseteq S$ , satisfying the CCA condition: if a document $s_i$ is not credited, the output distribution should be indistinguishable from the distribution where $s_i$ was excluded from the input.

Methodology

The authors investigate two natural approaches to constructing CCA-compliant autoregressive models:

Autoregressive Composition: Designing a CCA-compliant next-token predictor and rolling it out to generate sequences, aggregating the credit sets of individual tokens.
Retrofitting: Taking an existing non-crediting model and wrapping it with an algorithm that adds a credit set to its outputs while preserving the original generation distribution.

The paper employs theoretical analysis, including counterexamples, lower bound proofs, and oracle complexity arguments, to evaluate the feasibility of these approaches.

Key Contributions and Results

1. Non-Composition of Autoregressive CCA

The first major result challenges the standard approach used for Differential Privacy (DP) in LLMs, where a private next-token predictor is composed autoregressively to guarantee end-to-end privacy.

Finding: CCA does not compose autoregressively.
Theorem 4.2: The authors construct a counterexample showing that for any $\epsilon \ge 0$ and $\delta < 1$ , there exists a next-token predictor $\tilde{M}$ that satisfies the strictest $(0,0)$ -CCA condition, yet its autoregressive rollout $G_{\tilde{M}}$ fails to satisfy $(\epsilon, \delta)$ -CCA.
Theorem 4.3: A general lower bound is proven for the CCA parameter $\epsilon'$ of a rollout generated by an $\epsilon$ -CCA predictor. Counterintuitively, as the base predictor's $\epsilon$ approaches 0 (becoming "better" at attribution), the lower bound on the rollout's $\epsilon'$ can increase, making the composition guarantee weaker. This contrasts sharply with DP, where composition is well-understood and manageable.

2. Infeasibility of CCA Retrofitting

The second approach, retrofitting, involves adding a credit attribution layer to a pre-existing model via black-box access.

Finding: CCA retrofitting is computationally infeasible in the worst case.
Theorem 5.5: The authors prove that any algorithm attempting to retrofit a model to be $(\epsilon, 0)$ -CCA (with $\delta=0$ ) and credit-optimal (minimizing the expected number of credited items) requires exponentially many queries to the base model in terms of the output length $\ell$ .
Hardness Construction: They construct a family of models $\{M_z\}$ indexed by a hidden string $z \in \{0,1\}^\ell$ . To satisfy CCA, the retrofitting algorithm must effectively identify $z$ . While finding $z$ from the base model requires $\Omega(2^\ell)$ queries, finding $z$ from an optimal CCA augmentation requires only polynomial queries. This gap implies that any black-box retrofitting algorithm must make exponential queries to the base model to achieve the necessary approximation.
Vanishing Impact Paradox: The analysis reveals a conceptual issue: the constructed models are functionally indistinguishable with respect to the input document (total variation distance vanishes as $2^{-\ell}$ ), yet the optimal CCA augmentation is required to credit the document with a constant probability $\gamma > 0$ . This suggests that strict CCA definitions may force attribution for inputs with negligible impact.

Significance and Claims

The paper claims to be the first to formally study CCA in the context of generative autoregressive models. Its primary significance lies in identifying fundamental barriers to two intuitive strategies for implementing credit attribution:

Decoupling from DP: Unlike Differential Privacy, CCA does not compose under autoregressive generation. This implies that simply training a "credit-attributing" next-token predictor is insufficient to guarantee CCA for the full generated text.
Computational Limits: Retrofitting existing models to satisfy CCA is computationally prohibitive (exponential query complexity) under standard black-box assumptions and strict optimality requirements.

The authors conclude that these results highlight the difficulty of formalizing credit attribution for generative AI. They suggest that relaxing the definition (e.g., allowing $\delta > 0$ or relaxing the requirement that the augmented model exactly preserve the original output distribution) may be necessary to achieve feasible solutions, though such relaxations are left for future work. The paper does not propose new algorithms or experimental validations but rather delineates the theoretical limits of the current CCA framework when applied to autoregressive generation.