A Geometric Approach to Personalized Recommendation with Set-Theoretic Constraints Using Box Embeddings

We appreciate the reviewer’s suggestion to clarify how natural language queries are mapped to structured forms, as well as their thoughtful concerns regarding generalization, scalability, and efficiency.

Mapping from natural language to attributes:

In real-world recommendation systems — such as streaming platforms, e-commerce sites, or travel services — free-text queries (e.g., “funny action movies without clowns”) are typically mapped to a curated set of item tags (e.g., genre, theme, metadata) via a natural language understanding (NLU) module.

Our model operates after this step, assuming a structured query (e.g., Action ∧ Comedy ∧ ¬Clowns) has already been derived. While we do not include an NLP module, it is modular and complementary to our framework. Recent LLMs (e.g., GPT-4o) can perform this front-end task — identifying attribute constraints from text — while our model serves as the back-end executor for set-theoretic reasoning.

We thank the reviewer for this helpful suggestion; including such an example would indeed strengthen the narrative, and we will incorporate a clarifying illustration in the final version.

Extending the Framework for more complex queries:

1. Support for Arbitrary Logical Queries.

Using the inclusion-exclusion principle, any Boolean query can be transformed into disjunctive normal form (DNF). For example, a query like $(\text{User} \wedge A_1) \vee (\text{User} \wedge A_2)$ can be evaluated as:

$\text{Score}(((U \cap A_1) \cup (U \cap A_2)) \cap i) = \text{Score}(U \cap A_1 \cap i) + \text{Score}(U \cap A_2 \cap i) - \text{Score}(U \cap A_1 \cap A_2 \cap i)$, $i$ is the item.

Our containment-based scoring function remains applicable to any logical query formed over box embeddings, including negations and disjunctions.

2. Time complexity / Efficient Implementation via Gumbel Boxes.

Each term in the DNF expansion involves computing the intersection of multiple boxes, which we implement using a log-sum-exp (LSE) operation over the min and max coordinates. For a query involving $k$ attributes, the largest term in the DNF requires intersecting $k$ boxes, resulting in a complexity of $\mathcal{O}(k \cdot d)$, where $d$ is the box embedding dimension.

Now to compute scores for the full Boolean query with $t$ inclusion-exclusion terms: $\mathcal{O}(t \cdot k \cdot d)$. In worst case — e.g., a disjunction over $k$ variables — $t$ can be $\mathcal{O}(2^k)$.

• However, typical queries involve conjunctions and negations, resulting in far fewer DNF terms than the worst case. E.g.,(User∧Children∧Comedy∧¬Clowns)∨(Monster∧¬Animation) results into 8 terms in its DNF form.
• Additionally, each term is independently computable, and we parallelize the LSE computation across dimensions and query terms for intersection volumes calculation, enabling efficient batched evaluation. These optimizations are provided in our codebase.

There would be no difficulty in operating on more complex queries, such as $U \cap A_1 \cap A_2 \cap \neg A_3$. Note that our model does not need to be trained on complex queries — it is trained only on pairwise interactions but naturally generalizes to a broad space of unseen logical compositions. As noted above, evaluating on deeper queries is computationally efficient, and so we could certainly evaluate our model on such queries. The main challenge would be identifying deeper queries which would be representative of a real user query distribution, which is non-trivial.

Why Gumbel max instead of softmax-max:

We initially explored using the softmax-based approximation for max/min operations, but encountered numerical instability and a lack of probabilistic consistency. Specifically, softmax-max computes a convex weighted average that always underestimates the true max:

$\operatorname{SM-Max}(\mathbf{x}; \tau) =\sum_{i=1}^n\underbrace{ \Bigl(\frac{e^{x_i/\tau}}{\sum_j e^{x_j/\tau}}\Bigr)}_{w_i}\,x_i.$

$\operatorname{SM-Max}(\mathbf{x}; \tau) < \operatorname{max}(\mathbf{x})$,

$\operatorname{SM-Min}(\mathbf{x}; \tau) = -\operatorname{SMM}(-\mathbf{x}; \tau) > \operatorname{min}(\mathbf{x})$

This becomes problematic when computing box intersections, which rely on min/max operations over interval boundaries. For example, if box $[c,d]$ is fully contained in $[a,b]$ we should have $\operatorname{Vol}([a,b] \cap [c,d]) = \operatorname{Vol}([c,d])$. But the softmax-based approximation inflates the intersection to $[x, y]$ where $x < c$ and $y > d$, violating containment and producing invalid probabilities (e.g., $\operatorname{P}([x,y] \mid [c,d]) > 1$).

In contrast, GumbelBox embeddings have the opposite quality, they upper bound the max operation ensuring the $\operatorname{P}([x,y] \mid [c,d]) < 1$.

We thank the reviewer for highlighting this point — it indeed reflects an interesting theoretical contribution. We will provide the detailed proof in the final version of the paper.

Thank you for the thoughtful and constructive review. We appreciate your detailed engagement with our paper and the helpful suggestions on evaluation metrics.

Recommendation Task / NDCG evaluation / Hyperparameter

We calculate the NDCG score for the set theoretic queries. Please refer to the tables below.

Movielens-1M dataset

NYCR dataset.

Lastfm dataset also shows similar trends (omitting it for character constraint).

In addition to the logical queries, we also perform a standard recommendation task (i.e. recommend an item for a user), reported in terms of NDCG score (Table 6. in Appendix B2) on all four datasets where we observe that box embeddings outperform the baselines across all datasets. We posit this is because the box embedding space is more accurately able to capture the item-attribute information.

We provide the hyperparameter search details in Appendix B.2. We use wandb.ai for hyperparameter tuning (See Figure 3. for the hyperparams for Box).

Baseline consideration:

We have attempted to compare against formidable baselines which seem most capable of capturing set-theoretic semantics. The baselines chosen—MF, NeuMF, and LightGCN—are standard, well-established methods in recommendation systems. They represent varying levels of neural complexity and address user-item and attribute-item interactions effectively. More recent baselines either do not directly provide any particular advantage for set-theoretic queries, or use significant external information (eg. pretrained LLMs). We feel the selection of baselines covers the existing space fairly well (matrix, neural, and graph-based methods) without diluting the central contribution of introducing a method tailored to set-theoretic compositionally or introducing exogenous information.

Query Generation Bias:

We agree that not all attribute combinations reflect realistic user intents, and we explicitly address this concern in our query generation process through statistical heuristics combined with manual inspection, as described in Section 4.2.2.

Specifically, to ensure semantic plausibility, we define viable and non-trivial attribute pairs for intersection and difference queries based on two criteria:

1. Relevance: We require that the overlap between the attributes is greater than random chance, i.e., $|a_1 \cap a_2| > \varepsilon$, ensuring the pair co-occurs frequently enough to represent realistic co-preference.
2. Non-triviality: We further enforce that the overlap is not overly large, i.e., $|a_1 \cap a_2| < \alpha \cdot \min(|a_1|, |a_2|)$, to avoid trivial combinations where one attribute almost subsumes another (e.g., "fiction" ∧ "sci-fi").

This formulation reflects the plausibility of attribute combinations, avoiding unlikely or degenerate cases such as "sci-fi and documentary". In practice, the resulting combinations include interpretable and realistic pairs like ("action", "comedy") or ("children", "not monster"), which align with user behavior patterns. To further ensure the quality of queries, we have manually verified the plausibility of the selected attribute combinations to the best of our knowledge and effort. We also plan to release the full dataset upon paper acceptance to support reproducibility and facilitate future work in this space.

Changing User preferences:

Our current work does not explore incremental or online updates to user or item representations. However, it follows the standard recommendation framework, where embeddings are periodically retrained using accumulated user-item and item-attribute interactions — a paradigm widely adopted in practical systems. While we have not implemented streaming updates, such extensions could be supported via fine-tuning on recent data or by leveraging continual learning techniques common in embedding-based models.

Thank you for going through the paper so meticulously — we truly appreciate the careful reading and thoughtful feedback. We're glad you found the framework novel and the paper well-written, and we appreciate your comments highlighting both the strengths and areas for improvement.

We apologize for the oversight in the last step of the equation — we’ve corrected it, and the fix will be reflected in the final draft.

Regarding supporting evidence for the limitations of vector-based embeddings in handling set operations:

We found QUEST (Malaviya et al., 2023) to be a closely related study that introduces a benchmark for entity-seeking queries with implicit set-based semantics. Although QUEST does not focus on explicit constraints or personalization, which are central to our work, it empirically demonstrates that vector-based T5 embeddings struggle with set-theoretic operations — particularly with negation queries, and often treat conjunctions as disjunctions.

We thank the reviewers for raising thoughtful and forward-looking questions regarding possible extensions of our approach.

We agree that a recommendation systems framework should be recognized not only for its current performance but also for its extensibility to address practical challenges such as deployability, handling cold start problem, content-aware recommendation, and evolving user behavior etc. While we focus our paper on a clearly defined core contribution of handling set-theoretic constraints, we touch upon these broader aspects in the rebuttal to highlight the extensibility and practical relevance of our framework. We will include these discussions in the final version of the paper.

Box operation in high dimensions and Deployment in a search system:

Box embeddings remain computationally efficient even in high dimensions, as box intersection volume calculation can be parallelized across dimensions. Our method uses GumbelBox embeddings during training, where soft intersections are computed via log-sum-exp operations, however inference speed can be further improved by substituting soft approximations with hard min/max operations, providing faster evaluation at deployment time. This is achievable by annealing the Gumbel temperature to promote sharper boundaries during training (Capacity & Bias). Due to these advantages, box embeddings can actually provide even faster inference than approximate k-NN algorithms on vectors, as demonstrated in Mei et al. (2022b) which significant improvement over FAISS.

Content-aware recommendation / Handling Text image as side information / Cold start problem.

In this work, we treat genres, tags, and metadata as item content, making our setup inherently content-aware with respect to structured attributes. We understand the reviewer’s interest in whether our box embedding framework can be extended to richer content modalities such as text or images.

A practical approach is to encode text/image features using pretrained models like BERT or CLIP, and then project them into the box embedding space via a learnable transformation. Prior work supports this, to give a few examples; Onoe et al. (2021) derived box embeddings for entity mention representation from BERT, Rau et al. (2020) use ResNet50 features to construct box embeddings for visual scenes. Such multimodal integration would enable our model to handle unstructured content and is particularly promising for cold-start scenarios.

While our current method assumes some user/item interactions during training (as in standard collaborative filtering), we are actually uniquely well-suited to handle cold-start settings. To do so, we could “pretrain” item representations such that they are contained within their attribute boxes. In typical cold-start fashion, a new user would generally provide a list of like/dislike annotations on attributes, which would directly correspond to set-theoretic operations on the attribute box representations.

Evolving user preferences over time:

Our current work does not explore incremental or online updates to user or item representations. However, our method can operate within the standard recommendation framework, where embeddings are typically retrained periodically using updated user-item and item-attribute interaction data. This batch retraining paradigm is widely adopted in practical systems, where new interactions are accumulated over time and incorporated during scheduled model updates. While we have not implemented online or streaming updates in this work, such extensions could be supported by fine-tuning user or item embeddings on recent interaction data.

Recommendation without constraint (implicit setting):

In the implicit setting, the system defaults to using the user's historical preferences — captured via the user box learned from past interactions — as the query itself. This allows our model to function like standard collaborative filtering approaches, recommending items based on geometric containment between the user box and item points in the latent space.

Comparison to hybrid graph-based approaches:

We acknowledge that many recent attribute-aware recommendation models use Graph Convolutional Networks (GCNs) to capture item-user-attribute interactions. In our work, we include LightGCN (He et al., 2020) as a baseline and adapt it to a hybrid graph where items are connected to both users and attribute tags as a form of graph. This ensures attribute information is incorporated, aligning with our study’s objectives. We agree that such hybrid graph-based methods are strong baselines and may offer partial inductive biases for compositional reasoning. Note, however, that our method outperforms LightGCN by >40% on average over all the query types.

If the reviewer has a specific hybrid graph-based method in mind that supports logical constraints or compositional queries, we would be happy to review and discuss it in the final version.