Recommenders increasingly serve users whose choices consume a resource that builds up over a session: money under tiered delivery fees, time under venue opening hours, carbon or calories under a daily cap. The current practice is to rank items by learned taste and then penalize or filter expensive ones. That practice checks each item in isolation. It cannot tell that a sequence of individually affordable picks will leave the user unable to finish a day's plan, such as reaching a protein minimum before the budget runs out or arriving at the last venue before it closes. Formal verification of real-time systems has a well-studied tool for exactly this question. A priced timed automaton is a state machine with clocks and an accumulating cost, and zone abstraction summarizes the infinitely many clock-and-cost values from which a goal is still reachable as a few convex polyhedra. When prices are piecewise-linear, this question stays as tractable as the linear case.
We propose to attach such "feasibility zones" to multi-interest recommenders, which represent a user by several vectors, one per taste, instead of one averaged vector. The zones live in a deliberately tiny symbolic space of one clock and one or two resources. They are computed offline by backward reachability over coarse classes of items, and they are queried at serving time as a cheap membership test. The neural side stays high-dimensional, and the two sides touch only through each item's cost class. We expect this split to give recommendations that are guaranteed completable, at close to the latency of ordinary filtering. We also expect the per-interest structure to matter: when budgets are tight, feasibility concentrates in some tastes and not others, and a single averaged vector cannot redirect toward them.
Core Claim
The claim has two parts, and each can fail separately.
The first part is about the cost model. Session-level constraints in recommendation have two sides: upper caps on spending and lower requirements on what must be reached. Prices that are piecewise-linear in time, such as time-of-use or tiered tariffs, can be compiled into a one-clock priced automaton over item cost classes. Its backward-reachable zones then give an exact test for "a feasible completion still exists," and this test strictly dominates a check of the current item against the remaining budget.
The second part is about representation. Allocating retrieval slots across a user's interest vectors in proportion to both taste score and feasible mass recovers more relevant feasible items than applying the same exact test to a single-vector model's neighbors.
The theory behind the first part comes from On Nonlinear Prices in Timed Automata. That paper shows that optimal reachability with piecewise-linear prices remains PSPACE-complete, the same as linear priced automata, by splitting the state space into pieces with constant cost slope. It also gives price-preserving bisimulations that reduce piecewise-linear prices to linear ones. We reuse that reduction directly.
Two results constrain the design. Model Checking One-Clock Priced Timed Automata (see also the journal version) shows that a second clock or arbitrary cost rates already permit counter-machine encodings for temporal-logic checking. Quantitative analysis of real-time systems using priced timed automata notes that multiple competing costs quickly become undecidable for synthesis. We take both warnings literally. The symbolic part has one clock, and it carries at most two resources over a bounded horizon. Projecting embedding geometry into zones would multiply constraints, which is the explosion the research file flags, so we never do it.
We are also honest about where the guarantee comes from. With a bounded horizon, decidability is not the bottleneck. The contribution is an exact, precomputed, amortized feasibility oracle, not a new decidability result.
Research Program
Step 1: the abstraction. Catalog items are grouped into a finite alphabet of action classes by duration bucket, cost tier, and requirement contribution, for example a protein bucket. Prices are piecewise-linear in the clock or in accumulated spend. Locations record which discrete requirements have been met. Costs remain observer variables in the sense of the PTA survey above: they are checked against final budgets but never guard transitions mid-path. This keeps the model inside the tractable regime.
Step 2: backward reachability. Starting from goal locations, we compute for every location the set of (clock, spent) pairs from which some path reaches the goal within budget. Standard difference-bound matrices cannot hold a cost variable without losing convexity. Because our symbolic space is two- or three-dimensional, we instead store explicit convex polygons, or unions of them, using the corner-point refinement from the PTA survey to place exact boundaries where slopes switch. Personalized thresholds, such as an individual user's budget, enter as parameters. Zones are therefore computed once per constraint template and shifted per user rather than recomputed.
Step 3: serving. A multi-interest extractor, either ComiRec-SA or DMI-GNN, produces K interest vectors. For each candidate item, we apply its class transition to the user's current symbolic state and keep the item only if the successor lies in a feasible zone. Retrieval slots are then divided across interests in proportion to taste-weighted feasible mass. An interest whose neighborhood has become infeasible, such as an expensive cuisine late in a tight-budget day, gives up its slots to interests that can still be served.
The open problem in multi-interest work about how many vectors each user should get, raised in Multi-Interest Recommendation: A Survey, acquires a resource-aware answer here. Within a session, the number of interests that are actually served shrinks as the budget does.
Baselines
The naive reference point is an unconstrained multi-interest retriever with no cost handling. Specifically, it is ComiRec-SA from Controllable Multi-Interest Framework for Recommendation, which pools a user's history into several vectors through multiple attention queries. On Amazon Books, that paper reports that raising its diversity knob λ from 0 to 0.25 moves diversity from 23.2% to 55.1% for about a 5% recall drop. This is a useful yardstick for what an accuracy–constraint trade-off normally costs. The unconstrained retriever sets the accuracy ceiling and the violation-rate floor that every constrained method is measured against.
The strongest existing constrained method is the constraint-aware model of Eating for a Sustainable Planet. It combines multi-interest attention with a mixture-of-experts encoder of recipe sustainability features and re-ranks with personalized Lagrangian-style penalties when cost or carbon thresholds are exceeded. It is the strongest competitor because it is the only method in the file that already joins multi-vector users with resource costs, and it ships with data and code (SusDiet codebase). The file reports no NDCG or Recall values for it, so we have no reported result to quote and will rerun it ourselves. We will train it from the released code on the same splits, with the same backbone dimension and the same hyperparameter-search budget as ours, and tune its penalty weights on validation to minimize violations at matched recall. Our method beats it if, at equal or better NDCG@20, it reaches zero upper-bound violations and a strictly lower dead-end rate.
The practitioner's baseline is a myopic hard filter. It keeps an item only if paying for it right now stays under the remaining budget, and it uses the same multi-interest backbone.
The search baseline is constrained beam search. At serving time it rolls out short continuations over action classes, with the beam width chosen to match our latency.
The key ablation applies the identical zone oracle to a single-vector model, either the YouTube-DNN-style mean pool or SASRec, and separately removes feasibility-weighted slot allocation from the multi-interest model. This separates the contribution of the zones from the contribution of per-interest allocation. For context on the representation side, MIND reports a HitRate@50 gain of over 60% versus YouTube DNN on Tmall (MIND), and DMI-GNN reports an HR@20 of 40.26 on Tmall (DMI-GNN). We cite these only as evidence that multi-vector backbones are the right starting point, not as targets on our constrained task.
Why not just…?
Why not just add a Lagrangian penalty? The SusDiet model does this. A penalty nudges rankings but promises nothing, and its thresholds are static, so it cannot see that budget drains over a session or that price slopes change with time. The real risk is that, with tuning, penalties reach near-zero violations in practice. We will report the full violation-versus-accuracy curve across penalty weights. If some penalty weight matches our dead-end rate at equal NDCG, the guarantee is our only remaining advantage, and we will say so.
Why not just filter items whose immediate cost exceeds the remaining budget? This is the most serious threat. For pure upper caps with linear prices it may be nearly as good as our method. It fails on two-sided constraints, where a minimum must still be reachable, and on piecewise-linear timing effects, where an item is cheap now but forces an expensive tier later. Our experiments therefore vary the share of sessions that carry lower-bound requirements and tiered prices. If the gap between the myopic filter and our method disappears even at high shares, the zone machinery is not justified and we will narrow the claim to completion guarantees alone.
Why not just solve each request with an SMT or integer program? Exact per-request solving is correct but slow. On the Airport Landing Scheduling Problem with 10 planes and 10 runways, Z3 took about 1300 seconds, while UPPAAL-Cora's depth- and breadth-first search timed out (Bhave et al.). Bounded unrolling also caps the horizon. Our zones are computed once per template and amortized across users. We will measure per-request latency against Z3 at matched horizons, and we will run constrained beam search to show whether a cheaper search already suffices.
Proposed Experiments
Data and constraints. We use two settings where both a clock and a resource are natural. The first is the SusDiet dataset, about 180,000 users and 744,000 interactions, with USDA-derived costs and nutrition. It carries a daily-plan constraint: a tiered grocery price, a carbon cap, and a protein minimum. The second is Foursquare NYC and TKY. Its constraint is a one-day itinerary with travel time computed from coordinates, opening windows estimated from check-in time distributions, and piecewise-linear fares. These constraints are synthetic overlays on real interaction data, and we will release the generators.
Protocol. In offline replay, we truncate each session at every step and score held-out next items among the feasible candidates. In greedy rollout, we repeatedly take the top item and record whether the session completes.
Metrics. We report Recall@20 and NDCG@20 on feasible items, upper-bound violation rate, dead-end rate, and p99 serving latency.
Decisive checks. The proposal succeeds if three things hold. Zone-filtered multi-interest retrieval reaches zero violations and a markedly lower dead-end rate than both the myopic filter and the Lagrangian penalty, at NDCG within a few percent of the unconstrained model. The single-vector ablation with the same oracle loses more accuracy as budgets tighten, which is the bottleneck prediction. And latency stays within a small factor of plain filtering while beating per-request SMT by orders of magnitude.
As a soundness check of our zone engine, we will rerun an Airport Landing Scheduling instance against the Z3 result above. The experiment that could falsify the core claim is the sweep over the share of lower-bound and tiered constraints. If the myopic filter matches us throughout, the zone abstraction has no practical value in recommendation, and that is what we would conclude.
References
- On Nonlinear Prices in Timed Automata
- Model-Checking One-Clock Priced Timed Automata
- Quantitative analysis of real-time systems using priced timed automata
- Multi-Interest Recommendation: A Survey
- Controllable Multi-Interest Framework for Recommendation
- Eating for a Sustainable Planet: Personalized Sustainable Diet Recommendation via Constraint-Aware Decision-Making Modeling
- Multi-Interest Network with Dynamic Routing for Recommendation at Tmall
- Dynamic Multi-Interest Graph Neural Network for Session-Based Recommendation