{"id":"c925e734-61b3-430b-8389-370bdd2f69e7","arxiv_id":"2509.15676","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"KITE greedily selects in-context examples by maximizing a kernelized query-specific relevance score plus a D-optimal design diversity term, and reports accuracy gains over KATE, BM25, and DPP baselines on five classification benchmarks.","lead":"This paper introduces KITE, an algorithm that selects few-shot examples for an LLM prompt by treating the model as a linear regressor and greedily choosing examples that minimize predicted error on the user query while adding diversity. A generalist would read it as a theory-flavored attempt to replace nearest-neighbor exemplar retrieval with an optimization-based selection method.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's approximate-submodularity bound is false: an explicit 2D instance gives γ=0.6 while the lemma predicts γ≥0.714, so Theorem 4's approximation guarantee is unsupported.","rationale":"After reading the full manuscript, the most load-bearing defect is internal rather than a modeling disagreement. Lemma 3 is the sole bridge from the surrogate objective f_z to the greedy approximation guarantee in Theorem 4, and the lemma's stated lower bound is contradicted by an explicit finite-dimensional instance. The appendix proof's uncontrolled truncation is not a stylistic gap: the missing higher-order terms change the correction substantially, and the exact ratio falls below the claimed bound. This invalidates the provable-guarantee claim that distinguishes KITE from heuristic retrievers. A repaired proof would need a different argument, and the current manuscript would need to drop 'provable' or 'guarantee' language. The empirical section separately has weaknesses, including best-of-three-kernel reporting on the evaluation split and no error bars, but the theoretical counterexample is sufficient to justify rejection. I therefore agree with the reader's REJECT verdict; the reader's stated weakest assumption, the linear-model premise, is related but not the same as the concrete proof failure demonstrated here, so my agreement with that specific identification is partial.","tokens_in":19637,"tokens_out":17440,"duration_ms":140155,"concrete_test":"Independently compute the exact submodularity ratio for the 2D instance x1=(1,0), x2=(0.8,0.6), z=(0.6,-1.8), β=1, k=2, using the definition γ=(Δ1+Δ2)/(f_z(S∪L)-f_z(S)) with f_z(S)=-z^T V_S^{-1} z. Direct matrix inversion gives γ=0.6<0.714, so the Lemma 3 bound fails. As a robustness check, run a random search over d∈{2,3}, unit-norm x_i, arbitrary z, and β>0 to see whether any configuration satisfies the stated bound; if violations are found, Lemma 3 and Theorem 4 must be corrected or removed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim, that greedy maximization of f_z(S)=-z^T V_S^{-1} z carries a 1-exp(-1/(1+(k-1)μ)) approximation guarantee, rests entirely on Lemma 3, and Lemma 3 is not merely unproved; it is false. Take d=2, β=1, S=∅, k=2, x1=(1,0), x2=(0.8,0.6), z=(0.6,-1.8). Then V_S=I, so μ=|x1^T x2|/(sqrt(1+||x1||^2) sqrt(1+||x2||^2))=0.8/2=0.4. The individual marginal gains are Δ1=(z·x1)^2/(1+||x1||^2)=0.18 and Δ2=(z·x2)^2/(1+||x2||^2)=0.18. The joint gain is f_z(S∪L)-f_z(S)=||z||^2 - z^T(I+x1x1^T+x2x2^T)^{-1}z = 3.6-3.0=0.6. Hence the submodularity ratio is γ=(Δ1+Δ2)/0.6=0.6, while Lemma 3 requires γ≥1/(1+(k-1)μ)=1/1.4≈0.714. The appendix proof fails because it replaces (I+D+N)^{-1} by a two-term Neumann expansion and then treats the resulting expression as exact; the omitted terms are essential, and here the exact ratio falls below the claimed bound. Consequently Theorem 4's approximation guarantee is not established, and the provable near-optimality advertised in the abstract is unsupported. The empirical algorithm may still be useful and the synthetic experiments are suggestive, but the manuscript's central theoretical contribution is invalid as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes KITE, an unsupervised exemplar-selection method for in-context learning (ICL). It models the LLM as a linear function of input embeddings (Eq. (1)) and selects k examples to minimize a ridge-regression prediction-error bound for a query z, yielding the surrogate objective f_z(S) = -z^T V_S^{-1} z (Eq. (4)). A D-optimal-design diversity term log det(V_S) is added, and the method is kernelized so that computations are done through kernel evaluations. The central theoretical claim is Lemma 3, which lower-bounds the submodularity ratio of f_z by 1/(1+(k-1)μ), leading to a 1-exp(-1/(1+(k-1)μ)) greedy approximation guarantee in Theorem 4. Empirically, KITE is evaluated on five classification datasets with three LLMs against Random, BM25, Dense, and DPP baselines, with Table 1 reporting accuracy for each setting.","tokens_in":20032,"tokens_out":6124,"duration_ms":50736,"significance":"If the theoretical guarantee were valid, the paper would make a useful contribution: it offers a query-specific, computationally efficient selection rule with a clean diversity regularizer and a clear departure from kNN-style retrieval. The algorithmic machinery (Sherman-Morrison updates, kernel trick, D-optimal design) is presented cleanly, and the synthetic experiments provide some evidence that the score is sensible under the stylized linear model. However, the central guarantee does not hold: Lemma 3 is false, and the appendix proof explicitly truncates a Neumann-series expansion and then treats the truncated expression as exact. The empirical comparison is also compromised by per-dataset kernel selection on the evaluation split and by the absence of error bars. As a result, the advertised provable near-optimality is unsupported, and the empirical claims are not established at the reported level of confidence.","major_comments":[{"comment":"The claimed lower bound γ_k(f_z) ≥ 1/(1+(k-1)μ) is false. Consider d=2, β=1, S=∅, k=2, x1=(1,0), x2=(0.8,0.6), z=(0.6,-1.8). Then V_S=I, μ=0.4, Δ1=Δ2=0.18, and f_z(S∪L)-f_z(S)=0.6, so the submodularity ratio is γ=0.6, which is strictly less than the claimed bound 1/1.4≈0.714. The appendix proof replaces (I+D^{-1}N)^{-1} by a two-term Neumann expansion and then treats the result as exact; the omitted terms are essential, as this counterexample shows. Consequently Theorem 4's approximation guarantee is not established, and the abstract's claim of a principled greedy algorithm with an approximation guarantee is unsupported.","section":"Lemma 3 and Appendix: Proof of Lemma 3"},{"comment":"The headline empirical claim 'KITE consistently outperforms all baselines' is weakened by reporting the best result across the three kernel choices for each dataset on the same validation split used for evaluation. Table 3 shows that the kernel choice changes accuracy by up to 8 percentage points (e.g., MRPC: 75.27 for the linear kernel vs. 67.15 for the Gaussian RBF). Selecting the best kernel per dataset on the evaluation split is a form of test-set tuning, and the comparison to baselines, which do not receive this per-dataset kernel selection, is therefore not a fair test of the method. In addition, Tables 1, 3, and 4 report no error bars or multiple-seed variances, so the significance of differences of 0.1-1.7 points is unclear.","section":"Section 5 (Implementation Details) and Table 1"},{"comment":"The empirical validation does not compute the quantity in Definition 2. It samples a random triplet (S,L,z) with L selected by farthest-point sampling and reports the minimum observed ratio, but Definition 2 requires a minimum over all disjoint S,L with |L|≤k, with no restriction on how L is formed. The reported γ_min therefore cannot certify an approximate-submodularity ratio for f_z. Moreover, because Lemma 3 is false, the empirical table does not repair the theoretical guarantee and should not be presented as evidence that the greedy approximation bound holds.","section":"Section 5 (Empirical validation of submodularity) and Table 2"},{"comment":"The modeling premise—that LLM in-context responses are generated by a fixed linear function in BERT embedding space—is not validated by any experiment that compares the surrogate f_z(S) with actual LLM accuracy. The synthetic experiments verify the linear model only, not the transfer to LLMs. A concrete test would be to compare, on a held-out subset of queries, the ridge prediction error of selected sets against the LLM's prompt accuracy; without such evidence, the connection between the objective being optimized and the accuracy metric reported in Tables 1 and 3 remains an untested assumption.","section":"Section 3, Eq. (1)"}],"minor_comments":[{"comment":"There are several typos: 'emty set' in Algorithm 1, 'embddings' in the experiments section, and 'diagonmal' in the appendix proof should be 'empty set', 'embeddings', and 'diagonal', respectively.","section":"Throughout"},{"comment":"The right block of Table 4 appears to have a formatting or unit error: the reported LITE errors for μ_test=0,...,5 are in the range 67.8-84.0, which is inconsistent with the left block's scale (0.7-4.2) and with the text describing mean absolute prediction error.","section":"Table 4"},{"comment":"The proof invokes the condition ∥D^{-1}N∥≪1 without stating or verifying it; if Lemma 3 is to be salvaged, the statement should be revised to include an explicit small-coherence or small-norm assumption and the Neumann expansion should be carried out with a rigorous error bound.","section":"Appendix, Proof of Lemma 3"},{"comment":"The symbol β is used both as the ridge regularization parameter in Eq. (2) and as the noise variance in the mutual-information derivation in Section 4; the two uses should be distinguished notationally.","section":"Sections 3 and 4"},{"comment":"The notation for the submodularity ratio is inconsistent: Definition 2 uses γ_k(f), the main text later uses γ, and Table 2 uses γ_min; these should be unified.","section":"Definition 2 and Table 2"}],"recommendation":"reject","confidential_remarks":"The central theoretical result is contradicted by a simple explicit 2D counterexample, and the empirical design further compromises the headline comparisons by selecting the best kernel per dataset on the evaluation split. Even a thorough revision would need to remove the provable-guarantee claim and re-evaluate the experiments with honest kernel selection and variance reporting; as such, I recommend rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's central claim is a provable near-optimality guarantee for a query-specific exemplar retriever built on a ridge-regression surrogate plus a D-optimal diversity term. The concrete algorithm is new and the experiments show real gains, but the theory doesn't hold up: Lemma 3, which the whole guarantee rests on, is false as stated.\n\nWhat is actually new and does well: combining a query-specific ridge-regression objective with kernelized greedy marginals and a D-optimal diversity regularizer is a clean, principled departure from kNN and DPP heuristics. The synthetic linear-model experiments confirm the surrogate behaves as intended in the stylized setting, and the real-LLM evaluation spans five datasets and three models with ablations for kernel choice and lambda. The citation pattern looks fine; related work is adequately covered.\n\nThe soft spots are serious. Lemma 3's lower bound on the submodularity ratio is not just missing a step; it's false. An explicit 2D instance with beta=1, x1=(1,0), x2=(0.8,0.6), z=(0.6,-1.8) gives gamma=0.6, while the lemma claims gamma >= 0.714. The appendix proof truncates a Neumann series and then treats the approximation as an exact identity, which is where the argument goes wrong. Since Theorem 4 depends entirely on this lemma, the advertised 1-exp(-1/(1+(k-1)mu)) approximation guarantee is unsupported. That's a load-bearing flaw, not a cosmetic gap.\n\nOn the empirical side, without error bars and with the best of three kernels chosen on the evaluation split, the 13/15 win count is weaker than it appears. The gains over DPP are single-digit, so variance matters. The linear-in-BERT-embeddings assumption in Eq. (1) is strong, but the paper treats it as a motivation for the surrogate rather than a claim about LLM internals, so I don't see that as fatal on its own.\n\nThe right fix is to either repair Lemma 3 with a correct bound or drop the provable-guarantee language and present KITE as an empirically motivated algorithm. Given the novelty of the recipe and the solid experimental scaffolding, I think this deserves a serious referee—major revision, not acceptance as is. I'd bring it to reading group, and I'd cite it only after the theory is sorted.","headline":"KITE is a genuinely new ICL retrieval recipe with real empirical gains, but the paper's headline theoretical guarantee rests on a false lemma and should not be published as is.","tokens_in":20578,"tokens_out":3307,"would_cite":false,"duration_ms":26951,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"KITE frames in-context example selection as a query-specific optimization problem, proves an approximate-submodularity guarantee for greedy selection, and reports the best accuracy in 13 of 15 dataset-model settings.","keywords":["in-context learning","example selection","exemplar retrieval","submodular optimization","kernel trick","D-optimal design","few-shot classification"],"falsifier":"A benchmark where the label depends on an XOR or parity function of embedding coordinates, with a fixed kernel chosen before seeing any validation labels, would settle the claim: if the linear version of KITE fails to beat dense kNN or DPP retrieval, or if kernel choices made without the evaluation split reverse the reported ranking, then the optimized quantity does not track actual prompt accuracy.","tokens_in":19449,"feed_emoji":"🎯","tokens_out":11795,"duration_ms":93316,"temperature":0.7,"pith_summary":"The paper is trying to establish that the choice of in-context examples for an LLM can be made by a principled, fully unsupervised rule rather than by nearest-neighbor heuristics. It models the LLM as a linear function of the input embeddings and selects the subset of exemplars that minimizes a query-specific ridge prediction error, then adds a diversity regularizer. It proves the resulting objective is approximately submodular, so greedy selection carries a near-optimality guarantee. On five classification datasets and three models, the proposed selector, KITE, reports the highest accuracy in 13 of 15 settings.","feed_headline":"KITE beats nearest-neighbor ICL baselines on 13 of 15 tasks","feed_subtitle":"The method models prompt selection as query-specific ridge regression plus a diversity term, with no retraining.","key_machinery":"The central object is the design covariance matrix $V_S=\\beta I+\\sum_{i\\in S}x_i x_i^\\top$ and the greedy marginal gain it defines. For a candidate example $x$ given current set $S$, the relevance gain is $(z^\\top V_S^{-1}x)^2/(1+x^\\top V_S^{-1}x)$, and the Sherman-Morrison formula updates $V_S^{-1}$ in $O(d^2)$ per step. The kernel trick replaces every inner product with a kernel evaluation, turning the gain into $k_S(z,x)^2/(\\beta+k_S(x,x))$, where $k_S$ is the residual kernel after projecting out the selected examples. Diversity enters through the D-optimal design gain $\\log(1+x^\\top V_S^{-1}x)$, and the algorithm maximizes the sum of the relevance and diversity gains with trade-off parameter $\\lambda$. The proof machinery is the submodularity ratio $\\gamma_k(f_z)$, lower-bounded by $1/(1+(k-1)\\mu)$, which certifies near-optimality of the greedy selection.","core_discovery":"Conditioned on a test query $z$, the paper claims that the LLM's response is generated as $y=\\langle x,\\theta\\rangle+\\eta$ with $\\eta\\sim N(0,1)$, so the best prompt subset is the one that minimizes the ridge prediction error at $z$. The paper bounds that error by $\\|z\\|_{V_S^{-1}}^2$ with $V_S=\\beta I+\\sum_{i\\in S}x_i x_i^\\top$ and proposes maximizing $f_z(S)=-z^\\top V_S^{-1}z$. Because $f_z$ is only approximately submodular, the paper bounds its submodularity ratio below by $1/(1+(k-1)\\mu)$ and proves greedy selection achieves a $1-e^{-1/(1+(k-1)\\mu)}$ approximation factor. The kernel trick rewrites the greedy gain using only kernel evaluations, and the D-optimal term $\\log\\det(V_S)$ adds diversity. The empirical claim is that the combined algorithm, KITE, outperforms random, BM25, dense kNN, and DPP retrieval on most of the 15 dataset-model configurations.","pith_inferences":["A natural stress test would run KITE on tasks with known non-linear ICL behavior, such as parity or compositional reasoning; the theory predicts the linear version should lose its edge over nearest-neighbor retrieval there.","The reported protocol selects the best kernel per dataset on the evaluation split; a deployment-oriented version would choose kernels without validation labels, and that version is what a user would actually run.","The same query-specific ridge objective might double as a selection rule for other few-shot pipelines beyond LLMs, such as retrieval-augmented prediction, wherever the downstream predictor is approximately linear in the chosen representation."],"forward_implications":["KITE can be deployed as a frozen retriever: it needs only embeddings and a kernel, no labels at selection time, no fine-tuning, and each greedy step costs $O(d^2)$.","The $\\log\\det(V_S)$ diversity term is not decorative: on the MNLI ablation, pure relevance selection ($\\lambda=0$) underperforms a balanced $\\lambda$, so large redundant banks require diversity.","The best kernel is dataset-dependent; the reported gains come from picking among linear, polynomial, and Gaussian kernels, so kernel choice is part of the method's recipe.","The greedy guarantee degrades gracefully with the submodularity ratio, and increasing $\\beta$ pushes the ratio toward 1, making the selected set closer to the optimal one in the theory."],"supporting_citations":[{"why":"Defines the kNN-based KATE baseline (top-k dense retrieval) that KITE is designed to improve on.","marker":"Liu et al. 2021"},{"why":"The DPP-based compositional exemplar method; it is the strongest baseline and the diversity-aware competitor KITE must beat.","marker":"Ye et al. 2023a"},{"why":"Supplies the submodularity-ratio definition and the greedy bound that Theorem 4 adapts with Lemma 3.","marker":"Das and Kempe 2011"},{"why":"Gives the confidence-bound argument (Chapter 20) connecting prediction error to $\\|z\\|_{V_S^{-1}}^2$ and hence to the objective $f_z$.","marker":"Lattimore and Szepesvári 2020"},{"why":"Provides the RKHS and kernel-trick background used to lift the selection rule from linear to kernelized features.","marker":"Schölkopf and Smola 2002"},{"why":"Supplies the pre-trained transformer embeddings used to represent queries and examples in all experiments.","marker":"Devlin et al. 2019"}],"fun_headline_variants":["KITE: query-specific prompt selection beats kNN on 13/15","Ridge regression for prompt selection: KITE outperforms kNN baselines","KITE: diverse exemplars via kernel and D-optimal design","Information-theoretic ICL: KITE minimizes query-specific error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that, conditioned on a test query, an LLM's in-context prediction is close enough to a linear function of the input embeddings that minimizing the ridge prediction error at that query also minimizes actual prompt error; if that approximation fails, the objective $f_z(S)$ no longer tracks the quantity the paper reports.","fun_headline_variants_meta":{"raw":{"variants":["KITE: query-specific prompt selection beats kNN on 13/15","Ridge regression for prompt selection: KITE outperforms kNN baselines","KITE: diverse exemplars via kernel and D-optimal design","Information-theoretic ICL: KITE minimizes query-specific error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000386,"raw_usage":{"total_tokens":2103,"prompt_tokens":1074,"completion_tokens":1029,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":690,"completion_tokens_details":{"reasoning_tokens":951}},"tokens_in":690,"tokens_out":1029,"duration_ms":8469,"temperature":1.0,"reasoning_tokens":951,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:50:35.759886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A benchmark where the label depends on an XOR or parity function of embedding coordinates, with a fixed kernel chosen before seeing any validation labels, would settle the claim: if the linear version of KITE fails to beat dense kNN or DPP retrieval, or if kernel choices made without the evaluation split reverse the reported ranking, then the optimized quantity does not track actual prompt accuracy.","supporting_citations":[],"review_version":2}