acceptodds
Under review as a conference paper at ICLR 2027

In-Context Credit Assignment via the Core

Abstract

We propose incentive-aligned mechanisms for in-context credit assignment: the task of assigning credit for AI-generated content among creators whose intellectual property appears in the context window. Our approach is based on the least core solution concept from cooperative game theory, which distributes value in a way that is as stable as possible by ensuring that no subset of creators is significantly under-compensated relative to the value they could generate on their own. We develop algorithms for approximating the least core, which leverage novel routines for constraint seeding and constraint separation. On a web retrieval credit assignment task, we find that our approaches approximate the least core using an order of magnitude fewer LLM calls compared to alternative methods.

Primary area:
learning theory
Keywords:
game theory, credit assignment, the least core, incentives

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_HNVYOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies credit assignment for AI-generated content that uses multiple creators’ or webpages’ content in context. It models the problem as a coalitional game with an unknown ground-truth value function vv and an estimated value function v^\hat v, and uses the least core as the allocation concept to minimize the largest coalition under-compensation. The paper derives a sensitivity bound based on balanced distributions over coalitions, proposes joint LP/QP constraint-generation algorithms with sampling-based and LLM-based separation oracles, and discusses minimal winning coalition seeding for binary value functions. The experiments use LLM-based binary question-answering evaluations on BrowseComp-Plus and a synthetic web-retrieval dataset, comparing random sampling, constraint generation, LLM seeding, LLM separation, and zero-shot allocations. The authors report that constraint generation can achieve comparable holdout deficit to the Yan--Procaccia sampling baseline with fewer value-function queries, while LLM-based variants are faster but may produce sparser and less stable allocations.

Critical strengths
  1. The problem formulation is timely and potentially important. Modeling context attribution as a cooperative game gives a clear incentive-oriented interpretation of credit assignment. The least core is a meaningful alternative to purely marginal or interpretability-oriented attribution because it explicitly considers whether coalitions are under-compensated.
  2. The algorithmic framework is modular and potentially useful. The constraint-generation formulation separates the optimization problem from the coalition-search oracle, allowing random, domain-specific, or LLM-based separation procedures. The paper also explores the tradeoff between faster LLM-guided search and broader egalitarian allocations across multiple experimental variants.
Critical weaknesses
  1. The central theoretical claims are not sound as written. Example 3.3 is inconsistent with its own definition: the displayed conjunction implies that v^(S)=1\hat v(S)=1 only for S=NS=N, which gives ϵ^=0\hat\epsilon=0, not 1/21/2. The claimed counterexample appears to require a disjunction instead, together with a different disagreement-set expression. More substantially, Theorem 3.1 appears to use a dual characterization that ignores the primal nonnegativity constraints on uu. Proposition B.1 lacks a monotonicity assumption on v^\hat v, so the proposed marginal allocation can be negative. Corollary C.1 also appears to promote a δ\delta-probable sampled-feasibility guarantee to an exact global ℓ2\ell_2-optimality statement. These issues affect the theoretical foundation of the paper rather than being minor presentation errors.
  2. The empirical evidence does not establish the claimed least-core approximation or query-efficiency advantage. For n=32n=32, the evaluation uses only 212 uniformly sampled holdout coalitions and a 99th percentile, even though the least core is defined by the worst coalition over 2322^{32} possibilities. The Yan--Procaccia baseline is itself a random-sampling approximation, so matching it does not demonstrate closeness to the true least core. The supplementary package contains 69 synthetic instances with 34--42 documents per row, while the paper reports n∈{10,32}n\in\{10,32\} and 32 instances per dataset, without a split or run manifest. The released prompts expose the Gold Answer to the LLM-based initializer, oracle, and zero-shot methods, which would create label leakage if those prompts were used literally. The call-count accounting, model randomness, and cross-model robustness are also not sufficiently specified.
Questions for authors

Clarifications that materially affect the assessment

  1. Is the conjunction in Example 3.3 a typographical error for a disjunction? Under the formula currently printed, v^(S)=1\hat v(S)=1 only for S=NS=N, so ϵ^=0\hat\epsilon=0. Please provide the corrected statement and proof.
  2. Can the authors provide a complete dual derivation for Theorem 3.1 that explicitly accounts for ui≥0u_i\ge 0? In particular, why should all coalition inclusion loads be equal rather than bounded by a common dual variable? Does the claimed bound still hold for arbitrary normalized value functions v,v^:2N→[0,1]v,\hat v:2^N\to[0,1]?
  3. Were the Gold Answers actually passed to the LLM-based initializer, separation oracle, and zero-shot allocation prompts? If yes, why is this information available to the algorithm and how is the comparison with the random baseline fair? If no, please provide the exact prompts used in the experiments.
  4. What is the exact mapping from the 69 synthetic records in the supplementary package to the reported n=10n=10 and n=32n=32 experiments and the claimed 32 instances per dataset? Please provide the filtering, splitting, and run manifest.
  5. Please report whether each coalition evaluation is deterministic or cached, the model version, temperature, seed, retry behavior, and whether the full-document and empty-document coalitions are explicitly forced to satisfy v^(N)=1\hat v(N)=1 and v^(∅)=0\hat v(\varnothing)=0. Also report monotonicity violations of the independently evaluated binary v^\hat v.
  6. How are all LLM calls counted? Please clarify whether the reported counts include answer-generation calls, grading calls, initializer calls, LLM-oracle proposal calls, and zero-shot calls, and provide a complete quality-versus-cost table.
3 comments

Thank you for your detailed review. We want to emphasize that we’ve fixed all mathematical issues with the main theoretical results. The main message of our paper and the takeaways from the theory have not changed.

Example 3.3 is inconsistent with its own definition: the displayed conjunction implies that (\hat v(S)=1) only for (S=N), which gives (\hat\epsilon=0), not (1/2). The claimed counterexample appears to require a disjunction instead, together with a different disagreement-set expression.

This was a typo, as the conjunction indeed should be a disjunction. We’ve fixed this. We’ve also fixed the issue with the disagreement condition. It should read: the value functions disagree if and only if S=B∪TS = B\cup T for T a proper subset of A. The fraction of (nonempty) coalitions on which the value functions disagree is exponentially small: it is (2n/2−1)/(2n−1)=1/(2n/2+1)(2^{n/2} - 1) / (2^n - 1) = 1 / (2^{n/2} + 1). And, the least core deficits (with the above fixes) are 1/21 / 2 and 00, respectively. So, the fixed example conveys the point we wanted to get across here.

Theorem 3.1 appears to use a dual characterization that ignores the primal nonnegativity constraints on (u).

Indeed the dual we wrote down was incorrect as your counterexample shows. We have included a fix: the statement of Theorem 3.1 holds under the assumption that the coalitional value functions are monotone (that is, additional creators do not hurt coalitional value). To argue this, we analyze the corrected dual with the correct inequality constraints corresponding to the primal nonnegativity constraints. A simple value-transfer argument shows that balanced distributions are dual optimal, which then allows us to arrive at the claimed sensitivity bound using the same argument as before.

Monotonicity is a reasonable assumption in our credit assignment setting. For example, in our web-retrieval setting, access to more documents can only improve the quality of a response. We’ve included the monotonicity assumption in Section 2.

Proposition B.1 lacks a monotonicity assumption on (\hat v), so the proposed marginal allocation can be negative.

We’ve added the monotonicity assumption to the problem formulation. It is needed for our fixed version of Theorem 3.1 and is a realistic assumption that holds in our AI credit assignment setting. Thank you for pointing this out.

Corollary C.1 also appears to promote a (\delta)-probable sampled-feasibility guarantee to an exact global (\ell_2)-optimality statement.

We were a bit sloppy with the terminology here. Corollary 4.3 previously claimed exact ℓ2\ell_2 optimality over all feasible schemes, whereas the proof only establishes optimality relative to the sampled constraints. We have restated it more precisely as an approximate optimality result.

The empirical evidence does not establish the claimed least-core approximation or query-efficiency advantage. For (n=32), the evaluation uses only 212 uniformly sampled holdout coalitions and a 99th percentile, even though the least core is defined by the worst coalition over (2^{32}) possibilities. The Yan--Procaccia baseline is itself a random-sampling approximation, so matching it does not demonstrate closeness to the true least core. …

First, our holdout set has 4,096 coalitions (2122^{12}, not 212). Because checking every subset at n=32n=32 is intractable, we also ran n=10n=10 experiments which are presented in the appendix. You can see there that YP evaluates every subset (about ~2k calls) to find the exact least core, and on our synthetic dataset, CG with LLM seeding/oracle matches it on 31/32 questions in ~65 calls. At n=32n=32, CG with a random oracle matches YP using four to five times fewer calls. The LLM oracle is faster still: on our synthetic dataset it got within about 0.06 of YP in just 110 to 140 calls (60 to 75x fewer), ahead of zero shot. On BrowseComp it did roughly the same as ZS, likely because only 64% of gold docs answer the question on their own. We used the 99th percentile at n=32n=32 so one noisy LLM judgment, such as guessing from memory, doesn't push the deficit to 1.

Were the Gold Answers actually passed to the LLM-based initializer, separation oracle, and zero-shot allocation prompts? If yes, why is this information available to the algorithm and how is the comparison with the random baseline fair? If no, please provide the exact prompts used in the experiments.

Yes, those are the exact prompts, and this isn't label leakage. We assume the baseline answer is known and only want to assess the counterfactual of having a different subset of documents in context for that answer. In a real system, this answer might come from user feedback, such as a thumbs up or down. Every value function query, including YP's, grades against that same baseline answer. Also the LLM initializer and oracle only suggest subsets; we still score every suggestion with the value function and evaluate on our shared holdout set. Further, CG with random oracle + seeding never sees the answer in a proposal prompt, but still matches YP in far fewer calls.

What is the exact mapping from the 69 synthetic records in the supplementary package to the reported (n=10) and (n=32) experiments and the claimed 32 instances per dataset?

The supplement has all 69 synthetic questions. For both n=10n=10 and n=32n=32, we took the first 32 questions in file order, kept their gold and evidence documents, and trimmed extra negatives to reach nn. We did the same for the first 32 rows of BrowseComp.

Please report whether each coalition evaluation is deterministic or cached, the model version, temperature, seed, retry behavior, and whether the full-document and empty-document coalitions are explicitly forced to satisfy (\hat v(N)=1) and (\hat v(\varnothing)=0). Also report monotonicity violations of the independently evaluated binary (\hat v).

Each subset is evaluated once per question and cached on disk, so every method sees the same (deterministic) value function. We fixed empty and full sets to 0 and 1 by construction. We used one LLM with default decoding, fixed seeds for training and holdout sampling, and no retries on errors (which score zero). Across over two million nested pairs on BrowseComp, roughly 99.5% satisfy monotonicity. Only 0.51% of pairs violate it overall, with a 0.24% median per question and zero violations from all-negative subsets. This supports our assumption in Section 2.

How are all LLM calls counted? Please clarify whether the reported counts include answer-generation calls, grading calls, initializer calls, LLM-oracle proposal calls, and zero-shot calls, and provide a complete quality-versus-cost table.

Each new subset evaluation takes two calls (answer and grading), each LLM oracle step takes one call, and ZS takes one call. We exclude the holdout set because no algorithm sees it during search. It's only a test set for scoring final allocations. Here's the (mean, non-egalitarian) n=32 results:

MethodSeedOracleSynthetic DeficitSynthetic CallsBrowseComp DeficitBrowseComp Calls
YP0.5081920.648192
YPS0.5282560.718256
CGRR0.5117960.651852
CGLR0.541950.661625
CGSR0.642560.72412
CGRL0.551090.79128
CGLL0.561370.80211
CGSL0.561130.7696
ZS0.6710.761

Apologies for the typo in my Review: "... only 2^{12} uniformly sampled holdout ...", not "212". But it's alright, we're done here. Thanks for your detailed response. It addresses my concerns. I will raise my score.

Reviewer_K7yUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

This paper studies how to allocate credit among creators whose documents are used by an LLM to generate a response. The authors model the problem as a cooperative game, where each coalition of creators is assigned the reward that could be obtained using only their documents. They propose the least core, which allocates credit by minimizing the maximum amount by which any coalition's assigned credit falls below the reward it could generate on its own. Since the rewards of individual coalitions must be estimated, the authors study how errors in their estimation affect the optimal least-core deficit. To avoid evaluating all possible coalitions, they also propose algorithms that start with a small set of constraints and iteratively add those corresponding to coalitions that receive too little credit.

Critical strengths
  1. The least core is a well-motivated choice for credit allocation, as it minimizes the largest gap between what a coalition receives and what it could generate on its own. Unlike the Shapley value, it explicitly accounts for the incentives of groups of creators to act independently.
  2. The authors propose an efficient way to compute credit allocations without evaluating every possible group of creators. Their algorithm iteratively identifies groups that receive less credit than their estimated reward and uses them to improve the allocation.
Critical weaknesses
  1. The proof of Theorem 3.1 appears to use an incorrect LP dual. The nonnegative allocation constraints in Definition 2.1 lead to inequalities in the dual, whereas the authors impose equalities. These equalities correspond to allowing negative allocations, which is not the setting considered in the paper.
  2. Theorem 4.2 is not justified by Algorithm 4 as written. Algorithm 4 returns an allocation u(alg)u^{(\mathrm{alg})} and a deficit ε(alg)\varepsilon^{(\mathrm{alg})} as soon as no violated coalition constraint is found. It does not minimize the deficit. However, the proof assumes that ε(alg)≤ε^\varepsilon^{(\mathrm{alg})}\leq\hat\varepsilon, where ε^\hat\varepsilon is the optimal least estimated-core deficit. This inequality is not guaranteed. Consider two players with v^({1})=v^(N)=1\hat v(\{1\})=\hat v(N)=1 and v^({2})=0\hat v(\{2\})=0. Algorithm 4 immediately returns u=(1/2,1/2)u=(1/2,1/2) and ε(alg)=1/2\varepsilon^{(\mathrm{alg})}=1/2, although u=(1,0)u=(1,0) achieves the optimum ε^=0\hat\varepsilon=0. If DD assigns probability one to {1}\{1\}, the conclusion of Theorem 4.2 fails.
Questions for authors
  1. Theorem 3.1. The proof imposes ∑S∋iλS=μ\sum_{S\ni i}\lambda_S=\mu for every player, whereas the non-negative allocation constraints appear to require ∑S∋iλS≤μ\sum_{S\ni i}\lambda_S\leq\mu in the dual. How do you justify these equalities? Can the claimed bound on ∣ε∗−ε^∣|\varepsilon^*-\hat\varepsilon| still be proved using the correct dual?
  2. Theorem 4.2. The proof assumes ε(alg)≤ε^\varepsilon^{(\mathrm{alg})}\leq\hat\varepsilon, but Algorithm 4 stops without minimizing ε\varepsilon. What guarantees this inequality? Does the algorithm need to be modified for the claimed result to hold?
2 comments

Thank you for taking the time to review our submission and for pointing out several issues in our proofs. We want to emphasize that we’ve fixed all mathematical issues with the theoretical results. The main message of our paper and the takeaways from the theory have not changed.

The proof of Theorem 3.1 appears to use an incorrect LP dual. The nonnegative allocation constraints in Definition 2.1 lead to inequalities in the dual, whereas the authors impose equalities. These equalities correspond to allowing negative allocations, which is not the setting considered in the paper.

Indeed the dual we wrote down was incorrect as your counterexample shows. We have included a fix: the statement of Theorem 3.1 holds under the assumption that the coalitional value functions are monotone (that is, additional creators do not hurt coalitional value). To argue this, we analyze the corrected dual with the correct inequality constraints corresponding to the primal nonnegativity constraints. A simple value-transfer argument shows that balanced distributions are dual optimal, which then allows us to arrive at the claimed sensitivity bound using the same argument as before.

Monotonicity is a reasonable assumption in our credit assignment setting. For example, in our web-retrieval setting, access to more documents can only improve the quality of a response. We’ve included the monotonicity assumption in Section 2.

Theorem 4.2 is not justified by Algorithm 4 as written. Algorithm 4 returns an allocation u(alg)u^{(alg)} and a deficit ϵ(alg)\epsilon^{(alg)} as soon as no violated coalition constraint is found. It does not minimize the deficit. However, the proof assumes that ϵ(alg)≤ϵ^\epsilon^{(alg)} \leq \hat{\epsilon}, where ϵ^\hat{\epsilon} is the optimal least estimated-core deficit. This inequality is not guaranteed. Consider two players with v^(1)=v^(N)=1\hat{v}(1) = \hat{v}(N) = 1 and v^(2)=0\hat{v}(2) = 0. Algorithm 4 immediately returns u=(½,½)u = (½, ½) and ϵ(alg)=1/2\epsilon^{(alg)} = 1/2, although u=(1,0)u = (1,0) achieves the optimum ϵ^=0\hat{\epsilon} = 0. If D assigns probability one to 1, the conclusion of Theorem 4.2 fails.

We were able to fix this issue by modifying Algorithm 4 to optimize the deficit as well: Whenever the oracle finds no violated coalition, the algorithm saves the current point if its deficit is the smallest seen so far, adds the objective cut ϵ≤ϵ(t)\epsilon \leq \epsilon^{(t)}, and continues. It runs for a fixed number of iterations and returns the best saved point. The proof proceeds analogously to the previous one, with the exception of a new lemma which shows that the returned deficit satisfies ϵ(alg)≤ϵ^+η\epsilon^{(alg)} \leq \hat{\epsilon} + \eta for a user-specified tolerance, and Theorem 4.2 now relies on this bound instead of ϵ(alg)≤ϵ^\epsilon^{(alg)} \leq \hat{\epsilon}. We have included the updated theorem, algorithm, and proof in the new revision of our submission.

Thank you for the detailed response and the revised manuscript. I checked the revised proofs of Theorems 3.1 and 4.2, including the modified Algorithm 4 and the new Lemma C.1, and they are correct. My concerns have been addressed, and I am raising my score accordingly.

Reviewer_o4iUOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies in-context credit assignment, i.e., how to assign credits to different sources used by a LLM to generate a answer. It adopts the least-core principle, which defines the optimal credit assignment by letting each group's assign credit (sum of credits of each source) reflects if this group of sources help answer the question correctly. Roughly speaking, if a group can help LLM anwer the question, we should assign more credits to them, and if not we should assign credits as least as possible. The key challenge is that computing the least-core optimization is generally intractable as we have exponentially many source groups. To address this, it proposes an iterative constraint-generation methods, and theoretical analysis shows that this method can efficiently produces an epsilon-optimum with high probability. Empirically study demonstrates it substantial saves LLM calls on question-answering benchmarks for computing credits.

Critical strengths
  • The in-context credit assignment is an interesting problem with applications to content attribution and publisher compensation.

  • The proposed methods show promising computational savings for credit computation with sound theoretical analysis and empirical evaluation.

Critical weaknesses
  • As the authors acknowledge, the theoretical guarantees assume that groups of sources are sampled randomly or that the search always finds the most underpaid group. The practical LLM-guided search seems to be more like a heuristic that may not ensure those conditions.
Questions for authors
  • Regarding the Weeknesses, are there potential ways to modify the practical LLM-guided method to better match the assumptions of the theoretical analysis and retain some of its guarantees, while still maintaining the efficiency?
1 comment

Thanks for reviewing our submission. Our constraint generation algorithm is indeed a principled heuristic/relaxation of an impractical-yet-theoretically-grounded method, with superior empirical performance. We view this as a strength of our method, not a weakness. Our theoretical guarantees would carry over whenever the LLM oracle can be certified to be approximately correct. More broadly, as LLMs’ capabilities continue to improve, so will the performance of our LLM-guided method.

Reviewer_5MpDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies in-context credit assignment, where the goal is to distribute the value of AI-generated content among creators whose intellectual property is used in the model's context window. The authors model this as a cooperative game, where the value of a coalition represents the reward that its members could generate independently. They propose using the least core to minimize the maximum amount by which any coalition is undercompensated.

The paper first studies how errors in estimating coalition values affect the least-core deficit. It derives sensitivity bounds using balanced distributions over coalitions and considers special cases involving binary rewards and supermodular value functions. The authors then develop algorithms for computing approximate least-core allocations, including a sampling-based ellipsoid method and a practical constraint-generation algorithm. The latter uses different strategies for selecting initial coalitions and finding violated constraints, including LLM-based methods.

Experiments on semi-synthetic web retrieval tasks show that the proposed constraint-generation methods can approximate least-core allocations using substantially fewer LLM calls than the sampling-based baselines.

Critical strengths

An interesting application of cooperative game theory to content credit assignment.

The paper considers a relevant problem of assigning credit to creators whose contributions are used in AI-generated content. Modeling these contributions through coalition values is a reasonable approach, and the least core provides a way to limit how much any group of creators is undercompensated. Additionally, it is interesting that the authors consider the case where the true coalition values are unknown and must be estimated, which seems relevant in practice. Studying how these estimation errors affect the resulting allocations is also an important question.

Useful computational ideas and extensive experiments.

The paper combines theoretical analysis with algorithms for handling the exponentially many coalition constraints. I find the constraint-generation approach, together with different seeding and separation strategies, interesting. The results on sampling-based approximation and minimal winning coalitions are also useful. The experiments are encouraging, particularly the reduction in LLM calls compared to the sampling-based methods. The comparisons between different seeding strategies and egalitarian and non-egalitarian allocations also help explain the behavior of the proposed algorithms.

Critical weaknesses

Concern about Theorem 3.1: LP duality and a possible counterexample.

My main concern is with the dual characterization used in the proof of Theorem 3.1. Since the primal LP requires nonnegative allocations, the corresponding dual constraints should be

∑S∋iλS≤μ,∀i,\sum_{S\ni i}\lambda_S \leq \mu, \quad \forall i,

rather than equalities. The equality conditions used in the proof would be appropriate if the primal allocation variables were unrestricted. While complementary slackness guarantees equality for players receiving positive allocations, it does not necessarily guarantee equality for every player. Therefore, I am not sure why the dual can be restricted to balanced distributions under the stated assumptions.

In fact, I think the following is a counterexample with three players, N=1,2,3N=\\{1,2,3\\}. Define the true and estimated coalition values by

v(1)=v(2)=1,v(\\{1\\})=v(\\{2\\})=1,

v^(1)=v^(2)=12,\widehat v(\\{1\\})=\widehat v(\\{2\\})=\frac{1}{2},

with v(N)=v^(N)=1v(N)=\widehat v(N)=1, and both functions equal to zero on all remaining coalitions.

These functions satisfy the paper's normalization and boundedness assumptions. The corresponding least-core deficits are

The corresponding least-core deficits are ε⋆(v)=1/2\varepsilon^{\star}(v)=1/2 and ε⋆(v^)=0\varepsilon^{\star}(\widehat v)=0.

However, the right-hand side of Theorem 3.1 is

max⁡λ∈Λ∑SλS∣v(S)−v^(S)∣=12max⁡λ∈Λ(λ1+λ2)=13.\max_{\lambda\in\Lambda}\sum_S\lambda_S|v(S)-\widehat v(S)| = \frac{1}{2}\max_{\lambda\in\Lambda}(\lambda_{\\{1\\}}+\lambda_{\\{2\\}}) = \frac{1}{3}.

Thus, Theorem 3.1 would imply 1/2≤1/31/2 \leq 1/3, which is false. The last equality follows because balanced distributions satisfy λ1+λ2≤2/3\lambda_{\\{1\\}}+\lambda_{\\{2\\}}\leq 2/3, with equality achieved by assigning probability 1/31/3 to each singleton coalition.

This suggests that the stated sensitivity bound may fail for general normalized coalition value functions. Could the authors clarify the duality argument, or whether additional assumptions such as monotonicity are required for the theorem to hold?

The choice of the least core could be better motivated, and some computational guarantees rely on strong assumptions.

The authors motivate the least core mainly through coalitional stability. However, I would have liked a clearer explanation of why this is the right objective for assigning credit to creators. For example, it is not clear whether groups of creators can actually coordinate and independently generate the value assigned to their coalition.

I also think the comparison with the Shapley value is somewhat limited. The paper discusses why the least core may be preferable, but the experiments only compare different ways of computing least-core allocations. They do not compare the resulting allocations with Shapley-based methods. Such a comparison would help establish whether the least core is actually preferable for this application, rather than only showing that it can be computed more efficiently.

This is especially relevant for the supermodular setting considered in the appendix, where the Shapley value already belongs to the core (Shapley, 1971). Moreover, it can be approximated by sampling random permutations, with each sampled marginal allocation also belonging to the core. This provides a natural and potentially cheaper alternative in that setting.

Regarding computation, the paper provides polynomial-time and sample-complexity guarantees for a sampling-based approximation, which is useful. However, the practical constraint-generation algorithm relies on LLM-based or approximate separation methods. The stronger results for monotone binary games also assume access to a maximum-violation oracle and depend on the number of missing minimal winning coalitions. It would be helpful to explain more clearly how these theoretical guarantees relate to the practical implementations. The experiments also evaluate sampled coalition deficits rather than the worst-case deficit over all coalitions.

Questions for authors

I request the authors to address the points stated above in the weakness section.

7 comments

Thank you for taking the time to review our submission! Our responses to your questions and comments are below.

We want to emphasize that we’ve fixed all mathematical issues with the main theoretical results. The main message of our paper and the takeaways from the theory have not changed. Thank you for bringing them to our attention.

Concern about Theorem 3.1: LP duality and a possible counterexample.

Indeed the dual we wrote down was incorrect as your counterexample shows. We have included a fix: the statement of Theorem 3.1 holds under the assumption that the coalitional value functions are monotone (that is, additional creators do not hurt coalitional value). To argue this, we analyze the corrected dual with the correct inequality constraints corresponding to the primal nonnegativity constraints. A simple value-transfer argument shows that balanced distributions are dual optimal, which then allows us to arrive at the claimed sensitivity bound using the same argument as before.

Monotonicity is a reasonable assumption in our credit assignment setting. For example, in our web-retrieval setting, access to more documents can only improve the quality of a response. We’ve included the monotonicity assumption in Section 2.

The authors motivate the least core mainly through coalitional stability. However, I would have liked a clearer explanation of why this is the right objective for assigning credit to creators. For example, it is not clear whether groups of creators can actually coordinate and independently generate the value assigned to their coalition.

We do motivate our choice of the least core as the right solution concept for in-context credit assignment in Appendix A. In short, the Shapley value is not an equilibrium allocation, the least core may be viewed as the cooperative analog of a Nash equilibrium, and the egalitarian least core satisfies every Shapley axiom except for linearity (and linearity, as Yan and Procaccia also argue, is a questionable axiom for credit assignment).

Regarding coordination, we’d like to clarify that the core does not require creators to actually coordinate with each other. Instead, it guarantees that no group of creators is paid less than what their content alone would contribute. In the worst case for an AI platform, this deviation could take the form of withholding content from the platform and licensing it to a competitor.

I also think the comparison with the Shapley value is somewhat limited. The paper discusses why the least core may be preferable, but the experiments only compare different ways of computing least-core allocations. They do not compare the resulting allocations with Shapley-based methods. Such a comparison would help establish whether the least core is actually preferable for this application, rather than only showing that it can be computed more efficiently.

The purpose of our experiments was to show that our methods can approximate the least core efficiently using a small number of samples. The question of why the least core is preferable to Shapley values as a solution concept is a question about its allocation properties, which we mention in Appendix A and in our answer to your previous question. Experimental comparisons of the core to the Shapley value have already been done by previous work (e.g. Yan and Procaccia), in which they demonstrate several computational virtues of the core over Shapley values.

This is especially relevant for the supermodular setting considered in the appendix, where the Shapley value already belongs to the core (Shapley, 1971). Moreover, it can be approximated by sampling random permutations, with each sampled marginal allocation also belonging to the core. This provides a natural and potentially cheaper alternative in that setting.

We’d like to point out that in the supermodular setting, the core can be computed in closed form (Proposition B.1), which is even cheaper than the random sampling approximation of the Shaley value you are referring to.

Regarding computation, the paper provides polynomial-time and sample-complexity guarantees for a sampling-based approximation, which is useful. However, the practical constraint-generation algorithm relies on LLM-based or approximate separation methods.

We view this as a strength of our method, not a weakness. The Ellipsoid method on which the theory rests is an impractical algorithm. Our constraint generation algorithm is a principled heuristic/relaxation of this impractical-yet-theoretically-grounded method, with superior empirical performance.

The stronger results for monotone binary games also assume access to a maximum-violation oracle and depend on the number of missing minimal winning coalitions. It would be helpful to explain more clearly how these theoretical guarantees relate to the practical implementations.

Theorem 4.6 serves as a guiding principle for practical methods of seeding the egalitarian least core QP. Its experimental analog is the “LLM proposed coalitions (L)” seeding configuration. Lemma 4.5 and Theorem 4.6 say that seeding the QP with MWCs is the best thing one could do, assuming access to an exact max-violation oracle. The direct experimental analog is configuration “CG L L”, which asks the LLM to seed the QP with what it thinks are the MWCs, and at every stage add the coalitional constraint corresponding to what it thinks is the unhappiest coalition (i.e., to implement a max-violation oracle).

Of course, in credit assignment settings, there is not enough known structure on the coalitional value functions to plausibly assume access to (1) a perfect MWC generator nor a (2) perfect max-violation oracle (as the coalitional value function is an LLM-as-a-judge). So, as you point out, there is no direct theoretical guarantee that can be derived for the CG L L algorithm. But that is to be expected in our setting, and the theory serves to motivate our algorithm design used in experiments.

The experiments also evaluate sampled coalition deficits rather than the worst-case deficit over all coalitions.

Computing worst-case deficits at n=32 players would require reasoning about 2^32 coalitions, which is computationally intractable. For these experiments, the holdout metric estimates the quantity that our theory controls, and we do evaluate all coalitions exhaustively at n=10.

Reviewer_5MpDOpenReview ↗

Response to authors

Thanks for the detailed clarification and the revised proof of Theorem 3.1. I am satisfied with the revised argument given the monotonicity assumptions.

I still have two questions, mainly about how well the assumptions and the choice of allocation rule fit the application.

1. Monotonicity in practice.

The paper assumes that both the true and estimated coalition value functions are monotone. I understand this is a useful assumption theoretically, but I am not sure how realistic it is for the particular setting you study which is the LLM web search setting.

For example, adding more webpages does not always improve an LLM's answer. The additional information could be irrelevant, distracting, or even contradictory, which can potentially make the answers worse. This kind of behavior has been observed in the literature (Liu et al., 2024; Amiraz et al., 2025).

This can be even more tricky with the estimated value function, since the paper suggests using an LLM-as-a-Judge or a learned reward model. Even if the true coalition values are assumed to be monotone, it does not seem obvious that these estimators would preserve that property.

Have the authors checked how often monotonicity holds in their experiments, or is it enforced by their estimation procedure? It would also be useful to understand what happens when monotonicity is violated, since the theoretical results rely on this assumption.

2. Why prefer the egalitarian least core over Shapley in this application?

I appreciate the explanation in Appendix A and the reference to Yan and Procaccia (2021). I agree that coalitional stability is a reasonable motivation for considering the least core. My question is more about why it should be preferred over Shapley-based allocations for this particular LLM credit assignment problem.

The two approaches capture different notions of fairness. For instance, Shapley also has the strong monotonicity property, which says that increasing a creator's marginal contributions should not reduce their allocation (Young, 1985). This seems relevant to credit assignment as well.

I also understand that the experiments are mainly intended to show that the proposed algorithms compute the least core efficiently. However, they do not tell us much about how the resulting allocations compare with Shapley-based allocations in this setting. Previous comparisons in data and feature valuation are useful, but I am not sure they settle the question for the current application.

Regarding supermodularity, I agree that Proposition B.1 provides a direct way to construct a core allocation. However, this is a marginal allocation for one fixed ordering of the players, and it need not be the egalitarian least-core allocation. The same marginal-contribution construction is also used to approximate Shapley by sampling permutations.

So I am not sure that the closed-form construction establishes a particular computational advantage of the egalitarian least core. It gives us an inexpensive core allocation, but not necessarily the egalitarian one. If the goal is specifically to compute the egalitarian least core, an additional optimization problem is still needed. Otherwise, we are left with the question of how to select one allocation from the core, whereas the Shapley value provides a canonical choice by averaging over all orderings. This is useful to discuss i the paper given the numerous experiments comparing egalitarian and non-egalitarian least-core methods. However, these are not compared against Shapley allocations.

More generally, the main setting is not restricted to supermodular games. I think a direct comparison with Shapley in the authors' LLM credit assignment setting, using similar coalition-value query budgets, would help clarify the practical tradeoffs for the XAI community.

These are my main remaining questions. I appreciate the authors' clarifications and the computational contributions of the paper, but I think the practical applicability of monotonicity and the choice of allocation rule needs some further clarifications.

References

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.