{"id":"36a41425-2dd5-42cc-917b-20a59e74cdfd","arxiv_id":"2502.01827","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The optimal modification of a two-state LLM-like token distribution for maximum steganographic capacity under a divergence budget is a deterministic, piecewise water-filling policy.","lead":"This paper models a relaxed form of LLM steganography, where the next-token distribution is slightly modified to hide more bits, as a constrained Markov decision process. It derives a closed-form optimal policy for a simplified two-state version of the problem and shows the policy is deterministic and water-filling-like.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The two-state CMDP solution appears mathematically sound; the load-bearing gap is the unvalidated transfer of the closed-form policy to real LLM distributions, as the reader noted.","rationale":"The reader's strongest claim is mathematical; my independent check finds no obvious internal error in the deterministic-policy reduction or the KKT construction. The algebra in the appendices is not machine-checked, but the structural argument (Jensen) is sound. The genuinely load-bearing uncertainty is external: the paper identifies its own two-state Markov assumption as an abstraction and provides no evidence that LLM next-token distributions conform. Theorems 2 and 3 solve a different object than an actual LLM next-token distribution: actions set a binary transition probability, rewards are binary entropy, and no procedure maps LLM contexts to states. Therefore the practical conclusion in the title/abstract is not supported. This matches the reader's weakest_assumption, so no new objection is raised; the conditional verdict stands. If the authors re-scope the claims to the two-state model, the paper is acceptable as theory; if they want the LLM claim, the empirical test above is required.","tokens_in":19029,"tokens_out":20019,"duration_ms":195070,"concrete_test":"Instantiate the model on a public LLM: choose a concrete two-state partition of contexts/tokens (e.g., cluster the LLM's next-token distributions or use a binary entropy threshold), estimate p0 and p1 from a natural-language corpus, apply the Theorem 2/3 policy for a fixed budget b, and generate stego-text. Measure the realized per-token TV relative to the LLM distribution and the realized entropy gain; compare against the token-wise optimizer of prior work and against a CMDP solver on a larger empirical state space. If the two-state policy violates the promised TV budget by more than a trivial amount, or if a larger-state CMDP solver achieves materially higher entropy at the same budget, the abstraction gap is confirmed as load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem is a closed-form characterization of the optimal policy for an abstract two-state Markov chain. That characterization is internally coherent: the deterministic-policy reduction in Appendix A follows from Jensen on concave H and convex TV, and the KKT case analysis is at least plausible. The weak point is not the algebra but the paper's advertised object: 'LLM-based steganography.' To apply Theorem 2/3 to an LLM one must (i) map the LLM's context-dependent next-token distribution over a huge vocabulary onto two states with fixed transition probabilities p0, p1, (ii) assume the state process is stationary Markov with those probabilities, and (iii) identify the binary action a with the full next-token distribution so that H(a) is the embedding capacity. The paper specifies no such mapping, estimates no p0, p1 from any LLM, and runs no experiment. The conclusion even concedes the model is an abstraction 'to gain insights.' Unless real LLM distributions are well approximated by such a two-state chain, the closed-form policy does not describe how to modify actual LLM outputs, and the title/abstract overclaim an enhancement of LLM-based steganography.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a constrained Markov decision process (CMDP) formulation for relatively-secure LLM-based steganography. The sequential embedding process is abstracted to a two-state Markov chain whose action is a binary next-token probability; the reward is binary entropy and the cost is discounted total variation from the original LLM transition probabilities. The authors first reduce the functional linear program P1 to a finite four-variable problem P2 via a Jensen-based deterministic-policy argument, reparameterize it to a convex problem P3, and then solve the KKT conditions to obtain closed-form optimal policies. The claimed optimal policy is deterministic and piecewise water-filling: in the low-budget regime only the state further from uniform is adjusted, in the intermediate regime both states are adjusted together, and for a large budget both actions become uniform. The paper concludes that the result offers insights for adjusting LLM output distributions, with proofs deferred in part to an accompanying long version.","tokens_in":19177,"tokens_out":20912,"duration_ms":175952,"significance":"The mathematical route is genuinely interesting: the reduction from a functional optimization over occupancy measures to a finite convex program, and the observation that a deterministic policy is optimal, are clean and potentially transferable to other CMDP formulations with convex costs and concave rewards. If the closed-form characterization is correct, it gives a complete, parameter-free description of the optimal policy for the two-state abstraction. At the same time, the advertised object is 'LLM-based steganography,' and the manuscript provides no mapping from real LLM next-token distributions to the two-state model and no empirical validation. The paper is best assessed as a theory/insight contribution; its significance for actual LLM steganography depends on an unverified modeling assumption. The central theorem also contains an algebraic error in the displayed intermediate-regime formula, which must be corrected before the main claim can be accepted.","major_comments":[{"comment":"The closed-form formula for the intermediate regime is algebraically incorrect. For a0=a1=a and p0,p1≥1/2, the active cost constraint from (22) is b/2=d0(p0-a)+d1(p1-a)=d0p0+d1p1-a. Substituting d0=dγ0+γa and d1=dγ1+γ(1-a) (which follow from (20)-(21) when a0=a1=a) gives b/2=dγ0p0+(dγ1+γ)p1-a(1-γp0+γp1), so the correct expression is a=M(dγ0p0+(dγ1+γ)p1-b/2), not -M(b/2-dγ0p0-dγ1p1). A numerical check with γ=0.5, dγ0=0.4, dγ1=0.1, p0=0.6, p1=0.9, b=0.25 makes the discrepancy concrete: the printed formula gives a≈0.178, whereas the constraint requires a≈0.570. Because this formula appears in the statement of Theorem 2 and in the KKT assignment of Appendix B, the main characterization is not correct as written.","section":"Theorem 2, Eq. (35); Appendix B, Eq. (121)"},{"comment":"The practical claim that this is an LLM-based steganography method is not supported by the manuscript. The optimization is solved for an abstract two-state Markov chain whose transition probabilities ps=P(St+1=0|St=s) are introduced without any mapping from an LLM's next-token distribution over a large vocabulary to these two states, and no p0 or p1 are estimated from any LLM or language corpus. Theorems 2 and 3 characterize the optimal policy of that abstract chain; the conclusion itself describes the result as providing 'insights.' The title and abstract should either be reframed as a theoretical abstraction, or the authors should supply evidence that real LLM next-token distributions are well approximated by such a binary-state Markov model.","section":"Section II.B / III.A; title and abstract"}],"minor_comments":[{"comment":"The Lagrangian term for the state-1 absolute-value constraint duplicates β0; it should be β1(x1-d1p1-c1), consistent with the stationarity conditions (63)-(68).","section":"Appendix B, Eq. (62)"},{"comment":"The dual variables ρ0 and ρ1 are introduced without definition and do not appear elsewhere; they should presumably be ν0 and ν1 as used in the KKT system.","section":"Appendix B, Eqs. (126) and (163)"},{"comment":"The sentence following these equations appears to reverse the assignment of ψ0 and ψ1: from the defining inverse relations, ψ0 solves Ψp1=0 and ψ1 solves Ψp0=0, whereas the text states the opposite.","section":"Theorem 3, Eqs. (46)-(47)"},{"comment":"The relationship between the discounted-entropy reward in the CMDP and the total number of embeddable bits in a finite-length arithmetic-coding stego-text is not quantified; the discounted objective is a proxy, and the connection to the length-n procedure in Fig. 3 would benefit from an explicit statement.","section":"Section II.A"}],"recommendation":"major_revision","confidential_remarks":"The paper sits at a theory/insight level despite its LLM-oriented framing. The deterministic-policy reduction and the convexity argument are promising, and the algebraic error in the intermediate regime appears readily fixable. The larger issue is calibrating the claims to what is actually proved: a closed-form solution for a two-state abstraction, not a demonstrated technique for real LLM-generated text. With corrected formulas, a clear statement of the modeling gap, and a more cautious title/abstract, the paper could be suitable for a theory-oriented venue; in its present form the main theorem is not correct as printed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the math is right, the packaging oversells. The paper solves a clean convex optimization problem for a two-state CMDP abstraction of steganographic embedding, and the closed-form deterministic water-filling policy is genuinely new. But calling it 'LLM-based steganography' in title and abstract is a stretch: there is no experiment on any language model, and no argument that real next-token distributions map to the two-state chain. Read as an information-theoretic toy model, it's a solid paper.\n\nWhat's actually new: the reduction from a functional LP over visitation measures to a finite convex program in R4, using Jensen's inequality on concave entropy and convex TV. That is done cleanly and is fully self-contained. The KKT case analysis in the appendix is extensive and consistent with the stated regimes, and the water-filling structure (adjust the least random state first, then both together, then saturate at uniform) is a nice characterization. There are no free parameters and nothing is fitted; the derivation is from first principles. Good work there.\n\nSoft spots, in order: (1) The transfer to LLMs is unsupported. To apply Theorem 2/3 you must map a context-dependent next-token distribution over a huge vocabulary to two states with fixed transition probabilities p0, p1, and identify the binary action with the full token distribution. The paper specifies no such mapping and estimates no p0, p1 from any model. The conclusion even concedes the model is an abstraction 'to gain insights' — which is honest, but the abstract and title don't carry that caveat. (2) Some verification details for Theorems 2 and 3 are deferred to a long version; the appendix in this version is substantial but not fully self-contained. (3) Minor typos: duplicated beta0 in equation (62), rho0 versus nu0 in places. None of these affect the derivation.\n\nFor a reader: someone working on constrained Markov decision processes or on steganography theory will get a genuinely interesting and correct result for a simplified model. Someone hoping for enhanced LLM steganography will be disappointed. The paper deserves a serious referee, but I'd ask the authors to re-scope the claims or provide even a small validation that real LLM token distributions are compatible with the two-state abstraction. As is, it's a good theory paper with an overreaching title.","headline":"Solid convex-analysis result for a two-state CMDP toy model, packaged with an LLM title it doesn't actually support.","tokens_in":19759,"tokens_out":2359,"would_cite":true,"duration_ms":22109,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A60","68P30","90C25","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that the optimal replacement distribution for LLM-based steganography, under a discounted total-variation budget, is a deterministic piecewise water-filling policy: first adjust only the state farthest from uniform…","keywords":["steganography","large language models","constrained Markov decision processes","total variation distance","embedding efficiency","water-filling","closed-form optimal policy","arithmetic coding"],"falsifier":"On a real LLM, compute the optimal replacement policy numerically with the full context-dependent transition probabilities and compare its entropy gain per unit total-variation budget against the two-state closed-form policy; if the numerical optimum beats the closed-form policy at the same budget, the two-state abstraction is falsified.","tokens_in":18771,"feed_emoji":"🕵️","tokens_out":8755,"duration_ms":75217,"temperature":0.7,"pith_summary":"Generative steganography hides secret bits by sampling from a modified version of an LLM's next-token distribution; the more uniform the replacement distribution, the more bits can be embedded, but the larger the deviation from natural text. This paper treats the sequential choice of replacement distributions as a constrained Markov decision process, with entropy as the reward and a discounted total-variation budget as the cost. The paper's central claim is a complete closed-form characterization of the optimal policy for a two-state Markov abstraction of the LLM. The optimal policy is deterministic and has a water-filling structure: with a tight budget, spend it only on the state whose transition distribution is least random, then adjust both states together until both reach the uniform distribution. If the abstraction captures real LLM behavior, the result gives a direct rule for how to spend a deviation budget to maximize embedding rate.","feed_headline":"Optimal stego policy: adjust the least-random state first","feed_subtitle":"A two-state model shows the best replacement distribution under a total-variation budget is deterministic water-filling.","key_machinery":"The load-bearing object is the constrained Markov decision process (CMDP) formulated in terms of occupancy measures: the state is the preceding token context abstracted to two states, the action $a \\in [0,1]$ is the probability that the next token is state 0, the reward is the binary entropy $H(a)$, and the cost is the total-variation distance $2|a - p_s|$. Theorem 1 shows that any randomized policy can be replaced without loss of optimality by a deterministic policy using one action per state, because entropy is concave and total variation is convex, so Jensen's inequality makes a weighted average of actions at least as good. That reduction turns the functional linear program into the convex problem P3, and solving its KKT conditions yields the closed-form water-filling formulas in Theorems 2 and 3.","core_discovery":"For the two-state abstraction with transition probabilities $p_s = P(S_{t+1}=0 \\mid S_t=s)$, the problem of maximizing discounted cumulative binary entropy subject to a discounted total-variation budget $b$ has a deterministic optimal policy, given in closed form by Theorems 2 and 3. When both $p_0,p_1 \\ge 1/2$, the solution has three regimes: for small $b$, only the state farther from $1/2$ is adjusted toward $1/2$; for intermediate $b$, both states are set to the same adjusted value; for large $b$, both are set to $1/2$. When the states lie on opposite sides of uniform, the intermediate regime follows a unique curve described by a pair of equations rather than a single shared value. The proof works by replacing the infinite-dimensional optimization over policies with an equivalent four-variable convex program.","pith_inferences":["The same concavity-convexity reduction should carry over to an $n$-state Markov abstraction of a language model, producing a finite convex program and a candidate multi-state water-filling policy; the paper proves only the two-state case.","In practice the transition probabilities would have to be estimated from the LLM's context window, and the paper does not test whether the closed-form policy survives that estimation error.","The security guarantee is relative: with unbounded computation and full knowledge of the LLM, an eavesdropper could still distinguish stego-text at a rate governed by the total-variation budget, so the scheme is not perfectly secure."],"forward_implications":["At each state the optimal policy is deterministic: the agent always picks one adjusted distribution, and randomness in the generated text comes only from the secret bits.","With a tight deviation budget, effort should be concentrated on the state whose transition distribution is least random; spreading the budget evenly across states is suboptimal.","As the budget grows, both states should be adjusted toward a common distribution, and beyond a threshold both should be replaced by the uniform distribution, maximizing the embedding rate.","The closed form gives an explicit entropy-versus-deviation tradeoff, so the optimal replacement can be computed from $p_0$, $p_1$, $\\gamma$, and $b$ without solving a general CMDP numerically."],"supporting_citations":[{"why":"The authors' earlier token-wise optimized-distribution scheme that this work extends by accounting for future tokens.","marker":"[24]"},{"why":"Supplies the constrained Markov decision process formalism, including occupancy measures and the de-randomization result used to justify deterministic policies.","marker":"[25]"},{"why":"Provides arithmetic coding, the embedding mechanism that maps chosen distributions into hidden bits at the entropy rate.","marker":"[29]"},{"why":"Provides the perspective-function convexity result used to transform the functional optimization into the finite convex program P3.","marker":"[32]"},{"why":"Supplies the Markov decision process background, including the occupancy-measure and Bellman structure used in the formulation.","marker":"[31]"}],"fun_headline_variants":["Water-filling the least-random state yields optimal stego","Closed-form stego policy: water-fill toward uniform","Deterministic water-filling optimal for LLM stego","Steganography's secret: tilt the least random state","Optimal stego: prioritize the most predictable token"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The closed-form policy assumes an LLM's next-token distribution can be summarized by a stationary two-state Markov chain with fixed transition probabilities; real LLM distributions change with every new token in the context.","fun_headline_variants_meta":{"raw":{"variants":["Water-filling the least-random state yields optimal stego","Closed-form stego policy: water-fill toward uniform","Deterministic water-filling optimal for LLM stego","Steganography's secret: tilt the least random state","Optimal stego: prioritize the most predictable token"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000867,"raw_usage":{"total_tokens":3770,"prompt_tokens":970,"completion_tokens":2800,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":2719}},"tokens_in":586,"tokens_out":2800,"duration_ms":21292,"temperature":1.0,"reasoning_tokens":2719,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:21:14.082230+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a real LLM, compute the optimal replacement policy numerically with the full context-dependent transition probabilities and compare its entropy gain per unit total-variation budget against the two-state closed-form policy; if the numerical optimum beats the closed-form policy at the same budget, the two-state abstraction is falsified.","supporting_citations":[{"cited_title":"Arithmetic coding,","cited_arxiv_id":null,"evidence_quote":"Provides arithmetic coding, the embedding mechanism that maps chosen distributions into hidden bits at the entropy rate."},{"cited_title":"Convex optimization,","cited_arxiv_id":null,"evidence_quote":"Provides the perspective-function convexity result used to transform the functional optimization into the finite convex program P3."}],"review_version":1}