1 Introduction↩︎

Large language models (LLMs) generate text by sampling, at each step, from a categorical distribution over a large token vocabulary. Many downstream applications, such as LLM steganography, constrained generation, and structured discretization, need to replace this categorical distribution by a tractable approximation that interfaces cleanly with binary coding. Dyadic distributions, those whose probabilities are negative powers of two, fit this need. They correspond exactly to the leaf masses of full binary trees, where the root-to-leaf path of each leaf is itself a bitstring. For steganography, this gives a direct one-to-one correspondence between leaves and hidden messages. Specifically, sampling a token from the dyadic distribution is equivalent to transmitting the bitstring labeling its leaf, with the leaf mass \(2^{-d}\) determining how often that \(d\)-bit message is sent. This makes prefix-free coding, sampling, and arithmetic-coding manipulations straightforward.

This paper studies the resulting approximation problem. Given a categorical distribution \({\boldsymbol{p}}\) over \(n\) tokens, we look for a full binary tree together with a surjective assignment of tokens to its leaves, so that the induced dyadic distribution is close to \({\boldsymbol{p}}\) in some statistical sense and the resulting encoding has rate at least \(R\). We measure closeness by total variation distance because, in the LLM steganography setting that motivates this paper, it directly bounds an adversary’s advantage in detecting the hidden channel via binary hypothesis testing between the cover and stego distributions. This is in contrast to much of the existing LLM steganography literature, which optimizes Kullback–Leibler divergence or cross-entropy surrogates [1]–[3].

We call this the Tree-Partitioning Problem (TPP). The number of leaves \(L\) is induced by the tree rather than fixed in advance, and the rate constraint couples the tree shape to the partition through Kraft’s inequality [4]. Even very restricted instances of TPP — e.g., depth-\(1\) trees with \(L=2\) — are NP-hard via reduction from the partition problem, so we cannot hope for exact polynomial-time solutions. We instead build a polynomial-time additive approximation scheme, drawing on the classical polynomial-time approximation scheme (PTAS) toolkit for structured knapsack problems [5]–[7].

We work throughout in the constant-rate regime, where the target rate \(R\) is fixed independently of \(n\). This regime fits the LLM steganography setting, where the encoder needs the channel to carry at least some minimum number of bits per token but is otherwise free to optimize statistical fidelity. By contrast, regimes in which \(R\) or \(L\) scales with \(n\) degenerate either into trivial near-symbol-wise constructions or into substantially more complex enumeration problems. We comment briefly on these in the discussion.

We make three contributions. First, we introduce the TTP as a unified formulation of dyadic approximation under joint divergence and rate constraints, making explicit the roles of tree shape, leaf assignment, and Kraft’s inequality. Second, for the rate-constrained TPP (Problem 1), we give a polynomial-time additive approximation scheme with running time \(O(n)\cdot \exp(O(\log(1/\varepsilon)/\varepsilon))\) and total-variation guarantee \(\mathrm{OPT}+12\varepsilon\) in the constant-rate regime. Third, we position variable-length dyadic encodings and total variation distance as a natural but underexplored foundation for LLM steganography.

To design this approximation scheme, our algorithm builds on a standard PTAS toolkit for knapsack-type partitioning and load-balancing problems [7]–[10]. Specifically, we synthesize several techniques from this literature: mall-/large-item classification, aggregation of negligible items, depth truncation, structural monotonicity of optimal solutions, rounding onto a finite lattice, and dynamic programming over compressed load vectors. For a fixed height vector \({\boldsymbol{H}}\), the assignment subproblem has the flavor of target-load partitioning. More specifically, the token probabilities play the role of item sizes, leaves play the role of bins, and the dyadic masses \(2^{-h_j}\) are the target loads. This connects the fixed-tree subproblem to multiway number partitioning, scheduling/load-balancing, and bin-assignment objectives based on absolute deviation from prescribed targets [11]–[13]. The full TPP, however, is not a direct instance of these models. Its target loads are not fixed in advance and instead they are induced by a binary tree that must be optimized jointly with the partition. Consequently, the height vector must simultaneously determine dyadic masses, satisfy Kraft’s equality, and meet the rate constraint \(\sum_j 2^{-h_j}h_j\geqslant R\). Thus, while the fixed-tree assignment problem is knapsack-like, the main technical work is to adapt these ideas to a coupled partition-and-prefix-coding problem, a structure absent from standard multiple-knapsack, multiple-subset-sum, and load-balancing formulations [5], [14].

Section 2 defines the TPP, introduces two constrained variants, and states the NP-hardness result that motivates approximation. Section 3 specializes to the constant-rate regime by grouping items by mass and imposing three instance-level conditions. Section 4 contains the technical core. Here, we apply four reductions (truncation, grouping, dynamic programming, and feasibility repair) that together prove the main theorem. Section 5 discusses the relevance of the assumptions for LLM-scale supports, the dual formulation, and other scaling regimes.

2 Definitions and Problem Statement↩︎

Consider a categorical distribution \({\boldsymbol{p}}=\left( p_1, p_2, \ldots, p_n \right)\) defined over a support of size \(n\), representing the output token distribution of an LLM. Without loss of generality, we assume the probabilities are sorted in non-increasing order: \(p_1\geqslant p_2\geqslant\ldots \geqslant p_n\).

Our objective is to choose a full binary tree together with a partition of the support onto its leaves. For any candidate full binary tree, let \(L\) denote its number of leaves. Thus \(L\) is not fixed in advance; rather, it is induced by the tree under consideration. We assume throughout that every leaf is used, i.e., empty leaves are not permitted.

Figure 1 shows a small running example with \(n=8\) and \(L=5\) that illustrates the partition function \(\pi\), the partition \({\boldsymbol{S}}\),the height vector \(\boldsymbol{H}\), the divergence \(\mathfrak{D}\), and the rate \(\mathfrak{R}\).

2.1 The Tree-Partitioning Problem (TPP)↩︎

In its basic form, the TPP seeks a partition function \(\pi\) and height function \(h\) that seeks to both minimize the divergence \(\mathfrak{D}({\boldsymbol{S}}, {\boldsymbol{H}})\) and maximize the information rate \(\mathfrak{R}({\boldsymbol{S}}, {\boldsymbol{H}})\) subject to the constraint that the heights correspond to a valid full binary tree so that \[\begin{align} \label{eq:tree} \sum_{j=1}^L 2^{-h_j}=1. \end{align}\tag{1}\] Unless stated otherwise, we assume all height functions studied in this work correspond to a valid full binary tree and thus satisfies (1 ) according to the Kraft inequality [4].

We now introduce two constrained variants of the TPP, which incorporate rate constraints and rate optimization.

Problem 1: Rate-Constrained TPP. Given \({\boldsymbol{p}}\) and a fixed encoding rate \(R>0\) find \(({\boldsymbol{S}}, {\boldsymbol{H}})\) that minimizes \(\mathfrak{D}({\boldsymbol{S}},{\boldsymbol{H}})\) subject to \[\begin{align} \mathfrak{R}({\boldsymbol{S}},{\boldsymbol{H}}) \geqslant R. \label{eq:rate1} \end{align}\tag{2}\]

Problem 2: Divergence-Constrained TPP. Given \({\boldsymbol{p}}\) and a fixed tolerance \(\Delta>0\) find \(({\boldsymbol{S}}, {\boldsymbol{H}})\) that maximizes the information rate \(\mathfrak{R}({\boldsymbol{S}},{\boldsymbol{H}})\), subject to \[\begin{align} \mathfrak{D}({\boldsymbol{S}}, {\boldsymbol{H}}) \leqslant\Delta. \label{eq:KLF} \end{align}\tag{3}\]

The body of this paper focuses on Problem 1 in the constant-rate regime, which is the relevant regime for steganography. One typically imposes a minimum rate and optimizes detectability, measured here through total variation distance [15]–[17]. Problem 2 and regimes where \(R\) or \(L\) scales with \(n\) are discussed in Section 5.

As even very restricted instances of the TPP are computationally hard, we cannot hope for exact polynomial-time solutions. We therefore turn to approximation.

3 Constant-Rate Regime: Setup↩︎

We work in the constant-rate regime, where \(R\) is fixed independently of \(n\) and \(\varepsilon\to 0\) controls the additive approximation error. This section sets up the instance conditions used by the approximation algorithm. We first classify items as small or large according to their probability mass, which ensures that only constantly many items can be large. We then state three numerical assumptions on the support size and on \(\varepsilon\) for the seeding and repair steps in Section 4.

3.1 Small and Large Item Classification↩︎

We split the support by probability mass at the threshold \(\theta\triangleq\varepsilon\cdot 2^{-R/\varepsilon}\). The small item set is \[\begin{align} \label{eq:32small} \mathcal{S}_{\text{small}} \triangleq \{i\in [n]: p_i\leqslant\theta\},\end{align}\tag{4}\] and the large item set is \(\mathcal{S}_{\text{large}} \triangleq [n] \setminus \mathcal{S}_{\text{small}}\). Each large item has mass exceeding the constant \(\theta\), so the total mass constraint \(\sum_i p_i = 1\) forces \(|\mathcal{S}_{\text{large}}|\leqslant 1/\theta = O(1)\) for fixed \(R, \varepsilon\), and consequently \(|\mathcal{S}_{\text{small}}|\geqslant n - O(1)\).

3.2 Three Assumptions on the Instance↩︎

The algorithm of Section 4 operates under the following three numerical assumptions on the instance \(({\boldsymbol{p}},n,R,\varepsilon)\). Their role is to ensure that the support is large enough to support a depth-\(R\) encoding tree and contains enough small items for the technical operations performed in Section 4.

Assumption 1. \(n\geqslant 2^{R}\). The minimum vocabulary needed to support a tree with rate at least \(R\) via leaves at depth \(\geqslant R\).

Assumption 2. \(|\mathcal{S}_{\text{small}}| \geqslant 2^{R/\varepsilon} + 1/\varepsilon\). Minimal number of small items, required by Lemmas 5 and 6 below.

Assumption 3. \(\varepsilon\) is small enough that \(2^{R/\varepsilon}\geqslant 1/\varepsilon\). Automatic for all sufficiently small \(\varepsilon\) when \(R\) is constant.

We interpret each candidate solution as a dyadic tree whose leaves correspond to the partition subsets \(\{\mathcal{S}_j\}_{j=1}^L\).

4 Algorithm and Analysis↩︎

4.1 Roadmap↩︎

The hardness of TPP (Lemma 1) rules out exact polynomial-time solutions and motivates our additive approximation. The search space — arbitrary full binary trees together with arbitrary partitions of \([n]\) onto their leaves — is far too large to enumerate. Two of the four reductions shrink this search space combinatorially, and one shrinks it numerically. The fourth restores any feasibility lost in the process.

(i) Truncation. For an additive cost of zero in divergence, it suffices to consider trees of depth at most \(d\triangleq\log_2(1/\varepsilon)\). The set of such tree shapes is finite, with size \(\exp(O(1/\varepsilon))\). This reduction, made precise in Lemma 2, replaces the search over heights by enumeration over a constant number of bounded-depth tree shapes.

(ii) Grouping. Tokens with mass below \(\varepsilon^2\) can be aggregated into “blocks” of mass between \(\varepsilon^2\) and \(2\varepsilon^2\) at a divergence cost of \(4\varepsilon\). After grouping, the number of objects to assign (the original heavy items together with the blocks) is at most \(1/\varepsilon^2+1\), a constant. This step (Lemma 3) reduces the per-tree assignment problem to constant size.

(iii) Atomic assignment via dynamic programming. For each fixed bounded-depth tree, the resulting bounded-size assignment problem is solved by a dynamic program over a discretized leaf-mass lattice, returning an assignment within \(2\varepsilon\) of the divergence-optimal blocked assignment in time \(O(n)\cdot\exp(O(\log(1/\varepsilon)/\varepsilon))\) (Proposition 1).

(iv) Feasibility repair. The depth-truncated trees produced in step (i) need not satisfy \(\mathfrak{R}\geqslant R\). Whenever a bounded-depth candidate has a leaf at depth exactly \(d\), that leaf can be replaced by a complete subtree of \(T_L=2^{R/\varepsilon}\) uniform sub-leaves seeded with reserved small items. This restores rate at additive divergence cost \(4\varepsilon\) (Lemma 5).

Combining (i)-(iv) along with a leaf-seeding step that potentially includes a divergence cost of \(2 \epsilon\), we obtain Theorem 1: an algorithm with running time linear in \(n\) for fixed \(\varepsilon\) that returns a feasible solution within \(\mathrm{OPT}+12\varepsilon\) in total variation distance. Throughout, it will be convenient to denote by \[\mathrm{OPT}({\boldsymbol{H}}) \triangleq \min_{\boldsymbol{S}}\,\mathfrak D({\boldsymbol{S}},{\boldsymbol{H}})\] the divergence-optimal partition cost for a height vector \({\boldsymbol{H}}\), where the minimum is over surjective partitions \({\boldsymbol{S}}\) for \({\boldsymbol{H}}\).

4.2 Truncation Reduction↩︎

The first reduction bounds the depth of the trees we have to enumerate. Any feasible solution can be replaced, with no increase in divergence, by one of depth at most \(d = \log_2(1/\varepsilon)\). The set of full binary tree shapes of bounded depth is finite (with size \(\exp(O(1/\varepsilon))\)), so this turns the outer search into a finite enumeration at no cost in approximation quality. Truncation can, however, lower the rate, since shallower leaves contribute less to \(\mathfrak{R}\). Step (iv) (Section 4.5) recovers the lost rate by re-expanding a depth-\(d\) leaf into a uniform subtree, which is why the lemma additionally guarantees the existence of such a leaf.

4.3 Grouping Tiny Items↩︎

After truncation, every candidate height vector has at most \(1/\varepsilon\) leaves. The remaining task, divergence-optimally assigning \(n\) items to those leaves, still depends on \(n\), which for an LLM vocabulary is in the tens of thousands. The next reduction shrinks \(n\) to a constant: items of mass below \(\varepsilon^2\) are aggregated into “blocks” of mass between \(\varepsilon^2\) and \(2\varepsilon^2\), at a divergence cost of \(4\varepsilon\). After blocking, the number of atomic units — original heavy items together with blocks — is at most \(1/\varepsilon^2+1\), independent of \(n\). Section 4.4 solves the resulting bounded-size assignment problem by dynamic programming.

After applying Lemma 3, the algorithm works with a collection of atomic units consisting of (i) each original item of mass \(\geqslant\varepsilon^2\) and (ii) each block produced from items of mass below \(\varepsilon^2\). Every atomic unit except possibly the final residual block has mass at least \(\varepsilon^2\), so their total count, denoted by \(K\), is bounded by \(\varepsilon^{-2}+1\), a constant for fixed \(\varepsilon\).

4.4 Atomic Assignment via Dynamic Programming↩︎

After truncation and blocking, what is left for each candidate height vector \(\overline{\mathbf{H}}\) is a finite combinatorial problem. Assign \(K\leqslant 1/\varepsilon^2+1\) atomic units to \(L\leqslant 1/\varepsilon\) leaves so as to minimize divergence. Even in this finite form, brute force is exponential in \(1/\varepsilon\) as there are \(L^K \leqslant(1/\varepsilon)^{1/\varepsilon^2}\) possible assignments.

Divergence depends on the assignment only through the resulting leaf-mass vector, not on which atomic unit lands where. Discretizing each atomic unit’s mass to the nearest multiple of \(\delta\triangleq\varepsilon^3/2\) collapses the state space to a polynomial-size lattice of leaf-mass vectors, on which the assignment problem reduces to a standard knapsack-style dynamic program.

4.4.0.1 Discretization

Let the atomic units be indexed by \(u\in[K]\), where \(K\leqslant\varepsilon^{-2}+1\) and let \(q_u\) denote the probability mass of atomic unit \(u\). Set \[\delta \triangleq \frac{\varepsilon^3}{2}, \quad w_u \triangleq \left\lfloor \frac{q_u}{\delta}\right\rfloor \in \mathbb{Z}_{\geqslant 0}, \quad \widehat q_u \triangleq \delta\, w_u, \quad W \triangleq \sum_{u=1}^K w_u.\] Since the atomic units partition \([n]\), \(\sum_{u=1}^K q_u =1\), so \[W\leqslant\frac{1}{\delta}=\frac{2}{\varepsilon^3}.\]

Now consider any assignment \({\boldsymbol{A}}=(A_1,\ldots,A_L)\) of the atomic units to the \(L\) leaves of \(\overline{\mathbf{H}}\), where \(A_j\subseteq [K]\) denotes the set of atomic units assigned to leaf \(j\). (We use \({\boldsymbol{A}}\) for the assignment of atomic units to distinguish it from the assignment \({\boldsymbol{S}}\) of the original tokens.) Define the exact and rounded masses of leaf \(j\) by \[\begin{align} m_j({\boldsymbol{A}})\triangleq \sum_{u\in A_j} q_u, \qquad \widehat m_j({\boldsymbol{A}})\triangleq \sum_{u\in A_j} \widehat q_u. \end{align}\]

Since \(0\leqslant q_u-\widehat q_u<\delta\) for every \(u\), we have \[\begin{align} \sum_{j=1}^L |m_j({\boldsymbol{A}})-\widehat m_j({\boldsymbol{A}})| &=\sum_{j=1}^L \sum_{u \in A_j} \left( q_u - \widehat q_u \right) =\sum_{u=1}^K (q_u-\widehat q_u)\\ &< K\delta \leqslant\left(\frac{1}{\varepsilon^2}+1\right)\frac{\varepsilon^3}{2} = \frac{\varepsilon}{2}+\frac{\varepsilon^3}{2} \leqslant\varepsilon, \end{align}\] where the last inequality holds for \(0<\varepsilon\leqslant 1\). Thus replacing the exact atomic masses by their rounded versions changes the total leaf-mass vector by at most \(\varepsilon\).

4.4.0.2 Dynamic program

Although the assignment is to all \(L\) leaves, the rounded mass of the final leaf is determined by the first \(L-1\) leaves because the total rounded mass is fixed. For this reason, the dynamic program stores only the first \(L-1\) rounded leaf-loads.

Order the leaves as \(1,2,\ldots,L\). For \[\mathbf{a}=(a_1,\ldots,a_{L-1})\in \{0,1,\ldots,W\}^{L-1},\] interpret \(a_j\) as the rounded load assigned to leaf \(j\), measured in units of \(\delta\). Then the rounded load of leaf \(L\) is implicitly \(W-\sum_{j=1}^{L-1} a_j,\) corresponding to a rounded mass \({\delta\cdot\big(W-\sum_{j=1}^{L-1} a_j\big)}.\)

We define a Boolean DP table \(F_t(a_1,\ldots,a_{L-1}),\) which is true if and only if the first \(t\) atomic units can be assigned to the \(L\) leaves so that the rounded loads on the first \(L-1\) leaves are exactly \((a_1,\ldots,a_{L-1})\). The initialization is \(F_0(0,\ldots,0)=\mathrm{true},\) and all other states are false. For atomic unit \(t+1\), the transition places it on one of the \(L\) leaves:

• if it is placed on leaf \(j\in[L-1]\), then the \(j\)th coordinate increases by \(w_{t+1}\);

• if it is placed on leaf \(L\), then the state vector is unchanged.

For this setting we store the individual assignments of each of the reachable states. For a reachable terminal state \(\mathbf{a}\), the corresponding rounded leaf masses are \[\delta a_1,\delta a_2,\ldots,\delta a_{L-1}, \quad \delta\bigg(W-\sum_{j=1}^{L-1} a_j\bigg).\]

Hence for any assignment \({\boldsymbol{A}}\) corresponding to the terminal state \(\mathbf{a}\), we define the rounded objective \[\widehat{\mathfrak D}({\boldsymbol{A}},\overline{\boldsymbol{H}}) \triangleq \sum_{j=1}^{L-1}\left|2^{-\overline{h}_j}-\delta a_j\right| + \bigg|2^{-\overline{h}_L} -\delta\bigg(W-\sum_{j=1}^{L-1}a_j\bigg)\bigg|.\] Moreover, by the reverse triangle inequality and the preceding bound on the rounded leaf-mass error, \[\label{eq:rounded-objective-gap} \left| \mathfrak D({\boldsymbol{A}},\overline{\boldsymbol{H}})-\widehat{\mathfrak D}({\boldsymbol{A}},\overline{\boldsymbol{H}}) \right| \leqslant \sum_{j=1}^L |m_j({\boldsymbol{A}})-\widehat m_j({\boldsymbol{A}})| \leqslant \varepsilon.\tag{5}\] The dynamic program returns a terminal state minimizing the rounded objective, together with a corresponding explicit assignment of all atomic units to all \(L\) leaves.

4.4.0.3 Illustrative Example of the DP State Space

To build intuition for the state-space compression and the transition function \(F_t\), consider a minimal toy instance. Suppose we choose an error tolerance \(\varepsilon = \sqrt[3]{0.002} \approx 0.126\). This comfortably bounds the required tree depth \(d \leqslant\log_2(1/\varepsilon) \approx 2.98\), allowing us to legally construct a tree with \(L=3\) leaves at depths \(h_1=1\), \(h_2=2\), and \(h_3=2\). The corresponding dyadic targets \(2^{-h_j}\) are \(0.50\), \(0.25\), and \(0.25\).

We are given \(K=3\) atomic units with true probability masses \(m_1=0.50\), \(m_2=0.30\), and \(m_3=0.20\). Following the algorithm strictly, we apply the discretization step \(\delta = \varepsilon^3/2 = 0.001\). The true masses are mapped to integer weights \(w_u = \lfloor m_u / \delta \rfloor\), yielding \(w_1=500\), \(w_2=300\), and \(w_3=200\). The fixed total integer weight is \(W=1000\). The dyadic targets are analogously scaled by \(1/\delta\) to establish the integer targets \(T_1=500\), \(T_2=250\), and \(T_3=250\).

The dynamic program tracks the integer loads of the first \(L-1=2\) leaves. A state \((a_1, a_2)\) is reachable after assigning \(t\) items if the boolean function \(F_t(a_1, a_2) = \mathrm{true}\). The DP initializes with \(F_0(0,0) = \mathrm{true}\). As items are assigned, each reachable coordinate transitions to at most three new coordinates (adding \(w_t\) to \(a_1\), to \(a_2\), or to neither if placed in Leaf 3).

Figure 2 visualizes this state-space expansion. For visual clarity, the grid axes are scaled in units of 100. The colors represent the timeline of the expansion: \(t=1\) (blue), \(t=2\) (red), and \(t=3\) (green).

At the terminal step \(t=K=3\), the algorithm evaluates the discrete divergence \(\widehat{\mathfrak D}\) for all valid terminal states. By implicitly defining the load of the final leaf as \(W-\sum_{j=1}^{L-1}a_j\), the DP calculates the objective directly from the tracked coordinates: \[\widehat{\mathfrak D}({\boldsymbol{A}},\overline{\boldsymbol{H}}) \triangleq \sum_{j=1}^{L-1}\left|2^{-h_j}-\delta a_j\right| + \bigg|2^{-h_L} -\delta\bigg(W-\sum_{j=1}^{L-1}a_j\bigg)\bigg|\] Table 1 illustrates this exact calculation for the terminal nodes branching from \(F_2(500,300)\). Evaluating this formula strictly identifies \((500, 300)\) as the optimal assignment.

4.5 Feasibility Repair↩︎

The truncation reduction (Lemma 2) preserves divergence, but a depth-truncated candidate may have \(\mathfrak{R}<R\). Whenever such a candidate has a leaf at depth exactly \(d\), we can supply the missing rate by replacing that leaf with a complete subtree of \(T_L\triangleq 2^{R/\varepsilon}\) uniform sub-leaves. Small items from \(\mathcal{S}_\text{small}\) play two roles: filling each new sub-leaf and absorbing the migrated mass. The construction is cheap precisely because the deepest leaf can be chosen to carry the smallest mass, making its dyadic-target perturbation small.

Therefore, we can assume that the deepest leaf carry the smallest mass. In particular, when its mass approximates the dyadic target \(\varepsilon=2^{-d}\), the subtree replacement contributes only \(O(\varepsilon)\) to the divergence, as formalized in the next lemma.

4.6 The Algorithm and Main Theorem↩︎

The atomic-assignment DP (Proposition 1) returns an assignment that may leave some leaves empty, since the DP works over rounded mass-vectors and does not enforce one-item-per-leaf. Problem 1 forbids empty leaves, so before we can claim feasibility, surjectivity has to be restored. Since small items are abundant, we force one designated small item into each leaf. The cost is small because each small item has mass at most \(\varepsilon\cdot 2^{-R/\varepsilon}\), which is a constant times \(\varepsilon\) when summed over the \(L\leqslant 1/\varepsilon\) leaves.

The four ingredients (truncation, blocking, DP, repair), together with the seeding lemma, give the algorithm below.

Algorithm. Enumerate every full binary tree shape \(\overline{\boldsymbol{H}}\) of maximum depth \(d=\log_2(1/\varepsilon)\). For each:

• Block items of mass below \(\varepsilon^2\) into atomic units (Lemma 3).

• Run the atomic-assignment DP (Proposition 1) for \(\overline{\boldsymbol{H}}\), returning an assignment \({\boldsymbol{S}}_{\overline{\boldsymbol{H}}}\) of the atomic units, possibly with empty leaves.

• Unpack each block into its constituent items at the leaf to which the block was assigned, then seed \({\boldsymbol{S}}_{\overline{\boldsymbol{H}}}\) with \(L\) reserved small items (Lemma 6) to obtain a surjective \({\boldsymbol{S}}_{\overline{\boldsymbol{H}}}^{\mathrm{seed}}\).

• If \(\mathfrak{R}(\overline{\boldsymbol{H}})\geqslant R\), accept \(({\boldsymbol{S}}_{\overline{\boldsymbol{H}}}^{\mathrm{seed}},\overline{\boldsymbol{H}})\). Else if \(\overline{\boldsymbol{H}}\) has a depth-\(d\) leaf, apply repair (Lemma 5) using \(T_L=2^{R/\varepsilon}\) further small items disjoint from the seeds, and accept the result. Else discard.

Return the accepted candidate of minimum divergence.

5 Discussion↩︎

5.1 The Dual Formulation↩︎

The paper focuses on Problem 1 (minimize divergence subject to a rate constraint). The dual problem — Problem 2, maximize rate subject to a divergence constraint — is equally natural and the same machinery applies, with truncation, blocking, and the bounded-depth DP carrying over without change. Only the feasibility check and the role of the repair lemma swap places. We omit the details.

5.2 Scaling \(R\) or \(L\) with \(n\)↩︎

Both \(R\) and \(L\) are constants in our setting. When \(R = \Theta(\log n)\), the number of bounded-depth tree shapes is no longer a constant in \(n\), and tighter enumeration strategies are required. We expect approximate counting and structured enumeration ideas from the polynomial-knapsack literature [7] to be relevant. When \(L\) scales with \(n\), the problem moves toward a near-symbol-wise regime where vanishing divergence is achievable by trivial constructions. Neither regime is immediately motivated by LLM steganography, but they raise the question of whether the constant in \(\mathrm{OPT}+12\varepsilon\) depends qualitatively on the regime.

References↩︎

---

1. Department of Mathematics, University of Zurich, Switzerland; Department of Electrical and Computer Engineering and the Department of Computer Science UVA, USA; Calit2 at the UCSD, USA; Naval Information Warfare Center Pacific, USA.↩︎

2. Emails: daniella.bar-lev@math.uzh.ch, farzad@virginia.edu, rgabrys@ucsd.edu, ryan.gabrys.civ@us.navy.mil↩︎

3. The work of D. Bar-Lev was supported by Schmidt Sciences and by the Swiss National Science Foundation under grant number 212865.↩︎

4. The variation distance is typically defined as \(\frac{1}{2} \sum_{j=1}^L \left|2^{-h_j} - \Pr(\mathcal{S}_j)\right|\), but we chose to omit the \(\frac{1}{2}\) coefficient for brevity since the minimization of both formulations is the same.↩︎