acceptodds
Under review as a conference paper at ICLR 2027

Unit-Weight Posterior Coresets: Sharp KL Geometry and Certification Limits

Abstract

We characterize posterior fidelity for literal evidence subsets, with no reweighting and an exact cardinality. Under additive logits, omitted-evidence range equals the maximum posterior log-odds distortion. We derive the exact minimum and maximum forward Kullback-Leibler (KL) divergence at a prescribed range for a fixed full posterior; the minimum depends only on its two smallest masses. The lower envelope turns a range-solver lower bound into a KL optimality certificate. With smallest posterior mass , exact range initialization followed by KL-decreasing refinement achieves the sharp factor . A matching binary construction establishes sharpness even with a unique full winner and any fixed exchange radius. For nonadditive consumers, aggregate signed transfer error connects posterior control to decision certification. In 1,800 controlled instances, refinement reduces mean true range by 10% relative to KL-greedy, with mean true KL .3089 versus .3166. RACE, DREAM, and SciFact evaluations with two neural targets identify 172–232 winner-preserving omissions per operating point, while all four calibrated constructions issue zero nontrivial joint winner certificates. Together, the exact envelopes, optimization diagnostics, and source-aware neural evaluations characterize when posterior control supports informative certification.

Primary area:
learning theory
Keywords:
posterior coresets, evidence selection, KL divergence, posterior geometry, robust optimization, decision certification, language models

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_C7TfOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper talks about literal evidence subsets with exact cardinality and no reweighting. Under additive logit model, the range of the left alone contribution is equal to the largest change in posterior log odds.

The main theoretical result gives the exact minimum and maximum forward KL divergence at a fixed residual range and full posterior. The minimum depends only on the two smallest posterior masses. This result converts a range-solver lower bound into a KL optimality certificate. The paper also proves that the (1−β)/β(1-\beta)/\beta factor is sharp and constructs cases where bounded-exchange refinement cannot reach the better KL solution.

Critical strengths
  1. The paper identifies the exact lower endpoint, proves that it is attained, and shows how the two smallest posterior masses control the result.

  2. The paper derived when range minimization gives a KL guarantee in addition to showing why local KL refinement can remain trapped, even after exact range initialization and even when several atoms may be exchanged.

Critical weaknesses
  1. The real-model experiments do not report the envelope lower bound, the certified KL gap, or the practical tightness of the approximation factor. hence,main theorem is not connected to the main application by a quantitative result.

  2. CPC has higher displayed direct KL than LLR norm at all four operating points. Simple lexical selection is best in the atomic setting, while MMR lexical is best in the paired setting. Importantly, all 16 calibrated constructions issue zero useful certificates when evidence is omitted.

Questions for authors
  1. Can the proposed KL optimality certificate computed on the controlled experiments using verified MILP lower bounds? How tight is it?

  2. Is there any neural setting where CPC gives a useful certificate or a clear benefit over lexical, MMR, or LLR selection?

2 comments

Thank you for recognizing that the exact KL lower endpoint is attained, that it depends on the two smallest posterior masses, and that range initialization followed by local KL refinement has both guarantees and limits.

We also appreciate your constructive questions about certificate tightness and practical performance on neural models.

We computed the certificate with independently verified range bounds and added exhaustive neural measurements. A separate source-disjoint evaluation tests useful certification and baseline fidelity (Sections 5.1–5.2 and 6.1).

Q1. Can the proposed KL optimality certificate computed on the controlled experiments using verified MILP lower bounds? How tight is it? (Certificate tightness and approximation factor)

Yes. We evaluated it in 72 additive cells with 16 evidence items and five answer options. We independently checked the mixed-integer linear programming (MILP) range bounds against exact enumeration of the stored inputs, then evaluated all 514,512 subsets using outward-rounded KL intervals.

Lower-bound efficiency is the certified KL lower bound divided by the attained KL optimum. The controlled results are:

  • Median efficiency: 0.105, ranging from about 0.0000015 to 0.8516.

  • Median certified CPC gap: 0.00552 nats.

  • Median actual CPC gap: 0.000502 nats.

The certified gap uses the lower bound; actual regret uses the attained optimum. Each is a separate median (Section 6.1, Table 7, pp. 9–10; Appendix J, p. 21).

Every range-minimizing incumbent reaches the exact minimum for the stored inputs. We capped tiny raw-bound overshoots before conversion. The corrected KL lower bound agrees with the exact-range bound to numerical precision.

Most remaining conservatism is geometric: the envelope covers all residuals at a given range, while feasible subsets attain only finitely many. It can include residuals that no feasible subset produces.

We also scored every feasible subset in 264 neural families from 64 RACE, DREAM, and SciFact sources, giving 154,178 candidate scores across both targets.

Among 262 positive-optimum families, median efficiency is 0.173, with interquartile range [0.0536, 0.3596]; 40 families reach at least 0.5. Across all 264 families, median certified and actual CPC gaps are 0.129 and 0.104 nats (Section 5.2, Table 5, p. 8; Appendix K.1, p. 22).

The median reference-specific finite-range factor is 41.4, versus about 2,260 for the mass-only factor. These are approximation bounds, not CPC's achieved ratios. The direct-range initializer's median achieved ratio of 1.00 belongs to the target's range-minimizing subset.

Ratios exclude the two zero-optimum families; absolute gaps retain them.

The neural analysis uses direct target scores for complete subset families. Sources are reused across targets, evidence groupings, and budgets, so these summaries are descriptive. An estimator-only selector would not automatically have this information.

A surrogate lower bound certifies its own family. Transferring that bound to the target optimum requires valid transfer control across the whole target candidate family (Sections 2 and 3.2; Appendix K.1).

Q2. Is there any neural setting where CPC gives a useful certificate or a clear benefit over lexical, MMR, or LLR selection? (Direct KL performance and certification under omission)

Yes, useful certification occurs in a narrow paired-evidence setting. In the separate source-disjoint evaluation of 500 sources, additive-nominal CPC at calibration level 0.05 issues two joint winner-preservation certificates at each paired item fraction, 0.20 and 0.35. Both targets keep their full-context winner.

Each case retains two of three paired items. The same two sources issue at both fractions, so these are two example-level successes, not four independent ones.

SettingActual omissions among 500 sourcesUseful certificatesObserved false issuances
Atomic 0.2039700
Atomic 0.3539700
Paired 0.2037820
Paired 0.3537820

The fractions set the item-budget rule; both certified examples retain two of three paired items at each fraction. These successes are too few to estimate conditional precision, the correctness rate among issued certificates. The initial cohort's zero-issuance result remains separate.

Section 5.1 and Table 4 (pp. 7–8) report all five calibration constructions. Appendix K.2 (pp. 22–23) gives the population and scope.

The direct-KL comparisons support no general CPC advantage over the named selectors. We average both target losses within each of the 500 sources. Lower KL is better. Retained item counts are matched; tokens and runtime are not.

SettingCPCLexicalMMRLLRKL-greedy
Atomic 0.201.34031.07361.11171.16631.2291
Atomic 0.351.00660.73230.74850.87081.1052
Paired 0.200.99710.84700.86610.98391.0729
Paired 0.350.91580.72340.80320.88060.9983

The declared Monte Carlo/Holm procedure uses 10,000 paired source-level resamples for all 16 planned comparisons. It favors lexical at atomic 0.35 and paired 0.35, and MMR at atomic 0.35. It supports no CPC improvement over a named comparator; the others remain unresolved.

Table 3 (p. 7) reports the means. Tables 12–13 (pp. 22–23) include all 13 policies and the paired uncertainty analysis.

Thank you again for prompting these measurements of certificate tightness and practical usefulness. We keep the practical claims limited to the measured certificate quality and the two paired-evidence successes.

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

The paper studies selecting exactly k of n evidence sentences unmodified, so that a model’s posterior over answer options stays close to the full-evidence posterior in forward KL. Experiments cover a synthetic study, exhaustive small-scale graphs, and RACE/DREAM/SciFact with Qwen and Phi models.

Critical strengths

1.Theorem 1 gives tight KL envelopes at fixed range, and the minimum depends only on the two smallest masses, which is clean. 2.Corollary 2 turns a verified lower bound on range from a MILP solver into a lower bound on the best achievable KL.

Critical weaknesses

1.The problem of selecting exactly k of n evidence pieces, unchanged, so that a language model’s answer probabilities stay close to the full-evidence ones is concrete. I feel it should be more important to solve the practical problem well rather than focusing on theoretical discussion. 2.The central theoretical results are not tested on real models. The theory section is the paper’s largest contribution, yet the real-model section measures different things: winner preservation, calibrated coverage, and direct KL against baselines. As a reader I find the two halves feel like separate papers. And the theory’s assumptions are not met in the experiments. 3.The text is also very dense and hedged and the proposed method doesn’t win empirically.

Questions for authors

See the weakness

3 comments

Thank you for recognizing the tight KL envelopes in Theorem 1, the role of the two smallest posterior masses, and the conversion of a verified range bound into a KL lower bound in Corollary 2.

We also appreciate your constructive comments on practical usefulness, the link to neural experiments, and the dense presentation.

We added exhaustive neural and controlled certificate measurements and expanded the source-disjoint baseline comparison. We clarified where additivity is required and rewrote the introduction and Figure 1 to explain the task before the results (Sections 1, 3.2, 5.1–5.2, and 6.1).

Practical value of exact subset selection

We agree that the practical question is how well exactly k unchanged evidence pieces preserve the full-evidence posterior. The certificate bounds how much a better feasible subset could improve the selected loss. If that loss is d and a verified lower bound on the optimum is b, improvement is at most d minus b (Corollary 2, Section 3.2, p. 4).

We now compare the bound with the attained optimum after evaluating every feasible subset in each tested family. This tests the certificate's informativeness. The separate baseline comparison tests CPC's performance as a selector.

How the theory applies to neural models

Theorem 1 applies exactly to each realized pair of finite neural score vectors, without assuming additive evidence effects. The difference between full and subset logits gives a residual that transforms the full posterior into the subset posterior.

Additivity is needed for the range optimizer's surrogate. Its lower bound certifies its own family. Transferring that surrogate lower bound to a nonlinear target optimum requires the stated reference control and residual-error bounds across the whole target candidate family (Section 2, pp. 2–3; Section 3.2, p. 4).

We tested the theory on Qwen2.5-3B-Instruct and Phi-3.5-mini-instruct by scoring every feasible subset in 264 naturally eligible families from 64 RACE, DREAM, and SciFact sources. The 154,178 candidate scores give each family's minimum direct range and attained direct KL optimum.

The results show how informative the bounds are:

  • Among 262 families with positive KL optimum, the median lower-bound/optimum ratio is 0.173, with interquartile range [0.0536, 0.3596]. In 40 families, it reaches at least 0.5.

  • Across all 264 families, median certified and actual CPC gaps are 0.129 and 0.104 nats.

  • The median reference-specific finite-range factor is 41.4, compared with about 2,260 for the mass-only factor.

Section 5.2 and Table 5 (p. 8), with Appendix K.1 (p. 22), report these measurements.

The analysis uses direct target scores unavailable to an estimator-only selector at deployment. Ratios exclude two zero-optimum families; absolute gaps retain them. Families reuse sources across targets, evidence groupings, and budgets, so these are descriptive summaries, not independent source replications.

Performance against the baselines

We agree that the practical claims must reflect the strong baselines. All 13 policies use the same 500 sources at each operating point, with the two target losses averaged within source. Lexical and MMR have lower mean direct KL than CPC at all four operating points.

The source-stratified Monte Carlo/Holm procedure uses 10,000 resamples for 16 planned comparisons. It favors lexical at atomic 0.35 and paired 0.35, and MMR at atomic 0.35. It supports no CPC improvement over a named comparator. The other comparisons are unresolved; this does not establish equivalence (Section 5.1, Table 3, p. 7; Tables 12–13, pp. 22–23).

The separate calibration study gives a limited positive result. At calibration level 0.05, additive-nominal CPC issues two joint winner-preservation certificates at each paired fraction, with actual omission and no observed false issuance. The same two sources issue at both fractions.

These two example-level successes do not establish frequent issuance or conditional precision, the correctness rate among issued certificates (Table 4, p. 8; Appendix K.2).

The controlled study also shows the bound's limits. Across 72 additive cells and 514,512 subsets, median lower-bound efficiency is 0.105. Median certified and actual CPC gaps are 0.00552 and 0.000502 nats. Independently verified range optima show that most conservatism comes from residuals allowed by the envelope that no feasible subset can attain, rather than an inaccurate solve (Section 6.1, Table 7, pp. 9–10; Appendix J, p. 21).

Clarity of the presentation

Section 1 defines the task, score, forward KL objective, and three certificate meanings before the results. A two-answer example shows why the winner can stay the same while the posterior changes. Figure 1 (p. 2) connects the problem, residual mechanism, optimization certificate, and neural measurement.

We added explanations beside the formulas in Sections 2–4 and a certificate comparison in Section 3.2. The experimental discussion states what each measurement supports and the limits of the neural selector comparisons.

Reviewer_i8QSOpenReview ↗

Thank you for the rebuttal

Thank you for the detailed response and the new measurements. The exhaustive evaluation on Qwen and Phi connects the theory to real models quantitatively. These updates address my concern that the theory was not tested on real models, so I have raised my soundness score. I keep my overall rating unchanged. The main reason is the gap between the method and simple baselines. CPC has a higher mean direct KL than lexical, MMR, and LLR selection in all four settings. Lexical selection achieves the lowest mean KL in every setting. In certification study, we only have two of 500 sources receive a useful certificate, and the same two sources account for the successes at both fractions. I think this gap is too large to fill within the rebuttal period. The practical value of the approach would need a stronger empirical result.

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

The paper studies unit-weight coresets for posterior fidelity.

Critical strengths

None

Critical weaknesses

I honestly could not understand the paper. The paper would really benefit from a significant re-writing. Before jumping into what your results are, please clearly state the problem: please define the jargon you are using so that it's accessible to a reader even with an ML background. The line two says "connect an evidence-selection objective to a useful certificate": please define what you mean by certificate? What's the context behind evidence selection, what is the objective, what is the score? In beyond introduction, many quantities of interest are simply written as mathematical formulas, with no proper description! The text refers to Figure 1 without having defined ANY of those quantities formally!

Questions for authors

See Weaknesses.

3 comments

Thank you for your careful reading and for being clear about where the paper became difficult to follow.

We appreciate your constructive suggestions on the problem statement, scores, certificates, and Figure 1.

We rewrote the opening, added a two-answer example, and explained the three certificate meanings before the results. Figure 1 now gives an overview, and short explanations accompany the main formulas (Sections 1–4).

Q1. What's the context behind evidence selection, what is the objective, what is the score? (Problem statement and terminology)

The input is a question, fixed candidate answers, and n evidence pieces, such as sentences or dialogue turns. We ask which subset of exactly k pieces best preserves the full-evidence answer distribution. Each retained piece stays unchanged and appears once, with no reweighting. This literal subset is a unit-weight coreset.

A score is an unnormalized value assigned to an answer option. Softmax converts these scores into probabilities. In the neural experiments, each score is the summed log probability of the answer-label continuation.

We minimize forward Kullback-Leibler (KL) divergence from the full-evidence distribution to the subset distribution. Here, posterior means the normalized distribution over fixed answer options. It measures fidelity to the model's distribution, rather than factual correctness (Section 1, p. 1; Section 5).

Section 1 gives an example before the formal results. Two evidence pieces contribute (2, 0) and (−1, 0) to answers A and B. With zero base scores, full evidence gives (1, 0); keeping only the first piece gives (2, 0).

A wins in both cases, but its probability changes from 0.731 to 0.881. Keeping the same winner can therefore still change the distribution.

Q2. Please define what you mean by certificate? (Meaning and scope of a certificate)

A certificate is a bound that supports a specific claim under stated assumptions. We now explain the three claims separately:

  • A range bound limits the largest change in pairwise log odds caused by omitting evidence.

  • A KL optimality certificate bounds how much a better feasible subset could improve the selected KL loss. Corollary 2 turns a verified range lower bound for the whole candidate family into a lower bound on the best feasible KL. Subtracting it from the selected loss bounds the remaining improvement.

  • A winner certificate gives a sufficient condition for keeping the full-context winner. It requires a valid score-error bound and a strict answer margin. Seeing the same winner in an experiment alone does not provide that guarantee.

Section 1 introduces these definitions before the formal results. Section 3.2 (p. 4) gives a compact comparison of the questions each certificate answers.

Definitions in Figure 1 and explanations of formulas

We agree that the figure should explain its notation where it is used. Figure 1 (p. 2) now defines the certificate symbols in its caption. It starts with the literal subset problem and distinguishes it from weighted coresets. It shows how omission changes the scores and how Theorem 1 and Corollary 2 turn their residual range into a bound on optimal subset fidelity.

The bottom strip adds the direct-neural measurement. Explanations in Sections 2–4 describe Theorem 1 as the exact KL bounds at fixed range, Corollary 2 as the bound on remaining improvement, and Theorem 3 as the reason bounded exchanges can remain trapped. We hope these changes make the formal results easier to follow.

I thank the authors for their response, however, I still believe that the paper requires a significant re-write. It is very difficult to follow.

Comments on the paper

1 comment

We thank the reviewers for their careful reading and constructive comments. Your feedback helped us clarify the problem and add tests of certificate quality and practical usefulness.

Clearer definitions and examples. Section 1 defines the task, scores, forward KL objective, and three meanings of certificate. A two-answer example shows why the winner can stay the same while the posterior changes. Figure 1 connects the problem, theory, and neural measurements. Its caption now defines the certificate symbols at first use. Section 3.2 compares range, KL optimality, and winner certificates.

A direct test on neural models. We scored every feasible subset in 264 families from 64 RACE, DREAM, and SciFact sources, giving 154,178 candidate scores. Among 262 families with positive KL optimum, the median lower-bound/optimum ratio is 0.173, and 40 reach at least 0.5. Median certified and actual CPC gaps are 0.129 and 0.104 nats (Section 5.2, Table 5, p. 8; Appendix K.1, p. 22).

A controlled test of tightness. We evaluated 514,512 subsets in 72 additive cells using independently verified range bounds and outward-rounded KL intervals. The median lower-bound/optimum ratio is 0.105; median certified and actual CPC gaps are 0.00552 and 0.000502 nats. The range solve is essentially exact. Most conservatism comes from residuals allowed by the envelope that no feasible subset can attain (Section 6.1, Table 7, pp. 9–10; Appendix J, p. 21).

Useful certification and strong baselines. In a separate source-disjoint evaluation of 500 sources, additive-nominal CPC issues two joint winner-preservation certificates at each paired item fraction, 0.20 and 0.35. Evidence is omitted, and no false issuance is observed. The same two sources issue at both fractions. The adjusted direct-KL comparisons support no CPC improvement over the named baselines (Section 5.1, Tables 3–4, pp. 7–8; Appendix K.2, pp. 22–23).

The neural analysis measures complete subset families using direct target scores that an estimator-only selector would not have at deployment. The two certification successes show that useful issuance can occur in the tested paired setting. They do not establish conditional precision or a general advantage over the baselines.

We hope these changes sufficiently address the concerns raised by the reviewers.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.