StoBasket: Joint Upsell and Cross-Sell Optimization for Contribution Margin

# StoBasket: Joint Upsell and Cross-Sell Optimization for Contribution Margin
Source: [https://arxiv.org/html/2610.22768](https://arxiv.org/html/2610.22768)
Conference:StoBasket Research Manuscript; October 2026; Preprint draft© , 2026

###### Abstract\.

Retail recommenders rank relevance, but retailers realize contribution margin: an upsell earns the margin difference over a displaced item, whereas a cross\-sell earns an incremental margin\. We introduce*joint stochastic basket editing*, a formulation in which one policy selects typed replacement and addition offers for an existing basket, values them by expected incremental contribution margin, and couples their values through distinct displayed\-offer, accepted\-offer, and joint\-acceptance response channels\. To our knowledge, it is the first formulation in which upsell and cross\-sell responses are coupled: prior joint treatments assume this coupling away, which makes the two decisions separable, and are recovered here as the zero\-coupling special case\. This integrated action\-level formulation is the central contribution ofStoBasket: it places full\-price recommendations, optional promotion terms, display and inventory constraints, and stochastic customer response in one decision\. Real\-data\-calibrated simulations on five public basket datasets measure every policy against*attainable offer margin*: the expected extra contribution margin that the best possible offers would earn under the simulated customer response \(about $0\.47 per basket on Instacart\)\. All percentages below are shares of it\. With a correctly structured response model fit to a few thousand or more randomized offer sessions,StoBasketcaptures essentially all of it: within 0\.5% in every default\-price setting of all five markets, including high display costs, and within 0\.7% when the true response lies outside its model family\. Its remaining losses come from the response model, not the search: omitting cannibalization and offer fatigue costs 11–19%\. The economic layer is first\-order: a margin\-weighted popularity rule leaves as much as 11% unrealized at ordinary display costs and up to 98% when display is costly\. On the three datasets that are also standard next\-basket benchmarks, a published history\-based recommender leaves 11–52% unrealized even when reranked by margin, yet the same forecast adds up to 6% whenStoBasketuses it as an input\. Joint selection pays most where premium tiers and add\-ons are strongly linked: on Instacart it beats independent upsell and cross\-sell selection by 10\.2% of attainable margin after empirical\-Bayes noise correction and label placebos\. Because coupling is measurable from a retailer’s own baskets, the same analysis tells an operator where joint selection will pay, and active, randomized offer programs generate exactly the data that let it pay more broadly\. When display friction makes actions profitable only together, the best heuristic portfolio loses 64% under default Instacart prices while exact search stays within 0\.5%; across alternative price assumptions the heuristic loss ranges from 2% to 89%\. For a factor\-local subclass of the formulation, we characterize when staged policies succeed or fail and synthesize established geometric and graphical techniques into an exact optimizer\. The two exact methods agree on all 8,040 checked real\-basket instances\. With up to 20 upsell groups and four displayed upsells, vectorized exact enumeration solves every tested real basket in 0\.13 ms at the median, 30 ms at the 99th percentile, and at most 111 ms in Python\. Holding the optimizer fixed, a signal\-free propensity model loses 38%, while a correctly structured one trained on 5,000 randomized sessions comes within 0\.06% of perfect prediction: profit saturates long before accuracy does\. Separately, randomized fashion slates show that a same\-category neighbor causally lowers focal\-item clicks by 12%, supporting distinct exposure and acceptance channels\.StoBaskettherefore contributes the economic decision formulation first, evidence for when its coupling matters second, and a certifiable solver for the narrower regime in which local search fails\.

###### Keywords:

recommender systems, profit\-aware recommendation, upsell, cross\-sell, contribution margin, stochastic choice, economic optimization

## 1\.Introduction

Recommender systems commonly estimate product relevance or purchase propensity and then rank candidate items\. In retail checkout, however, the decision concerns*actions on an existing basket*\. Replacing a product and adding a product have distinct financial consequences, feasibility constraints, and customer\-response mechanisms\. A high preference score does not, by itself, determine whether a recommendation increases the retailer’s contribution margin\.

Profit\-aware recommendation provides a substantial foundation: surveys cover more than one hundred economic\-recommender studies, and prior systems incorporate provider profit through reranking, joint relevance–profit objectives, or model training\([De Biasio et al\., 2024b](https://arxiv.org/html/2610.22768#bib.bib9);[Louca et al\., 2019](https://arxiv.org/html/2610.22768#bib.bib28);[De Biasio et al\., 2024a](https://arxiv.org/html/2610.22768#bib.bib8)\)\. Earlier deployed work also generated both upsell and cross\-sell candidates for a current basket and ranked them by expected revenue or margin\([Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34)\)\.StoBasketadvances this line from economic item ranking to a joint stochastic edit policy whose replacement and addition actions have different incremental economics and whose values depend on what else is displayed and accepted\.

Consider a basket containing regular burger patties and buns\. Recommending premium patties is an*upsell*: if accepted, it replaces the regular patties, so the financial gain is the premium margin*minus*the margin of the displaced product\. Recommending cheddar is a*cross\-sell*: if accepted, it adds an incremental item without removing the patties\. The two decisions need not be independent\. Recommending premium patties may change the probability of purchasing cheddar; conversely, the combined recommendation can be economically attractive even when neither component is profitable in isolation\. Conventional matrix factorization can supply useful product representations, but a relevance score does not encode this upsell/cross\-sell accounting or the interactions between recommended actions\([Ruiz et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib31);[McAuley et al\., 2015](https://arxiv.org/html/2610.22768#bib.bib29)\)\.

Our central contribution is the resulting*decision formulation*\. We formulate*joint stochastic basket editing*: one policy chooses replacement and addition offers for an existing basket; replacement value deducts the margin of the displaced item, addition value does not; and the response law allows an offer’s value to depend separately on which upsells are displayed, accepted, or accepted together\. The policy then maximizes*expected incremental contribution margin*over feasible offer sets\. This combination is consequential: it makes the two recommendation types economically commensurable without making them behaviorally independent, and it creates profitable sets whose individual actions can all look unattractive\. To our knowledge, no prior formulation couples the two action types\. Earlier systems rank upsell and cross\-sell candidates independently\([Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34)\)or assume responses under which the two subproblems separate\([Ban et al\., 2024](https://arxiv.org/html/2610.22768#bib.bib4)\)\. Those models are the zero\-coupling special case of ours: Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)shows that they remain optimal when coupling is absent and can fail arbitrarily badly when it is present\.

#### Why a stochastic policy\.

The word*stochastic*, which givesStoBasketits name, refers to the customer, not to the search\. The retailer chooses offers deterministically, but whether each offer is accepted is random, and the acceptances are correlated: a shopper who takes premium patties is more likely to take cheddar, and merely seeing one suggestion changes the response to another\. A set of offers or recommendations therefore induces a probability distribution over possible final baskets, rather than determining a single final basket\. Treating offers as if they were purchases overvalues every offer; scoring them one at a time ignores the correlation; and both errors grow exactly where interaction value is largest\. The correct object is a policy that maximizes expected incremental margin under the joint response distribution\.

That object raises a computational question\. Enumerating offer sets grows exponentially with the number of candidates, ranking or staging offers carries no approximation guarantee once offers interact, and general\-purpose mixed\-integer or bandit search must either linearize an expectation over correlated choices or explore a combinatorial action space without certifying anything\.StoBasketinstead exploits linearity of expectation: expected margin depends on the response distribution only through first\- and selected second\-order acceptance moments \(Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\)\), and every upsell choice influences cross\-sells only through a short summary vector with one coordinate per response channel \(Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\)\)\. This compression supports both fast joint local search in ordinary markets and an exact optimizer where local search provably fails \(Section[4](https://arxiv.org/html/2610.22768#S4)\)\. The exact solution is also a trust anchor: for the same fitted objective, it certifies the greatest attainable predicted margin and so separates optimization error from prediction error\. Recommendations may be shown at regular prices; item discounts and conditional bundle rebates are optional terms priced in the same objective, and the policy needs no persistent customer identifier\.

Our experiments separate three sources of value\. First, typed margin accounting matters in every evaluated market: even margin\-weighted popularity leaves up to 11% of attainable offer margin unrealized \(Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)defines this measure\)\. Second, joint selection pays where premium tiers and add\-ons are strongly linked, as in Instacart’s organic and premium assortments, and Carbo\-Loading’s real prices independently confirm that such coupling exists; the same estimates yield a decision\-aware market\-basket diagnostic\. Coupling is strongest in the most digitally active market, which we interpret as evidence that active offer programs both create and reveal the interactionsStoBasketmonetizes \(Section[8\.2](https://arxiv.org/html/2610.22768#S8.SS2)\)\. Third, exact search matters in the narrower*bundle\-only\-profitability*regime, where display friction makes each action unattractive alone although the set is profitable\. Finally, profit saturates long before prediction accuracy does: with the optimizer fixed, a signal\-free propensity model loses 38% of attainable margin, while a correctly structured model trained on a few thousand randomized sessions comes within 0\.06–0\.3% of perfect prediction, much as ranking skill rather than forecast precision drives value in portfolio investing\.

#### Contributions\.

\(1\) The joint stochastic basket\-editing formulation: replacement and addition actions with displaced\-versus\-incremental margin, feasibility constraints, display cost, and optional promotion terms in one expected\-margin objective\. \(2\) A compact response\-to\-value representation in which cross\-sell value depends separately on displayed, accepted, and jointly accepted upsells, which shows exactly when separate pipelines are valid\. \(3\) Evidence on five public basket datasets that economic accounting is broadly material, that supported coupling creates value in two markets, and that exact search is decisive only in the bundle\-only regime\. \(4\) For a factor\-local, bounded\-treewidth subclass, a characterization of when staged policies are exact, a proof that they have no constant\-factor guarantee under coupling, and an exact solver verified on real interaction graphs\. \(5\) A link from response estimation to decision regret, with a field\-test and campaign design\.

Figure 1\.Illustration only\(constructed counterexample; not calibrated retail data\)\. A deliberately chosen response law makes each singleton recommendation lose money while the joint set earns\+$2\.60\+\\$2\.60\. The figure teaches the staging trap; it does not claim that typical grocery upgrades are unprofitable alone\.
#### Reading Figure[1](https://arxiv.org/html/2610.22768#S1.F1)\.

The instance is instructional\. Upsell acceptance probability is0\.50\.5, but accepting the upsell*reduces*incumbent\-category margin by$2\\$2\(expected−$1\-\\$1alone\)\. That is not the usual “cheap SKU→\\tohigher\-margin premium”; it is the opposite case—for example a private\-label to national\-brand swap whose shelf price rises while the margin rate falls, or a promoted upgrade whose discount erodes the gain\. The add\-on \(cheddar\) has margin$10\\$10and base purchase probability0\.020\.02, so its standalone expected margin is$0\.20\\$0\.20; displaying it costs$0\.50\\$0\.50, hence−$0\.30\-\\$0\.30alone\. Display cost is attached to the cross\-sell and is the same whether or not the upsell is shown\. Offering both raises cheddar purchase probability from0\.020\.02to0\.800\.80when the upsell is accepted, so the joint expected increment is\+$2\.60\+\\$2\.60\. Every heuristic that requires a profitable first step therefore stops at “show nothing,” while the joint policy captures the interaction\. Ordinary markets often have positive upgrades alone; the figure isolates the rarer bundle\-only\-profitability regime that Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)and the exact solver address\.

## 2\.Recommendation System and Decision Process

#### Context and candidate actions\.

At a recommendation opportunity, the system observes a basketBBand contextss, including product attributes, prices, contribution margins, inventory, store or region, and temporal features where available\. We operationalize an*upsell*as an upgrade that displaces an incumbent product, represented byREPLACE\(i,j\), and a*cross\-sell*as an add\-on that extends the basket, represented byADD\(k\)\. Compatibility rules prohibit conflicting upsells, while display and cardinality budgets restrict the number of recommendations\. Contextual features condition the choice model; they are not additional combinatorial decision variables\.

#### Choice estimation\.

The learning layer predicts which upsells shoppers accept, which cross\-sells they buy, and how both depend on the combination shown\. Estimating display effects requires logs of what was shown; purchase\-only histories reveal product relationships but not responses to offers that were never made\. For theory and simulation we use a finite latent\-class response model: each shopping occasion has an unobserved type, such as “premium\-minded” or “value\-minded,” with its own acceptance probabilities, and averaging over types yields consistent individual and joint acceptance probabilities\. Any estimator that supplies coherent probabilities can replace it \(Section[5](https://arxiv.org/html/2610.22768#S5); Appendix[A](https://arxiv.org/html/2610.22768#A1)\)\.

#### Economic optimization and serving\.

A joint optimizer returns the feasible offer set with maximum expected incremental margin, choosing upsells and cross\-sells together rather than in an upsell\-first or cross\-sell\-first pipeline, and serves it through a checkout screen, cart page, or associate device\. Realized revenue, displaced\-product margin, promotion redemption, and display costs determine the outcome\. Section[3](https://arxiv.org/html/2610.22768#S3)defines the objective, Section[4](https://arxiv.org/html/2610.22768#S4)the optimizer, and Section[6](https://arxiv.org/html/2610.22768#S6)the evaluation\.

## 3\.Joint Stochastic Basket\-Edit Formulation

Four equations form the formulation: Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\) states the decision, Eq\. \([2](https://arxiv.org/html/2610.22768#S3.E2)\) the accounting for one realized response, Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) the value of*every*candidate offer set in a structured subclass \(the objective, not its solution\), and Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\) the response probabilities that evaluate it\. Section[4](https://arxiv.org/html/2610.22768#S4)finds the maximizer\.

#### Running example\.

We illustrate every symbol with the burger basket of Section[1](https://arxiv.org/html/2610.22768#S1)\. The basket contains regular patties and regular buns\. The retailer can recommend two upsells, premium patties in place of the regular patties and brioche buns in place of the regular buns, and two cross\-sells, cheddar and bacon\. Per\-unit contribution margins are $1\.50 for regular patties, $3\.00 for premium patties, and $1\.20 for cheddar\. Table[1](https://arxiv.org/html/2610.22768#S3.T1)collects the notation\.

Table 1\.Notation, with the running burger example\.
#### The decision\.

For any permitted offer setAA, define its value

F⁡\(A,s,D\)=\\displaystyle F\(A;s,D\)=\{\}𝔼\[MD\(B⊕Y\)∣s,A,D\]−M0\(B;s\)−c\(A,D;s\),\\displaystyle\\mathbb\{E\}\[M\_\{D\}\(B\\oplus Y\)\\mid s,A,D\]\-M\_\{0\}\(B;s\)\-c\(A,D;s\),\(1\)A∗​\(D\)∈\\displaystyle A^\{\*\}\(D\)\\in\{\}arg⁡maxA∈𝒜⁡\(s,D\)⁡F⁡\(A,s,D\)\.\\displaystyle\\arg\\max\_\{A\\in\\mathcal\{A\}\(s;D\)\}F\(A;s,D\)\.In words:FFscores a candidate offer set by how much its expected final\-basket contribution margin exceeds the margin of the basket as it stands, net of the cost of making the offers; the policy chooses the permitted offer set with the highest score\. ThusMMmeasures a basket, whileFFmeasures an offer set\. Each component has a concrete meaning\.

- •AAis the offer set\. Recommending premium patties in place of regular patties together with cheddar isA=\{REPLACE​\(i,j\),ADD​\(k\)\}A=\\\{\\texttt\{REPLACE\}\(i,j\),\\ \\texttt\{ADD\}\(k\)\\\}, withiithe regular patties,jjthe premium patties, andkkcheddar\.
- •𝒜⁡\(s,D\)\\mathcal\{A\}\(s;D\)is the set of permitted offer sets: at mostLLupsells andKKcross\-sells, at most one replacement per basket item, in\-stock products only, and any merchandising rules\.
- •YYis the shopper’s random response toAA, for example “accepts premium patties, declines cheddar\.”B⊕YB\\oplus Yis the resulting final basket, here premium patties and regular buns\.
- •MD​\(⋅\)M\_\{D\}\(\\cdot\)is the contribution margin of a basket—revenue minus variable product cost—after any redeemed promotion, and𝔼\[⋅∣s,A,D\]\\mathbb\{E\}\[\\,\\cdot\\mid s,A,D\]averages it over the possible responsesYY\. The subscript inM0​\(B,s\)M\_\{0\}\(B;s\)is zero: it is the contribution margin of the original basket before any offer is made\. Subtracting it turns the expectation into an*incremental*contribution margin\.
- •c⁡\(A,D,s\)c\(A,D;s\)collects the costs of making the offers thatMDM\_\{D\}does not already include: screen space, associate time, and shopper attention\. WhenD=∅D=\\varnothingwe writec⁡\(A,s\)c\(A;s\)\.

The same objective covers ordinary recommendations \(D=∅D=\\varnothing\), fixed item discounts, which change realized margins and response probabilities, and conditional bundle rebates: a rebaterrpaid only when upgradeggand add\-onkkare both accepted contributes−rPr\(Yg=1,Zk=1∣s,A,D\)\-r\\Pr\(Y\_\{g\}=1,Z\_\{k\}=1\\mid s,A,D\)\. We select offers under given promotion terms; optimizing discount levels is a distinct extension \(Appendix[A\.4](https://arxiv.org/html/2610.22768#A1.SS4)\)\.

#### Typed economic effects\.

Consider one upsell in groupggthat replaces incumbent productiiwith alternativejj, and one cross\-sell add\-onkk\. LetYg=1Y\_\{g\}=1if the shopper accepts the upsell andYg=0Y\_\{g\}=0otherwise, and letZk=1Z\_\{k\}=1if the shopper buys the add\-on\. At ordinary prices, the realized margin increment inside Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\) is

\(2\)Δ​M=Yg​\(mj−mi\)\+Zk​mk−c⁡\(A,s\)\.\\Delta M=Y\_\{g\}\(m\_\{j\}\-m\_\{i\}\)\+Z\_\{k\}m\_\{k\}\-c\(A;s\)\.The first term is the replacement: an accepted upsell earns the*difference*in margin, because the incumbent leaves the basket\. Premium patties replacing regular patties earn$3\.00−$1\.50=$1\.50\\$3\.00\-\\$1\.50=\\$1\.50, not $3\.00\. The second term is the addition: a purchased add\-on earns its full margin, $1\.20 for cheddar, because nothing is displaced\. The third term is the cost of presenting the offers\. Taking expectations gives𝔼⁡\[Δ​M\]=pg​\(mj−mi\)\+Pr⁡\(Zk=1\)​mk−c⁡\(A,s\)\\mathbb\{E\}\[\\Delta M\]=p\_\{g\}\(m\_\{j\}\-m\_\{i\}\)\+\\Pr\(Z\_\{k\}=1\)\\,m\_\{k\}\-c\(A;s\), withpgp\_\{g\}defined in Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\)\. Because the replacement/addition type is part of the action, it changes the value optimized*before*serving rather than appearing only in a report afterward\. When the recommendations interact, the joint distribution of\(Yg,Zk\)\(Y\_\{g\},Z\_\{k\}\)depends on the selected policy, so optimizing the two action types independently may be suboptimal\.

#### Core structured coupling representation\.

Let the basket haveGGupsell groups, one per incumbent item that could be upgraded; in the exampleG=2G=2\(patties and buns\)\. Letxg∈\{0,…,Jg\}x\_\{g\}\\in\\\{0,\\ldots,J\_\{g\}\\\}denote the upsell recommended for groupgg, where00means no upsell andJgJ\_\{g\}is the number of alternatives;x1=1x\_\{1\}=1recommends premium patties\. LetCCbe the set of recommended cross\-sells, chosen fromMMcandidates;C=\{cheddar\}C=\\\{\\text\{cheddar\}\\\}in the example\. Every offer setAAin this subclass is therefore represented by a pair\(x,C\)\(x,C\)\. Fix the observed contextssand the promotion termsDD, and absorb those terms into the margins and response parameters\. For*any*feasible pair\(x,C\)\(x,C\), writeF⁡\(x,C,s\)F\(x,C;s\)for the valueF⁡\(A,s,D\)F\(A;s,D\)of Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\) whenAAis the offer set described by\(x,C\)\(x,C\)\. Under the structured response assumptions of Appendix[A](https://arxiv.org/html/2610.22768#A1), this value takes the form

F⁡\(x,C,s\)=\\displaystyle F\(x,C;s\)=\{\}U⁡\(x,s\)\+∑k∈C\[αk​\(s\)\+βk​\(s\)⊤​z​\(x,s\)\]\\displaystyle U\(x;s\)\+\\sum\_\{k\\in C\}\\big\[\\alpha\_\{k\}\(s\)\+\\beta\_\{k\}\(s\)^\{\\top\}z\(x;s\)\\big\]\(3\)\+∑\{k,ℓ\}⊆Cηk​ℓ\(z\(x;s\);s\),\\displaystyle\+\\sum\_\{\\\{k,\\ell\\\}\\subseteq C\}\\eta\_\{k\\ell\}\(z\(x;s\);s\),z⁡\(x,s\)=\\displaystyle z\(x;s\)=\{\}∑f∈ℋμf​\(xSf,s\)\.\\displaystyle\\sum\_\{f\\in\\mathcal\{H\}\}\\mu\_\{f\}\(x\_\{S\_\{f\}\};s\)\.Equation \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) assigns a value to every candidate offer set, profitable or not\. The optimal offer set is the candidate with the largest value:

\(4\)\(x∗,C∗\)∈arg⁡max\(x,C\)∈𝒜⁡\(s,D\)⁡F⁡\(x,C,s\)\.\(x^\{\*\},C^\{\*\}\)\\in\\arg\\max\_\{\(x,C\)\\in\\mathcal\{A\}\(s;D\)\}F\(x,C;s\)\.Equation \([4](https://arxiv.org/html/2610.22768#S3.E4)\) is Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\) restricted to the structured subclass\. Section[4](https://arxiv.org/html/2610.22768#S4)solves it exactly, and Appendix[A](https://arxiv.org/html/2610.22768#A1)derives Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) from an affine customer\-response model \(Appendix Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\)\)\. The terms of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) read as follows in the burger basket\.

- •U⁡\(x,s\)U\(x;s\)is the expected value of the upsells by themselves\. For each offered upsell it adds the acceptance probability times the margin difference, minus the cost of showing it, plus any extra margin when two upsells are accepted together\. If premium patties are accepted with probability0\.50\.5and cost $0\.10 to show, they contribute0\.5×$1\.50−$0\.10=$0\.650\.5\\times\\$1\.50\-\\$0\.10=\\$0\.65\.
- •αk​\(s\)\\alpha\_\{k\}\(s\)is the standalone value of add\-onkk: its margin times its purchase probability when no upsell is shown, minus its display cost\. If cheddar sells with probability0\.100\.10on its own and costs $0\.05 to show,αcheddar=0\.10×$1\.20−$0\.05=$0\.07\\alpha\_\{\\text\{cheddar\}\}=0\.10\\times\\$1\.20\-\\$0\.05=\\$0\.07\.
- •z⁡\(x,s\)∈ℝrz\(x;s\)\\in\\mathbb\{R\}^\{r\}summarizes, inrrnumbers, everything about the upsell choicexxthat matters to add\-ons\. In the response model of Appendix[A](https://arxiv.org/html/2610.22768#A1),r=3r=3, one coordinate per channel through which upsells change add\-on purchases: \(i\)*accepted upsells*,∑gpg​tg\\sum\_\{g\}p\_\{g\}t\_\{g\}, wheretgt\_\{g\}measures how much accepting upsellggshifts add\-on demand: a shopper who switches to premium patties is more likely to add cheddar; \(ii\)*displayed upsells*,∑gvg\\sum\_\{g\}v\_\{g\}, wherevgv\_\{g\}measures the effect of merely showing upsellgg: seeing the premium suggestion changes the cheddar decision even if the shopper declines it; and \(iii\)*joint acceptance*,∑\(g,h\)ρg​h​ζg​h\\sum\_\{\(g,h\)\}\\rho\_\{gh\}\\zeta\_\{gh\}, whereζg​h\\zeta\_\{gh\}measures the extra shift when upsellsggandhhare both accepted: premium patties together with brioche buns signal a “better burger” beyond either alone\.
- •βk​\(s\)∈ℝr\\beta\_\{k\}\(s\)\\in\\mathbb\{R\}^\{r\}converts that summary into money for add\-onkk: each coordinate is the add\-on’s margin times its sensitivity to the corresponding channel\. Thusβk⊤​z\\beta\_\{k\}^\{\\top\}zis how much the chosen upsells raise or lower add\-onkk’s expected value, andαk\+βk⊤​z\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}zis its total contribution when shown\.
- •ηk​ℓ\\eta\_\{k\\ell\}is the optional interaction between two add\-ons shown together\. Cheddar and bacon may compete for the same burger spend \(η<0\\eta<0, cannibalization\) or reinforce each other \(η\>0\\eta\>0\); the interaction may itself depend onzz\.
- •The second line states the general structure ofzz: a sum of local contributionsμf\\mu\_\{f\}, each depending only on the upsell choicesxSfx\_\{S\_\{f\}\}in a small set of groupsSfS\_\{f\}\. The collectionℋ\\mathcal\{H\}of such factors includes one factor per group, contributing\(pg​tg,vg,0\)\(p\_\{g\}t\_\{g\},v\_\{g\},0\), and one per correlated pair, contributing\(0,0,ρg​h​ζg​h\)\(0,0,\\rho\_\{gh\}\\zeta\_\{gh\}\)\. Locality is what makes exact optimization possible in Section[4](https://arxiv.org/html/2610.22768#S4)\.

These channels are distinct economically and statistically: display can change response without acceptance, and correlated acceptance can create value not recoverable from marginal probabilities\. The coupling termβk⊤​z​\(x,s\)\\beta\_\{k\}^\{\\top\}z\(x;s\)is what distinguishes this formulation from prior joint treatments\. When it is zero for every feasiblexxandkk, Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) separates into an upsell problem and a cross\-sell problem \(Proposition[B\.2](https://arxiv.org/html/2610.22768#A2.Thmtheorem2)\), which recovers the separable models of earlier work\([Ban et al\., 2024](https://arxiv.org/html/2610.22768#bib.bib4)\)\.

The dimensionrrcounts response channels, not products, promotions, or action types: a discount or bundle rebate changes coefficients, notrr\(Appendix[A\.4](https://arxiv.org/html/2610.22768#A1.SS4)\), and a fourth coordinate would add another channel, for example separate meat and bread effects\. The summary has a dual role: it makes the policy nonseparable while compressing many upsell choices into a fixed\-dimensional economic state, which is what Section[4](https://arxiv.org/html/2610.22768#S4)exploits\. The number of distinct add\-on rankings the optimizer must consider grows asMO⁡\(r\)M^\{O\(r\)\}, polynomial in the number of candidates for fixedrr\.

#### Coherent customer\-response moments\.

For an offered upgradegg, letYgY\_\{g\}denote acceptance, and define

\(5\)pg=Pr⁡\(Yg=1∣A,s\),ρg​h=Pr⁡\(Yg=Yh=1∣A,s\)\.p\_\{g\}=\\Pr\(Y\_\{g\}=1\\mid A,s\),\\qquad\\rho\_\{gh\}=\\Pr\(Y\_\{g\}=Y\_\{h\}=1\\mid A,s\)\.Herepgp\_\{g\}is the probability that the shopper accepts upsellgggiven the whole offer set, andρg​h\\rho\_\{gh\}the probability of accepting bothggandhh; they weight the margin terms inUUand the accepted and joint\-acceptance channels ofzz\. In the example,p1=p2=0\.5p\_\{1\}=p\_\{2\}=0\.5whileρ12=0\.30\\rho\_\{12\}=0\.30exceeds the0\.250\.25that independence would imply, because shoppers who upgrade one item tend to upgrade the other\. These first\- and second\-order moments are the interface between any coherent response model—neural, latent\-variable, or otherwise—and the economic objective; they must come from a valid choice distribution and respect the factor scopes the optimizer requires \(Appendix[A](https://arxiv.org/html/2610.22768#A1)\)\. For one upsell and one cross\-sell, the mixed differenceF⁡\(1,1\)−F⁡\(1,0\)−F⁡\(0,1\)\+F⁡\(0,0\)F\(1,1\)\-F\(1,0\)\-F\(0,1\)\+F\(0,0\)of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\), where the arguments indicate whether each offer is shown, measures the value of coupling them; in Figure[1](https://arxiv.org/html/2610.22768#S1.F1)it is$2\.60\+$1\.00\+$0\.30=$3\.90\\$2\.60\+\\$1\.00\+\\$0\.30=\\$3\.90\.

## 4\.Exact Structured Optimization

This section solves the maximization of Eq\. \([4](https://arxiv.org/html/2610.22768#S3.E4)\): given the valueF⁡\(x,C,s\)F\(x,C;s\)of every candidate offer set, find the candidate with the largest value\. Combining hyperplane arrangements with tree\-decomposition dynamic programming\([Lo and Topaloglu, 2019](https://arxiv.org/html/2610.22768#bib.bib27);[Del Pia, 2025](https://arxiv.org/html/2610.22768#bib.bib10)\), the multi\-channel structure of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) identifies a nonseparable class of stochastic basket\-edit policies whose global optimum is computable\. The main text gives the algorithm and its intuition; Appendix[L](https://arxiv.org/html/2610.22768#A12)gives the proof, complexity, tie handling, and implementation\.

The central computational obstacle is the exponential number of joint recommendation sets: trying every combination of upsells and cross\-sells quickly becomes infeasible\. Equation \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) exposes structure that permits a more efficient search\. In the additive cross\-sell subclass of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) \(ηk​ℓ=0\\eta\_\{k\\ell\}=0\), each candidate add\-on has an affine scoreℓk​\(z\)=αk\+βk⊤​z\\ell\_\{k\}\(z\)=\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z, its total contribution when shown\. Given a fixed upsell summaryzzand a cross\-sell budgetKK, the optimal cross\-sells are theKKlargest positive scores\. The ordering of these scores changes only across pairwise\-equality and zero\-score hyperplanes in therr\-dimensional summary space\.

This observation yields a finite family of candidate cross\-sell sets\. For each candidate set, the remaining upsell objective is a sum of the local factors of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) and can be optimized by a count\-augmented dynamic program on a tree decomposition of the upsell interaction graph, the graph that joins two upsell groups whenever they share a factor scopeSfS\_\{f\}\. The resulting algorithm combines*geometric enumeration of economically relevant cross\-sells*with*graphical optimization of feasible upsells*, avoiding enumeration of every possible joint basket edit\.

###### Proposition 0 \(Exact joint optimization for structured responses\)\.

Suppose that in Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) cross\-sell contributions are additive \(ηk​ℓ=0\\eta\_\{k\\ell\}=0\) and affine in a summaryzzof fixed dimensionrr; the upgrade factors inUUandzzhave a primal interaction graph of fixed treewidth; all input coefficients are rational; and upgrade and add\-on budgetsLLandKKare separate\. Under coherent, policy\-local acceptance moments \(Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\)\), an offer set\(x,C\)\(x,C\)maximizing Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\), and hence the expected incremental margin of Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\) within this class, can be computed in polynomial time in the encoded input size\.

Algorithm\.\(1\) Estimate the response momentspgp\_\{g\}andρg​h\\rho\_\{gh\}of Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\) for contextss\. \(2\) Construct the termsUU,αk\\alpha\_\{k\},βk\\beta\_\{k\}, andzzof Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\)\. \(3\) Enumerate the candidate top\-KKcross\-sell sets induced by the arrangement of scoresℓk​\(z\)=αk\+βk⊤​z\\ell\_\{k\}\(z\)=\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z, including boundary ties\. \(4\) For each candidate setCC, maximize Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) over upsellsxxby tree\-decomposition dynamic programming subject to the upsell budgetLL\. \(5\) Return the pair\(x,C\)\(x,C\)with the largest value of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\); this is the maximizer\(x∗,C∗\)\(x^\{\*\},C^\{\*\}\)of Eq\. \([4](https://arxiv.org/html/2610.22768#S3.E4)\)\.

#### What the certificate means operationally\.

Under the assumptions of Proposition[4\.1](https://arxiv.org/html/2610.22768#S4.Thmtheorem1), no other feasible offer set has greater value under the supplied response estimates and economic objective\. A retailer may therefore run any faster heuristic it prefers and use the exact policy selectively or offline as a trust anchor: the differenceF⁡\(x∗,C∗,s\)−F⁡\(x^,C^,s\)F\(x^\{\*\},C^\{\*\};s\)\-F\(\\widehat\{x\},\\widehat\{C\};s\)measures the heuristic’s optimization loss on the same basket and model\. Exact execution makes this search loss zero and isolates the remaining uncertainty in the response estimates, margins, and structural assumptions\. It does*not*make poor data accurate or an omitted customer\-response mechanism harmless; Sections[5](https://arxiv.org/html/2610.22768#S5)and[8](https://arxiv.org/html/2610.22768#S8)quantify those separate prediction and specification risks\.

The proof and exact assumptions appear in Appendix[L](https://arxiv.org/html/2610.22768#A12)\(Proposition[C\.1](https://arxiv.org/html/2610.22768#A3.Thmtheorem1)\)\. Because upgrade factors may span several groups, the statement also covers local exposure effects in which displaying one upsell changes another’s acceptance\. Add\-on interactions \(ηk​ℓ≠0\\eta\_\{k\\ell\}\\neq 0\) lie outside this exact class; without structure on them, the problem is NP\-hard \(Appendix[D](https://arxiv.org/html/2610.22768#A4)\)\. The implementation samples every arrangement cell in exact rational arithmetic and runs the dynamic program on a min\-fill tree decomposition; it matches exhaustive search on cyclic graphs of induced width up to four forr=3r=3andr=4r=4\(Appendix[E\.2](https://arxiv.org/html/2610.22768#A5.SS2)\)\. The arrangement hasMO⁡\(r\)M^\{O\(r\)\}cells, so boundedrris a substantive modeling assumption\.

#### Five heuristic solution strategies\.

Practical systems often avoid the joint problem by staging it\. We compare the exact optimizer with five heuristics that solve the*same*problem, Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\), with the same objective and the same exact sub\-solvers for the best upsells given cross\-sells \(x\|Cx\\mid C\) and the best cross\-sells given upsells \(C\|xC\\mid x\)\. They differ only in how they search, not in their customer model \(Table[2](https://arxiv.org/html/2610.22768#S4.T2)\)\.

Table 2\.The five heuristic strategies and the exact optimizer, all solving Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) with the same objective and sub\-solvers\. “Trap” refers to bundle\-only profitability \(Figure[1](https://arxiv.org/html/2610.22768#S1.F1); Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)\)\.###### Proposition 0 \(Staging gap\)\.

\(i\) Independent≤\\lequpsell\-first, cross\-sell\-first≤\\leqalternating≤\\leqoptimum, for every instance\. \(ii\) Ifβk⊤​z​\(x\)=0\\beta\_\{k\}^\{\\top\}z\(x\)=0for all feasiblexxandkk, and the budgets are separate, then independent, both sequential policies, and alternating best response are optimal; greedy need not be when upsell or add\-on pairs interact\. \(iii\) For everyλ\>0\\lambda\>0there is an instance with one upsell and one cross\-sell on which all five policies return value00while the optimum is2\.6​λ2\.6\\lambda\. Hence none of them has a positive approximation ratio\. \(iv\) For everyn≥1n\\geq 1there is a valid instance withnnupsells and one cross\-sell in which every nonempty policy with at mostnnoffers has negative value, while offering alln\+1n\+1is profitable\. Local search that changes up tonnoffers per step, started from the empty policy, therefore also returns00\.

*Proof sketch\.*\(i\) Each later policy optimizes over a set containing the earlier policy’s choice\. \(ii\) Under the condition,F⁡\(x,C\)=U⁡\(x\)\+∑k∈CαkF\(x,C\)=U\(x\)\+\\sum\_\{k\\in C\}\\alpha\_\{k\}by Proposition[B\.2](https://arxiv.org/html/2610.22768#A2.Thmtheorem2), so the independent policy is optimal, and \(i\) closes the chain\. \(iii\) Scale the instance of Figure[1](https://arxiv.org/html/2610.22768#S1.F1)byλ\\lambda\. From the empty policy, each single action has negative value, so each staged step, each best response, and each greedy move retains the empty policy\. \(iv\) Each upsell loses a little alone but gainsb\>0b\>0when the cross\-sell is shown; the cross\-sell alone losesAAwith\(n−1\)​b<A<n​b\(n\-1\)b<A<nb\. Appendix[E\.3](https://arxiv.org/html/2610.22768#A5.SS3)gives the explicit valid response model\.

## 5\.Learning Customer Choice and Decision Quality

A finite latent\-class model provides one coherent construction for the moments of Eq\. \([5](https://arxiv.org/html/2610.22768#S3.E5)\)\. Let a latent preference classQQtake valueqqwith probabilityπq\\pi\_\{q\}, and letpq​gp\_\{qg\}denote the acceptance probability for upgradeggconditional on classqqand its exposure\. Under conditional independence within a class,

\(6\)pg=∑qπq​pq​g,ρg​h=∑qπq​pq​g​pq​h\.p\_\{g\}=\\sum\_\{q\}\\pi\_\{q\}p\_\{qg\},\\qquad\\rho\_\{gh\}=\\sum\_\{q\}\\pi\_\{q\}p\_\{qg\}p\_\{qh\}\.In the burger example, one class might be “premium\-minded” shoppers who accept both upgrades with high probability and another “value\-minded” shoppers who accept neither; mixing the two producesρ12\>p1​p2\\rho\_\{12\}\>p\_\{1\}p\_\{2\}even though choices are independent within each class\. This latent\-class construction gives a concrete route to mutually coherent moments\. The mixture induces correlated decisions after marginalizingQQ\. Its class weights and acceptance rates can be conditioned on the basket, store, and time; individual purchase history can provide additional features\. The optimizer requires coherent response moments, rather than persistent identity information or a particular neural architecture\.

Choice estimation affects decisions through errors in expected policy values\. LetF⁡\(A\)F\(A\)denote the true value of offer setAA\(Eq\. \([1](https://arxiv.org/html/2610.22768#S3.Ex1)\), or Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\) in the structured class\), and letF^\\widehat\{F\}be the value function implied by estimated moments, withsupA∈𝒜\|F⁡\(A\)−F^​\(A\)\|≤ε\\sup\_\{A\\in\\mathcal\{A\}\}\|F\(A\)\-\\widehat\{F\}\(A\)\|\\leq\\varepsilon\. IfA^\\widehat\{A\}maximizesF^\\widehat\{F\}, the standard plug\-in decision inequality gives

\(7\)F⁡\(A∗\)−F⁡\(A^\)≤2​ε\.F\(A^\{\*\}\)\-F\(\\widehat\{A\}\)\\leq 2\\varepsilon\.Section[6\.3](https://arxiv.org/html/2610.22768#S6.SS3)measures this link directly by varying predictor quality while holding the optimizer fixed \(Figure[5](https://arxiv.org/html/2610.22768#S6.F5)\), complementing existing choice\-learning and decision\-regret analyses\([Erginbas et al\., 2025](https://arxiv.org/html/2610.22768#bib.bib14)\)\.

## 6\.Economic Results and Evaluation

#### Coupling multiplier\.

*Cross\-action coupling*is the termβk⊤​z​\(x\)\\beta\_\{k\}^\{\\top\}z\(x\)through which upsells change a cross\-sell’s value\. In the experiments a dimensionless multiplierγ≥0\\gamma\\geq 0scales only these terms, holding margins, base rates, display costs, candidates, and budgets fixed:γ=0\\gamma=0removes coupling,γ=1\\gamma=1is the generated or receipt\-calibrated reference strength, andγ=2\\gamma=2is a doubled stress test\. It is not a probability\. If an upsell raises an add\-on’s purchase probability from 8% to 12% atγ=1\\gamma=1, the same channel gives 8%, 10%, and 16% atγ=0\\gamma=0,0\.50\.5, and22\.

Figure 2\.Mean expected\-margin gap between the exact joint optimum and each of the five heuristic strategies of Table[2](https://arxiv.org/html/2610.22768#S4.T2)as the multiplierγ\\gammascales all generated upsell\-to\-cross\-sell response terms\. The same 60 synthetic instances are evaluated at each multiplier;γ=0\\gamma=0removes cross\-action coupling andγ=1\\gamma=1restores the generated reference strength\. All staged strategies are exact at zero coupling\.
#### Synthetic optimization experiments\.

In the 60\-seed interaction sweep, every staged baseline and alternating best response coincides with the joint optimum at zero coupling, as Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)\(ii\) requires\. The gaps grow with the cross\-action effect \(Figure[2](https://arxiv.org/html/2610.22768#S6.F2)\)\. At full coupling, the mean advantage of the exact joint policy, and the number of instances on which it is strictly better, is$0\.199\\$0\.199\(44/60\) over independent,$0\.111\\$0\.111\(32/60\) over upgrade\-first,$0\.084\\$0\.084\(22/60\) over add\-on\-first,$0\.026\\$0\.026\(10/60\) over greedy, and$0\.009\\$0\.009\(6/60\) over alternating best response\. Best\-response iteration recovers most of the independent gap but, by Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)\(iii\), carries no worst\-case guarantee\. The exact solver also matches exhaustive optimization on all reported small structured instances, including cyclic upgrade graphs \(Appendix Table[7](https://arxiv.org/html/2610.22768#A5.T7)\)\.

### 6\.1\.Real\-data\-calibrated evaluation

No public dataset records which recommendations were displayed and accepted, so we evaluate by*real\-data\-calibrated simulation*\(Appendix[F](https://arxiv.org/html/2610.22768#A6)\)\. Five public retail datasets provide real baskets and market structure\.*Complete Journey*supplies prices, discounts, stores and timestamps; margins are assumed\.*Ta Feng*supplies prices and per\-line cost, hence real margins\.*Instacart*supplies large\-scale in\-cart sequences but requires price imputation\.*Online Retail II*is a non\-grocery UK giftware replication\.*Carbo\-Loading*supplies paid prices and built\-in complementary categories—pasta and sauce, pancake mix and syrup—plus brand tiers and store promotion flags\. Real test\-period baskets define the decisions: up to four upsell groups with two premium alternatives each, six add\-on candidates, and budgetsL=K=2L=K=2\. Training receipts calibrate acceptance shares and the three channels of Section[3](https://arxiv.org/html/2610.22768#S3)\. Because true offer responses are unobserved, each experiment fixes one of three simulated*response truths*, which determine how shoppers actually react and against which every policy is scored\.S1\(in\-family\) follows the response model of Section[3](https://arxiv.org/html/2610.22768#S3)\.S2\(out\-of\-family\) uses logistic responses and latent shopper classes that the fitted model cannot represent exactly\.S3\(stress\) adds add\-on cannibalization, offer fatigue, and a train–test shift\. Appendix[F](https://arxiv.org/html/2610.22768#A6)gives their full specifications\. Policies are learned from simulated randomized offer logs and scored by exact expected margin under the truth\. We report incremental contribution margin per 1,000 test baskets with paired bootstrap intervals\. Appendix[F](https://arxiv.org/html/2610.22768#A6)describes each dataset and lists its source and license\.

Table 3\.Economic scorecard across five markets\(S1, the in\-family response truth of Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1); percentage of oracle offer margin\)\. Economic\-policy gain is the learned exact policy over margin\-weighted popularity in the base regime; it combines response learning and decision optimization rather than isolating accounting alone\. Joint\-selection gain uses EB shrinkage where available\. Exact\-search premium is the largest portfolio gap in the tested display\-friction map throughτ=3\\tau=3for Complete Journey/Ta Feng andτ=2\\tau=2for Instacart/Carbo\-Loading; Online Retail II has only the base comparison\.†: 63\.8% uses EB shrinkage and default imputed prices; alternative price assumptions give 2–89%\.MarketEconomic\-policy gainJoint\-selection gainExact\-search premiumvs\. margin\-pop\. \(%\)vs\. independent \(%\)vs\. portfolio \(%\)Complete Journey2\.40\.17≤0\.09\\leq 0\.09Ta Feng1\.5≈0\\approx 0≤0\.09\\leq 0\.09Instacart11\.410\.263\.8†Online Retail II1\.00\.34≈0\\approx 0Carbo\-Loading4\.70\.73≤0\.14\\leq 0\.14Table 4\.Exact joint policy minus each baseline, in expected incremental margin per 1,000 baskets \(USD; NT$ for Ta Feng; Instacart prices imputed\)\. Oracle and Exact are absolute values\. All model\-based policies use the same fitted model\.†: 95% interval contains zero\.\-: baseline significantly better\.Figure 3\.Exact joint policy minus each baseline as the receipt\-calibrated cross\-action channel effects are scaled byγ\\gamma\(in\-family truth S1, Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)\), as a percentage of the oracle’s expected margin\. Hereγ=0\\gamma=0removes the calibrated spillovers,γ=0\.5\\gamma=0\.5halves them,γ=1\\gamma=1is the reference calibration, andγ=2\\gamma=2doubles them as a stress test\.Figure 4\.Where exact optimization matters\.Left: exact minus alternating best response \(bars\) and a post\-hoc best\-of\-heuristics portfolio \(ticks\), as a percentage of oracle offer margin\. Right: exact minus the portfolio under separate budgets as display cost increases;τ\\tauis display cost divided by mean standalone add\-on value andγ\\gammascales cross\-action coupling\. Weakly coupled Complete Journey and Ta Feng remain easy\. Instacart enters a bundle\-only\-profitability regime in which all tested heuristics fail\.#### Economic accounting is first\-order\.

Table[3](https://arxiv.org/html/2610.22768#S6.T3)separates the economic\-policy gap over a margin\-weighted popularity rule, the joint\-selection gain, and the exact\-search premium across all five markets; Table[4](https://arxiv.org/html/2610.22768#S6.T4)gives the primary three\-dataset baseline detail, and Appendix Table[10](https://arxiv.org/html/2610.22768#A8.T10)gives the external\-data rows\. Unless stated otherwise, percentages are shares of*attainable offer margin*: the oracle policy’s expected incremental margin under the simulated truth, not total store profit\. On Instacart this is about $0\.47 per basket, so leaving 11% unrealized forgoes about 5 cents per basket; equivalently,StoBasketearns about 13% more than that baseline\. Against this benchmark, the learnedStoBasketpolicy comes within 0\.1% of the oracle in every market when the simulated response matches its model family, and within 0\.7% when it does not \(Table[4](https://arxiv.org/html/2610.22768#S6.T4); Appendix Table[10](https://arxiv.org/html/2610.22768#A8.T10)\)\. A relevance\-style association rule that ignores displaced and incremental margins forfeits $534 of $536 per 1,000 Complete Journey baskets, 52% of attainable margin on Ta Feng, 19% on Instacart, and 15% on Carbo\-Loading\. Weighting popularity by margin recovers most of that loss but still trails the learned economic policy by 2\.4%, 1\.5%, 11\.4%, 1\.0%, and 4\.7% on Complete Journey, Ta Feng, Instacart, Online Retail II, and Carbo\-Loading, respectively\. On Carbo\-Loading the gap reaches 27%, 54%, and 98% as display cost rises from one to two times standalone add\-on value\. Correctly valuing replacement versus addition is therefore the broad economic result; interaction\-aware optimization determines how much more can be recovered\.

Table 5\.Against prior art on shared benchmarks\(E20; percentage of oracle offer margin, 3,000 test baskets per row\)\. TIFU\-KNN\([Hu et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib17)\)is run from the reference code of the next\-basket benchmark study\([Li et al\., 2023](https://arxiv.org/html/2610.22768#bib.bib25)\)with its published hyperparameters\.ω\\omegascales a personal\-habit effect on add\-on purchase rates;ω=0\\omega=0is the reference in\-family S1 truth \(Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)\)\.*StoBasket \+ TIFU*adds the TIFU\-KNN forecast as one regressor in the same response model;*relevance*fills every offer slot with TIFU\-KNN’s top\-scored items;*×\\timesmargin*reranks them by score times margin gain\. Bold: best at the shown precision\.
#### Against prior art on the same benchmarks\.

The baselines form three tiers, all applied to the same candidates and economics\. Practice rules are classical association rules\([Agrawal et al\., 1993](https://arxiv.org/html/2610.22768#bib.bib3);[Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34)\)and profit\-aware item ranking by margin\-weighted popularity\([Louca et al\., 2019](https://arxiv.org/html/2610.22768#bib.bib28);[De Biasio et al\., 2024b](https://arxiv.org/html/2610.22768#bib.bib9)\); they measure the value of correct economics\. A published recommender, TIFU\-KNN, is described below\. The strongest tier is the five heuristics of Table[2](https://arxiv.org/html/2610.22768#S4.T2)—including independent selection as in Singh et al\.’s candidate lists and the separable regime of Ban et al\.\([Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34);[Ban et al\., 2024](https://arxiv.org/html/2610.22768#bib.bib4)\)—plus a post\-hoc portfolio of all of them\. They use the same fitted model, margins, and constraints asStoBasket, so they isolate the value of search alone: against them the exact policy nearly ties in ordinary markets, and its gains concentrate where offers pay only together \(Section[6\.3](https://arxiv.org/html/2610.22768#S6.SS3)\)\. Complete Journey’s source, Ta Feng, and Instacart are also the standard next\-basket benchmarks\([Li et al\., 2023](https://arxiv.org/html/2610.22768#bib.bib25)\), so we also run TIFU\-KNN\([Hu et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib17)\), a personalized\-frequency method that matches or exceeds deep next\-basket models on them\. Because it uses the shopper’s purchase history, whichStoBasket’s anonymous model does not, the simulated shopper receives a personal habit: add\-on purchase rates are scaled byπω\\pi^\{\\omega\}, whereπ\\piis the customer’s own category purchase rate relative to the population\. Used as the recommender, TIFU\-KNN leaves 17–111% of attainable offer margin unrealized; reranked by margin, it still leaves 11–52% \(Table[5](https://arxiv.org/html/2610.22768#S6.T5)\)\. The losses arise whereStoBasket’s accounting applies: on Complete Journey 44% of the upgrades it shows displace margin, on Ta Feng short histories leave 55% of premium alternatives unscored, and on Instacart it picks habitual add\-ons rather than those the current basket makes likely\. As one extra regressor inStoBasket’s response model, the same forecast adds 0\.3–0\.4% on Complete Journey and Ta Feng and 6\.0% on Instacart when habits matter \(ω=1\\omega=1\), and at most 0\.012% when they do not\. Next\-basket recommenders supply better forecasts;StoBasketconverts them into margin\.

#### Joint selection monetizes supported interactions\.

EB shrinkage reduces the S1 exact\-minus\-independent gain from $3\.50 to $0\.91 per 1,000 baskets on Complete Journey \(0\.17% of the oracle\), eliminates the Ta Feng gain, and retains $47 of $53 on Instacart \(10\.2%\)\. Carbo\-Loading supplies a complementary real\-price result: exact gains $1\.65 \(0\.73%\) under the in\-family truth S1, 1\.22% under the out\-of\-family truth S2, and 2\.63% when coupling is doubled\. Its real\-label gain survives both item\- and line\-label placebos, which yield $0\.13 and−$0\.22\-\\$0\.22, and EB shrinkage leaves it unchanged because the training sample is large\. A second measure uses a narrower base,*coupling value*: the part of the oracle policy’s margin that exists only because of cross\-action interactions, i\.e\., its value minus the value of the same offers with coupling switched off\. In Instacart and Carbo\-Loading, joint selection captures 32–52% of that coupling value \(Appendix Table[11](https://arxiv.org/html/2610.22768#A8.T11)\)\. The method converts a comparable share of interaction opportunity into margin; what differs most across markets is whether interactions carry 2% or more than 30% of attainable value\.

### 6\.2\.Decision\-Aware Market\-Basket Analysis

StoBasket turns classical market\-basket analysis from a descriptive association report into a decision\-aware economic diagnostic\. It keeps the familiar support, confidence, and lift\([Agrawal et al\., 1993](https://arxiv.org/html/2610.22768#bib.bib3);[Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34)\)and adds premium\-versus\-regular anchors, empirical\-Bayes shrinkage and placebos, signed cross\-action effects, contribution margin, replacement\-versus\-addition semantics, and the operational test: whether an association is large enough to change the optimized offer set\.

#### Scaling in common notation\.

ConsiderNNbaskets over a catalog ofdditems, withbnb\_\{n\}items in basketnn\. Classical mining of associations up to orderqqfaces∑j≤q\(dj\)=O⁡\(dq\)\\sum\_\{j\\leq q\}\\binom\{d\}\{j\}=O\(d^\{q\}\)candidate itemsets—polynomial in the catalog but exponential in the order—and counting requires∑n\(bnq\)\\sum\_\{n\}\\binom\{b\_\{n\}\}\{q\}*updates*, each adding one to the tally of a combination found in a basket; a 10\-item basket alone contains 210 four\-item combinations\.StoBasketpools items intoGGanchor groups andMMadd\-on cells \(G,M≤dG,M\\leq d\) and estimates one signed premium\-versus\-regular contrast per anchor/add\-on pair plus selected local moments:O⁡\(G​M\+\|E\|\)O\(GM\+\|E\|\)quantities from∑nan​mn\\sum\_\{n\}a\_\{n\}m\_\{n\}sparse updates, wherean,mn≤bna\_\{n\},m\_\{n\}\\leq b\_\{n\}count the anchor groups and add\-on cells in basketnn\. Neither count grows withqq, because effects of several offers enter through the additive channel summary rather than as separate itemsets\. At one million Instacart orders \(46,798 products, 10\.1 items per order, 134 aisle\-level groups\), four\-item mining faces2×10172\\times 10^\{17\}candidate itemsets and3\.1×1093\.1\\times 10^\{9\}subset updates, whereasStoBasketestimates 17,956 contrasts from7\.6×1077\.6\\times 10^\{7\}updates, with the average anchor group observed in about 54,000 baskets \(Appendix Table[21](https://arxiv.org/html/2610.22768#A10.T21)\)\. Pair counting costs about the same in both methods; the gap opens with association order and with the number of quantities each basket must support\. A single support threshold over that large candidate space creates the rare\-item dilemma—high support discards infrequent but valuable relationships, low support yields a combinatorial number of noisy patterns\([Liu et al\., 1999](https://arxiv.org/html/2610.22768#bib.bib26)\)—whereasStoBasketshrinks noisy contrasts toward zero by empirical Bayes\. Because the same contrasts already feed the optimizer, the report is a natural byproduct rather than a second mining model\. It is sparsity\-aware, not sparsity\-proof: relationships with no exposure remain unidentified, and a genuinely irreducible three\- or four\-item effect outside the additive summary requires an extension\.

The patterns are data\-derived\. In Carbo\-Loading’s training receipts, baskets anchored by premium pancake mix contain Aunt Jemima syrup 11\.3% of the time, versus 3\.3% for regular pancake\-mix baskets \(a3\.43×3\.43\\timesrelative rate\); private\-label syrup appears 9\.4% versus 28\.4%\. Premium pasta\-sauce baskets contain Barilla pasta 8\.2% versus 4\.8% \(Appendix Table[20](https://arxiv.org/html/2610.22768#A10.T20)\)\. Like all market\-basket statistics, these are observational; they give an interpretable opportunity report before any policy is served, and the implementation is suitable for separate open\-source release as a market\-basket\-analysis component\.

### 6\.3\.Optimization, Learning, and Deployment Insights

#### Real coupling does not always require exact search\.

The same Carbo\-Loading report reveals coherent complement and avoidance patterns, but alternating search captures them too; the heuristic portfolio remains within 0\.14% of exact even when display cost is twice standalone cross\-sell value\. Online Retail II and the noise\-corrected Complete Journey and Ta Feng results show the same operational conclusion for different reasons: either coupling is weak or local search captures it\. These markets benefit from theStoBasketeconomic objective without paying for exact search\.

#### Coupling plus display friction: exact becomes necessary\.

Instacart’s organic and premium tiers induce stronger upgrade\-to\-add\-on associations\. With separate budgets and display costτ=1\.5\\tau=1\.5times mean standalone add\-on value, the heuristic portfolio gives up 16% of oracle margin\. Atτ=2\\tau=2it gives up 65% under fixed shrinkage and 64% under EB shrinkage; when coupling is also doubled, the fixed\-shrinkage gap is 78% \($138 of $177 per 1,000 baskets\)\. Exact search remains within 0\.2–0\.5% of the oracle in the default calibration\. Here each component can be unattractive after display cost although the coupled pair is profitable, so every local method refuses the first move—the real\-basket analogue of Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)\(iii\)\. The size of the failure is price\-sensitive: atτ=2\\tau=2, the portfolio gap is 89% with a 10% organic premium, 5\.8% with a 40% premium, and 2\.0% after item\-level price noise; exact regret is at most 0\.5% except in the low\-value 10% arm\. Shared offer budgets break naive alternating by 1\.3%, 1\.5% and 21% on Complete Journey, Ta Feng and Instacart, respectively, but enumerating every fixed upsell/add\-on budget split repairs the gap to at most 0\.07%\. Thus shared budgets alone do not establish a need for exact search; bundle\-only profitability does, while prices determine how often that regime occurs\. In this regime display costs consume most of the value—attainable margin falls from $474 to $46 per 1,000 Instacart baskets atτ=2\\tau=2—so the 65% heuristic loss is about 3 cents per basket\. The finding concerns reliability: no heuristic signals when it has entered this regime, and prices alone move its loss from 2% to 89%\. Appendix[H](https://arxiv.org/html/2610.22768#A8)reports the full map\.

#### Model adequacy and economic robustness\.

Under the stress truth S3 \(Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)\), a base model that omits same\-department cannibalization and offer fatigue loses 12–17% of oracle margin\. Adding those two mechanisms to the fitted model recovers their true parameters and reduces regret to 0\.13–0\.32% even with the test\-period shift\. This controlled result shows that richer response structure can repair known misspecification, not that unknown misspecification is harmless\. Bundle economics also matter: on Instacart, ignoring a rebate equal to the add\-on margin loses $34 per 1,000 baskets \(7\.6% of oracle\), whereas alternating search with the rebate\-aware objective stays within $1\.3\. Dominick’s accounting data give national\-brand and private\-label gross margins of 22\.1% and 36\.8%; substituting these real rates for Complete Journey’s assumed rates changes the joint gain only from 0\.65% to 0\.58%\.

Figure 5\.How much prediction quality matters\(Instacart, exact optimizer held fixed\)\. Left: as randomized logged sessions grow, prediction error in policy values \(squares, dashed\) falls slowly while decision regret \(circles, solid\) falls much faster\. Right: decision regret for learned predictors versus a predictor fit to 50,000 sessions with shuffled outcomes \(hatched\)\. Percentages are of oracle offer margin; both axes in the left panel and the right panel’s vertical axis are logarithmic\.
#### How much does prediction quality matter?

StoBasketaccepts any coherent predictor, so we ask how much the response predictor, often called the propensity model, changes the economic result when everything else is fixed\. On Instacart, the market with the strongest surviving coupling, truth, candidates, budgets \(L=K=2L=K=2\), economics, and the exact optimizer are identical in every arm\. Learned predictors fit the same three\-channel model—a logistic regression for upsell acceptance, one correlation factor for joint acceptance, and a linear regression for add\-on purchase \(Appendix[F](https://arxiv.org/html/2610.22768#A6)\)—to between 100 and 50,000 randomized offer sessions\. A signal\-free predictor fits it to 50,000 sessions whose outcomes are permuted across all sessions and items: overall acceptance rates survive, but which items and offers work does not, so it effectively ranks offers by margin alone \(Figure[5](https://arxiv.org/html/2610.22768#S6.F5); Appendix Table[19](https://arxiv.org/html/2610.22768#A9.T19)\)\. Prediction quality is decisive at the bad end: the signal\-free predictor loses 38\.4% of attainable offer margin, and 100 valid sessions lose 4\.6%\. Decision value then saturates quickly: 500 sessions come within 0\.37% of the oracle, 1,000 within 0\.30%, and 5,000 within 0\.06%\. Economic regret falls far faster than prediction error: from 1,000 to 50,000 sessions, policy\-value error falls only from 5\.1% to 2\.3% and the oracle’s exact offer set is chosen 85% and 96% of the time\. Competing offer sets are often nearly tied—the median gap between the best and second\-best policy is $0\.003 per basket—so residual errors usually swap one near\-optimal set for another, and the2​ε2\\varepsilonbound of Eq\. \([7](https://arxiv.org/html/2610.22768#S5.E7)\) is a worst case\. Because the predictor shares the simulated truth’s functional form, these curves are a best case; Section[8\.3](https://arxiv.org/html/2610.22768#S8.SS3)brackets misspecification\.

#### Profit saturates before accuracy: security selection and portfolio construction\.

The closest practitioner analogy is active equity management, which separates*alpha forecasting*from*portfolio construction*: a model scores expected returns, security selection ranks the stocks, and an optimizer converts the scores into positions under risk and capacity constraints\. Forecast skill is summarized by the*information coefficient*, the correlation between scores and subsequent returns, because a useful ranking can build a good book even when return magnitudes are poorly calibrated; modest skill applied across many independent opportunities produces meaningful performance\([Grinold, 1989](https://arxiv.org/html/2610.22768#bib.bib15);[Grinold and Kahn, 2000](https://arxiv.org/html/2610.22768#bib.bib16)\)\. InStoBasket, predicted offer value is the alpha signal, ranking candidate offer sets is security selection, display and compatibility limits are portfolio constraints, and exact optimization is portfolio construction\. Decision analysis calls the resulting insensitivity a*flat maximum*\([von Winterfeldt and Edwards, 1982](https://arxiv.org/html/2610.22768#bib.bib36)\), and predict\-then\-optimize formalizes that decision loss, not forecast error alone, is the relevant metric\([Elmachtoub and Grigas, 2022](https://arxiv.org/html/2610.22768#bib.bib13)\)\.

#### Is calibrated coupling real?

Scaling channel effects byγ\\gammagives zero gaps atγ=0\\gamma=0and increasing gaps thereafter \(Figure[3](https://arxiv.org/html/2610.22768#S6.F3)\)\. EB shrinkage drives line\-placebo gains to approximately zero, retains mean coupling weight 0\.89 on Instacart and 0\.50 on Complete Journey, and detects no signal on Ta Feng\. Carbo\-Loading strengthens this diagnostic: its 2\.5 million training baskets make shrinkage negligible, yet both label placebos remove the gain while cross\-commodity effects remain under real labels\. We therefore treat Instacart and Carbo\-Loading as the supported coupling calibrations, with Carbo adding real paid prices\. These tests establish that the receipt associations are structured rather than sampling noise; they do not turn observational co\-purchase into a causal offer effect\.

#### Randomized evidence for an exposure channel\.

Building on exposure\-aware recommenders that distinguish awareness from preference\([Sato et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib33)\), we test whether neighboring display changes response in 454,265 screens from the Open Bandit Dataset’s uniform\-random fashion slates\([Saito et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib32)\)\. Holding focal item and position fixed, each same\-category neighbor at the coarsest seven\-level category lowers focal click probability by 12\.3% \(slate\-randomizationp=0\.012p=0\.012, Holm\-adjustedp=0\.036p=0\.036across three category resolutions\)\. Neighbor attractiveness and the other category resolutions are null\. Clicks are nine times more likely when a neighbor is clicked, but that association is not causal\. This experiment supplies causal evidence for the exposure channel used by our economic policy\. Its scope is fashion clicks; a field experiment will test the complete mechanism for grocery purchases\.

#### Graph structure and exactness at scale\.

Real upsell interaction graphs are seldom forests: half of Complete Journey’s graphs over upgrade\-eligible items contain a cycle, and 94% do when eight or more items are eligible\. With up to 20 upsell groups, enumeration and the tree\-decomposition DP agree on all 8,040 checked baskets\. Exact serving is fast once the enumeration is vectorized: scoring every feasible upsell policy at once with array operations, rather than one at a time in a Python loop, solves all 3,600 held\-out baskets atL=4L=4in 0\.13 ms median, 30 ms p99, and 111 ms maximum on one core, with values matching brute force or DP on all 8,100 solves\. An earlier scalar implementation took 1\.1 ms median and up to 3\.0 s \(Appendix Table[18](https://arxiv.org/html/2610.22768#A9.T18)\)\. The slow tail came from Python per\-policy overhead on dense 20\-group baskets, not from the problem’s difficulty, so no native\-code rewrite is needed at these budgets\. Budgets aboveL=4L=4, where enumeration grows asO⁡\(\(G​J\)L\)O\(\(GJ\)^\{L\}\)and graphical DP becomes the scalable route, remain untested\.

Table 6\.How StoBasket advances representative foundations\.Prior work supplies essential capabilities; StoBasket connects them in a joint post\-basket decision over interacting replacement and addition offers\.

## 7\.Relationship to Prior Work

Table[6](https://arxiv.org/html/2610.22768#S6.T6)summarizes the foundations and the advance\. The new object is the*joint post\-basket edit policy*, which differs from item ranking or assortment in three ways\. Actions are typed:REPLACEremoves an incumbent and earns a margin difference, whereasADDearns incremental margin\. Response is policy\-conditioned across action types, through separate display, acceptance, and joint\-acceptance channels\. And the optimization results match that decision: when separate pipelines are exact, why staged methods have no constant\-factor guarantee under coupling, and a global certificate for a structured class\. The closest precedents each supply part of this object\. Singh et al\. rank upsell and cross\-sell candidates for a current basket\([Singh et al\., 2006](https://arxiv.org/html/2610.22768#bib.bib34)\); Ban et al\. jointly formulate upgraded substitutes and co\-purchases under responses that separate\([Ban et al\., 2024](https://arxiv.org/html/2610.22768#bib.bib4)\); Acar retrieves cross\-category candidates\([Acar, 2026](https://arxiv.org/html/2610.22768#bib.bib2)\); next\-basket recommenders such as TIFU\-KNN forecast purchases thatStoBasketcan use as an input\([Hu et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib17);[Li et al\., 2023](https://arxiv.org/html/2610.22768#bib.bib25)\); linked\-category choice models represent related decisions without typed basket edits\([Ke and Wang, 2022](https://arxiv.org/html/2610.22768#bib.bib24);[El Housni et al\., 2025](https://arxiv.org/html/2610.22768#bib.bib12)\); and Lo–Topaloglu and Del Pia supply the sparse\-interaction and factorized\-optimization techniques that the exact solver combines\([Lo and Topaloglu, 2019](https://arxiv.org/html/2610.22768#bib.bib27);[Del Pia, 2025](https://arxiv.org/html/2610.22768#bib.bib10)\)\. Causal\-mediation and exposure\-bias methods underlie the logging requirements\([Imai et al\., 2010](https://arxiv.org/html/2610.22768#bib.bib18);[Chen et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib7)\)\.

## 8\.Discussion and Limitations

### 8\.1\.Six Key Insights

Percentages below are shares of attainable incremental*offer*margin, not total store profit\.

#### 1\. Optimize margin, not recommendation scores\.

Across all five markets, treating an upsell as a replacement and a cross\-sell as an addition changes which offers should be shown\. Even after popularity is weighted by margin, the remaining opportunity is1\.0–11\.4%\. A published next\-basket recommender used directly leaves11–52%unrealized after margin reranking, but adds up to6%when its forecast is fed intoStoBasket\. The product implication is simple: a better predictor is an input; it is not a substitute for the economic decision layer\.

#### 2\. Historical data reflects the offer program that produced it\.

Joint selection gains10\.2%on digitally active Instacart, compared with0\.17%on Complete Journey and approximately zero on Ta Feng\. Weak measured coupling can describe current merchandising rather than the ceiling of customer response\. A retailer should therefore test joint offers before concluding that its market has no interaction opportunity\.

#### 3\. The response layer is also market\-basket analysis\.

The same estimates used to choose offers produce premium\-conditioned support, confidence, lift, signed complement or avoidance effects, and contribution margin\. For example, premium pancake\-mix baskets contain Aunt Jemima syrup11\.3%of the time versus3\.3%for regular\-mix baskets, a3\.43×3\.43\\timesrelative rate\. This decision\-aware market\-basket report is an interpretable product byproduct, while remaining explicitly observational rather than causal\.

#### 4\. Ranking offer sets matters more than perfect probability forecasts\.

With 1,000 randomized sessions, policy\-value error remains5\.1%, yet the resulting margin regret is only0\.30%; residual errors usually exchange nearly tied policies\. In contrast, a predictor trained on shuffled outcomes loses38%\. The practical target is therefore useful signal and correct decision ranking, not marginal accuracy improvements after economic value has saturated\.

#### 5\. Exact optimization provides a trust anchor\.

For every instance satisfying Proposition[4\.1](https://arxiv.org/html/2610.22768#S4.Thmtheorem1),StoBasketreturns the globally best feasible offer set under the supplied model: no heuristic can produce greater predicted margin for that same basket, objective, and response estimates\. Retailers may still deploy faster heuristics; the exact solution supplies the benchmark that certifies them and measures their optimization gap\. That distinction matters little in ordinary markets, where strong heuristics stay within0\.09–0\.14%, but matters sharply in the bundle\-only regime, where they lose65%\. A heuristic gives no warning when it enters that regime—Instacart price assumptions alone move its loss from 2% to 89%—so the value of the guarantee is that a retailer need not guess\. Exact serving takes0\.13 ms at the medianand at most111 mson every tested real basket\. The guarantee removes search error; it does not correct bad response data or model misspecification\.

#### 6\. Structure makes that certificate computationally practical\.

The unrestricted interacting\-offer problem is NP\-hard \(Appendix[D](https://arxiv.org/html/2610.22768#A4)\)\. Fixed\-dimensional response channels and local interaction factors convert the stated class into an exact polynomial\-time problem, and two independent exact methods agree on all8,040 of 8,040checked real baskets\. The contribution is therefore not merely a smarter heuristic: it identifies the conditions under which a global certificate is both mathematically valid and operationally affordable\.

### 8\.2\.Industrial Impact and Deployment

The gains are market\-dependent, and that dependence is itself actionable\. Joint selection earns the most where premium tiers and add\-ons are strongly linked, as in Instacart; where measured coupling is weak, the economic objective still recovers margin and fast heuristics suffice\. We interpret this pattern as a statement about merchandising practice as much as about shoppers\. Receipts record behavior under a retailer’s existing offer regime\. Instacart operates a digital platform on which ranking models were already in production when its public data were released\([Stanley, 2017](https://arxiv.org/html/2610.22768#bib.bib35)\); today it serves in\-cart complement suggestions, real\-time personalized recommendations, and brand coupons that appear on item cards and prompt shoppers in the cart\([Jia, 2023](https://arxiv.org/html/2610.22768#bib.bib22);[Ruan et al\., 2023](https://arxiv.org/html/2610.22768#bib.bib30);[Instacart Ads, 2026](https://arxiv.org/html/2610.22768#bib.bib20)\)\. Its baskets display the strongest premium\-to\-add\-on coupling in our study\. Complete Journey and Ta Feng record more conventional retail settings, where premium tiers and complements are less often presented together, and their receipts show weak coupling\. A retailer that rarely pairs premium items with complements will observe little such association in its data; that silence measures the current regime, not the ceiling of the opportunity\.

This interpretation is a hypothesis that our observational data cannot settle, but it carries a clear prescription\. A retailer whose historical data shows little joint\-selection value should not conclude that its shoppers lack the opportunity\. It should run randomized joint offers\. Randomization refreshes the data with logged exposure and acceptance, identifies the display and acceptance channels that receipts cannot separate, and reveals whether coupling emerges once offers are actually made\. The relationship is self\-reinforcing: the more actively a retailer experiments with joint upsell and cross\-sell offers, the richer the interaction data becomes, and the more valueStoBasketcan extract from it\.

### 8\.3\.Scope and Next Steps

#### \(1\) Scope of the exactness guarantee\.

The guarantees apply to coherent acceptance moments, factor\-local dependence, bounded interaction width, and fixed response dimension\. Arbitrary choice laws, optimized promotion amounts, and high\-order bundle conditions may require different algorithms\. Latency was measured only forL≤4L\\leq 4and at most 20 upsell groups; larger offer budgets are where graphical DP should matter most\.

#### \(2\) Cost of the structured approximation\.

Exactness holds within the structured projection of Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\), not for arbitrary customer response\. If the projected value approximates the true value withinε\\varepsilonfor every offer set, the plug\-in argument of Eq\. \([7](https://arxiv.org/html/2610.22768#S5.E7)\) bounds structural regret by2​ε2\\varepsilon; without such a bound, a nonlinear response law can reverse policy rankings\. Empirically, under the out\-of\-family truth S2 \(Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)\), whose logistic saturation, latent classes, and three\-way response lie outside the fitted family, regret is only 0\.02–0\.69% across five datasets\. Under the stress truth S3, omitting cannibalization, fatigue, and temporal shift costs 10\.6–19\.3%, and modeling cannibalization and fatigue reduces it to 0\.08–0\.32%\. Smooth curvature can be benign; omitted mechanisms that create new interactions are not\.

#### \(3\) Evidence is calibrated simulation, not live uplift\.

Receipt co\-occurrence alone cannot identify the causal effect of displaying recommendations\([Imai et al\., 2010](https://arxiv.org/html/2610.22768#bib.bib18);[Chen et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib7)\)\. Carbo\-Loading has real paid prices but assumed margins, and alternative imputations of Instacart’s missing prices move the high\-friction heuristic gap atτ=2\\tau=2from 2% to 89%\. The randomized fashion result independently identifies a display effect, but for clicks rather than grocery purchases\.

#### \(4\) Learning results assume the right model family\.

The stress\-test recovery and the prediction\-quality results both use one calibrated truth and a correctly specified response family, so a field test should confirm the required log size in each market\. Without a simulator, a retailer can check the same property on its own data: hold out randomized sessions and compare predicted with realized offer margin, retrain on growing log sizes to see whether policy value has plateaued, and estimate new policies off\-policy from logged selection probabilities before serving them \(Appendix[K\.1](https://arxiv.org/html/2610.22768#A11.SS1)\)\.

#### \(5\) Next step: an A/B test any retailer can run\.

A retailer can measureStoBasket’s uplift on its own traffic in five steps \(Appendix[K\.1](https://arxiv.org/html/2610.22768#A11.SS1)\)\. First, use the market\-basket diagnostic of Section[6\.2](https://arxiv.org/html/2610.22768#S6.SS2)to choose a category with strong premium\-to\-add\-on coupling\. Second, randomize each basket, by a hash of its session identifier, to the current recommender or toStoBasket, keeping a small no\-offer arm and a 5–10% uniformly random arm for re\-estimation\. Third, log what was shown, its selection probability, what was accepted, the final basket, and realized prices, costs, and rebates\. Fourth, compare arms on offer\-attributable incremental contribution margin per basket\. Fifth, size the test from Appendix Table[22](https://arxiv.org/html/2610.22768#A11.T22): about 1,400 baskets per arm under Instacart\-like coupling with offer\-level logs, but 20–50 times more if only till receipts are available\.

#### \(6\) Next step: campaigns that make coupling learnable\.

Weak coupling in historical receipts can reflect how offers were run rather than how shoppers respond\. When upsell and cross\-sell programs are planned, owned, and measured separately, premium items and their complements are seldom shown together; the logs then contain little joint exposure, and the coupling coefficients are not identified\. This is the positivity requirement of causal and off\-policy evaluation\([Chen et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib7);[Saito et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib32)\)applied to merchandising: an effect that is never exposed cannot be learned, and its absence from the data is not evidence that it is zero\. The same separation also produces the staging trap of Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2), because each program judges its offers alone\. The remedy is operational rather than algorithmic: co\-display premium anchors with candidate complements under one contribution\-margin objective, keep a small randomized share with logged selection probabilities, record shown and accepted offers separately, and direct exploration toward the cells that the shrinkage diagnostic marks as uninformative\. Appendix[K\.2](https://arxiv.org/html/2610.22768#A11.SS2)gives the full recipe\.

## 9\.Conclusion

StoBasketcontributes a formulation before it contributes a solver\. To our knowledge, it is the first formulation of joint upsell and cross\-sell selection in which the two responses are coupled; separable treatments are its zero\-coupling special case\. With a correctly structured response model fit to a few thousand or more randomized offer sessions,StoBasketcomes within 0\.5% of the best attainable offer margin in every default\-price setting of five retail markets, and within 0\.7% when the true response lies outside its model family; where it falls short, the cause is the response model, never the search\. Across those markets, correctly accounting for displaced and incremental margin is the largest and most consistent source of value\. Joint selection pays most where interactions are strong, beating independent selection on Instacart by 10\.2% of attainable offer margin\. Exact optimization is a targeted final layer: unnecessary when alternating search captures the interaction, as on Carbo\-Loading, but decisive when actions pay only together\. Its certificate is practical—exact methods agree on every checked real basket, and vectorized exact search takes 0\.13 ms at the median and at most 111 ms—and serves as a trust anchor that removes search error, leaving prediction quality and economic inputs as separate, measurable risks\. The predictor must rank offer sets correctly rather than forecast perfectly, so a few thousand randomized sessions suffice\. The next step is a randomized field test in an interaction\-heavy category, with shown offers, acceptances, realized costs, and contribution margin logged end to end\.

## References

- Acar \(2026\)Serhat Mirkan Acar\. 2026\.Cross\-Category Basket Recommendation via Transactional Debiasing and Graph Propagation\. In*Proceedings of the 49th International ACM SIGIR Conference on Research and Development in Information Retrieval*\. Association for Computing Machinery\.[doi:10\.1145/3805712\.3808425](https://doi.org/10.1145/3805712.3808425)
- Agrawal et al\.\(1993\)Rakesh Agrawal, Tomasz Imieliński, and Arun Swami\. 1993\.Mining Association Rules between Sets of Items in Large Databases\. In*Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data*\. 207–216\.[doi:10\.1145/170035\.170072](https://doi.org/10.1145/170035.170072)
- Ban et al\.\(2024\)Gah\-Yi Ban, M\. Hichame Benbitour, and Boxiao Chen\. 2024\.Selling Personalized Substitutes and Co\-Purchases in Online Grocery Retail\.Working paper, SSRN 4911633\.[https://papers\.ssrn\.com/sol3/papers\.cfm?abstract\_id=4911633](https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4911633)
- Boehmke and Mortimer \(2025\)Brad Boehmke and Steven M\. Mortimer\. 2025\.completejourney: Retail Shopping Data\.R package version 1\.1\.1, data from the 84\.51° Complete Journey 2\.0 source files\.[https://CRAN\.R\-project\.org/package=completejourney](https://cran.r-project.org/package=completejourney)
- Chen \(2012\)Daqing Chen\. 2012\.Online Retail II\.UCI Machine Learning Repository\.[doi:10\.24432/C5CG6D](https://doi.org/10.24432/C5CG6D)
- Chen et al\.\(2020\)Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He\. 2020\.Bias and Debias in Recommender System: A Survey and Future Directions\.arXiv:2010\.03240[https://arxiv\.org/abs/2010\.03240](https://arxiv.org/abs/2010.03240)
- De Biasio et al\.\(2024a\)Alvise De Biasio, Dietmar Jannach, and Nicolò Navarin\. 2024a\.Model\-Based Approaches to Profit\-Aware Recommendation\.*Expert Systems with Applications*249 \(2024\), 123642\.[doi:10\.1016/j\.eswa\.2024\.123642](https://doi.org/10.1016/j.eswa.2024.123642)
- De Biasio et al\.\(2024b\)Alvise De Biasio, Nicolò Navarin, and Dietmar Jannach\. 2024b\.Economic Recommender Systems: A Systematic Review\.*Electronic Commerce Research and Applications*63 \(2024\), 101352\.[doi:10\.1016/j\.elerap\.2023\.101352](https://doi.org/10.1016/j.elerap.2023.101352)
- Del Pia \(2025\)Alberto Del Pia\. 2025\.Factorized Binary Polynomial Optimization\.Mathematical Programming \(online publication\)\.[doi:10\.1007/s10107\-025\-02274\-5](https://doi.org/10.1007/s10107-025-02274-5)
- dunnhumby \(2026\)dunnhumby\. 2026\.Carbo\-Loading: A Relational Database\.dunnhumby Source Files, accessed October 2026\.[https://www\.dunnhumby\.com/source\-files/](https://www.dunnhumby.com/source-files/)
- El Housni et al\.\(2025\)Omar El Housni, Shuo Sun, and Rajan Udwani\. 2025\.A Markovian Approach for Cross\-Category Complementarity in Choice Modeling\.arXiv:2508\.18566[https://arxiv\.org/abs/2508\.18566](https://arxiv.org/abs/2508.18566)
- Elmachtoub and Grigas \(2022\)Adam N\. Elmachtoub and Paul Grigas\. 2022\.Smart “Predict, then Optimize”\.*Management Science*68, 1 \(2022\), 9–26\.[doi:10\.1287/mnsc\.2020\.3922](https://doi.org/10.1287/mnsc.2020.3922)
- Erginbas et al\.\(2025\)Yigit Efe Erginbas, Thomas Courtade, and Kannan Ramchandran\. 2025\.Online Assortment and Price Optimization Under Contextual Choice Models\. In*Proceedings of the 28th International Conference on Artificial Intelligence and Statistics*, Vol\. 258\. PMLR, 4456–4464\.[https://proceedings\.mlr\.press/v258/erginbas25a\.html](https://proceedings.mlr.press/v258/erginbas25a.html)
- Grinold \(1989\)Richard C\. Grinold\. 1989\.The Fundamental Law of Active Management\.*The Journal of Portfolio Management*15, 3 \(1989\), 30–37\.[doi:10\.3905/jpm\.1989\.409211](https://doi.org/10.3905/jpm.1989.409211)
- Grinold and Kahn \(2000\)Richard C\. Grinold and Ronald N\. Kahn\. 2000\.*Active Portfolio Management: A Quantitative Approach for Producing Superior Returns and Controlling Risk*\(2nd ed\.\)\.McGraw\-Hill, New York\.
- Hu et al\.\(2020\)Haoji Hu, Xiangnan He, Jinyang Gao, and Zhi\-Li Zhang\. 2020\.Modeling Personalized Item Frequency Information for Next\-basket Recommendation\. In*Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval*\. Association for Computing Machinery, 1071–1080\.[doi:10\.1145/3397271\.3401066](https://doi.org/10.1145/3397271.3401066)
- Imai et al\.\(2010\)Kosuke Imai, Luke Keele, and Teppei Yamamoto\. 2010\.Identification, Inference and Sensitivity Analysis for Causal Mediation Effects\.*Statist\. Sci\.*25, 1 \(2010\), 51–71\.[doi:10\.1214/10\-STS321](https://doi.org/10.1214/10-STS321)
- Instacart \(2017\)Instacart\. 2017\.The Instacart Online Grocery Shopping Dataset 2017\.[https://www\.instacart\.com/datasets/grocery\-shopping\-2017](https://www.instacart.com/datasets/grocery-shopping-2017)
- Instacart Ads \(2026\)Instacart Ads\. 2026\.Promotions\.Product documentation, accessed October 2026\.[https://www\.instacart\.com/company/ads/products/promotions](https://www.instacart.com/company/ads/products/promotions)
- James M\. Kilts Center for Marketing, University of Chicago Booth School of Business \(2026\)James M\. Kilts Center for Marketing, University of Chicago Booth School of Business\. 2026\.Dominick’s Finer Foods Dataset\.Accessed October 2026\.[https://www\.chicagobooth\.edu/research/kilts/research\-data/dominicks](https://www.chicagobooth.edu/research/kilts/research-data/dominicks)
- Jia \(2023\)Cheng Jia\. 2023\.One Model to Serve Them All: How Instacart Deployed a Single Deep Learning pCTR Model for Multiple Surfaces\.tech\-at\-instacart \(Instacart engineering blog\)\.[https://tech\.instacart\.com/one\-model\-to\-serve\-them\-all\-0eb6bf60b00d](https://tech.instacart.com/one-model-to-serve-them-all-0eb6bf60b00d)
- Kaggle user chiranjivdas09 \(2026\)Kaggle user chiranjivdas09\. 2026\.Ta Feng Grocery Dataset\.Kaggle, as redistributed with the choice\-learn Python package; accessed October 2026\.[https://www\.kaggle\.com/datasets/chiranjivdas09/ta\-feng\-grocery\-dataset](https://www.kaggle.com/datasets/chiranjivdas09/ta-feng-grocery-dataset)
- Ke and Wang \(2022\)Chenxu Ke and Ruxian Wang\. 2022\.Cross\-Category Retailing Management: Substitution and Complementarity\.*Manufacturing & Service Operations Management*24, 2 \(2022\), 1128–1145\.[doi:10\.1287/msom\.2021\.0968](https://doi.org/10.1287/msom.2021.0968)
- Li et al\.\(2023\)Ming Li, Sami Jullien, Mozhdeh Ariannezhad, and Maarten de Rijke\. 2023\.A Next Basket Recommendation Reality Check\.*ACM Transactions on Information Systems*41, 4 \(2023\), 116\.[doi:10\.1145/3587153](https://doi.org/10.1145/3587153)
- Liu et al\.\(1999\)Bing Liu, Wynne Hsu, and Yiming Ma\. 1999\.Mining Association Rules with Multiple Minimum Supports\. In*Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*\. 337–341\.[doi:10\.1145/312129\.312274](https://doi.org/10.1145/312129.312274)
- Lo and Topaloglu \(2019\)Venus Lo and Huseyin Topaloglu\. 2019\.Assortment Optimization under the Multinomial Logit Model with Product Synergies\.*Operations Research Letters*47, 6 \(2019\), 546–552\.[doi:10\.1016/j\.orl\.2019\.09\.009](https://doi.org/10.1016/j.orl.2019.09.009)
- Louca et al\.\(2019\)Raphael Louca, Moumita Bhattacharya, Diane Hu, and Liangjie Hong\. 2019\.Joint Optimization of Profit and Relevance for Recommendation Systems in E\-Commerce\. In*Workshop on Recommendation in Multistakeholder Environments \(RMSE@RecSys\)**\(CEUR Workshop Proceedings, Vol\. 2440\)*\.[https://ceur\-ws\.org/Vol\-2440/short1\.pdf](https://ceur-ws.org/Vol-2440/short1.pdf)
- McAuley et al\.\(2015\)Julian McAuley, Rahul Pandey, and Jure Leskovec\. 2015\.Inferring Networks of Substitutable and Complementary Products\. In*Proceedings of KDD*\. Association for Computing Machinery, New York, NY, USA, 785–794\.[doi:10\.1145/2783258\.2783381](https://doi.org/10.1145/2783258.2783381)
- Ruan et al\.\(2023\)Chuanwei Ruan, Allan Stewart, Han Li, Ryan Ye, David Vengerov, and Haixun Wang\. 2023\.Dynamic Embedding\-based Retrieval for Personalized Item Recommendations at Instacart\. In*Companion Proceedings of the ACM Web Conference 2023*\. Association for Computing Machinery, 983–987\.[doi:10\.1145/3543873\.3587668](https://doi.org/10.1145/3543873.3587668)
- Ruiz et al\.\(2020\)Francisco J\. R\. Ruiz, Susan Athey, and David M\. Blei\. 2020\.SHOPPER: A Probabilistic Model of Consumer Choice with Substitutes and Complements\.*The Annals of Applied Statistics*14, 1 \(2020\), 1–27\.[doi:10\.1214/19\-AOAS1265](https://doi.org/10.1214/19-AOAS1265)
- Saito et al\.\(2020\)Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita\. 2020\.Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off\-Policy Evaluation\. In*Advances in Neural Information Processing Systems*, Vol\. 33\. 12290–12301\.[https://proceedings\.neurips\.cc/paper/2020/hash/8b5c8441a8ff8e151b191c53c1842a38\-Abstract\.html](https://proceedings.neurips.cc/paper/2020/hash/8b5c8441a8ff8e151b191c53c1842a38-Abstract.html)
- Sato et al\.\(2020\)Masahiro Sato, Janmajay Singh, Sho Takemori, Takashi Sonoda, Qian Zhang, and Tomoko Ohkuma\. 2020\.Modeling User Exposure with Recommendation Influence\. In*Proceedings of the 35th Annual ACM Symposium on Applied Computing*\. 1461–1464\.[doi:10\.1145/3341105\.3375760](https://doi.org/10.1145/3341105.3375760)
- Singh et al\.\(2006\)Pramod Singh, A\. Charles Thomas, and Ariel Sepulveda\. 2006\.Market Basket Recommendations for the HP SMB Store\.*ACM SIGKDD Explorations Newsletter*8, 1 \(2006\), 57–64\.[doi:10\.1145/1147234\.1147243](https://doi.org/10.1145/1147234.1147243)
- Stanley \(2017\)Jeremy Stanley\. 2017\.3 Million Instacart Orders, Open Sourced\.tech\-at\-instacart \(Instacart engineering blog\)\.[https://tech\.instacart\.com/3\-million\-instacart\-orders\-open\-sourced\-d40d29ead6f2](https://tech.instacart.com/3-million-instacart-orders-open-sourced-d40d29ead6f2)
- von Winterfeldt and Edwards \(1982\)Detlof von Winterfeldt and Ward Edwards\. 1982\.Costs and Payoffs in Perceptual Research\.*Psychological Bulletin*91, 3 \(1982\), 609–622\.[doi:10\.1037/0033\-2909\.91\.3\.609](https://doi.org/10.1037/0033-2909.91.3.609)

## Appendix AResponse model and economic scope

### A\.1\.Feasible basket edits

Partition a current basket intoGGincumbent groups\. Each groupggpermits one chosen upgrade offerxg∈\{0,1,…,Jg\}x\_\{g\}\\in\\\{0,1,\\ldots,J\_\{g\}\\\}, withxg=0x\_\{g\}=0denoting no offer\. At mostLLgroups receive an upgrade offer\. Independently, choose a set of offered additionsC⊆\[M\]C\\subseteq\[M\]with\|C\|≤K\|C\|\\leq K\. These are*simultaneously selected offers*, not assumed purchases\. An accepted upgrade removes its incumbent and inserts an alternative\. A purchased add\-on inserts an item without removing an incumbent\. The action constraints prevent conflicting replacements by construction\.

LetYg∈\{0,1\}Y\_\{g\}\\in\\\{0,1\\\}indicate acceptance of the offered upgrade \(zero whenxg=0x\_\{g\}=0\)\. For fixed contextss, writepg​\(xg,s\)=Pr⁡\(Yg=1∣xg,s\)p\_\{g\}\(x\_\{g\};s\)=\\Pr\(Y\_\{g\}=1\\mid x\_\{g\},s\)and, for edges\(g,h\)\(g,h\)of a graphH=\(V,E\)H=\(V,E\),

\(8\)ρg​h​\(xg,xh,s\)=Pr⁡\(Yg=Yh=1∣xg,xh,s\)\.\\rho\_\{gh\}\(x\_\{g\},x\_\{h\};s\)=\\Pr\(Y\_\{g\}=Y\_\{h\}=1\\mid x\_\{g\},x\_\{h\},s\)\.Crucially,ρg​h\\rho\_\{gh\}need not equalpg​php\_\{g\}p\_\{h\}\. We assume these first and edgewise second moments are*policy\-local*: changing offers outside their endpoints does not change these moments\. We also assume the supplied moments come from a consistent joint distribution\. On a forest, compatible edgewise binary marginals specify at least one such distribution\.

### A\.2\.Offered and realized utility effects

For each active groupgg, letdg​\(xg\)d\_\{g\}\(x\_\{g\}\)be the incremental accepted\-upgrade margin,tg​\(xg\)t\_\{g\}\(x\_\{g\}\)its accepted latent displacement,vg​\(xg\)v\_\{g\}\(x\_\{g\}\)its*presentation*feature, andcg​\(xg\)c\_\{g\}\(x\_\{g\}\)the cost of displaying it\. Each offered complementkkhas incremental marginmk≥0m\_\{k\}\\geq 0in this nonpromotional or fixed\-terms subclass and display costckc\_\{k\}\. We allow pairwise upgrade effects on edges: accepted upgradesg,hg,hmay contribute extra marginγg​h​\(xg,xh\)\\gamma\_\{gh\}\(x\_\{g\},x\_\{h\}\)and a latent interaction featureζg​h​\(xg,xh\)\\zeta\_\{gh\}\(x\_\{g\},x\_\{h\}\)\.

A structured*conditional*add\-on acceptance model is

\(9\)qk​\(Y,x\)=ak\+bk⊤​∑gYg​tg​\(xg\)\+ek⊤∑gvg\(xg\)\+hk⊤∑\(g,h\)∈EYgYhζg​h\(xg,xh\),\\begin\{split\}q\_\{k\}\(Y,x\)=\{\}&a\_\{k\}\+b\_\{k\}^\{\\top\}\\sum\_\{g\}Y\_\{g\}t\_\{g\}\(x\_\{g\}\)\\\\ &\+e\_\{k\}^\{\\top\}\\sum\_\{g\}v\_\{g\}\(x\_\{g\}\)\+h\_\{k\}^\{\\top\}\\sum\_\{\(g,h\)\\in E\}Y\_\{g\}Y\_\{h\}\\zeta\_\{gh\}\(x\_\{g\},x\_\{h\}\),\\end\{split\}where each feature may be vector\-valued\. Parameters must satisfy0≤qk​\(Y,x\)≤10\\leq q\_\{k\}\(Y,x\)\\leq 1for every feasible action/acceptance realization\. The model allows an offer to affect another item’s purchase probability*even when rejected*\. We do not require add\-on purchases to be conditionally independent, but assume their expected margin is additive and the purchase probabilities do not depend on which other additions are offered\. These conditions specify the tractable conditional\-response family analyzed below\.

Define the finite\-dimensional moment summary

\(10\)z⁡\(x\)=\(CLOSE\\displaystyle z\(x\)=\\Big\(∑gpg​\(xg\)​tg​\(xg\),∑gvg​\(xg\),\\displaystyle\\sum\_\{g\}p\_\{g\}\(x\_\{g\}\)t\_\{g\}\(x\_\{g\}\),\\,\\sum\_\{g\}v\_\{g\}\(x\_\{g\}\),OPEN∑\(g,h\)∈Eρg​h​\(xg,xh\)​ζg​h​\(xg,xh\)\)∈ℝr\.\\displaystyle\\sum\_\{\(g,h\)\\in E\}\\rho\_\{gh\}\(x\_\{g\},x\_\{h\}\)\\zeta\_\{gh\}\(x\_\{g\},x\_\{h\}\)\\Big\)\\in\\mathbb\{R\}^\{r\}\.Absorb the appropriate coefficients intoβk=mk​\(bk,ek,hk\)\\beta\_\{k\}=m\_\{k\}\(b\_\{k\},e\_\{k\},h\_\{k\}\)and letαk=mk​ak−ck\\alpha\_\{k\}=m\_\{k\}a\_\{k\}\-c\_\{k\}, whereckc\_\{k\}is the display cost of add\-onkk\. The expected incremental margin of the policy is

\(11\)F⁡\(x,C\)=∑g\[pg​dg−cg\]⏟U⁡\(x\)\+∑\(g,h\)∈Eρg​h​γg​h\+∑k∈C\(αk\+βk⊤​z​\(x\)\)⏟ℓk​\(z​\(x\)\)\.\\boxed\{\\begin\{aligned\} F\(x,C\)=\{\}&\\underbrace\{\\sum\_\{g\}\[p\_\{g\}d\_\{g\}\-c\_\{g\}\]\}\_\{U\(x\)\}\+\\sum\_\{\(g,h\)\\in E\}\\rho\_\{gh\}\\gamma\_\{gh\}\\\\ &\+\\sum\_\{k\\in C\}\\underbrace\{\(\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z\(x\)\)\}\_\{\\ell\_\{k\}\(z\(x\)\)\}\.\\end\{aligned\}\}The optimization ismaxx,C⁡F⁡\(x,C\)\\max\_\{x,C\}F\(x,C\)under∑g𝟏\{xg≠0\}≤L\\sum\_\{g\}\\mathbf\{1\}\\\{x\_\{g\}\\neq 0\\\}\\leq Land\|C\|≤K\|C\|\\leq K\. Allp,ρ,d,t,v,γ,ζp,\\rho,d,t,v,\\gamma,\\zetaare evaluated at the chosen local actions and fixed observed contextss; we suppressssfrom most expressions for readability\. The baseline incumbent margin cancels when taking incremental profit\.

### A\.3\.Context conditioning

Every quantity in this appendix is conditional on one fixed transaction contexts=\(B,ℓ,τ,P,I,…\)s=\(B,\\ell,\\tau,P,I,\\ldots\): the basket, store or verified regionℓ\\ell, store\-local timeτ\\tau, pricesPP, and available inventoryII\. Acceptance moments and add\-on response coefficients may vary withss, and sparse location–time strata back off to coarser estimates\. The exactness conditions below must hold for each fixed context; dependence induced by an arbitrary trained conditional model does not satisfy them automatically\.

### A\.4\.Optional promotions: economic scope and tractability

A recommendation selects what to suggest; a*promotion*sets optional transaction terms such as a percentage discount, a coupon, or a bundle rebate\. These are distinct decisions\. LetDDbe a set of fixed promotion terms, withD=∅D=\\varnothingdenoting ordinary prices\. In the unrestricted economic formulation, the response law isP⁡\(Y∣s,A,D\)P\(Y\\mid s,A,D\)and net incremental contribution margin is

\(12\)F\(A,D\)=𝔼\[MD\(B⊕Y\)−M0\(B\)∣s,A,D\]−c\(A,D\)\.F\(A,D\)=\\mathbb\{E\}\\\!\\left\[M\_\{D\}\(B\\oplus Y\)\-M\_\{0\}\(B\)\\mid s,A,D\\right\]\-c\(A,D\)\.HereMDM\_\{D\}includes net realized selling prices, product costs and any redeemed promotion funding, whereascccomprises costs not already counted inMDM\_\{D\}\. Thus a discount is charged*once*, only when its eligibility/redemption conditions hold\. The baselineM0​\(B\)M\_\{0\}\(B\)refers to keeping the original basket at baseline transaction terms\. SettingD=∅D=\\varnothingrecovers the nonpromotional model\.

A retailer\-funded discountδ\\deltaon accepted upgradeggchanges its accepted margin fromdgd\_\{g\}todg−δd\_\{g\}\-\\deltaand may changepgp\_\{g\}topg​\(D\)p\_\{g\}\(D\); a cross\-sell discount similarly changesmkm\_\{k\}tomk−δkm\_\{k\}\-\\delta\_\{k\}\. These modified parameters enter Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\), and the exact results apply,*provided*its affine\-response, local\-dependence, and additive\-margin assumptions continue to hold\. A bundle rebaterrpaid only if an upsell and a cross\-sell are both accepted contributes−rPr\(Yg=1,Zk=1∣s,A,D\)\-r\\Pr\(Y\_\{g\}=1,Z\_\{k\}=1\\mid s,A,D\), a joint moment that must be modeled rather than recovered from marginals\. Arbitrary bundle thresholds, price\-dependent nonlinear response, and the joint choice of discount amounts can create new interactions, so exact solvability must then be rechecked\.

## Appendix BStructural characterizations

###### Proposition 0 \(Moment sufficiency\)\.

Under Eq\. \([9](https://arxiv.org/html/2610.22768#A1.E9)\) and additive expected margins,F⁡\(x,C\)F\(x,C\)depends on the joint distribution of upgrade acceptances only through the marginalspgp\_\{g\}and selected joint momentsρg​h\\rho\_\{gh\}appearing in Eq\. \([10](https://arxiv.org/html/2610.22768#A1.E10)\)\. No higher\-order moments or independence assumption are required\.

*Proof sketch\.*Apply linearity of expectation toYgY\_\{g\},Yg​YhY\_\{g\}Y\_\{h\}, and each conditional add\-on probability\. All terms then reduce topgp\_\{g\}andρg​h\\rho\_\{gh\}, giving Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\)\. See Appendix[L](https://arxiv.org/html/2610.22768#A12)\.

###### Proposition 0 \(Exact separability condition\)\.

Assume no\-offer is feasible,z⁡\(0\)=0z\(0\)=0,L,K≥1L,K\\geq 1, and the feasibility constraints on upgrades and additions are separate\. Then the objective can be written asF⁡\(x,C\)=U0​\(x\)\+V0​\(C\)F\(x,C\)=U\_\{0\}\(x\)\+V\_\{0\}\(C\)for all feasible pairs if and only if

\(13\)βk⊤​z​\(x\)=0for every feasiblexand itemk\.\\beta\_\{k\}^\{\\top\}z\(x\)=0\\quad\\text\{for every feasible $x$ and item $k$\.\}

*Proof sketch\.*The mixed finite difference

\(14\)D⁡\(x,k\)=F⁡\(x,\{k\}\)−F⁡\(x,∅\)−F⁡\(0,\{k\}\)\+F⁡\(0,∅\)=βk⊤​z​\(x\)D\(x,k\)=F\(x,\\\{k\\\}\)\-F\(x,\\varnothing\)\-F\(0,\\\{k\\\}\)\+F\(0,\\varnothing\)=\\beta\_\{k\}^\{\\top\}z\(x\)vanishes for everyx,kx,kexactly when the cross term can be removed\. A nonzero difference certifies objective\-level coupling, but does*not*imply that separate optimization necessarily selects a different optimum\.

## Appendix CAn exact algorithm for structured interactions

###### Proposition 0 \(Fixed\-dimensional, bounded\-treewidth exact solvability\)\.

Suppose \(i\) add\-on response is affine as in Eq\. \([9](https://arxiv.org/html/2610.22768#A1.E9)\), with additive expected add\-on margins; \(ii\) every upgrade\-side term—each expected margin inUUand each contribution to the summaryzz—depends only on the actionsxSfx\_\{S\_\{f\}\}of a factor scopeSfS\_\{f\}, and the primal graph joining upgrade groups that share a scope has fixed treewidthww; \(iii\) only separate cardinality budgetsLLandKKapply; \(iv\) all input coefficients are rational; and \(v\) the summary dimensionrris fixed\. ThenStoBasketoptimization admits an exact algorithm running in time polynomial in the number of upgrade choices, the number of add\-ons, and the coefficient encoding length\.

Condition \(ii\) covers the single\-group and edge moments of Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\), as well as local exposure effects in which displaying a neighboring upsell changespgp\_\{g\}\. It does not cover a graphical choice model whose induced marginals depend on the whole policy; such a model must first be shown to have locally factorized expected values\.

*Proof sketch\.*For a fixedxx, the best addition set consists of at mostKKpositive values ofℓk​\(z⁡\(x\)\)=αk\+βk⊤​z​\(x\)\\ell\_\{k\}\(z\(x\)\)=\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z\(x\)\. The order and positivity of these affine scores can change only across hyperplanesℓk=ℓj\\ell\_\{k\}=\\ell\_\{j\}orℓk=0\\ell\_\{k\}=0\. There areO⁡\(M2\)O\(M^\{2\}\)hyperplanes in fixed dimensionrr, yieldingO⁡\(M2​r\)O\(M^\{2r\}\)open cells\. Enumerate one top\-KKselection per cell, with tie handling\. Some selection from these cells is optimal at the statez⁡\(x∗\)z\(x^\{\*\}\)of a global optimum\. For each such fixedCC, the objective becomes a sum of local factors over the scopesSfS\_\{f\}\. A tree\-decomposition dynamic program, with an additional state counting upgrade offers up toLL, solves this exactly for fixedww\. Maximizing over the enumeratedCCrecovers a global optimum\. Full details are in Appendix[L](https://arxiv.org/html/2610.22768#A12)\.

Implementation\.The reference solver \(engine/treewidth\_exact\.py\) covers any fixedrrand arbitrary factor scopes\. The outer step \(engine/arrangement\.py\) returns, in exact rational arithmetic, a point in every full\-dimensional cell of the score arrangement by adding the coordinate hyperplanes, slicing between consecutive vertex coordinates, and recursing on dimension; on a tie face, an adjacent cell’s top\-KKset is optimal, so cells suffice\. This simple sampler is polynomial for fixedrrbut targets verification rather than speed\. The inner step \(engine/treewidth\_dp\.py\) is max\-sum variable elimination along a min\-fill ordering, with messages indexed by separator assignment and upgrade\-offer count; the ordering affects only the cost,O⁡\(G​Jmaxw′\+1​\(L\+1\)2\)O\(G\\,J\_\{\\max\}^\{w^\{\\prime\}\+1\}\(L\+1\)^\{2\}\)per candidate set for induced widthw′w^\{\\prime\}\. The algorithm combines known arrangement and graphical\-DP techniques rather than proposing them as new\([Lo and Topaloglu, 2019](https://arxiv.org/html/2610.22768#bib.bib27);[Del Pia, 2025](https://arxiv.org/html/2610.22768#bib.bib10)\)\.

## Appendix DWhy structure is needed

Fixed response dimension alone does not make the problem tractable\. The two reductions below show that the add\-on and response restrictions of Proposition[C\.1](https://arxiv.org/html/2610.22768#A3.Thmtheorem1)carry the result\.

Unrestricted add\-on interactions\.Allow pairwise add\-on payoffsηk​ℓ\\eta\_\{k\\ell\}as in Eq\. \([3](https://arxiv.org/html/2610.22768#S3.Ex2)\)\. Given a graphHHand an integerK≥2K\\geq 2, create one add\-on per vertex, no upgrade groups, zero unary values, add\-on budgetKK, andηk​ℓ=1\\eta\_\{k\\ell\}=1exactly for the edges ofHH\. The objective counts edges among the chosen add\-ons, so value\(K2\)\\binom\{K\}\{2\}is attainable exactly whenHHhas aKK\-clique\. The optimization problem is therefore NP\-hard even when the summary is identically zero\.

Nonlinear response\.Given positive integersw1,…,wGw\_\{1\},\\ldots,w\_\{G\}with sumSSand a targetT∈\[0,S\]T\\in\[0,S\], letL=GL=GandK=1K=1, let each upgrade be accepted with certainty when offered and change no margin, and let one add\-on with unit margin and no display cost have purchase probabilityq⁡\(x\)=1−\(\(∑gwg​xg−T\)/S\)2∈\[0,1\]q\(x\)=1\-\\big\(\(\\sum\_\{g\}w\_\{g\}x\_\{g\}\-T\)/S\\big\)^\{2\}\\in\[0,1\]\. Expected value11is attainable exactly when some subset of thewgw\_\{g\}sums toTT\. A one\-dimensional summary with a nonlinear response is thus already NP\-hard; the affine response of Eq\. \([9](https://arxiv.org/html/2610.22768#A1.E9)\) is what restores tractability\.

## Appendix ESynthetic verification

### E\.1\.Controlled validity tests

All data below are synthetic\. We generate multiple incumbent groups, several upgrade alternatives per group, a random forest of potential cross\-upgrade effects, and complementary items\. Coefficients are restricted or explicitly checked to ensure conditional add\-on probabilities are within\[0,1\]\[0,1\]\.

Table 7\.Reproducible finite\-instance verification; exactness means agreement with exhaustive search on the enumerated instances, not a proof of all\-instance correctness\.The optimizer matched brute force on all 320 small forest instances, 289 with a nonempty upgrade\-interaction graph, and the closed\-form expected margin matched explicit summation over a correlated joint law to within8\.9×10−168\.9\\times 10^\{\-16\}\. These checks establish numerical consistency under synthetic parameters, not predictive accuracy\.

### E\.2\.Bounded\-treewidth upgrade graphs

These checks test Proposition[C\.1](https://arxiv.org/html/2610.22768#A3.Thmtheorem1)beyond forests\. The tree\-decomposition program matched brute force on 300 random factor graphs \(cycles, ladders, and partial 2\- and 3\-trees\)\. The complete solver matched exhaustive search on 240 rational instances withr≤2r\\leq 2\(216 cyclic\) and on 120 coherent latent\-class instances with exposure spillovers, in which displaying a neighboring upgrade shifts acceptance \(109 cyclic, induced width up to four\); there the moment objective matched the full joint law to within1\.3×10−151\.3\\times 10^\{\-15\}\. The cell sampler hit every sign pattern found by dense random sampling on 56 arrangements in dimensions one to four\. In the model’s natural dimensionr=3r=3, with separate accepted, displayed, and joint\-acceptance coefficients, the solver matched exhaustive search on 48 rational and 36 latent\-class instances, and on 12 instances withr=4r=4\. Largerrrwould add response features rather than a new mechanism; the arrangement’sMO⁡\(r\)M^\{O\(r\)\}cells make boundedrra substantive assumption\. The 60\-instance interaction sweep of Figure[2](https://arxiv.org/html/2610.22768#S6.F2)uses four upgrade groups, six add\-ons, and budgetsL=K=3L=K=3; all baselines coincide with the optimum at zero coupling\.

### E\.3\.Proof of the staging\-gap proposition

Writex0=arg⁡maxx⁡F⁡\(x,∅\)x^\{0\}=\\arg\\max\_\{x\}F\(x,\\varnothing\)andC0=arg⁡maxC⁡F⁡\(0,C\)C^\{0\}=\\arg\\max\_\{C\}F\(0,C\)\. The independent policy is\(x0,C0\)\(x^\{0\},C^\{0\}\)\. Upgrade\-first returns\(x0,arg⁡maxC⁡F⁡\(x0,C\)\)\(x^\{0\},\\arg\\max\_\{C\}F\(x^\{0\},C\)\), whose value is at leastF⁡\(x0,C0\)F\(x^\{0\},C^\{0\}\)becauseC0C^\{0\}is feasible\. Add\-on\-first returns\(arg⁡maxx⁡F⁡\(x,C0\),C0\)\(\\arg\\max\_\{x\}F\(x,C^\{0\}\),C^\{0\}\), likewise at leastF⁡\(x0,C0\)F\(x^\{0\},C^\{0\}\)\. Alternating best response starts from the better of the two and never decreases the objective, so it dominates both\. Every policy is feasible, so none exceeds the optimum\. This proves \(i\)\.

For \(ii\), Proposition[B\.2](https://arxiv.org/html/2610.22768#A2.Thmtheorem2)givesF⁡\(x,C\)=U⁡\(x\)\+∑k∈CαkF\(x,C\)=U\(x\)\+\\sum\_\{k\\in C\}\\alpha\_\{k\}, withU⁡\(x\)=F⁡\(x,∅\)U\(x\)=F\(x,\\varnothing\)\. Because the budgets are separate,maxx,C⁡F=maxx⁡U⁡\(x\)\+max⁡∑k∈CC⁡αk\\max\_\{x,C\}F=\\max\_\{x\}U\(x\)\+\\max\_\{C\}\\sum\_\{k\\in C\}\\alpha\_\{k\}, and\(x0,C0\)\(x^\{0\},C^\{0\}\)attains both maxima\. By \(i\) the sequential and alternating policies are also optimal\. Greedy can fail even here\. IfL≥2L\\geq 2and two upgrades each have value−ϵ\-\\epsilonalone and a pair margin3​ϵ3\\epsilontogether, greedy never adds the first one\. The same holds for a pair of add\-ons with a positive interaction\.

For \(iii\), take one upgrade with acceptancep=1/2p=1/2, accepted margin change−2​λ\-2\\lambdaand latent feature0\.60\.6, and one add\-on with margin10​λ10\\lambda, base acceptance0\.020\.02, slope1\.31\.3on the accepted\-upgrade feature, and display cost0\.5​λ0\.5\\lambda, withL=K=1L=K=1\. ThenF⁡\(∅\)=0F\(\\varnothing\)=0,F⁡\(upgrade\)=−λF\(\\text\{upgrade\}\)=\-\\lambda,F⁡\(add\-on\)=−0\.3​λF\(\\text\{add\-on\}\)=\-0\.3\\lambdaandF⁡\(both\)=2\.6​λF\(\\text\{both\}\)=2\.6\\lambda\. Herex0x^\{0\}andC0C^\{0\}are both empty\. The best addition given no upgrade is none, and the best upgrade given no addition is none\. Alternating best response is therefore at a fixed point, and both greedy moves from the empty policy have negative gain\. All five policies return00, while the optimum is2\.6​λ\>02\.6\\lambda\>0\. No positive multiplicative guaranteeALG≥c⋅OPT\\mathrm\{ALG\}\\geq c\\cdot\\mathrm\{OPT\}can hold, and the additive gap2\.6​λ2\.6\\lambdais unbounded\.

For \(iv\), takenngroups, each with one upgrade of acceptancep=1/2p=1/2, accepted margin change−0\.2\-0\.2, no display cost, and accepted featuret=1/nt=1/n\. Take one add\-on with margin1010, base acceptance00, unit slope on the accepted\-upgrade feature, and display costA=\(n−12\)​bA=\(n\-\\tfrac\{1\}\{2\}\)b, whereb=5/n−0\.1\>0b=5/n\-0\.1\>0forn<50n<50\. Its conditional acceptance∑gYg/n\\sum\_\{g\}Y\_\{g\}/nlies in\[0,1\]\[0,1\]for every realization, so the response law is valid\. An upgrade alone is worth−0\.1\-0\.1\. With the add\-on shown, each offered upgrade adds10⋅12⋅1n−0\.1=b10\\cdot\\tfrac\{1\}\{2\}\\cdot\\tfrac\{1\}\{n\}\-0\.1=b\. A policy with the add\-on andjjupgrades is worthj​b−Ajb\-A, which is negative forj≤n−1j\\leq n\-1and equalsb/2\>0b/2\>0forj=nj=n\. Policies without the add\-on are worth−0\.1​j\-0\.1j\. Every nonempty policy with at mostnnoffers is therefore negative\. Any search that moves from the empty policy only to a policy withinnnoffer changes, and only on strict improvement, stops at00; this includes all five baselines\. Exhaustive enumeration confirms the construction forn=1,…,6n=1,\\ldots,6\. Scaling all margins and costs byλ\\lambdaagain makes the gap arbitrary\. The traps depend on the starting policy: best\-response iteration started from a policy that already shows the add\-on reaches the optimum here\. Whether a heuristic succeeds thus depends on such design choices, whereas the exact solver certifies optimality independently of them\.

## Appendix FReal\-data\-calibrated evaluation: data and design

Claim boundary\.No public dataset records which upsells and cross\-sells were displayed and whether they were accepted\. All results in Section[6\.1](https://arxiv.org/html/2610.22768#S6.SS1)are therefore*real\-data\-calibrated simulations*\. Real baskets, prices, contexts and \(for Ta Feng\) costs define the decision problems; purchase patterns in training receipts calibrate simulated offer responses; policies are learned from simulated randomized offer logs and scored by their exact expected value under the simulator\. The settings below were fixed in a written plan before the first full run\.

Table 8\.Datasets\. Splits are chronological; customer identifiers are not used\.Data sources and licenses\.All datasets are public and are used here for research\. Complete Journey 2\.0 originates from 84\.51° and is used through thecompletejourneyR package, released under CC0\([Boehmke and Mortimer, 2025](https://arxiv.org/html/2610.22768#bib.bib5)\)\. Online Retail II\([Chen, 2012](https://arxiv.org/html/2610.22768#bib.bib6)\)and the Open Bandit Dataset\([Saito et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib32)\)are released under CC BY 4\.0\. The Instacart Online Grocery Shopping Dataset 2017 is provided for non\-commercial use under Instacart’s dataset terms\([Instacart, 2017](https://arxiv.org/html/2610.22768#bib.bib19)\)\. Carbo\-Loading is distributed through dunnhumby Source Files for research and non\-commercial use\([dunnhumby, 2026](https://arxiv.org/html/2610.22768#bib.bib11)\)\. The Dominick’s Finer Foods data are provided for academic research by the James M\. Kilts Center for Marketing, University of Chicago Booth School of Business\([James M\. Kilts Center for Marketing, University of Chicago Booth School of Business, 2026](https://arxiv.org/html/2610.22768#bib.bib21)\)\. The Ta Feng grocery data are publicly distributed without a stated license\([Kaggle user chiranjivdas09, 2026](https://arxiv.org/html/2610.22768#bib.bib23)\)\. We report only aggregate statistics and derived results\. No raw transactions are redistributed: the accompanying code downloads each dataset, and users must accept each provider’s terms\.

Data\.Table[8](https://arxiv.org/html/2610.22768#A6.T8)summarizes the three datasets\. In Complete Journey, the retailer’s revenue is the sales value and the shelf price is

shelf price=\(sales value\+retail discount\+coupon match\)/quantity\.\\text\{shelf price\}=\(\\text\{sales value\}\+\\text\{retail discount\}\+\\text\{coupon match\}\)/\\text\{quantity\}\.We keep grocery, fresh and health departments and drop fuel and quantities above 20\. Ta Feng’sASSETfield is the line’s cost of goods\. Within every product it is exactly proportional to quantity, it lies below the sales price in 91% of lines, and it implies a 15% gross margin; we therefore use\(price−ASSET\)/quantity\(\\text\{price\}\-\\text\{ASSET\}\)/\\text\{quantity\}as the real unit margin\. A Ta Feng basket is one customer\-day\. Instacart has no prices\. We impute a department price from comparable Complete Journey departments, add 25% for organic items, and label every Instacart economic quantity as imputed\. Its decision basket is the first half of the cart, so recommendations are made in\-cart\. Its mirror’s row counts equal the official release\.

Decision instances\.For a basket, an upsell group is a basket item with a premium alternative in the same fine category that sold at least 20 times in training and costs more on the shelf\. We keep the four highest\-value such items and their two most purchased alternatives\. A replacement’s margin isqty×\(mj−mi\)\\text\{qty\}\\times\(m\_\{j\}\-m\_\{i\}\), using the incumbent’s actual revenue in the basket\. Add\-on candidates are the six categories absent from the basket with the largest gainmaxc∈B⁡P⁡\(d∣c\)−P⁡\(d\)\\max\_\{c\\in B\}P\(d\\mid c\)\-P\(d\), each represented by its most purchased item\. Budgets areL=K=2L=K=2\.

Margins\.Ta Feng uses real costs\. Complete Journey uses gross\-margin rates of 18%, 28% and 38% for national brands, with private label 8 points higher\. A robustness arm instead applies Ta Feng’s median margin rates by premium tier, rescaled to the 28% mean\. Instacart uses the 28% scenario\.

Channel associations\.For upsell categoryuuand add\-on categorydd,A⁡\[u,d\]=P⁡\(d∣premium​u\)−P⁡\(d∣regular​u\)A\[u,d\]=P\(d\\mid\\text\{premium \}u\)\-P\(d\\mid\\text\{regular \}u\)in training baskets, shrunk byn/\(n\+50\)n/\(n\+50\)withnnthe smaller tier count, and clipped to±0\.15\\pm 0\.15\. This fixed shrinkage defines the original calibration in Table[4](https://arxiv.org/html/2610.22768#S6.T4)\. Batch 3 adds an empirical\-Bayes sensitivity analysis that estimates per\-entry noise from the binomial counts and a dataset\-level signal variance by moments \(Table[14](https://arxiv.org/html/2610.22768#A8.T14)\)\. These are correlational quantities; the simulator adopts them as causal truth, which is the main modeling assumption of the study\.

Simulators\.S1 is the paper’s model\. Upsell acceptance is

pg​j=min⁡\(max⁡\(κup⋅2​sj/\(si\+sj\),0\.01\),0\.6\),p\_\{gj\}=\\min\\big\(\\max\(\\kappa\_\{\\text\{up\}\}\\cdot 2s\_\{j\}/\(s\_\{i\}\+s\_\{j\}\),\\,0\.01\),\\,0\.6\\big\),wheressare purchase shares within the category in the basket’s store and time stratum, shrunk to global shares, andκup=0\.25\\kappa\_\{\\text\{up\}\}=0\.25\. Two latent classes with weights\(0\.6,0\.4\)\(0\.6,0\.4\)and multipliers\(0\.6,1\.6\)\(0\.6,1\.6\)make acceptances correlated\. An add\-on is bought with probability

qk=κaddbk\+γ\[∑gYgAg​k\+λ2∑g𝟏\{xg≠0\}Ag​k\+λ3∑g<hYgYhAg​k\+Ah​k2\],q\_\{k\}=\\kappa\_\{\\text\{add\}\}b\_\{k\}\+\\gamma\\Big\[\\textstyle\\sum\_\{g\}Y\_\{g\}A\_\{gk\}\+\\lambda\_\{2\}\\sum\_\{g\}\\mathbf\{1\}\\\{x\_\{g\}\\neq 0\\\}A\_\{gk\}\+\\lambda\_\{3\}\\sum\_\{g<h\}Y\_\{g\}Y\_\{h\}\\tfrac\{A\_\{gk\}\+A\_\{hk\}\}\{2\}\\Big\],clipped to\[0,1\]\[0,1\], wherebk=maxc∈B⁡P⁡\(dk∣c\)b\_\{k\}=\\max\_\{c\\in B\}P\(d\_\{k\}\\mid c\)adjusted to the stratum andκadd\\kappa\_\{\\text\{add\}\}makes the mean base rate 8%\. Defaults areγ=1\\gamma=1,λ2=λ3=0\.5\\lambda\_\{2\}=\\lambda\_\{3\}=0\.5\. S2 is out of family: logistic upsell acceptance with three classes and class\-specific slopes, and logistic add\-on purchase whose linear predictor contains the same channel terms\. S3 is a stress test: S1 with add\-on cannibalization \(two displayed add\-ons from one department each lose 40%\), display fatigue \(−10%\-10\\%on every acceptance per extra offer\), and a test\-period shift \(κup×0\.8\\kappa\_\{\\text\{up\}\}\\times 0\.8,κadd×1\.2\\kappa\_\{\\text\{add\}\}\\times 1\.2\)\. At most two upsells are displayed, so every expectation is computed exactly by enumerating acceptance outcomes and classes; Monte Carlo draws agree with these values\.

Learning\.Logs contain 50,000 training baskets with a uniformly random feasible display policy\. The fitted model has three parts\. A logistic upsell model uses the log share ratio and the log price ratio\. A correlation factorψ=∑Yg​Yh/∑p^g​p^h\\psi=\\sum Y\_\{g\}Y\_\{h\}/\\sum\\hat\{p\}\_\{g\}\\hat\{p\}\_\{h\}is estimated from pairs displayed together\. A linear add\-on model regresses purchase on the base rate and the three channel regressors\. The two\-channel variant ties the accepted and displayed coefficients\. The learner sees features only at its context arm \(C0 basket only, C1 time, C2 store or area, C3 both; the truth uses C3\) and never sees classes or simulator parameters\.

Policies and metrics\.The exact policy enumerates all upsell policies within the budget and adds the top\-KKpositive add\-ons under the fitted model; this is exact for the fitted model\. The five baselines of Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)use the same fitted model\. Two model\-free rules are included:*association*offers the most purchased upgrades and the highest\-lift add\-ons, and*margin popularity*ranks by purchase share times margin gain\. The oracle optimizes the true simulator, including add\-on interactions, by enumeration\. We report expected incremental margin per 1,000 baskets in the dataset’s currency and paired bootstrap 95% intervals over 5,000 test baskets \(1,000 for each of five seeds\)\.

## Appendix GReal\-data\-calibrated evaluation: additional results

Table[9](https://arxiv.org/html/2610.22768#A7.T9)reports the secondary experiments, each over five seeds and 5,000 test baskets\.

Coupling \(γ\\gamma\)\.The gap to the staged policies grows with the calibrated channel effects\. Atγ=0\\gamma=0it vanishes, except on Ta Feng, where acting on spuriously estimated coupling costs NT$1\.0 per 1,000 baskets relative to independent selection\.

Log size\.Regret at 10,000 logged baskets is already close to its value at 200,000\. The remaining regret on Ta Feng \(about NT$5\) reflects the fitted model’s form, logistic acceptance and an unclipped linear add\-on response, rather than sampling error\.

Context\.The truth varies by store and time stratum exactly as the receipts do\. A learner restricted to basket information loses 1\.8% of the oracle margin on Complete Journey and 1\.2% on Ta Feng\. Time context alone does not help Complete Journey, whose heterogeneity is mainly by store\. When context is missing, alternating best response can slightly beat the exact optimizer of the misspecified model \(Ta Feng C0 and C2\)\.

Channels\.Tying the displayed and accepted coefficients costs little when the display effect is positive\. It matters when displaying an upsell suppresses add\-on purchases \(λ2=−0\.5\\lambda\_\{2\}=\-0\.5\), most clearly on Instacart\. There, regret rises from $0\.3 to $4\.7 per 1,000 baskets, and the exact policy’s edge over independent selection shrinks from $6\.2 to $1\.7\.

Margins\.Under low, high and Ta Feng\-derived margin rates, the ranking of policies is unchanged\. Gaps scale with the margin level: $1\.0, $3\.5 and $8\.5 over independent selection at 18%, 28% and 38%\.

Table 9\.Secondary experiments \(S1 unless stated\): oracle expected margin and exact\-policy regret per 1,000 baskets, and the exact policy’s margin over three baselines\. Currency as in Table[4](https://arxiv.org/html/2610.22768#S6.T4)\.
## Appendix HExactness regimes and robustness

Table 10\.External\-data checks: Online Retail II \(GBP per 1,000 invoices\), Complete Journey under Dominick’s margin rates, and Carbo\-Loading \(USD per 1,000 baskets\)\. Exact regret and exact minus each baseline are absolute amounts\.Protocol\.The questions and settings in this section were written before the second empirical batch\. Two baselines were added after inspecting the first exactness\-regime results and are explicitly post hoc:*alternating over splits*runs alternating best response for every fixed upsell/add\-on split of a shared budget and keeps the best result; the*portfolio*runs every independent, sequential, greedy and alternating policy and keeps the policy with greatest value under the fitted model\. Neither baseline observes the simulator’s truth\. Display cost isc=τ​v¯c=\\tau\\bar\{v\}per offer, wherev¯\\bar\{v\}is mean standalone expected add\-on margin in the seed\-0 training pool\. All percentages are of the oracle’s expected incremental offer margin\.

Table 11\.Market opportunity and method effectiveness\. Coupling value is the oracle policy’s value under the stated channels minus the value of that*same policy*withγ=0\\gamma=0; it overlaps add\-on value and is not an additional additive category\. The final column normalizes the exact\-minus\-independent gain by this coupling value\.Value decomposition\.Table[11](https://arxiv.org/html/2610.22768#A8.T11)separates how much economic value flows through interactions from how much of that value joint selection recovers relative to independent selection\. In the two supported S1 calibrations, coupling accounts for 31% of oracle margin on EB\-shrunk Instacart and 2% on real\-price Carbo\-Loading; exact\-minus\-independent recovers 32% and 41% of that coupling value\. Under S2 the recovery shares are 40% and 52%, respectively\. The fixed\-shrinkage Complete Journey and Ta Feng rows are retained for comparability, but E17 shows that much or all of their small apparent signal is sampling noise\. The denominator is policy\-specific and counterfactual: it measures the interaction contribution to the oracle policy, not a causal decomposition of observed retailer profit\.

Table 12\.Where exact optimization matters \(S1\)\. “Portfolio” is the post\-hoc best\-of\-heuristics baseline evaluated by the fitted model; “Differs” is the share of baskets on which exact and alternating choose different policies\. Exact regret and exact\-minus\-baseline columns are percentages of oracle offer margin\.Display friction and budgets\.Table[12](https://arxiv.org/html/2610.22768#A8.T12)supplies the full data behind Figure[4](https://arxiv.org/html/2610.22768#S6.F4)\. With separate budgets, increasing candidate count or budgets leaves all portfolio gaps at or below 0\.12%\. Shared budgets make a single alternating run sensitive to its initial split: atT=3T=3it loses 1\.33%, 1\.52% and 21\.22% on Complete Journey, Ta Feng and Instacart\. Enumerating fixed splits reduces those gaps to at most 0\.07%, so this is a repairable search failure\. The distinct failure occurs on Instacart under display friction\. Atτ=1\.5\\tau=1\.5the portfolio loses 16\.1%; atτ=2\\tau=2it loses 65\.1%; and atτ=2,γ=2\\tau=2,\\gamma=2it loses 78\.0% \($138 per 1,000 baskets\)\. Exact regret is 0\.14%, 0\.50%, and 0\.19%, respectively\. On Complete Journey and Ta Feng the portfolio remains within 0\.09% throughτ=3,γ=2\\tau=3,\\gamma=2\. These stress settings map the mechanism; they are not estimates of any retailer’s actual display cost\.

Table 13\.Instacart price sensitivity \(E16, S1,γ=1\\gamma=1\)\. Entries are percentages of oracle offer margin\. The portfolio is the post\-hoc best fitted\-value heuristic\. Margin\-rate arms rescale both margins and the display\-cost unit and are therefore decision\-invariant\.Price sensitivity\.Table[13](https://arxiv.org/html/2610.22768#A8.T13)varies the assumptions behind Instacart’s imputed economics\. The pre\-registered criterion—portfolio regret at least 10% for someτ≤2\\tau\\leq 2, with exact regret at most 1%—holds for the default 25% organic premium and the 10% premium, but not for the 40% premium or item\-level price noise\. Atτ=2\\tau=2, exact\-minus\-portfolio ranges from 2\.0% under price noise to 89\.3% under the 10% premium\. Exact regret stays below 0\.5% except in the 10% arm atτ=2\\tau=2, where it is 3\.3% and the oracle itself is only $7\.5 per 1,000 baskets\. The result isolates the mechanism: local policies fail when display cost makes single actions unattractive, and prices determine how often actions lie near that threshold\.

Table 14\.Fixed versus empirical\-Bayes coupling shrinkage \(E17\)\. Absolute exact\-minus\-independent values use dataset currency per 1,000 baskets; portfolio/alternating gaps are percentages of oracle offer margin\.Noise\-corrected coupling\.The pre\-registered moment estimator over all association entries returned zero signal even on Instacart because thousands of sparse pairs dominated the moments and half\-count smoothing inflated their noise\. Before inspecting any policy\-decision result, we changed the estimator to use unsmoothed binomial variance floored at one proportion count and to estimate signal variance over entries with at least 30 baskets in each premium tier\. This protocol deviation is recorded in the experiment plan\. Under the corrected estimator, a line\-label placebo has zero estimated signal on all datasets\. Real labels yield signal standard deviation 0\.018 on Complete Journey \(mean shrinkage weight 0\.50\), 0\.026 on Instacart \(weight 0\.89\), and no detectable signal on Ta Feng\. Table[14](https://arxiv.org/html/2610.22768#A8.T14)shows the decision consequence: S1 exact\-minus\-independent falls from $3\.50 to $0\.91 on Complete Journey, from NT$71 to approximately zero on Ta Feng, and from $53 to $47 on Instacart\. The Instacartτ=2\\tau=2portfolio gap changes only from 65\.1% to 63\.8%\. Policy ordering and the large cost of margin\-blind recommendation are otherwise unchanged\.

Table 15\.Robustness tests\. Rebate losses are in dataset currency per 1,000 baskets; stress\-test values and log\-size regret are percentages of oracle offer margin\.Promotions and misspecification\.Table[15](https://arxiv.org/html/2610.22768#A8.T15)reports three checks\. First, a rebate\-blind optimizer increasingly misprices a bundle as the conditional rebate grows; at a full add\-on\-margin rebate it loses $34 per 1,000 Instacart baskets\. Second, the rich fitted model adds same\-department add\-on cannibalization and multiplicative fatigue from offer count\. Nonlinear least squares estimates cannibalization at 0\.39–0\.41 \(truth 0\.4\) and fatigue at 0\.08–0\.09 \(truth 0\.1\)\. It reduces exact\-policy regret from 10\.6–17\.5% to 0\.08–0\.10% without period shift and to 0\.13–0\.32% with the shift\. This experiment gives the learner the correct functional family and therefore tests recoverability of known mechanisms, not robustness to arbitrary omitted structure\. Third, the small\-log arm shows that decision regret falls primarily below 5,000–10,000 randomized sessions\.

Placebos and coupling gate\.Permuting premium labels across items retains 65–92% of the original three\-dataset joint gain because item\-level heterogeneity remains\. A stricter line\-level placebo assigns the premium label independently to every purchase line at the category’s observed premium rate\. Under fixed shrinkage it retains 42% of Complete Journey’s gain, 48% of Ta Feng’s, and 12% of Instacart’s; E17’s noise correction reduces every line\-placebo gain to approximately zero\. Carbo\-Loading passes a stronger economic check: exact\-minus\-independent is $1\.65 with real labels, versus $0\.13 under the item placebo and−$0\.22\-\\$0\.22under the line placebo, and EB shrinkage leaves the real\-label result unchanged\. A heteroskedasticity\-robust joint Wald gate sets all coupling coefficients to zero unless their joint null is rejected at 5%\. It remains closed in everyγ=0\\gamma=0seed and opens in every seed forγ≥0\.5\\gamma\\geq 0\.5without materially changing results\.

Additional retail data and real margins\.Online Retail II is a non\-grocery UK giftware dataset\. We treat an invoice as a basket, derive coarse product groups from description head nouns, define premium by above\-median within\-group price, assume margins, and split chronologically at July 1, 2011\. Under S1 exact gains £22 per 1,000 invoices \(0\.34%\) over independent selection and £0\.04 over alternating\.

Carbo\-Loading contains 5\.2 million purchase lines from pasta, pasta sauce, pancake mix, and syrup\. Weeks 1–78 form training and weeks 79–104 test\. An upsell group is a commodity; plain store brand is the regular tier and other brands are premium candidates\. Add\-on categories are commodity–brand cells with at least 1% share, restricted to commodities absent from the basket so that a second brand of pasta is not treated as a cross\-sell\. We use observed paid prices, assign the private\-label margin bonus to store brands, and restrict EB moments to cross\-commodity entries used by the policy\. Under S1, exact\-minus\-independent is $1\.65 per 1,000 baskets \(0\.73% of oracle\) and exact\-minus\-portfolio is approximately zero\. Atγ=2\\gamma=2the independent gap rises to 2\.63%\. Atτ=2\\tau=2, margin popularity loses $93\.4 of the $95 oracle while the portfolio remains within 0\.14% of exact\. Thus real\-price coupling is present and economically usable, but it does not create a local\-search trap\.

For a separate margin check, we estimate revenue\-weighted national\-brand and private\-label gross\-margin rates from 17 Dominick’s Finer Foods categories\. The rates are 22\.1% and 36\.8%, with a median within\-category difference of 10\.8 percentage points\. Applying them to Complete Journey lowers oracle margin from $536 to $439 per 1,000 baskets but changes the joint gain only from 0\.65% to 0\.58%; applying them to Carbo\-Loading retains a 1\.13% exact\-minus\-independent gain\.

Randomized display\-interference analysis\.This analysis is separate from the calibrated simulations\. The Open Bandit Dataset contains fashion recommendation slates generated by a uniform\-random policy\. After cleaning, there are 454,265 screens, 59,687 distinct slates and 609,492 focal\-item test rows; focal click rate is 0\.34%\. A linear probability model with focal\-item and position fixed effects estimates the effect of the other two displayed items\. At the coarsest seven\-level category, each same\-category neighbor changes focal click probability by−0\.000424\-0\.000424, or−12\.3%\-12\.3\\%relative to the mean\. A permutation test that reassigns whole randomized slates givesp=0\.012p=0\.012; Holm correction over three category resolutions givesp=0\.036p=0\.036\. The other resolutions, neighbor attractiveness, and a joint neighbor\-identity test do not distinguish signal from their placebos\. This identifies an exposure effect among fashion substitutes under randomized display\. It neither estimates grocery purchase response nor separates replacement from addition\.

## Appendix ISolver scale, prediction quality, and prior art

Interaction\-graph structure\.For each of about 4,000 test baskets per dataset, we form a graph whose nodes are all items with an eligible premium alternative, without the cap of four\. An edge joins two items when buying the premium tier of one changes the probability of buying the premium tier of the other by more than 0\.02 in training receipts, after the same shrinkage asAA\. Table[16](https://arxiv.org/html/2610.22768#A9.T16)reports the size, the share of graphs with a cycle, and the induced width of a min\-fill ordering, an upper bound on treewidth\. Forests are the exception once baskets contain several eligible items\. Most graphs nevertheless have small width, while the largest Complete Journey baskets reach widths above 20, where exact dynamic programming over all items is impractical\. The 0\.02 threshold is a modeling choice; larger thresholds give sparser graphs\.

Table 16\.Structure of real upsell interaction graphs \(GG: items with an eligible upgrade\)\.Table 17\.Tree\-decomposition dynamic programming on real interaction graphs \(E15\)\. Runtime is median/p99; baseline gaps are percentages of oracle offer margin\. “DP faster” compares measured runtimes on each basket\.Exact optimization on larger real graphs\.E15 retains up to 20 upsell groups and restricts joint\-acceptance terms to edges of the premium\-association graph\. The count\-augmented tree\-decomposition DP and enumeration agree on all 8,040 checked baskets\. Between 73% and 91% of baskets have induced width at most two; median DP runtime is 1\.8–3\.5 ms\. Runtime grows with width rather thanGG: approximately 0\.7 ms at width zero, 13 ms at width two, 0\.2 s at width four, 2 s at width six, 20 s at width eight, and 60 s at width nine in the pure\-Python implementation\. Enumeration instead grows with the number of feasible upgrade policies and completes every tested basket within 3 s\. It is faster on nearly everyL=2L=2basket; atL=4L=4, DP is faster on 27–36% of Complete Journey and Ta Feng baskets and 4% of Instacart baskets\. Exact\-minus\-portfolio is at most 0\.01% on Complete Journey and Ta Feng and 0\.44% on Instacart\.

Table 18\.Per\-basket solve time of exact methods on held\-out seeds 1–2 \(E15b, E15c\)\. The scalar hybrid predicts enumeration or DP runtime from seed 0; “Best of both” chooses with hindsight; DP instances above the width cap are unfinished, so its worst time is over completed instances\. Vectorized enumeration evaluates the same policy set and objective with array operations and finishes every test basket\.Exact solve time\.E15b fits a post\-hoc runtime selector on seed 0 that runs scalar enumeration or tree\-decomposition DP, whichever it predicts is faster, on the 5,400 baskets of seeds 1–2\. AtL=4L=4it achieves 1\.1 ms median, 1\.8 s p99, and 3\.0 s maximum \(Table[18](https://arxiv.org/html/2610.22768#A9.T18)\)\. Every slow basket has 20 upsell groups and a dense interaction graph \(induced width 7–13\): DP is exponential in width there, and the scalar loop over 87,441 upsell policies costs about 30μ\\mus per policy in interpreter overhead\. E15c removes that overhead\. It builds every feasible policy as an index array, computes acceptance moments, channel summaries, and top\-KKadd\-on scores for all policies with array operations, and takes the maximum\. The policy set and objective are unchanged, so the method is exact: its values match brute\-force enumeration or DP on all 8,100 solves \(maximum difference4×10−164\\times 10^\{\-16\}\), and they match the fitted model’s scalar evaluator on every basket\. On the held\-out seeds it takes 0\.13 ms median, 16 ms p95, 30 ms p99, and 111 ms maximum atL=4L=4, and at most 0\.4 ms atL=2L=2, measured with one process per configuration on six concurrent workers\. The tested budgets therefore need neither the hybrid selector nor native code\. Budgets aboveL=4L=4remain the regime in which enumeration’sO⁡\(\(G​J\)L\)O\(\(GJ\)^\{L\}\)growth makes graphical DP the scalable route\.

Prediction quality \(E19\)\.E19 holds the exact optimizer, candidates, budgets, economics, and response truth fixed and varies only the predictor\. The truth is the Instacart S1 calibration with empirical\-Bayes\-shrunk channels, default imputed prices, separate budgetsL=K=2L=K=2, and no display cost\. Learned predictors fit the same three\-channel model toN∈\{100,250,500,1​k,2​k,5​k,10​k,50​k\}N\\in\\\{100,250,500,1\\text\{k\},2\\text\{k\},5\\text\{k\},10\\text\{k\},50\\text\{k\}\\\}randomized sessions\. The signal\-free endpoint fits the same model to 50,000 sessions after independently shuffling upsell, pair, and add\-on outcomes, which preserves outcome rates but removes their relation to context and actions\. Prediction quality is measured as policy\-value RMSE over a fixed grid of 100 baskets×\\times64 feasible policies per seed; decision quality as true expected margin, regret to the oracle, and oracle\-policy agreement, over 1,000 test baskets×\\times5 seeds\. Settings were registered before the run\. The oracle earns $460\.45 per 1,000 baskets\. Every learned\-predictor regret has a paired 95% interval excluding zero; for example,N=100N=100regret is $20\.03–$22\.67 andN=1N=1k regret is $1\.23–$1\.52 per 1,000 baskets\. The true gap between the best and second\-best policy is small: mean $0\.0049 and median $0\.0028 per basket, with 24% of baskets below $0\.001 and 85% below $0\.01\. Table[19](https://arxiv.org/html/2610.22768#A9.T19)reports all arms\.

Table 19\.Prediction quality with the exact optimizer held fixed \(E19, Instacart S1\)\. Value RMSE is the error in predicted policy values; oracle\-policy agreement is the share of baskets on which the chosen offer set equals the oracle’s\.Prior art on shared benchmarks \(E20\)\.E20 was registered before any E20 code ran\. TIFU\-KNN\([Hu et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib17)\)is ported line by line from the reference implementation of Li et al\.\([Li et al\., 2023](https://arxiv.org/html/2610.22768#bib.bib25)\); its per\-basket weights match that code exactly for histories of 1–39 baskets\. We use Li et al\.’s published hyperparameters without tuning:\(k,rb,rg,α,m\)=\(300,0\.9,0\.7,0\.7,7\)\(k,r\_\{b\},r\_\{g\},\\alpha,m\)=\(300,0\.9,0\.7,0\.7,7\)for Ta Feng,\(900,0\.9,0\.6,0\.2,3\)\(900,0\.9,0\.6,0\.2,3\)for dunnhumby, and\(900,0\.9,0\.7,0\.9,3\)\(900,0\.9,0\.7,0\.9,3\)for Instacart\. Each query uses the customer’s baskets strictly before the decision basket; neighbors are other customers’ training\-period histories, and Instacart histories are read in full from the raw files for up to 20,000 users\. An add\-on category’s score is the sum of its item scores, and a premium alternative’s score is its item score\. In the personalized truth, each add\-on base rate is multiplied byπc​kω\\pi\_\{ck\}^\{\\omega\}, whereπc​k\\pi\_\{ck\}is customercc’s leave\-one\-out lifetime basket share of categorykk, shrunk toward the population rate with five pseudo\-baskets, divided by that rate, capped to\[0\.1,10\]\[0\.1,10\], and normalized to mean one on the training pool\. This construction is generous to TIFU\-KNN because both summarize purchase frequency; upsell response is not personalized\.*StoBasket \+ TIFU*adds one add\-on regressor, base rate times TIFU\-KNN category score relative to its pool mean, to the same three\-channel model fitted on the same 50,000 sessions\. As a check of the port on its native task, Recall@20 on full test baskets is 0\.428 for TIFU\-KNN, 0\.406 for personal top\-frequency, and 0\.091 for global top\-frequency on Instacart; on Ta Feng it is 0\.146, 0\.160, and 0\.083\. On Complete Journey TIFU\-KNN \(0\.178\) trails personal top\-frequency \(0\.197\), missing the registered expectation\. The likely reason is pool size: our one\-year release has 2,441 households, sok=900k=900averages 37% of all customers\. A post\-hoc diagnostic that scaleskkto Li et al\.’s pool share \(k=98k=98\) yields a tie \(NDCG@20 0\.1926 versus 0\.1924\); all reported decision results use the publishedkk\. Against StoBasket \+ TIFU, every listed competitor’s loss has a paired 95% interval excluding zero, except anonymous StoBasket atω=0\\omega=0, where differences are at most 0\.012%\.

## Appendix JDecision\-aware market\-basket analysis: derivation and scaling

Table 20\.Post\-hoc decision\-aware market\-basket diagnostic from Carbo\-Loading training receipts\. “Premium” and “Regular” are conditional co\-purchase rates given the anchor tier; policy effect is the empirical\-Bayes\-shrunk difference used by the calibrated simulator, clipped to±15\\pm 15percentage points\. Relative rate is premium divided by regular\. Like all market\-basket statistics, these are observational associations\.Notation\.Throughout,NNis the number of baskets,ddthe number of catalog items,bnb\_\{n\}the number of items in basketnn, andqqthe association order\.StoBasketpools items intoGGanchor groups andMMadd\-on cells, withG,M≤dG,M\\leq d;an≤bna\_\{n\}\\leq b\_\{n\}andmn≤bnm\_\{n\}\\leq b\_\{n\}count the anchor groups and add\-on cells present in basketnn\.

Classical itemset growth\.Mining associations up to orderqqfaces

∑j=1q\(dj\)=O⁡\(dq\)\\sum\_\{j=1\}^\{q\}\\binom\{d\}\{j\}=O\(d^\{q\}\)candidate itemsets: polynomial in the catalog size for fixedqq, exponential inqq, and2d−12^\{d\}\-1without an order limit\. Counting support visits∑n\(bnq\)\\sum\_\{n\}\\binom\{b\_\{n\}\}\{q\}order\-qqsubsets per pass, so its work grows with bothNNandqq\. Apriori, FP\-growth, and related methods prune the candidate family, and multiple\-minimum\-support methods improve coverage, but a single support threshold retains the rare\-item problem\([Liu et al\., 1999](https://arxiv.org/html/2610.22768#bib.bib26)\)\. More baskets sharpen relationships that receive support; they do not remove the catalog\-by\-order explosion\.

Typed contrast as a policy byproduct\.LetNNbe the number of training baskets\. Define sparse incidence matricesX\+,X−∈\{0,1\}N×GX^\{\+\},X^\{\-\}\\in\\\{0,1\\\}^\{N\\times G\}, whereXn​g\+X^\{\+\}\_\{ng\}\(respectivelyXn​g−X^\{\-\}\_\{ng\}\) marks that basketnncontains a premium\-tier \(regular\-tier\) item from anchor groupgg, and letW∈\{0,1\}N×MW\\in\\\{0,1\\\}^\{N\\times M\}mark the add\-on cells present in each basket\. The calibration already required by the policy computes

\(15\)C±=\(X±\)⊤​W,p^g​k±=Cg​k±∑nXn​g±,A^g​k=p^g​k\+−p^g​k−\.C^\{\\pm\}=\(X^\{\\pm\}\)^\{\\top\}W,\\qquad\\widehat\{p\}^\{\\pm\}\_\{gk\}=\\frac\{C^\{\\pm\}\_\{gk\}\}\{\\sum\_\{n\}X^\{\\pm\}\_\{ng\}\},\\qquad\\widehat\{A\}\_\{gk\}=\\widehat\{p\}^\{\+\}\_\{gk\}\-\\widehat\{p\}^\{\-\}\_\{gk\}\.Herep^g​k\+\\widehat\{p\}^\{\+\}\_\{gk\}andp^g​k−\\widehat\{p\}^\{\-\}\_\{gk\}are conventional confidence quantities conditional on premium and regular anchors, while support and lift follow from the same counts\. The signed contrastA^g​k\\widehat\{A\}\_\{gk\}is the premium\-to\-add\-on association consumed by the response model: positive values identify complements strengthened by the premium tier and negative values identify avoidance or substitution\. The report therefore requires no second mining model\. It exposes counts already computed for the optimizer, attaches representative products and contribution margins, and sorts rows by noise\-corrected effect and economic relevance\.

Low\-count regularization\.Letσ^g​k2\\widehat\{\\sigma\}^\{2\}\_\{gk\}be the binomial sampling variance of the difference in Eq\. \([15](https://arxiv.org/html/2610.22768#A10.E15)\), and letτ^2\\widehat\{\\tau\}^\{2\}be the across\-entry signal variance estimated by moments\. The empirical\-Bayes policy effect is

\(16\)A~g​k=τ^2τ^2\+σ^g​k2​A^g​k\.\\widetilde\{A\}\_\{gk\}=\\frac\{\\widehat\{\\tau\}^\{2\}\}\{\\widehat\{\\tau\}^\{2\}\+\\widehat\{\\sigma\}^\{2\}\_\{gk\}\}\\,\\widehat\{A\}\_\{gk\}\.The multiplier approaches one for well\-supported contrasts and zero when sampling noise dominates\. In contrast to a global minimum\-support rule, weak entries are retained with appropriately reduced influence rather than all being discarded at one threshold\.

Typed scaling and a one\-million\-basket comparison\.Eq\. \([15](https://arxiv.org/html/2610.22768#A10.E15)\) produces a fixedG×MG\\times Mtable, and selected local pair\-acceptance moments add only the edgesEEretained by the response graph\. Direct sparse counting therefore takes∑nan​mn\\sum\_\{n\}a\_\{n\}m\_\{n\}co\-occurrence updates and storesO⁡\(G​M\+\|E\|\)O\(GM\+\|E\|\)quantities, independent ofqq: effects of several offers enter the response through the additive channel summary rather than as separate itemsets\. Table[21](https://arxiv.org/html/2610.22768#A10.T21)evaluates both methods at one million baskets using each market’s observed catalog size and basket\-size distribution\. Pair counting costs about the same in both\. The gap opens with order: on Instacart, classical updates grow from7\.4×1077\.4\\times 10^\{7\}atq=2q=2to3\.1×1093\.1\\times 10^\{9\}atq=4q=4while candidate itemsets reach2×10172\\times 10^\{17\}, whereasStoBasketneeds7\.6×1077\.6\\times 10^\{7\}updates for 17,956 contrasts at any order; on Complete Journey, whose basket sizes are more skewed, four\-item counting reaches2\.4×10102\.4\\times 10^\{10\}updates\. Each typed contrast is also well supported: the average Instacart anchor group appears in about 54,000 of the million baskets\.

Table 21\.Classical itemset mining versus typed contrasts at10610^\{6\}baskets, from each market’s observed catalog and basket sizes\. A counting update adds one to the tally of one combination found in one basket; classical mining performs\(bnq\)\\binom\{b\_\{n\}\}\{q\}updates for a basket ofbnb\_\{n\}items, typed contrastsan​mna\_\{n\}m\_\{n\}regardless ofqq\. Candidate itemsets do not depend on the number of baskets; counting updates do\.Category/tier pooling supplies additional support, and Eq\. \([16](https://arxiv.org/html/2610.22768#A10.E16)\) moves noisy low\-count contrasts toward zero\. An initial moment estimator over all entries failed even on Instacart because thousands of sparse pairs dominated its variance estimate; the corrected estimator learns signal variance from entries with at least 30 baskets in each tier, removes every line\-placebo gain, eliminates unsupported Ta Feng coupling, and retains $47 of the original $53 per 1,000\-basket Instacart joint\-selection gain \(Table[14](https://arxiv.org/html/2610.22768#A8.T14)\)\. The result is sparsity\-aware, not sparsity\-proof: a relationship with no observations or randomized exposure remains unidentified, and genuine high\-order effects omitted from the typed low\-order model require an extension that may lose the stated tractability\.

## Appendix KDeployment recipes

Table 22\.Two\-arm field\-test power under calibrated effects: baskets per arm for 80% power at 5% two\-sided size\. “Offer log” uses offer\-attributable margin from logged exposure and acceptance; “till” uses total basket margin\. M denotes million and k thousand\.### K\.1\.A/B test recipe

This protocol expands item \(5\) of Section[8\.3](https://arxiv.org/html/2610.22768#S8.SS3)\. It requires no customer identifier and can be run by a retailer on its own checkout, cart, or associate\-assisted traffic\.

1. \(1\)Choose the category\.Run the market\-basket diagnostic of Section[6\.2](https://arxiv.org/html/2610.22768#S6.SS2)on training receipts and select categories whose premium anchors have strong, shrinkage\-robust associations with add\-ons\. Weakly coupled categories need millions of baskets per arm \(Table[22](https://arxiv.org/html/2610.22768#A11.T22)\); testing there measures a small effect, not a failed method\.
2. \(2\)Randomize\.The unit is the basket or cart session, assigned by a hash of its session identifier\. If offers are delivered by store associates, randomize by store\-day and inflate the sample size by the design effect\. Use four arms: \(A\) no offers; \(B\) the retailer’s current recommender or staged upsell\-then\-cross\-sell rule; \(C\)StoBasketon the same candidate sets and budgets; and \(D\) a 5–10% arm that shows uniformly random feasible offer sets, which keeps every offer’s selection probability positive for re\-estimating the response model\.
3. \(3\)Log\.For every basket record the pre\-offer basket and context; the candidate sets; each shown offer with its type, displaced item, position, and selection probability; accepted replacements and purchased additions; the final basket; and realized prices, costs, discounts, and rebates\.
4. \(4\)Measure\.The primary endpoint is offer\-attributable incremental contribution margin per basket, Δ​M=∑gYg​\(mjg−mig\)\+∑kZk​mk−c⁡\(A\)−rebates paid,\\Delta M=\\sum\_\{g\}Y\_\{g\}\(m\_\{j\_\{g\}\}\-m\_\{i\_\{g\}\}\)\+\\sum\_\{k\}Z\_\{k\}m\_\{k\}\-c\(A\)\-\\text\{rebates paid\},the realized form of Eq\. \([2](https://arxiv.org/html/2610.22768#S3.E2)\)\. Secondary endpoints are acceptance and attach rates and total basket margin\.
5. \(5\)Size\.With per\-basket standard deviationσ\\sigmaofΔ​M\\Delta Mand target differenceδ\\delta, a two\-arm comparison at 5% two\-sided size and 80% power needs approximately n=2​\(z0\.975\+z0\.80\)2​σ2δ2≈15\.7​σ2δ2n=\\frac\{2\(z\_\{0\.975\}\+z\_\{0\.80\}\)^\{2\}\\sigma^\{2\}\}\{\\delta^\{2\}\}\\approx\\frac\{15\.7\\,\\sigma^\{2\}\}\{\\delta^\{2\}\}baskets per arm\. Table[22](https://arxiv.org/html/2610.22768#A11.T22)evaluates this from simulator variances, not observed treatment effects: about 1,400 per arm for joint versus independent selection under Instacart\-like coupling, versus 1\.4 million on Complete Journey and 7\.0 million on Ta Feng\. Exact versus alternating is detectable only in shared\-budget regimes \(about 450 per arm on Instacart\)\. Using total basket margin instead ofΔ​M\\Delta Madds the variance of the pre\-offer basket and inflatesnnby roughly 20–50 times\.
6. \(6\)Analyze\.Pre\-register the comparisons and estimate arm differences in means with heteroskedasticity\-robust intervals\. Reduce variance with pre\-offer basket margin and model\-predicted value as covariates, and apply Holm correction across pairwise arm comparisons\. Analyze in this order: offers versus no offers;StoBasketversus the current policy; and, within the random arm \(D\), a regression of add\-on purchase on shown and accepted upsells that tests whether the display and acceptance channels differ\.
7. \(7\)Guard\.Monitor acceptance rate, checkout time or abandonment, and complaints\. Stop any arm whose margin per basket falls below the no\-offer arm with 99% confidence\.
8. \(8\)Close the loop\.Refit the response model on the randomized logs, compare the estimated channel coefficients with the receipt\-calibrated ones, and rerun the exactness map of Appendix[H](https://arxiv.org/html/2610.22768#A8)with the field\-estimated values\.

### K\.2\.Campaign\-design recipe: making coupling learnable

This recipe expands item \(6\) of Section[8\.3](https://arxiv.org/html/2610.22768#S8.SS3)\. Its premise is an identification fact\. Letπ\\pibe the policy that generated a retailer’s offer logs\. The display effect of upsellggon add\-onkkin contextssis the contrast

𝔼\[Zk∣xg=j,k∈C,s\]−𝔼\[Zk∣xg=0,k∈C,s\]\.\\mathbb\{E\}\[Z\_\{k\}\\mid x\_\{g\}=j,\\ k\\in C,\\ s\]\-\\mathbb\{E\}\[Z\_\{k\}\\mid x\_\{g\}=0,\\ k\\in C,\\ s\]\.It can be estimated from the logs only if both conditioning events occur with positive probability underπ\\pi\. A campaign program that never showskkalongsidegg, or always does, observes only one of the two terms, so the effect is not identified without extrapolation; separating display from acceptance additionally requires mediation assumptions or designs\([Imai et al\., 2010](https://arxiv.org/html/2610.22768#bib.bib18)\)\. Weak measured coupling is therefore uninformative when the logging policy never created the relevant contrast\. The following steps make the contrast exist and make it visible\.

1. \(1\)Diagnose before concluding\.Compute the market\-basket diagnostic of Section[6\.2](https://arxiv.org/html/2610.22768#S6.SS2)together with the shrinkage weightswg​k=τ^2/\(τ^2\+σ^g​k2\)w\_\{gk\}=\\widehat\{\\tau\}^\{2\}/\(\\widehat\{\\tau\}^\{2\}\+\\widehat\{\\sigma\}^\{2\}\_\{gk\}\)of Eq\. \([16](https://arxiv.org/html/2610.22768#A10.E16)\)\. A large shrunk effect with high weight is a supported opportunity\. A weight near zero marks an*uninformative*cell, one with too little exposure to measure, not a cell whose effect is zero\. In our calibrations the mean weight is 0\.89 on Instacart and 0\.50 on Complete Journey, and Ta Feng shows no detectable signal \(Appendix[H](https://arxiv.org/html/2610.22768#A8)\)\.
2. \(2\)Unify the objective and its owner\.Evaluate upsell and cross\-sell offers under one objective, offer\-attributable incremental contribution margin, owned by one policy\. Separate key performance indicators, such as upgrade rate for one team and attach rate for another, encourage staged rules, which suppress joint exposure and fall into the staging trap of Proposition[4\.2](https://arxiv.org/html/2610.22768#S4.Thmtheorem2)\.
3. \(3\)Co\-display deliberately\.Design campaigns that present premium anchors with plausible complements, for example premium pancake mix with a national\-brand syrup, whose receipt co\-purchase rate is 11\.3% after premium versus 3\.3% after regular mix \(Table[20](https://arxiv.org/html/2610.22768#A10.T20)\)\. Without joint exposure the coupling channels cannot be estimated\.
4. \(4\)Keep a randomized share\.Show uniformly random feasible offer sets to 5–10% of eligible baskets and log each set’s selection probability\. Deterministic rules produce no within\-context contrast, and recorded propensities permit unbiased off\-policy evaluation of new policies\([Saito et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib32)\)\.
5. \(5\)Aim exploration where information is missing\.Allocate the randomized share preferentially to cells with low weightwg​kw\_\{gk\}and high potential margin, so that each exploratory display buys the most decision\-relevant information\.
6. \(6\)Randomize promotions separately\.When discounts or bundle rebates are used, vary their terms independently of which offers are displayed and record them\. Otherwise promotional lift is confounded with the display and acceptance channels\.
7. \(7\)Log typed events\.Record shown and accepted offers separately, with offer type, displaced item, position, propensity, and realized margin\. Receipts alone cannot separate display from acceptance\([Imai et al\., 2010](https://arxiv.org/html/2610.22768#bib.bib18);[Chen et al\., 2020](https://arxiv.org/html/2610.22768#bib.bib7)\)\.
8. \(8\)Re\-measure each cycle\.Rerun the diagnostic after each campaign period\. Weights should rise in explored cells\. Once a cell’s coupling is supported, serve it with joint selection; use exact search where display friction is also high \(Appendix[H](https://arxiv.org/html/2610.22768#A8)\)\.

These steps do not tailor the data toStoBasket\. They are the conditions under which any interaction\-aware policy, including a retailer’s own, can learn whether its offers reinforce one another\.

## Appendix LProof details

### L\.1\.Why pair moments suffice

Write the realized incremental value \(before conditioning on add\-on realizations\) as

V⁡\(Y,x,C\)=∑g\(Yg​dg−cg\)\+∑\(g,h\)Yg​Yh​γg​h\+∑k∈C\[mkqk\(Y,x\)−ck\]\.\\begin\{split\}V\(Y,x,C\)=\{\}&\\sum\_\{g\}\(Y\_\{g\}d\_\{g\}\-c\_\{g\}\)\+\\sum\_\{\(g,h\)\}Y\_\{g\}Y\_\{h\}\\gamma\_\{gh\}\\\\ &\+\\sum\_\{k\\in C\}\\big\[m\_\{k\}q\_\{k\}\(Y,x\)\-c\_\{k\}\\big\]\.\\end\{split\}All terms are finite linear combinations of11,YgY\_\{g\}, andYg​YhY\_\{g\}Y\_\{h\}\. Their expectations are11,pgp\_\{g\}, andρg​h\\rho\_\{gh\}respectively\. Consequently Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\) holds without any independence assumption\. If a nonlinearqkq\_\{k\}contains, for example,Yg​Yh​YlY\_\{g\}Y\_\{h\}Y\_\{l\}, third\-order moments may be necessary\. The same applies to nonlinear joint\-bundle margins\.

### L\.2\.Forest\-consistent correlation

For each edge\(g,h\)\(g,h\), the binary pairwise table is

Yh=0Yh=1Yg=01−pg−ph\+ρg​hph−ρg​hYg=1pg−ρg​hρg​h\\begin\{array\}\[\]\{c\|cc\}&Y\_\{h\}=0&Y\_\{h\}=1\\\\ \\hline\\cr Y\_\{g\}=0&1\-p\_\{g\}\-p\_\{h\}\+\\rho\_\{gh\}&p\_\{h\}\-\\rho\_\{gh\}\\\\ Y\_\{g\}=1&p\_\{g\}\-\\rho\_\{gh\}&\\rho\_\{gh\}\\end\{array\}which is nonnegative provided

max⁡\{0,pg\+ph−1\}≤ρg​h≤min⁡\{pg,ph\}\.\\max\\\{0,p\_\{g\}\+p\_\{h\}\-1\\\}\\leq\\rho\_\{gh\}\\leq\\min\\\{p\_\{g\},p\_\{h\}\\\}\.Root each tree and construct a joint distribution by sampling the root marginal and sampling a child conditional on its parent according to this edge table\. This distribution reproduces all specified node and edge marginals\. No unique full joint law is asserted without further assumptions; the tree\-Markov construction selects one valid law\. Our synthetic code uses a convex interpolation betweenpg​php\_\{g\}p\_\{h\}andmin⁡\{pg,ph\}\\min\\\{p\_\{g\},p\_\{h\}\\\}\.

### L\.3\.Full proof of separability

WriteF⁡\(x,C\)=A⁡\(x\)\+∑k∈C\[αk\+βk⊤​z​\(x\)\]F\(x,C\)=A\(x\)\+\\sum\_\{k\\in C\}\[\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z\(x\)\], whereAAcontains upgrade node and edge terms andz⁡\(0\)=0z\(0\)=0\. Ifβk⊤​z​\(x\)=0\\beta\_\{k\}^\{\\top\}z\(x\)=0for allx,kx,k,FFseparates intoA⁡\(x\)\+∑k∈CαkA\(x\)\+\\sum\_\{k\\in C\}\\alpha\_\{k\}\. Conversely, supposeF=U0​\(x\)\+V0​\(C\)F=U\_\{0\}\(x\)\+V\_\{0\}\(C\)on a Cartesian feasible domain\. For any feasiblexxand feasible singleton complement\{k\}\\\{k\\\}, the double differenceF⁡\(x,\{k\}\)−F⁡\(x,∅\)−F⁡\(0,\{k\}\)\+F⁡\(0,∅\)F\(x,\\\{k\\\}\)\-F\(x,\\varnothing\)\-F\(0,\\\{k\\\}\)\+F\(0,\\varnothing\)must vanish\. By direct expansion it equalsβk⊤​z​\(x\)\\beta\_\{k\}^\{\\top\}z\(x\), establishing necessity\. Notice this is*objective separability*; different algorithms may produce the same maximizer despite nonzero interactions\.

### L\.4\.Detailed proof of Proposition[C\.1](https://arxiv.org/html/2610.22768#A3.Thmtheorem1)

For any fixed statezz, the complement subproblem selects the up\-to\-KKpositive scores amongℓk​\(z\)=αk\+βk⊤​z\\ell\_\{k\}\(z\)=\\alpha\_\{k\}\+\\beta\_\{k\}^\{\\top\}z\. Introduce a zero\-score dummy option for excluding a complement\. Compare all pairs of affine scores and all scores with zero\. TheO⁡\(M2\)O\(M^\{2\}\)resulting rational hyperplanes subdivideℝr\\mathbb\{R\}^\{r\}intoO⁡\(M2​r\)O\(M^\{2r\}\)full\-dimensional cells for fixedrr\. Every cell induces a fixed strictly ordered positive\-score selection\. At a boundary state, ties among scores can be resolved using a nearby full\-dimensional cell\. Such a tie\-resolved selection achieves the same score at the boundary; therefore at least one enumerated complement set is optimal at any realizablezz, including degenerate cases after identifying permanently identical affine functions\. We may enumerate redundant sets, which does not hurt correctness\.

Fix an enumeratedCCand letBC=∑k∈CβkB\_\{C\}=\\sum\_\{k\\in C\}\\beta\_\{k\}andaC=∑k∈Cαka\_\{C\}=\\sum\_\{k\\in C\}\\alpha\_\{k\}\. Writing the upgrade value asU⁡\(x\)=∑fuf​\(xSf\)U\(x\)=\\sum\_\{f\}u\_\{f\}\(x\_\{S\_\{f\}\}\)and the summary asz⁡\(x\)=∑fμf​\(xSf\)z\(x\)=\\sum\_\{f\}\\mu\_\{f\}\(x\_\{S\_\{f\}\}\),

F⁡\(x,C\)=aC\+∑f\[uf​\(xSf\)\+BC⊤​μf​\(xSf\)\]\.F\(x,C\)=a\_\{C\}\+\\sum\_\{f\}\\big\[u\_\{f\}\(x\_\{S\_\{f\}\}\)\+B\_\{C\}^\{\\top\}\\mu\_\{f\}\(x\_\{S\_\{f\}\}\)\\big\]\.In the model of Eq\. \([11](https://arxiv.org/html/2610.22768#A1.E11)\), the single\-group factors areug=pg​dg−cgu\_\{g\}=p\_\{g\}d\_\{g\}\-c\_\{g\}andμg=\(pg​tg,vg,0\)\\mu\_\{g\}=\(p\_\{g\}t\_\{g\},v\_\{g\},0\), and the edge factors areug​h=ρg​h​γg​hu\_\{gh\}=\\rho\_\{gh\}\\gamma\_\{gh\}andμg​h=\(0,0,ρg​h​ζg​h\)\\mu\_\{gh\}=\(0,0,\\rho\_\{gh\}\\zeta\_\{gh\}\)\. This is a discrete graphical optimization on the primal graph of the scopes, with one global count budget on nonzero group actions\. Max\-sum variable elimination along a tree decomposition of widthww, with each message also indexed by the number of upgrade offers0,…,L0,\\ldots,Lmade in the eliminated subtree, is exact; fixedwwbounds the bag size andL≤GL\\leq Gbounds the counter\. The inner algorithm is therefore polynomial inGG,JmaxJ\_\{\\max\}, and input size, and combining it with the polynomial outer enumeration proves the claim\.

## Appendix MImplementation details

The code package provides: \(1\)engine/moment\_extension\.py, supporting policy\-local edgewise second moments, a correlated\-tree joint sampler, and exhaustive search; \(2\)engine/arrangement\.py, the exact rational cell sampler,engine/treewidth\_dp\.py, a count\- or summary\-augmented max\-sum program on a min\-fill tree decomposition, andengine/treewidth\_exact\.py, the exact rational solver for bounded\-treewidth factor graphs together with the latent\-class exposure model; \(3\)engine/baselines\.py, the independent, sequential, alternating and greedy baselines shared by all models; \(4\)engine/make\_figures\.pyfor repeatable synthetic figures; \(5\)tests/smoke\.py, which runs every solver check and pins each instance count reported here \(make test\)\.

Random seeds and per\-instance sweep results are provided as a CSV\. Synthetic stress examples are*purpose\-built*to show when coupling changes the optimum; they are not samples from a calibrated user population\.