{"id":"b62e8a1c-87a1-4151-9b61-fb507667d19e","arxiv_id":"2507.02689","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper claims a first convergence proof for LLM-based black-box optimizers, but the key lemma is proven by assertion rather than derivation.","lead":"This paper models the iterative LLM optimizer as a finite-state Markov chain and claims it converges to the global optimum under elitist sampling. The central proof step, a claimed positive transition probability into the optimal state set, appears asserted rather than derived, so the guarantee is not established.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's proof of P2 positivity is a non-sequitur: upper-triangular P4 only gives a better non-optimal successor, not a transition into S*, so Theorem 2's almost-sure convergence relies on an unstated reachability assumption.","rationale":"The reader identified the correct load-bearing weakness. The central convergence claim in Theorem 2 depends on P2 having at least one positive entry in every column: Appendix D uses this to show each column of P4 sums to less than 1, hence ρ(P4)<1 and P4^∞=0. The only support for this property is Lemma 2, whose Appendix C proof derives upper triangularity of P4 and P3=0, then jumps from a positive transition to some higher-ranked state to the existence of a positive transition into S*. That jump is logically invalid because the higher-ranked state may itself be non-optimal. The concern is not a disagreement with community consensus; it is an internal proof gap at the exact point where the paper's strongest claim is established. The paper does contain useful independent material: the Markov-chain modeling in Theorem 1 is a reasonable formalization, and the numerical experiments are extensive, but they do not supply the missing analytical reachability condition. I also note that the gap may be repairable through the positive-probability structure of (9)-(10), but as written the proof does not invoke or establish that, and the multi-LLM convergence-rate theorem inherits the unsupported premise.","tokens_in":26198,"tokens_out":10770,"duration_ms":132380,"concrete_test":"Construct the three-state counterexample to Appendix C: let states be sorted o≻a≻b with S*={o}, S'={a,b}, and define a column-stochastic transition matrix with P1=[1], P3=0, P2=[0,0], and P4=[[1,p],[0,1-p]] for p∈(0,1), where rows and columns index a then b. This satisfies every property Lemma 2 actually proves before its final inference (P1/P4 upper triangular, P3=0), yet the chain has zero probability of ever entering S*. This demonstrates that 'P4 upper triangular' does not imply 'P2 has a positive entry in each column.' Then decide whether Assumptions 1-2 plus (9)-(10) imply pL(TBPE(X*)|non-optimal examples)>0 for some X*∈S*; if they do, the gap is repairable by adding that explicit reachability argument; if not, Theorems 2 and 3 are unsupported as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix C's proof of Lemma 2 asserts that because P4 is upper triangular, \"for some s ≻ s˜, p_{s˜s} has at least one positive value,\" and then concludes that P2 has at least one positive entry in each column. This does not follow: an upper-triangular P4 only guarantees a move to a higher-ranked state inside S', not a state in S*. A three-state example with one optimal state o and two non-optimal states a,b, where p(a|b)>0, p(b|b)=1-p(a|b), p(a|a)=1, p(b|a)=0, and no transitions from a or b to o, satisfies the properties that Appendix C actually derives (P1/P4 upper triangular, P3=0) while P2 is identically zero, so the LLMO can remain in the non-optimal block forever. Theorem 2's proof in Appendix D uses exactly the missing property: P2 must have a positive entry in each column so that every column of P4 sums to less than 1, making (I-P4)^{-1} valid and P4^∞=0. The paper never proves the required reachability of S*; Assumptions 1-2 only ensure the relevant tokens are in the restricted vocabulary and that numbers have finite precision, not that from every non-optimal in-context example the LLM places positive probability on at least one optimal action population. A repair is conceivable from the softmax positivity in (9)-(10), but the paper does not make that argument, and the multi-LLM results in Theorem 3 inherit the same gap through Lemma 2.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a Markov chain model for the LLM optimizer (LLMO) framework applied to black-box network management. The authors formalize the tokenization of action populations, define a finite state space, and prove (Theorem 2) that with elitist sampling the LLMO converges almost surely to a state containing a globally optimal action, regardless of the convexity of the reward function or the initial distribution. They then extend the analysis to a multi-LLM architecture (Section IV), deriving an average convergence rate that decreases exponentially with the number of identical LLMs (Theorem 3). The theoretical claims are supported by extensive simulations on interference channels, broadcast channels, and massive MIMO systems using several LLMs.","tokens_in":26551,"tokens_out":12594,"duration_ms":141917,"significance":"If the theoretical results were correct, this would be a valuable first rigorous foundation for LLM-based black-box optimizers, justifying the widely observed empirical success of elitist sampling and multi-LLM designs. The paper also contributes a clean tokenizer-level state space construction and a broad experimental study. However, as the major comments detail, the central convergence proof and the multi-LLM transition analysis contain load-bearing gaps. The significance is therefore conditional on a successful revision; the current manuscript does not establish its advertised claims.","major_comments":[{"comment":"The proof that P2 has at least one positive entry per column is a non-sequitur. Upper-triangularity of P4 only implies that from a non-optimal state there is a positive transition to some higher-ranked state; it does not imply that this state lies in the optimal set S*. For example, order states as o ≻ a ≻ b with o optimal and a,b non-optimal, and set p(a|b)=ε, p(b|b)=1-ε, p(a|a)=1, with no transitions from a or b to o. Then P4 is upper triangular and P3=0, yet P2 is identically zero. The proof of Theorem 2 in Appendix D relies precisely on the column sums of P4 being less than 1, which requires the unproven P2 positivity. Thus the almost-sure convergence claim is unsupported.","section":"Appendix C, Lemma 2"},{"comment":"The identity s(t) = max{s(t)_1, ..., s(t)_L, s(t-1)} in (20) is incorrect for P>1. The elitist sampler selects the P best actions from the union of the L generated populations and the previous in-context examples, which is not the lexicographic maximum of states as defined in Definition 4. For instance, with P=2, let state A have rewards (10,1) and state B have rewards (9,8). The lexicographic maximum is A, but the top two actions from the union are (10,9), a state different from both A and B. Consequently, the transition probability formula (19) and the subsequent convergence-rate conclusions in Theorem 3 are not established.","section":"Section IV-A, Lemma 3"},{"comment":"The theorem claims convergence regardless of the convexity of the reward function or the initial distribution, but the proof assumes, through Lemma 2, that from every non-optimal state there is a positive transition to an optimal state. This reachability is not implied by Assumptions 1-2, which only ensure token availability and finite precision. The softmax positivity in (9)-(10) could provide such a guarantee if the restricted vocabulary set T contains all tokens in (13), but this argument is not made, and the notation T is ambiguous because it is reused for the restricted sampling vocabulary in (9) and the token set in (13). The proof therefore effectively assumes the very reachability that it sets out to establish.","section":"Section III-C, Theorem 2"}],"minor_comments":[{"comment":"The symbol T is used both for the restricted sampling vocabulary in (9) and for the set of relevant tokens in (13). Please disambiguate these two sets, for example by using T_samp and T_tok.","section":"Section III-A, equations (9) and (13)"},{"comment":"The sentence 'We need three extra tokens for the decimal point, minus sign, comma, and newline character' lists four items; clarify that the comma and newline are alternative separators for the CSV format, so that the total number of extra tokens is three.","section":"Appendix A"},{"comment":"The state ordering should be stated explicitly as a lexicographic order on the sorted reward sequences of the P actions; the current formulation is informal and could lead to ambiguity.","section":"Definition 4"},{"comment":"The proof uses conditional independence of s(t)_l for l=1,...,L given s(t-1) without explicitly stating that the L LLMs generate independently given the same prompt; this assumption should be stated.","section":"Proof of Lemma 3"},{"comment":"The state space S is defined as all token vectors of length P D N_token, which includes token strings that do not correspond to valid CSV action matrices; this over-approximation is harmless for the Markov chain construction but should be acknowledged.","section":"Lemma 1"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an important problem and contains extensive experiments, but the theoretical core has substantial gaps. The errors in Lemma 2 and Lemma 3 are load-bearing and require careful repair. The authors should be given a chance to revise, but if the multi-LLM transition analysis cannot be corrected, the paper may not be publishable in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is the first to try to prove convergence for LLM optimizers in black-box wireless network management via a finite-state Markov chain, and the empirical work is extensive. But the central theorem does not go through: Lemma 2's proof in Appendix C fails to establish that from every non-optimal state there is a positive transition into the optimal set, and Theorem 2 depends exactly on that property.\n\nWhat is genuinely new is the Markov chain formalization. Lemma 1 on BPE tokenization giving a finite state space is plausible for the stated tokenizer, and the block decomposition into S* and S' is standard. The result that elitist sampling makes P3 = 0 and makes P4 upper triangular is correct as far as it goes. The multi-LLM setup and the convergence-rate analysis are a clean translation of known evolutionary algorithm results (Rudolph 1994, He and Lin 2016), and the numerical experiments are thorough, covering IFC, BC, and massive MIMO with multiple open-source LLMs. The empirical observation of linear convergence and the scaling with the number of LLMs is interesting.\n\nThe load-bearing gap is in Lemma 2. The proof derives that P4 is upper triangular, which only says each non-optimal state has some positive transition to a strictly better non-optimal state or an optimal state. It does not say the better state is optimal. A three-state counterexample with two non-optimal states satisfies the properties proven in Appendix C while P2 is zero, so the chain can stay in the non-optimal block forever. The paper needs an explicit reachability assumption, e.g., that from every non-optimal in-context example the LLM assigns positive probability to at least one optimal action population. That might be repairable from the softmax positivity in (8)-(10) and Assumption 1, but the paper does not make that argument, and the 'different from all above' instruction is not modeled. The multi-LLM Theorem 3 inherits the same gap through Lemma 2, so it is also unproven. The LIFO result is fine once positive matrices are assumed, though that positivity also is not established from the LLM output distribution alone.\n\nWho this is for: readers working on theoretical guarantees for LLM-based optimizers will find the modeling framework useful as a starting point, but they should not rely on Theorem 2 as a proof. The paper deserves a serious referee: the gap is specific, the modeling is meaningful, and a repair is plausible. I would send it to review but expect the reviewers to require the reachability argument before accepting.","headline":"First serious Markov-chain model of LLM-based black-box optimization, but the central convergence proof depends on a P2-positivity claim that Lemma 2 does not prove.","tokens_in":27065,"tokens_out":3501,"would_cite":false,"duration_ms":38127,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","90C26","68T50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the LLM optimizer framework converges to a globally optimal action whenever it uses elitist sampling, and derives how multiple parallel LLMs accelerate that convergence.","keywords":["large language models","black-box optimization","finite-state Markov chain","elitist sampling","convergence analysis","wireless network management","multi-LLM optimization"],"falsifier":"Run the LLMO with elitist sampling on a reward where the global optimum is isolated and many nearby states are better than their predecessors but never optimal; if the LLM's token sampler from some non-optimal state assigns zero probability to the token vector of the global optimum, the process will never enter $\\mathcal{S}^\\star$ and the empirical probability of reaching the optimum stays below $1$. That can be checked directly by enumerating the support of the LLM's output distribution from that state.","tokens_in":25988,"feed_emoji":"🤖","tokens_out":9749,"duration_ms":101868,"temperature":0.7,"pith_summary":"This paper tries to establish that the large language model optimizer (LLMO) framework is not just a heuristic that works in simulations: it is a convergent stochastic search algorithm. The authors model the LLMO loop as a finite-state Markov chain and prove that with the elitist sampler, which feeds back the best actions seen so far, the probability of being at an optimal state tends to $1$ as iterations grow, regardless of the reward function's convexity or the initial actions. They further prove that the multi-LLM variant converges faster, with the optimality gap reduced by a factor of $\\lambda^L$ per iteration when $L$ identical LLMs share a memory. If these results hold, prompt-based LLMs can be used as universal black-box solvers for network management tasks that lack closed-form models and gradients.","feed_headline":"LLM optimizers provably converge to the global optimum","feed_subtitle":"Markov-chain proof: elitist sampling guarantees optimality, and extra LLMs speed the search.","key_machinery":"The central object is the finite state space $\\mathcal{S}$ of byte-pair-encoding (BPE) token vectors for every possible action population, together with the optimal-state subset $\\mathcal{S}^\\star$. The argument runs through the transition matrix $P_{\\mathrm{LLM}}$, split into blocks $P_1,\\dots,P_4$ according to moves inside, into, and out of the optimal set. Lemma 2 is the load-bearing mechanism: with elitist sampling, $P_1$ and $P_4$ are upper triangular, $P_2$ has at least one positive entry in every column, and $P_3=0$; the Perron-Frobenius theorem then forces $P_4^{\\infty}=0$, which is exactly the claim that non-optimal states are left forever. The convergence-rate analysis uses the average convergence rate $\\gamma(t)$ and its limit $q_{\\max}=\\max_{s\\in\\mathcal{S}'}q_{ss}$, which becomes $\\lambda^L$ for identical LLMs.","core_discovery":"The core claim is that every LLMO run is a finite-state Markov chain, because tokenization turns candidate solutions into a finite language space. In that chain, elitist sampling imposes a special block structure on the transition matrix: rewards never decrease, transitions leaving the optimal set are impossible, and from every non-optimal state there is a positive-probability path into the optimal set. Theorem 2 then concludes $\\lim_{t\\to\\infty} \\Pr\\{s(t)\\in\\mathcal{S}^\\star\\}=1$ for any initial distribution, and states that the LIFO sampler, which feeds back only the most recent proposals, cannot guarantee this. For the multi-LLM architecture, the paper characterizes the average convergence rate and shows the optimality gap shrinks by a factor $q_{\\max}<1$ per iteration, reducing to $\\lambda^L$ when all $L$ LLMs are identical. The paper also acknowledges that many local optima can still make practical convergence difficult, since the theorem is asymptotic.","pith_inferences":["Editorial inference: The guarantee is asymptotic and inherits the unproven reachability premise that the LLM can always propose the global optimum with positive probability; this is why the paper's own caveat about many local optima is the practical failure mode to watch.","Editorial inference: Nothing in the Markov-chain argument is specific to language models as such; any tokenizable stochastic proposal generator with positive support on the optimum would inherit the same convergence theorem, so the result acts as a general template for elitist in-context search.","Editorial inference: A direct way to test the theoretical rate in practice is to estimate $q_{\\max}$ from the LLM's empirical token-level transition distribution and compare predicted versus observed optimality-gap slopes across base models, prompt templates, and population sizes."],"forward_implications":["A single LLM with elitist sampling is guaranteed to converge to a globally optimal action for any bounded black-box reward, convex or not, so the LLMO cannot be dismissed as a lucky heuristic.","The choice of sampler is decisive: LIFO sampling, which keeps only recent proposals, fails the guarantee and can stay stuck in non-optimal states, while elitist sampling retains the best actions and forces monotone improvement.","In the multi-LLM architecture, the optimality gap contracts by a fixed factor each iteration, and with $L$ identical models the factor is $\\lambda^L$; thus increasing $L$ exponentially accelerates convergence.","The theoretical slopes from Theorem 3 match measured convergence curves on power control and massive MIMO tasks, giving practitioners a quantitative way to predict how many iterations and LLMs a deployment needs."],"supporting_citations":[{"why":"introduces the original single-LLM optimizer framework whose convergence is proven in Section III.","marker":"[18]"},{"why":"introduces the multi-LLM architecture whose convergence-rate behavior is characterized in Section IV.","marker":"[25]"},{"why":"provides the average-convergence-rate definition and the eigenvalue result used for $q_{\\max}$ in Lemmas 4-5 and Theorem 3.","marker":"[49]"},{"why":"supplies the Perron-Frobenius spectral argument that makes $P_4^{\\infty}=0$ in the proof of Theorem 2.","marker":"[56]"},{"why":"gives the limiting-transition-matrix formula used to compute the steady state in Theorem 2.","marker":"[60]"}],"fun_headline_variants":["LLM optimizers provably converge, thanks to Markov chain proof","Markov chain proof reveals LLM optimizers always converge","LLM optimizer convergence proven; multiple LLMs speed search","Theoretical proof: LLM optimizers converge, even with multiple agents","First convergence proof for LLM optimizers in black-box networks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that from every non-optimal state the LLM can eventually produce a globally optimal proposal with positive probability; showing that the LLM can improve is not the same as showing it can reach the true optimum, and the latter is not proven.","fun_headline_variants_meta":{"raw":{"variants":["LLM optimizers provably converge, thanks to Markov chain proof","Markov chain proof reveals LLM optimizers always converge","LLM optimizer convergence proven; multiple LLMs speed search","Theoretical proof: LLM optimizers converge, even with multiple agents","First convergence proof for LLM optimizers in black-box networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000757,"raw_usage":{"total_tokens":3364,"prompt_tokens":947,"completion_tokens":2417,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":563,"completion_tokens_details":{"reasoning_tokens":2330}},"tokens_in":563,"tokens_out":2417,"duration_ms":19440,"temperature":1.0,"reasoning_tokens":2330,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:24:03.007087+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the LLMO with elitist sampling on a reward where the global optimum is isolated and many nearby states are better than their predecessors but never optimal; if the LLM's token sampler from some non-optimal state assigns zero probability to the token vector of the global optimum, the process will never enter $\\mathcal{S}^\\star$ and the empirical probability of reaching the optimum stays below $1$. That can be checked directly by enumerating the support of the LLM's output distribution from that state.","supporting_citations":[{"cited_title":"Large language models as optimizers,","cited_arxiv_id":null,"evidence_quote":"introduces the original single-LLM optimizer framework whose convergence is proven in Section III."},{"cited_title":"Large Language Models for Knowledge-Free Network Management: Feasibility Study and Opportunities","cited_arxiv_id":"2410.17259","evidence_quote":"introduces the multi-LLM architecture whose convergence-rate behavior is characterized in Section IV."},{"cited_title":"Average convergence rate of evolutionary algorithms,","cited_arxiv_id":null,"evidence_quote":"provides the average-convergence-rate definition and the eigenvalue result used for $q_{\\max}$ in Lemmas 4-5 and Theorem 3."},{"cited_title":"Horn and C","cited_arxiv_id":null,"evidence_quote":"supplies the Perron-Frobenius spectral argument that makes $P_4^{\\infty}=0$ in the proof of Theorem 2."},{"cited_title":"Isoifescu, Finite Markov Processes and Their Applications","cited_arxiv_id":null,"evidence_quote":"gives the limiting-transition-matrix formula used to compute the steady state in Theorem 2."}],"review_version":1}