acceptodds
Under review as a conference paper at ICLR 2027

Certified Context Integrity for In-Context Predictors

Abstract

Modern in-context predictors treat a support set as part of the inference input: tabular foundation models condition on support tables, and large language models condition on demonstrations. This opens a poisoning surface that needs no retraining, because whoever controls the context can change predictions without touching the model. Against four tabular foundation models and 15-NN on six real tables, a median of one to eight inserted rows flips an undefended prediction, and for TabICL a single row suffices on half the tables. We introduce *certified context partitioning*, a retraining-free, black-box wrapper that issues a deterministic certificate for each query. Each support row is assigned to a shard by a cryptographic hash of its own features, the frozen predictor runs once on every realised shard, and the prediction is the plurality of the shard votes. An insertion, deletion or relabelling can change only one shard, so the vote gap certifies how many such operations the prediction survives; feature edits receive half that radius. Across 20 OpenML/UCI tables, 12 base learners, shard counts up to 256 and three seeds, a median certified radius of 7 rows (m = 16) costs a median 1.0 accuracy point. With every configuration chosen on held-out validation queries, partitioned in-context prediction beats certified k-NN, the closest retraining-free baseline, by 0.67, 1.00 and 0.94 points of certified accuracy at radii 1, 2 and 4 (winning on 14, 14 and 13 of 20 tables), while the same certificate over classical learners does not; under arbitrary edits the two are level unless rows carry trusted identifiers. Two white-box adaptive attacks that know the model, hash and partition produce no certificate violation in 3,600 attacks on 1,800 defended queries, and for TabICL, TabPFN v2.6 and Mitra v2 the median successful insertion attack needs exactly r + 1 rows, so the bound is attained. Content addressing costs no measurable accuracy against a balanced random partition, and partitioning cuts peak GPU memory 12–29× at 20,000 support rows. A learning-curve law predicts certified accuracy to a median error of 0.6 points and picks the best shard count outright in 60–74% of cells. Changing only the partitioner and backend certifies Qwen3.5-2B and Qwen3.5-4B on SST-2 at 89.0% and 88.0% against any eight inserted, deleted or relabelled demonstrations out of 512. Context supplied at inference time can therefore be treated as a certifiable security boundary, with deterministic guarantees and no retraining.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
certified robustness, data poisoning, in-context learning, tabular foundation models, partition aggregation, large language models, provable defences

Reviews

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

The paper addresses an important problem: inference-time context poisoning in tabular foundation models. The authors propose a training-free approach that partitions the context into multiple shards and aggregates their predictions through plurality voting. Because inserting, deleting, or relabeling a single row can affect at most one shard, the voting margin provides a deterministic guarantee against a bounded number of malicious modifications. The paper establishes theoretical guarantees and presents extensive empirical evaluations supporting the approach.

Critical strengths
  • Training-free certification. While partitioning and voting are established techniques, notably in Deep Partition Aggregation (DPA), this paper adapts them from training-time poisoning defense to inference-time context protection. This eliminates the need for retraining and enables certification of frozen foundation models.
Critical weaknesses
  1. Modest improvement over existing methods. The improvement over certified kk-NN is relatively small. In the held-out comparisons (Table 2), the proposed approach achieves median gains of only 0.67, 1.00, and 0.94 percentage points in certified accuracy at radii 1, 2, and 4, respectively. The advantage largely disappears when arbitrary feature edits are allowed without trusted row identifiers. Given the additional computational cost, the practical significance of these improvements is unclear.

  2. Trade-off between robustness and accuracy. The experiments reveal a substantial trade-off: increasing the number of shards allows larger certification radii but reduces the context available to each shard, potentially degrading predictive accuracy. For TabPFN v2, using 256 shards leads to a 6.9-percentage-point reduction in accuracy (Table 1). The trade-off can be more pronounced for LLMs that genuinely depend on their demonstrations. For Qwen3.5-2B with arbitrary class labels, certified accuracy at radius 8 falls to 62%, compared with 91.3% undefended accuracy (§9). These findings raise questions about the usefulness of the approach for tasks requiring substantial contextual information.

  3. Limited robustness against larger poisoning budgets. The certified radius is relatively small compared with typical context sizes. For example, the median certificate at 16 shards covers only seven malicious row modifications, a small fraction of datasets containing thousands of examples. While this is consistent with the paper's stated threat model, it limits protection against attackers who can control a larger portion of the context. Increasing the radius further comes at the expense of accuracy and computational cost.

  4. Significant inference overhead. Evaluating the foundation model independently on multiple shards substantially increases inference cost. For example, at 64 shards, TabPFN v2 incurs approximately 17× the undefended wall-clock latency on the benchmark datasets (§5). Although the authors report memory savings and potential latency benefits for larger contexts, the overhead remains significant in latency-sensitive deployments. Combined with the modest improvement over certified kk-NN, this raises concerns about practical cost-effectiveness.

  5. Limited theoretical novelty. The main robustness guarantee largely reuses the partition-and-vote certification argument from Deep Partition Aggregation (DPA), adapted from training-time poisoning to inference-time contexts. The primary novelty lies in applying this established mechanism to frozen in-context predictors and empirically evaluating its effectiveness, rather than developing a fundamentally new certification method.

  6. Presentation. The paper is difficult to follow due to highly compressed prose, dense numerical reporting, and frequent transitions between theoretical claims, experimental findings, and qualifications. A clearer presentation of the central idea and a more structured discussion of the accuracy–robustness–compute trade-off would substantially improve readability.

Questions for authors

1. Does the modest improvement over certified kk-NN justify the additional inference cost?

The proposed approach outperforms certified kk-NN by approximately one percentage point in certified accuracy at small robustness radii, while requiring multiple foundation-model inference passes. Moreover, the advantage largely disappears under arbitrary feature edits without trusted identifiers.

Could the authors provide a more systematic comparison of the accuracy–robustness–latency trade-off against certified kk-NN, particularly under matched computational budgets? In what deployment scenarios would the additional inference cost be justified by the observed gains? It would also be helpful to identify the conditions under which partitioned in-context prediction provides a meaningful advantage over simpler and cheaper alternatives.

2. How well does the approach scale to larger poisoning budgets?

The reported guarantees cover a relatively small fraction of the context, and increasing the number of shards introduces accuracy and computational costs. How does the method scale when an attacker can modify a more substantial fraction of the context, such as 1% or 5% of the support examples? Is there a practical regime in which the method can provide meaningful protection against larger poisoning budgets without excessive loss of predictive accuracy or inference efficiency?

4 comments
AuthorsOpenReview ↗

Response to Reviewer V52g [Part 1/2]

Thank you for the review and for the deployment questions. We ran new experiments for each, including one that sets a clear limit on the method (Q2). Changes in the revised PDF are in blue.

Q1 / W1 / W4. Is a one-point gain worth the cost? Matched compute? When does it pay?

(1) The certified margin understates the benefit. A certificate is paid for on every query, attacked or not.

  • At the configuration each method selects for a given radius (Table 2 protocol), the partition's clean test accuracy is a mean 3.2 to 3.7 points above certified k-NN's at radii 1–8.
  • At radius 2 the median gain is 1.2 points, on 14 of 20 tables (p = 0.002).
  • The reason: to certify, k-NN must smooth with a large k (median 31–101). The partition loses a median of one point at m = 16.

(2) Matched compute. Capping the shard count keeps the lead. Margin over certified k-NN, with (tables won) and [significant splits of 5]:

armm ≤ρ = 1ρ = 2A100 latency vs undefended
pooled in-context16+0.56** (15) [5/5]+0.93** (16) [5/5]5.2× (panel median)
Mitra v2 alone16+0.83* (12) [5/5]+0.22* (15) [5/5]1.4× (9.8 ms)
TabPFN v2 alone16+0.67** (15) [5/5]+0.77** (17) [5/5]5.2× (19.7 ms)
  • The 17× in the submission is for m = 64 (radius 31).
  • At radii 1–2, the design rule selects m = 16–32.
  • Certified k-NN (0.03–0.3 ms) remains cheaper.

(3) The overhead is per call, not per FLOP. Each shard attends over only N/m rows; what grows is each call's fixed cost. At 20,000 rows the effect reverses:

  • Mitra v2 is faster defended than undefended at every m ≤ 64.
  • Peak GPU memory falls 12–29× (Appendix J).

Appendix G plots accuracy, robustness and latency together.

(4) When it pays (deployment guide, Appendix P):

  • Use the partition when an in-context model is already served for its accuracy and the context is append-only, signed or identifier-keyed.
  • Use it for LLM demonstrations, where embedding certified k-NN is weak: on SST-2 at radius 8, it certifies 61.0% against the partition's 89.0%.
  • Use certified k-NN for a mutable store without identifiers, under very tight latency budgets, or at large budgets (Q2).

W2. The robustness–accuracy trade-off, especially for LLMs that depend on demonstrations

  • The trade-off is predictable and controllable.
    • The new Algorithm 1 picks m from a target radius and a clean-accuracy floor, using only the learning curve.
    • Held out, the returned m meets the floor in 85–93% of cells, with median regret zero (§8, Appendix P).
  • The demonstration-dependent case.
    • With foo/bar labels, Qwen3.5-2B certifies 62.0% at radius 8 (law: 62.1%), because 16-demonstration shards sit on the steep part of the learning curve.
    • With 4× more context (2,048 demonstrations), this rises to 82.0% (law: 78.6%), and to 80.0% at radius 16.
    • With that context the partition leads embedding k-NN held out (89.2% vs 79.2% at radius 8).
  • New multi-class tasks (AG News, TREC, DBpedia):
    • With natural labels the partition certifies 78.0%, 56.0% and 79.8% at radius 8, and the law is within 3.8 points.
    • With unrelated labels and 512 demonstrations, embedding k-NN is ahead. §9 states this as a limit.
AuthorsOpenReview ↗

Response to Reviewer V52g [Part 2/2]

Q2 / W3. Budgets of 1% or 5% of the table

Setup:

  • The budget is ρ = round(f·N), on all 20 tables, under the held-out protocol.
  • We extended the partition to m = 1,024 and certified k-NN to k = 4,001.
  • We added a context-free reference: the validation majority class, which ignores the context and so is certified at every budget. A certificate is informative only where it beats this reference.
budget (% of table)0.25%0.5%1%2%5%
median radius (rows)142854109273
partition: median certified acc. (tables above context-free)86.8 (15)79.7 (14)73.2 (10)65.4 (6)0.0 (0)
certified k-NN81.7 (15)78.2 (13)74.8 (13)68.4 (10)61.0 (3)
context-free62.562.562.562.562.5
  • Up to about 0.5%, both certificates are far above the context-free reference and level with each other.
  • At 1%, both are still informative, and k-NN with very large k leads by a median 1.5 points.
  • At 5%, no method we evaluated beats the context-free predictor in the median.

Why: new Corollary 2 (§3). Under the law's assumption, a fraction f is certifiable for a query only if the learner is right on it from at most 1/(2f) rows: 50 rows at 1%, 10 at 5%. This is an inference-time form of the Lethal Dose Conjecture.

  • 5% is out of reach for any partition certificate.
  • Sample-efficient in-context learners are what make the reachable range work.
  • In absolute rows the radius still grows with the table: at 40,000 rows the partition leads on adult and shuttle at radii 4 and 16 (Appendix L).
  • The certificate targets a bounded number of malicious contributors. The abstract and §10 now say so.

W5. Theoretical novelty

The voting bound is DPA's, and we claim no new one (§2, "From training sets to inference-time contexts"). Our contribution is what a frozen model with a per-request context requires:

  • Soundness conditions, which fail in practice. TabPFN v2 changes 0.1–0.2% of shard votes when the rows are permuted.
  • Explicit pricing of feature edits (Corollary 1). Our attacks show that halving the radius is necessary.
  • A predictive theory: Prop. 3, new Corollary 2 and new Algorithm 1. DPA cannot have one, because its models must first be trained.

Under the same certificate, no classical learner beats certified k-NN, while four in-context learners fixed in advance do (Table 3).

W6. Presentation

We revised the whole paper:

  • a shorter abstract;
  • one paragraph on the relation to DPA;
  • Table 3, which gathers the robustness checks;
  • an algorithm box and a deployment-guide table (Appendix P);
  • one topic per appendix section.

Dear Reviewer V52g,

Thank you again for your detailed review and deployment questions. We wanted to check whether our response addressed your concerns. In brief:

  • Cost versus gain (Q1, W1, W4). Capping the shard count at 16 keeps the lead at radii 1–2, significant on all five splits: +0.56 and +0.93 points for the pooled in-context arm, and +0.83 and +0.22 for Mitra v2 alone at 1.4× its undefended latency (Table 10, Figure 4). The partition also keeps a mean 3.7 points more clean accuracy than certified kk-NN. We now state plainly when certified kk-NN is the better choice (Appendix P).
  • Larger budgets (Q2, W3). We tested budgets of 0.25–5% of the table (Table 19). Up to 0.5%, both certificates are well above a context-free predictor and level with each other. At 1%, certified kk-NN leads by 1.5 points. At 5%, no certificate we evaluated beats the context-free predictor in the median. The new Corollary 2 explains why this limit is structural, and §10 states it.
  • Accuracy trade-off (W2). Algorithm 1 now chooses the shard count from a clean-accuracy floor, and with more context the demonstration-dependent LLM case recovers (82.0% certified at radius 8, against 62.0% before).
  • Novelty and presentation (W5, W6). Clarified in §2; the paper was revised throughout for readability.

We would be glad to answer any remaining question. If our response resolves your concerns, we would appreciate your considering an update to your assessment.

Thank you for the additional experiments and clarifications. I appreciate the authors' efforts to address my concerns. However, three questions remain:

  1. Clean accuracy vs. robustness. While higher clean accuracy improves overall utility, I am not convinced that it directly strengthens the robustness claim, particularly when an attacker can probe multiple inputs and selectively target vulnerable queries.
  2. Cost-effectiveness. The claimed matched-compute comparison still shows substantially higher inference latency than certified k-NN, while the certified-accuracy improvements remain modest.
  3. Certification soundness. Given the reported sensitivity of TabPFN v2 to row permutations, how does the implementation ensure that modifying one row cannot affect predictions from otherwise unchanged shards?
Reviewer_SdU4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper tackles the issue of data poisoning of in-context learning at inference time. The authors propose certified context partitioning, a deterministic certification framework that partitions the support table into shards, runs the base predictor once on each shard, and takes the majority vote.

Critical strengths

(1) The paper identifies one practical security vulnerability from data poisoning. (2) The proposed certification method is straightforward. (3) The authors explicitly state the assumptions A1-A6 under which the certificate holds. The experiments cover 20 datasets, eight in-context learners.

Critical weaknesses

(1) This paper has limited technical novelty. (2) The authors provides limited evaluation on one LLM task for binary sentiment classification, which leaves a question for the generalizability to other tasks. (3) The presentation of the paper could be clearer.

Questions for authors

How can we select the shard count given a certified radius and a clean accuracy?

2 comments
AuthorsOpenReview ↗

Response to Reviewer SdU4

Thank you for the review. We answered both concrete requests, more LLM tasks and a procedure for choosing the shard count, with new experiments. Changes in the revised PDF are in blue.

W2. Only one LLM task, binary sentiment

We added three multi-class tasks, with the certificate, partitioner and law unchanged:

  • AG News (4 classes);
  • TREC (6 classes);
  • DBpedia (14 classes).

All three use natural label words. AG News and TREC also use unrelated labels (foo/bar/…), so the model can learn the task only from the demonstrations, which the adversary may poison.

The setup matches the SST-2 study: Qwen3.5-2B, 512 demonstrations, 200 queries and 2–3 seeds (one seed for the 2,048-demonstration run). The baseline is certified k-NN over frozen sentence embeddings (all-mpnet-base-v2), which is the text version of the tabular k-NN certificate.

Certified accuracy (%) at radius 8 with m = 32, the law's prediction, and the held-out lead over embedding k-NN (m and k chosen on 40% of the queries, scored on the rest):

tasklabelspartitionlawemb. k-NNheld-out lead, ρ = 1…8
AG News (4)natural78.075.469.5+4.8 to +9.4
TREC (6)natural56.055.836.7+20.9 to +23.9
DBpedia (14)natural79.876.035.8+10.4 to +47.1
AG News (4)unrelated22.222.969.0k-NN ahead
TREC (6)unrelated28.021.735.5k-NN ahead
SST-2 (2), 2,048 demosunrelated82.078.677.5+5.0 to +10.0
  • The certificate works unchanged for 4 to 14 classes. With natural labels it beats the text baseline held out at every radius on every task.
  • The law predicts each result from the learning curve alone, within 3.8 points on the natural-label tasks.
  • The limit is predictable and fixable.
    • When the demonstrations carry the task (unrelated labels), 16-demonstration shards are too small, and embedding k-NN is ahead.
    • The law predicts this in advance.
    • With 4× more context, the partition leads again.
  • A second model behaves the same way. Qwen3.5-0.8B certifies 73.2% on AG News and 56.5% on TREC.

In the paper: §9 (Table 4, "Beyond sentiment") and Appendix N.

Q1. Choosing the shard count from a target radius and clean accuracy

The new Algorithm 1 (§8; boxed in Appendix P) runs once on trusted data, because A1 requires m to be fixed in advance:

  1. Measure the per-query learning curve p_q(n) on a few random subsamples. No partition is run.
  2. For each m ≥ 2ρ*+1, predict clean and certified accuracy with the law (Prop. 3).
  3. Among the m whose predicted clean accuracy meets the floor a*, return the one with the highest predicted certified accuracy at ρ*.
  4. If no m meets the floor, report the predicted frontier, so the deployer can lower ρ* or a*.

Intuition (binary tasks). A query is certified at ρ roughly when p_q(N/m) > ½ + ρ/m. The radius pushes m up; the accuracy floor pushes it down.

What is achievable at all. The new Corollary 2 shows that certifying a fraction f of the context needs a learner that is right from at most 1/(2f) rows.

Held-out evaluation. We used 7 learners × 20 tables × 3 seeds × 5 splits, with the floor set 2 points below undefended validation accuracy:

ρ*rule returns an mmeets the floor on test (±1 pt)median m*median regret
190%93%80.0
282%91%160.0
475%89%320.0
864%86%640.0

The rule alone, with one learner fixed in advance, also gives the lead over certified k-NN in Table 3.

W1. Limited technical novelty

The voting bound is DPA's, and we claim no new one (§2, "From training sets to inference-time contexts"). Our contribution is what a frozen model with a per-request context requires:

  • Soundness conditions, which fail in practice. TabPFN v2 changes 0.1–0.2% of shard votes when the rows are permuted.
  • Explicit pricing of feature edits (Corollary 1). Our attacks show that halving the radius is necessary.
  • A predictive theory: Prop. 3, Corollary 2 and Algorithm 1. DPA cannot have one, because its models must first be trained.

Under the same certificate, no classical learner beats certified k-NN, while four in-context learners fixed in advance do.

W3. Presentation

We revised the whole paper for readability:

  • a shorter abstract;
  • one paragraph on the relation to DPA;
  • Table 3, which gathers the robustness checks;
  • an algorithm box and a deployment-guide table (Appendix P);
  • one topic per appendix section.

Dear Reviewer SdU4,

Thank you again for your review. We wanted to check whether our response addressed your concerns. In brief:

  • Choosing the shard count (Q1). The new Algorithm 1 (§8, Appendix P) returns the shard count from a target radius and a clean-accuracy floor using the learning curve alone. Held out, the returned mm meets the floor in 85–93% of cells with median regret zero (Table 27).
  • More LLM tasks (W2). We added AG News (4 classes), TREC (6) and DBpedia (14). With natural labels, the partition leads certified kk-NN over sentence embeddings at every radius from 1 to 8 on every task, held out, by 4.8 to 47.1 points (Table 4, Appendix N). We also report where it does not lead, with unrelated label words, and show that more context restores the lead.
  • Novelty and presentation (W1, W3). We clarified the relation to DPA in §2 and revised the paper for readability, with a shorter abstract, an algorithm box and a deployment guide.

We would be glad to answer any remaining question. If our response resolves your concerns, we would appreciate your considering an update to your assessment.

Reviewer_kpYaOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors study poisoning of the support context used by frozen in-context predictors. The authors adapt deep partition aggregation by dividing the context into shards and voting over the predictions. The experiments on tabular models and LLM classification show that the method has modest gains over certified k-NN on the tabular benchmark when feature edits are excluded.

Critical strengths
  1. The authors adapt an established robustness certificate to inference-time context, providing guarantees without training of models.

  2. The authors conduct experiments with multiple learners and datasets, with comparisons against certified k-NN. The adaptive attacks assess the tightness of the certificates, while the learning-curve analysis helps explain the choice of shard count.

Critical weaknesses
  1. The work builds directly on DPA with limited changes to the certification framework. The extension replaces per-partition model training with inference using a frozen pretrained model, while largely retaining DPA’s existing certification argument.

  2. The improvement over certified k-NN is limited and depends on the attack setting. In the experiments, the method was shown to have marginal improvements with conditions, making the practical benefit difficult to assess.

Questions for authors
  1. Table 2 selects both the base learner and shard count for each dataset. The gains over certified k-NN when a single base learner is fixed in advance and only the shard count is tuned are not established under the same held-out protocol.
2 comments
AuthorsOpenReview ↗

Response to Reviewer kpYa

Thank you for the review. The question about Table 2 pointed to a selection effect we had not controlled. We ran the control, and it now supports the main comparison. Changes in the revised PDF are in blue.

Q1. A single learner fixed in advance, with only the shard count tuned, under the same held-out protocol

We reran Table 2's protocol from the stored per-query votes, with no model re-run: 20 tables × 3 seeds, and each table's queries split 40/60 into validation and test. The one change is that the learner is fixed before any table is seen. Only m is chosen on validation, by the design rule. Certified k-NN chooses k (now up to 4,001) and its metric on the same queries. For each result we also count how many of five independent splits make it Holm-significant.

Margin over certified k-NN in certified accuracy (points; insertions, deletions and relabellings). Each cell gives the median over 20 tables, (tables won) and [significant splits of 5]:

learner fixed in advanceρ = 1ρ = 2ρ = 4
TabPFN v2+0.89* (14) [5/5]+0.78** (17) [5/5]+0.50 (12) [0/5]
TabPFN v3+0.72* (14) [5/5]+1.00** (16) [5/5]+0.44* (13) [2/5]
TabICL v2+0.94** (14) [5/5]+1.00** (15) [5/5]+0.39 (13) [1/5]
Mitra v2+0.39* (13) [5/5]+0.89* (16) [5/5]+1.00* (14) [2/5]
learner chosen on the other 19 tables+0.94* (14) [5/5]+0.83* (16) [5/5]+0.50 (12) [0/5]
RF / XGBoost (classical)+0.06 / +0.00 [0/5]+0.28 / +0.00 [0/5]+0.11 / −0.44 [0/5]

(* p<0.05, ** p<0.01; one-sided Wilcoxon over tables, Holm within each row.)

  • The gain does not come from choosing the learner per table.
    • Four learners fixed in advance each beat certified k-NN at radii 1–2 on all five splits.
    • So does a learner picked using only the other 19 tables.
  • The gain comes from the in-context learner. Under the same certificate, partition and protocol, no classical learner is significant on any split at any radius.
  • The scope of the claim is unchanged.
    • The lead is significant at radii 1–2.
    • Under arbitrary feature edits without row identifiers, every fixed learner is level with k-NN.
    • With identifier-keyed shards, TabPFN v2 alone leads by +0.83** and +1.50** (Appendix F).

In the paper: Table 3 and the paragraph "One learner, fixed in advance" (§6). Appendix D has the table for all 12 learners.

W1. Builds directly on DPA

The voting bound (Props. 1–2) is DPA's, and we claim no new one. §2 now says so in a dedicated paragraph. Our contribution is what makes that bound work on a frozen model whose context changes with every request, a setting DPA never meets:

  1. Soundness per request.
    • m must be fixed before the context is seen.
    • Votes must not depend on row order or on batching.
    • Both conditions fail in practice: TabPFN v2 changes 0.10–0.22% of shard votes when the rows are permuted (Appendix E).
  2. Accounting for feature edits.
    • Under content addressing a feature edit counts at half the radius; with identifier keys it counts at the full radius (Corollary 1).
    • An edit-and-relabel attack shows the halving is necessary.
  3. Prediction before deployment, which DPA cannot offer because its models must first be trained:
    • the learning-curve law (Prop. 3);
    • new Corollary 2: certifying a fraction f of the context needs a learner that is right from at most 1/(2f) rows;
    • new Algorithm 1: the shard count from a target radius and a clean-accuracy floor.

W2. The improvement is small and depends on the attack setting

  • The lead is robust. It holds for each fixed learner, on 5/5 splits, and with at most 16 shards (+0.56** and +0.93** at radii 1–2; Appendix D).
  • It is larger in clean accuracy.
    • At the configuration each method selects for radius 2, the partition's clean accuracy is a mean 3.7 points above certified k-NN's (14 of 20 tables, p = 0.002).
    • The reason: to certify, k-NN needs a large k (median 31–101).
  • We make the attack setting explicit.
    • For append-only, signed or identifier-keyed stores, the partition leads.
    • For a mutable store without identifiers, the two are level, and we recommend certified k-NN because it is cheaper (deployment guide, Appendix P).
  • The gap is large where alternatives are weak.
    • On LLM demonstrations (SST-2, radius 8), certified k-NN over sentence embeddings certifies 61.0% against the partition's 89.0%.
    • Held out on AG News, TREC and DBpedia, the partition leads at every radius from 1 to 8, by 4.8 to 47.1 points.
  • The limit is stated.
    • From about 1% of the table, certified k-NN is level with the partition or ahead.
    • At 5%, no certificate we evaluated beats a context-free predictor (§6.1, Corollary 2).

Dear Reviewer kpYa,

Thank you again for your review. As the discussion period continues, we wanted to check whether our response addressed your concerns. In brief:

  • Fixed learner (Q1). We ran the control you asked for. With one learner fixed before any table is seen and only the shard count tuned on validation, four in-context learners lead certified kk-NN at radii 1–2, Holm-significant on all five splits (Table 3, Appendix D). No classical learner does, so the lead comes from the in-context learner, not from selection.
  • Relation to DPA (W1). We now state in §2 that the voting bound is DPA's. The contribution is what a per-request context requires: soundness conditions that we show fail in practice, the pricing of feature edits, and a theory that predicts the certificate before deployment.
  • Size of the gain (W2). At the configuration each method selects, the partition also keeps a mean 3.7 points more clean accuracy than certified kk-NN (14 of 20 tables, p=0.002p = 0.002), and the deployment guide (Appendix P) states when to use which certificate.

We would be glad to answer any remaining question. If our response resolves your concerns, we would appreciate your considering an update to your assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.