{"id":"a556ce50-bb60-4251-bd06-ba5912d96f5b","arxiv_id":"2505.11183","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper claims that no polynomial-time decoder is optimal for all distributions under N-gram Hamming loss, that random sampling is consistent for sequence cross-entropy, and that temperature scaling only works at temperature one; the central lower-bound proof is invalid as written.","lead":"This paper studies whether common LLM decoding methods, such as greedy search and random sampling, can be trusted to achieve different end goals. It formalizes a split: retrieval tasks favor deterministic decoders, creative generation favors stochastic sampling, but the paper's main impossibility proof has a flaw.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's proof is invalid as written: under the stated uniform conditional distribution no node can exceed 1/|V|, so the adversarial node does not exist and the theorem is false on its literal reading; the intended distribution-free lower bound is never proved.","rationale":"The reader's rejection is substantially correct. The weakest assumption is indeed in Theorem 4.2: the proof postulates a node with conditional probability exceeding 1/|V| inside a distribution where every conditional probability is exactly 1/|V|. Literally read, the theorem is false, because uniformity makes g(y) constant and a constant-time decoder is optimal for that p. Charitably read, the authors want a distribution-free lower bound, but then the proof must construct an adversary distribution consistent with all queried values; it never does. This is not cosmetic: Corollary 4.2.1 and the abstract's central impossibility claim rest on it. I do not share the reader's certainty that the underlying claim is false; a standard adversary construction may repair it. But the submitted paper does not contain that construction, and Theorem 4.4 is close to definitional, so the theoretical novelty is not established. The cross-entropy results and simulations are fine but do not rescue the main claim. Verdict: reject as submitted; a conditional accept would require a rewritten and correct lower-bound proof.","tokens_in":20840,"tokens_out":18432,"duration_ms":185033,"concrete_test":"Implement the adversary check for Theorem 4.2: fix a deterministic decoder that makes fewer than |V|^{L-1} conditional-probability queries on the uniform distribution and record all queried (prefix, token) pairs. Determine whether there exists a prefix with at least two unqueried child tokens. If so, construct p' by raising one unqueried child to 1/|V| + delta and lowering another to 1/|V| - delta, leaving all queried nodes at 1/|V|, and verify that p' has a unique N-gram-Hamming argmax different from the decoder's output. If such p' can always be found, the lower bound can be repaired by a standard adversary argument; if not, the claimed Omega(|V|^{L-1}) bound is false.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 4.2 fixes p(y_i | y[i-1]) = 1/|V| for every prefix. Then p(y) = |V|^{-L} for every sequence and p(y_i:i+N-1) = |V|^{-N} for every N-gram, so g(y) = sum_i p(y_i:i+N-1) is constant across Y. On this distribution any fixed output is optimal; a decoder that only has to be optimal for this p runs in O(1), directly contradicting the claimed Omega(|V|^{L-1}) lower bound. Appendix B.5's key step, 'If either of these nodes have a weight more than 1/|V|', is never satisfied under the stated p. The surrounding text suggests the authors mean a decoder that is optimal for all probability distributions; for that reading the proof must exhibit an alternate distribution p' that agrees with the uniform distribution on every queried (prefix, token) pair and has a different unique N-gram-Hamming optimum. The proof does not construct p' or even state this adversary; it argues as though the actual unqueried node is already > 1/|V|. Since Theorem 4.2 and Corollary 4.2.1 are the sole support for the abstract's 'no polynomial-time algorithm is optimal for all probability distributions' claim, this is the load-bearing gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decoding of next-token predictors under two target objectives: the N-gram Hamming loss, intended to model information retrieval, and the cross-entropy loss on full output sequences, intended to model creative generation. It analyzes K-T lookahead (including greedy), random sampling, and temperature-scaled random sampling, under the assumption that the next-token predictor converges to the true conditional distribution. The paper claims (i) random sampling is consistent for the cross-entropy objective, (ii) deterministic decoders have infinite cross-entropy loss for non-deterministic targets, (iii) no polynomial-time decoder is optimal for all probability distributions for the N-gram Hamming loss, and (iv) K-T lookahead is optimal only on a restricted class of distributions. The appendix contains proofs and a simulation study on Markov chains.","tokens_in":21060,"tokens_out":11539,"duration_ms":117018,"significance":"The surrogate-loss-consistency framing for LLM decoding is a reasonable and potentially useful contribution, and the positive result that random sampling from converged next-token probabilities matches the target sequence distribution in cross-entropy is correct and cleanly proved in Appendix B.13. However, the manuscript's headline impossibility result is false as stated, and the main characterization of K-T lookahead is a tautology. Since these items support the abstract's central dichotomy and the claim that the studied decoders lack theoretical grounding outside a subset of distributions, the paper does not currently establish its main claims. If the negative results were replaced by a valid distribution-free adversary argument and a non-vacuous characterization, the framework could be valuable, but the present version is not publishable in its current form.","major_comments":[{"comment":"Theorem 4.2 is false as stated. Under the hypothesis p(y_i | y[i-1]) = 1/|V| for every prefix, every sequence has probability |V|^{-L}, every N-gram marginal equals |V|^{-N}, and the function g(y) in Lemma 4.1 is constant on Y. Consequently every output is optimal, and a decoder that always outputs a fixed sequence is optimal in O(1) time, contradicting the claimed Ω(|V|^{L-1}) lower bound. The key step in Appendix B.5, 'If either of these nodes have a weight more than 1/|V|', is never satisfied under the stated distribution. The surrounding discussion suggests the intended claim is a distribution-free lower bound, but that requires constructing an alternate distribution that agrees with the uniform conditional on every queried (prefix, token) pair and has a different unique N-gram-Hamming optimum. The proof neither states nor constructs such an adversary. Corollary 4.2.1 therefore does not follow.","section":"§4.2, Theorem 4.2 and Appendix B.5"},{"comment":"The characterization is vacuous. The set C is defined as the set of inputs x for which the sequence produced by repeatedly taking conditional arg maxs (the K-T lookahead output) equals the global arg max of g(y); the theorem then asserts that K-T lookahead is optimal iff p*_x(C)=1. This is a restatement of the definition of optimality rather than a characterization of the distributions for which the decoder is consistent. It provides no structural condition on p* that could be checked or falsified, and it does not support the conclusions drawn in the surrounding discussion or in the simulation analysis. The notation (arg max ...)_{[T]} also needs to be defined explicitly.","section":"§4.3, Theorem 4.4"},{"comment":"There is a mismatch between the consistency definition and the cross-entropy claim. Section 3 defines consistency as convergence to inf_{h:X→Y} R(h, p*, ℓ), where h is a deterministic decoder. For a non-deterministic p*, the cross-entropy risk of any deterministic h is infinite, so the infimum is +∞, while the proof of Proposition 5 shows CE(p*, p_i) → H(p*) < ∞. Under the stated definition, random sampling would not be consistent; the proof implicitly changes the benchmark to the minimum over all output distributions. Either the consistency definition must be extended to randomized decoders or to distribution-valued outputs, or Proposition 5 must be restated as distribution matching rather than consistency in the earlier sense.","section":"§5.2, Proposition 5 vs. the consistency definition in §3"}],"minor_comments":[{"comment":"The theorem says '∀i∈L'; the index set should be [L] (or {1,...,L-1} for the prefix conditionals).","section":"§4.2, Theorem 4.2 statement"},{"comment":"The sentence 'by Proposition 1 and Theorem 4.2, neither of these are consistent for all probability distributions' is misleading: Theorem 4.2 is a lower bound for optimal decoders and does not directly apply to random or temperature-scaled sampling. The inconsistency follows from Proposition 4; please correct the reference.","section":"§4.4.1"},{"comment":"The sign conventions for the constants are inconsistent: the lower bound in (1) is written as γC1 - opt, but the proof's inequality (⋆) ≥ -γ C_{2,i} + log|V|, when summed, gives a γ coefficient of -Σ C_{2,i}, which is negative, so C1 cannot be a positive integer with the stated inequality unless the constants are redefined. Please define C1, C2, C3 explicitly and verify the displayed bounds.","section":"Appendix B.15, proof of Proposition 7"},{"comment":"The figures would be easier to read with explicit axis labels and with the tie-breaking rule stated in the captions; Appendix A.3 explains the tie handling only in the text.","section":"Figures 1-6"}],"recommendation":"reject","confidential_remarks":"The stated counterexample distribution in Theorem 4.2 makes the theorem false, not merely unproven, and Theorem 4.4 is a tautology. The correct positive results on cross-entropy sampling are not sufficient to support the paper's central negative claims. A publishable revision would need a genuinely different adversary-based lower-bound proof and a substantive characterization of K-T lookahead consistency, so I recommend rejection rather than minor or major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a useful framing and one correct positive result, but the central impossibility theorem is false as stated, so the headline claim doesn't hold up.\n\nWhat's actually new: applying surrogate-consistency thinking to LLM decoders is a genuinely helpful way to organize the problem. The N-gram Hamming loss is a defensible proxy for retrieval-style goals, and the deterministic-vs-stochastic dichotomy is a clean conceptual takeaway: deterministic decoders can be consistent for Hamming loss, while stochastic sampling is necessary for the cross-entropy objective. The random-sampling consistency result (Prop 5) is correct by a direct KL argument. The temperature-scaling rate bounds (Prop 7) are a useful addition, even if they are qualitative. The simulation study is careful and the tie-handling discussion is honest.\n\nThe soft spot is fatal. Theorem 4.2, the paper's main negative result, is false as stated. The distribution in the theorem has every conditional uniform at 1/|V|. Then every sequence has probability |V|^{-L}, and every N-gram has marginal |V|^{-N}, so g(y) is constant and every output is equally optimal for N-gram Hamming loss. A decoder that simply emits a fixed sequence in O(L) time is optimal for that distribution, which directly contradicts the claimed Ω(|V|^{L-1}) lower bound. The proof in Appendix B.5 needs a node with weight strictly above 1/|V|; under the stated distribution no such node exists. The surrounding text hints at an intended distribution-free adversary with small perturbations, but that adversary is never constructed and the theorem as written is wrong.\n\nTheorem 4.4 is also weaker than it looks: C is defined as the set of inputs where lookahead already matches the global arg max, so the equivalence is essentially a restatement of optimality.\n\nThe positive results stand, and the paper is worth reading for the framing alone. But the abstract's claim that no polynomial-time algorithm is optimal for all distributions is unsupported. I would not cite the paper for that result. A serious editor could still send this to review, because the topic is timely and the flaw is potentially repairable, but I would want the lower bound actually proved (or the claim dropped) before recommending publication.","headline":"Interesting framing and one correct positive result, but the central impossibility theorem is false as stated, so the headline claim does not hold up.","tokens_in":21626,"tokens_out":4434,"would_cite":false,"duration_ms":37692,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that LLM decoding algorithms are consistent only when matched to their end goal: deterministic search for information retrieval, random sampling for creative generation.","keywords":["next-token prediction","decoding algorithms","large language models","surrogate loss consistency","N-gram Hamming loss","cross-entropy loss","information retrieval","creative generation"],"falsifier":"Under the distribution p(y_i | y_{<i}) = 1/|V|, calculate g(y) for any two sequences: both equal (L-N+1) * |V|^{-N}. Because g is constant, the sequence 'aaaa...a' is an optimal output and can be produced without any next-token queries, so the claimed runtime lower bound of $\\Omega$(|V|^{L-1}) fails for this distribution.","tokens_in":20574,"feed_emoji":"🎲","tokens_out":13824,"duration_ms":113125,"temperature":0.7,"pith_summary":"The paper asks whether standard LLM decoding algorithms—greedy, lookahead, random sampling, and temperature-scaled sampling—are consistent for the two main ways people use language models: retrieving a correct answer and generating fresh samples from a distribution. It argues that these goals impose opposite requirements on decoders: deterministic algorithms are the only ones that can be optimal for a retrieval-style N-gram Hamming loss, while random sampling is necessary and sufficient to reproduce the true sequence distribution under cross-entropy loss. The paper also claims that optimal decoding for the retrieval objective is computationally hard in the worst case, requiring exponential time in sequence length for at least one next-token distribution. The practical upshot is that decoder choice should track user intent, and many common decoders lack theoretical grounding outside narrow classes of distributions.","feed_headline":"Retrieval needs deterministic decoding; generation needs sampling","feed_subtitle":"Random sampling matches true distributions; optimal retrieval decoding is exponentially hard.","key_machinery":"The central objects are the reformulated expected risk R(D, p, p_ntp, ell), which averages the loss over inputs, true outputs, and the decoder's randomized outputs, and the N-gram Hamming loss defined as the sum of indicators that each length-N block of the predicted sequence differs from the true block. The load-bearing identity is Lemma 4.1: minimizing this expected loss is equivalent to maximizing g(y) = sum_{i=1}^{L-N+1} p(y_{i:i+N-1}), the sum of N-gram marginals, which generalizes the known optimal-output characterizations for Hamming and 0-1 loss. This identity turns decoding into a combinatorial maximization problem on a tree of conditional probabilities, and it is the engine behind both the optimality characterization of K-T lookahead and the exponential lower bound. The dichotomy between retrieval and generation is carried by the difference between point-mass output distributions (deterministic decoders) and distributions that replicate the true sequence distribution (random sampling): the former can win on the N-gram objective but have infinite cross-entropy to non-deterministic targets, while the latter match the cross-entropy optimum but necessarily put mass on suboptimal sequences for retrieval.","core_discovery":"On the paper's own terms, the central discovery is a formal inconsistency dichotomy. Fix a true next-token distribution p* and assume the trained predictor converges to it in KL divergence. For the N-gram Hamming loss—a sum over whether each length-N block of the decoded sequence matches the true block—the optimal output is the sequence maximizing the sum of N-gram marginal probabilities (Lemma 4.1). Deterministic decoders such as K-T lookahead can be consistent for this loss, but only on a restricted class of distributions characterized by a greedy-optimality condition (Theorem 4.4); and no deterministic decoder can be consistent everywhere, because the paper exhibits a distribution for which any optimal deterministic or stochastic decoder must query $\\Omega$(|V|^{L-1}) next-token probabilities, yielding an exponential-time lower bound (Theorem 4.2, Corollary 4.2.1). For the cross-entropy loss on whole sequences, the situation flips: deterministic decoders incur infinite expected loss whenever the true sequence distribution is non-deterministic, while random sampling is consistent for every distribution (Proposition 5), and temperature scaling with parameter gamma != 1 recovers the true distribution only in uniform or deterministic cases (Proposition 6). Taken together, the paper claims that retrieval and generation are not served by the same decoding strategy.","pith_inferences":["The consistency argument for random sampling does not actually depend on the specific sampling order; any method that produces a sequence with probability equal to the product of the true conditionals will be cross-entropy consistent, so the result extends to other ancestral sampling schemes.","The N-gram Hamming framework can be applied to other N-gram-based evaluation metrics that are not simple sums of indicators, such as BLEU or ROUGE, by replacing the loss with a smoothed or clipped variant; the optimal-output characterization would need to be re-derived for those non-additive losses.","The exponential lower bound is stated for a fully uniform conditional distribution; a natural testable extension is whether the bound survives arbitrarily small perturbations away from uniform, since in the exact uniform case any fixed output is already optimal.","The dichotomy suggests a testable design principle for adaptive decoding: algorithms that shift continuously between deterministic and stochastic behavior, such as temperature adjustment, will be consistent for at most one of the two objectives unless the true distribution is degenerate."],"forward_implications":["If the next-token predictor converges to the true distribution, then random sampling is consistent for the goal of generating samples from the true sequence distribution under cross-entropy loss, for every input distribution.","For information retrieval, there is no polynomial-time decoding algorithm that is optimal for all probability distributions; optimal N-gram Hamming decoding requires exponential time in sequence length in the worst case.","K-T lookahead, including greedy and beam search variants, is consistent for N-gram Hamming loss exactly on the set of distributions where the greedy path coincides with the global maximizer of the N-gram marginal sum; outside that set it can be suboptimal.","Increasing lookahead depth K or decreasing the number of committed tokens T does not, in general, enlarge the class of distributions for which K-T lookahead is consistent.","Temperature-scaled random sampling with gamma != 1 is consistent with the true sampling distribution only for uniform or deterministic distributions, and its suboptimality gap in cross-entropy grows at a rate linear in gamma."],"supporting_citations":[{"why":"Supplies the known optimal-output characterization for Hamming and subset 0-1 loss that Lemma 4.1 extends to N-gram Hamming loss.","marker":"Dembczyński et al., 2010"},{"why":"Provides the surrogate-loss consistency framework that the paper adapts to next-token decoding.","marker":"Bartlett et al., 2006"},{"why":"Extends the consistency framework to multiclass losses, informing the reformulated expected risk.","marker":"Tewari and Bartlett, 2007"},{"why":"Introduces BLEU and N-gram-based evaluation, motivating the N-gram Hamming loss as a tractable proxy.","marker":"Papineni et al., 2002"},{"why":"Introduces ROUGE-N, further motivating N-gram metrics in sequence evaluation.","marker":"Lin, 2004"}],"fun_headline_variants":["Decoding split: deterministic for retrieval, random for generation","Random sampling matches true distribution; retrieval decoding is hard","No single decoder works for all goals: retrieval vs generation","Sampling for generation, deterministic for retrieval: the decoder split"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hardness theorem assumes that a decoder facing a perfectly uniform next-token distribution must still search for a high-probability continuation, even though in that distribution every continuation is equally probable and every output is optimal.","fun_headline_variants_meta":{"raw":{"variants":["Decoding split: deterministic for retrieval, random for generation","Random sampling matches true distribution; retrieval decoding is hard","No single decoder works for all goals: retrieval vs generation","Sampling for generation, deterministic for retrieval: the decoder split"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000395,"raw_usage":{"total_tokens":2129,"prompt_tokens":1061,"completion_tokens":1068,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":677,"completion_tokens_details":{"reasoning_tokens":1001}},"tokens_in":677,"tokens_out":1068,"duration_ms":10193,"temperature":1.0,"reasoning_tokens":1001,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:56:50.975509+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Under the distribution p(y_i | y_{<i}) = 1/|V|, calculate g(y) for any two sequences: both equal (L-N+1) * |V|^{-N}. Because g is constant, the sequence 'aaaa...a' is an optimal output and can be produced without any next-token queries, so the claimed runtime lower bound of $\\Omega$(|V|^{L-1}) fails for this distribution.","supporting_citations":[{"cited_title":"L., Jordan, M","cited_arxiv_id":null,"evidence_quote":"Provides the surrogate-loss consistency framework that the paper adapts to next-token decoding."},{"cited_title":"and Bartlett, P","cited_arxiv_id":null,"evidence_quote":"Extends the consistency framework to multiclass losses, informing the reformulated expected risk."}],"review_version":1}