Four LLM requests share one compute budget. Each request could choose how much compute to use on its own, but those choices must fit within the same budget. A shared price gives them a way to coordinate: when total demand is too high, raise the price; when it is too low, lower it.

This is the idea behind dual decomposition. Applying Lagrangian relaxation to a shared constraint separates the original problem into independent subproblems. A master problem adjusts the price, or multiplier, using their aggregate response. We’ll first see this work for continuous compute allocations, then explore what changes when each request must make a discrete model choice. The interactive figures let you follow the allocations, the bounds, and the price updates.

The decomposition step

For block $i$, $x_i\in X_i$ is its local decision, $f_i$ is its local objective, and $A_i x_i$ is its contribution to the shared requirement $b$. The blocks interact only through that requirement:

$$ \min \; \sum_i f_i(x_i) \quad \text{s.t.} \quad \sum_i A_i x_i = b, \qquad x_i \in X_i . $$

The shared equality couples the blocks. Relax it with an unrestricted multiplier $\lambda$:

$$ g(\lambda) \;=\; \lambda^\top b \;+\; \sum_i \underbrace{ \min_{x_i \in X_i}\, \big[f_i(x_i)-\lambda^\top A_i x_i\big] }_{g_i(\lambda)\,:\,\text{subproblem }i} \;\le\; p^\star . $$

Each $g_i(\lambda)$ is the value of an independent subproblem. For any feasible $x$, the priced constraint vanishes, so $g(\lambda)$ is a lower bound on the optimal cost $p^\star$. The master problem maximizes $g(\lambda)$ to find the strongest such bound, updating $\lambda$ from the aggregate violation.

Example: allocating test-time compute

Suppose four LLM requests share a budget of $B$ test-time compute units. Treating compute as continuous, let request $i$ have the toy loss $\ell_i(x_i)=w_i/(1+x_i)$: more compute lowers loss, with diminishing returns.

$$ \min_{x_i\ge0}\;\sum_i \frac{w_i}{1+x_i} \qquad\text{s.t.}\qquad \sum_i x_i\le B. $$

Pricing the budget by $\lambda\ge0$ gives independent subproblems $\min_{x_i\ge0}\{\ell_i(x_i)+\lambda x_i\}$. For $\lambda>0$, each has the closed-form response

$$ x_i(\lambda)=\left[\sqrt{\frac{w_i}{\lambda}}-1\right]_+, \qquad [z]_+=\max\{0,z\}. $$

The master changes the price by $\alpha(\sum_i x_i(\lambda_k)-B)$ at each step: excess demand raises the price, and unused compute lowers it. At $\lambda=0$, each loss approaches zero as compute grows without bound, so there is no finite subproblem minimizer. The widget keeps the price strictly positive.

Try it: Press Run with the default settings. The initial price leaves compute unused, so watch the price fall and the allocations grow. Then increase the budget and run again: more available compute should lead to a lower clearing price.

With $B=17$ and $w=(64,36,16,9)$, the optimal price is $\lambda^\star=1$ and the requests choose $x^\star=(7,5,3,2)$. These choices exactly use the budget and minimize the total loss. The default update approaches this allocation without averaging. Continuity of the responses makes exact clearing possible here; convergence of the price updates also requires a suitable step size.

Nonconvex example: model routing

Now suppose each request must use either a base model or a stronger model. Upgrading request $i$ costs $c_i$ compute units and adds $a_i$ units of quality. The router must reach an aggregate quality target $b$:

$$ \min_{x_i\in\{0,1\}}\;\sum_i c_i x_i \qquad\text{s.t.}\qquad \sum_i a_i x_i\ge b. $$

At price $\lambda\ge0$ per unit of missing quality, request $i$ independently upgrades when $\lambda a_i>c_i$. Each binary response jumps at $c_i/a_i$. Every routing $x$ also contributes an affine piece $c^\top x+\lambda(b-a^\top x)$ to the dual function. At any price, $g(\lambda)$ is the lowest of these lines, because the subproblems choose the cheapest routing under the priced objective.

Use $c=(4,9,7)$, $a=(2,3,5)$, and $b=6$, with coordinates ordered as Math, Code, and Long-context.

Try it: In the default instance, move $\lambda$ from just below 2 to just above it. Quality jumps from 5 to 7 as Math switches to the stronger model. Click Go to λ★ to see the two routing lines tie at the peak of the dual curve, where the bound is 9.

The optimal routing upgrades the Math and Long-context requests for cost $p^\star=11$. The best dual bound is $d^\star=9$ at $\lambda^\star=2$. Just below that price only Long-context upgrades, giving quality 5; just above it Math also upgrades, giving quality 7. At the price itself, both routings minimize the Lagrangian. Neither gives exactly 6.

The fractional routing $(1/2,0,1)$ reaches quality 6 at cost 9. It represents an equal mixture of those two routings. Across repeated batches with the same request types and gains, upgrading half of the Math requests and every Long-context request gives average quality 6 and average cost 9 per batch. Individual batches still have quality 5 or 7, so this meets an average quality requirement, not a target of at least 6 in every batch. This mixture is the convexified solution measured by the dual bound.

Where the gap comes from

Start with the optimal discrete routing. Its cost is 11 and its quality is 7, so at $\lambda^\star=2$ its Lagrangian value is

$$ L(x^\star,2)=11+2(6-7)=9. $$

The priced objective credits the routing for its one unit of surplus quality. Even though this routing is both feasible and a Lagrangian minimizer, its priced value is two units below its actual cost. Finding the best price does not remove that gap.

To see the geometry, let $p(u)$ be the best cost when the quality target is changed to $b-u$, with $p(u)=+\infty$ if no routing is feasible. Positive $u$ loosens the target; negative $u$ tightens it. In this example, $p(0)=11$, $p(-1)=11$, and $p(1)=7$. Mixing the last two possibilities equally gives average $u=0$ and cost $(11+7)/2=9$.

For $\lambda\ge0$, $g(\lambda)=\inf_u[p(u)+\lambda u]$. Equivalently, the line $g(\lambda)-\lambda u$ lies below $p(u)$ and touches it wherever that infimum is attained. Its height at $u=0$ is the dual bound.

Write $p^{\star\star}$ for the closed convex envelope of $p$: the greatest lower-semicontinuous convex function lying below it. Here it traces the cheapest costs obtainable by mixing routings. The best supporting line reaches height $p^{\star\star}(0)=9$, so

$$ \text{duality gap} \;=\; p(0) - p^{\star\star}(0) \;=\; 11-9 \;=\; 2. $$

Try it: Click Go to λ★. On the left, the supporting line touches the staircase at $u=-1$ and $u=1$ but passes below it at $u=0$. Toggle convex envelope of p to see how mixing fills in the segment between those two points. Move $\lambda$ away from 2 and watch the line’s height at $u=0$ fall along with the dual bound on the right.

More generally, for a linear objective $c^\top x$, compact local decision set $X$, and a feasible problem, the best dual bound equals the optimum obtained by replacing $X$ with its convex hull while retaining the shared constraint:

$$ d^\star=\min\{c^\top x:Ax\ge b,\;x\in\operatorname{conv}(X)\}. $$

If this convex hull is just the usual LP relaxation, the Lagrangian bound is no stronger than the LP bound. A useful relaxation keeps subproblem structure that the LP would discard.

Updating the price

Because $g$ is concave, $s_k=b-Ax_k$ is formally a supergradient; it is often called a subgradient in the Lagrangian-relaxation literature. The standard update is

$$ \lambda_{k+1} \;=\; \big[\lambda_k + \alpha_k (b - Ax_k)\big]_+ . $$

The projection $[\cdot]_+$ keeps $\lambda\ge0$ when the relaxed constraint is the inequality $Ax\ge b$; for an equality, $\lambda$ is unrestricted and the projection is dropped.

Despite the name “subgradient ascent,” a step need not increase $g$. Track the best bound $\max_{j\le k}g(\lambda_j)$ rather than only the latest value.

Try it: Run with constant α and watch the current dual value bounce while the best bound stays level or rises. Reset and compare α / k with Polyak (needs d★). The Polyak demonstration uses the known answer $d^\star=9$ to choose its steps; even when it reaches that bound, the discrete optimum remains 11.

In this example, a constant step typically oscillates around the kink. For general concave duals with bounded supergradients and an attained optimum, the standard constant-step guarantee is convergence of the best bound to within a neighborhood of the optimum; exact convergence can occur in special cases. Suitable diminishing steps, such as $\alpha_k=\alpha/k$, make the best bound converge to $d^\star$, though progress can be slow. A Polyak step uses the optimal dual value to set the step size. Replacing that value with an estimate requires care, especially when a feasible primal cost lies above $d^\star$ because of a duality gap.

In practice

  • Try a problem-specific repair. A dual solution may violate the shared constraint, so use it as a starting point for a feasible candidate. Here, upgrading only Long-context gives quality 5; adding the Math upgrade raises quality to 7 at cost 11. Repair changes a discrete decision. In a mixed discrete–continuous problem, fixing the discrete choices and re-solving the continuous part helps only if those choices allow a feasible completion.
  • Track both sides. The best dual bound and best feasible candidate give a certified upper bound on the candidate’s suboptimality. Here, even the optimal candidate costs 11 while the best dual bound is 9, so the certificate retains a gap of 2.
  • Average only when useful. Suitable averaging schemes can recover a convexified solution. Check whether the application permits an average constraint across batches; fractional decisions do not automatically yield a feasible discrete routing for each batch.

Reading

Cite this post

@misc{emara2026visualizing,
  author = {Yahya Emara},
  title  = {Visualizing Dual Decomposition},
  year   = {2026},
  url    = {https://yahya010.github.io/blog/dual-decomposition/}
}