🤖 AI

Right-Sizing Communication and Recommendation Set Size in AI-Assisted Search

This paper models the trade-off between user communication costs and AI search costs in a Bayesian recommendation system, demonstrating that the optimal interaction strategy is governed by the relative costs of these mechanisms, which give rise to distinct regimes prioritizing communication, search, or a hybrid approach, while the specific sampling distribution merely determines the existence of the hybrid middle-ground regime.

Original authors: Jing Dong, Prakirt Raj Jhunjhunwala, Yash Kanoria

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jing Dong, Prakirt Raj Jhunjhunwala, Yash Kanoria

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking into a massive, high-tech library to find the perfect book. You don't know exactly which one you want, but you have a vague idea. The librarian is an AI assistant. This paper explores the best way for you and the librarian to work together to find that book without wasting your time or mental energy.

The authors break this down into two main "costs" you pay during the interaction:

Communication Cost: The mental effort it takes for you to explain what you want. (e.g., "I want a sci-fi book, but not too long, maybe with a robot, but not a sad ending...")
Search Cost: The effort it takes for you to look through the list of books the librarian hands you. (e.g., Reading the titles and summaries of 50 books to find the one you like).

The paper asks a fundamental question: How much should you describe your taste, and how many books should the librarian show you, to get the best result with the least effort?

The core insight is that the answer depends on the relative cost of talking versus searching. Regardless of how the AI behaves, distinct "regimes" emerge:

If communicating is cheap (relative to searching), you should prioritize communication: give a precise description to get a single, perfect result.
If communicating is expensive (relative to searching), you should prioritize search: say little and browse a larger list.

The researchers studied this using a mathematical model where "features" exist in a very high-dimensional space. They looked at two different ways the librarian (the AI) might behave to see how these cost regimes play out.

Scenario 1: The "Honest but Passive" Librarian (Posterior Sampling)

Imagine a librarian who listens to your description and then randomly pulls books from the shelf that might fit. They don't try to game the system; they just follow the probabilities.

The Finding: In this scenario, the relative costs create a Hybrid Regime.
The Analogy: You shouldn't just say "I want a book" (too vague), nor should you write a 10-page essay (too exhausting). Instead, you give a "good enough" description.
The Result: Because your description isn't perfect, the librarian shows you a list of several books to cover the gaps.
The Sweet Spot: Here, the "middle ground" exists. It pays off to do both: you spend a little effort describing your taste, and the librarian shows you a small list (say, 10–15 items). This hybrid zone emerges because the passive AI allows for a balance where partial communication and partial search work together efficiently.

Scenario 2: The "Super-Optimized" Librarian (Tilted Distribution)

Now, imagine a smarter librarian. This one doesn't just randomly pull books. Instead, they actively tilt their selection. They take your description and say, "Okay, I know you said 'robot,' but since you only gave me a short description, I'm going to lean heavily on that word and show you books that are definitely about robots."

The Finding: In this scenario, the relative costs force you into Pure Regimes. The "Hybrid" middle ground collapses.
The Analogy:
- If talking is cheap: You give a very detailed, precise description. The librarian, knowing you are precise, gives you one single, perfect book. You don't need to browse because the AI has "tilted" its choice to match you perfectly.
- If talking is expensive: You say nothing. The librarian, knowing you won't talk, gives you a huge list of random books to browse.
The Result: You rarely do both. The system forces you to pick the cheaper path. If it's easy to talk, you talk and get one result. If it's hard to talk, you stay silent and browse a big list.

The "High-Dimensional" Twist

The paper emphasizes that this happens in a world with many features (like a library with thousands of genres).

Why it matters: In a complex world, you can't possibly describe everything.
The Scaling: As complexity grows, the number of books the librarian needs to show you grows exponentially (but stays manageable, like 15 instead of millions) if you give a partial description.

Summary of the "Rules"

The most important takeaway is that the relative cost of communication vs. search dictates your strategy, regardless of the AI's specific behavior.

The Universal Principle:
- Prioritize Communication when it is cheap relative to searching. (Give more detail, expect fewer results).
- Prioritize Search when communication is expensive relative to searching. (Give less detail, expect a larger list).
The Role of the AI (Passive vs. Tilted):
- The AI's behavior (whether it is "passive" or "tilted") does not create this trade-off; the costs do.
- However, the AI's behavior determines how you navigate that trade-off:
  - With a Passive AI, the trade-off allows for a Hybrid Regime (do a bit of both).
  - With a Tilted AI, the trade-off forces a Pure Regime (do one or the other, but not both).

The paper concludes that understanding these "costs" helps us design better AI assistants. By recognizing whether we are in a cheap-communication or expensive-communication regime, we can tell users exactly how much effort to put into their prompts to get the best results, whether that means writing a detailed prompt or simply browsing a curated list.

Technical Summary: Right-Sizing Communication and Recommendation Set Size in AI-Assisted Search

Problem Statement

This paper addresses the fundamental trade-off in AI-assisted decision-making between the cost of user communication and the cost of search. In modern recommendation systems (e.g., e-commerce, healthcare), users face vast product spaces. While AI agents can process these spaces, they lack direct access to a user's true latent preferences. To bridge this gap, users must communicate preferences, incurring a communication cost (cognitive effort and time). In return, the agent provides a set of recommendations, but evaluating this set incurs a search cost (cognitive load proportional to the set size).

The core research question is: How should one jointly choose the amount of preference information communicated by the user and the number of recommendations provided by the AI agent to balance communication costs, search costs, and product utility?

The authors model this interaction in a high-dimensional feature space ( $d$ -dimensions), where both user preferences and products are represented as unit vectors on a sphere. The utility of a product is defined by its alignment (dot product) with the user's true preference vector.

Methodology

1. Interaction Model

The interaction is modeled as a three-stage process:

Communication: The user transmits a noisy message $m$ with precision $\kappa$ . The message is generated via a von Mises-Fisher (vMF) distribution centered on the true preference $h$ . The communication cost is quantified information-theoretically as the Kullback-Leibler (KL) divergence between the agent's prior and posterior beliefs, scaled by a cost parameter $\lambda_c$ .
Recommendation: The agent interprets the message to form a posterior belief and generates a recommendation menu of size $n$ $n$ . The paper analyzes two sampling strategies:
- Posterior Sampling: Recommendations are independent and identically distributed (i.i.d.) draws from the agent's posterior belief (typical of standard Gen AI).
- Tilted Sampling: The agent optimally modifies (tilts) the sampling distribution to place additional weight on the user's communicated preference, acting as a design lever.
Search: The user selects the best item from the menu. The search cost is proportional to the logarithm of the menu size ( $\lambda_s \log n$ ), reflecting the entropy reduction required to identify the best option.

2. High-Dimensional Asymptotic Analysis

To derive structural insights, the authors analyze the regime where the feature dimension $d \to \infty$ . They employ a Large Deviation Principle (LDP) to characterize the maximum utility induced by a set of $n$ recommendations.

Scaling Laws: The analysis reveals that for the problem to remain non-trivial, the message precision $\kappa$ must scale linearly with $d$ , and the recommendation set size $n$ must scale exponentially with $d$ (i.e., $n \approx e^{\alpha d}$ ). Consequently, the cost parameters $\lambda_c$ and $\lambda_s$ must scale as $O(1/d)$ .
Deterministic Approximation: The stochastic optimization problem is reduced to a deterministic optimization problem involving the rate function of the LDP. This allows for explicit characterization of optimal policies.

Key Contributions

Novel Theoretical Framework: The paper introduces a model that jointly optimizes message precision and recommendation set size, measuring costs information-theoretically (KL divergence for communication and entropy for search).
Asymptotic Characterization: By establishing an LDP for the maximum utility, the authors reduce the complex stochastic problem to a tractable deterministic optimization problem, providing explicit scaling laws for optimal system design in high dimensions.
Distinction Between Sampling Regimes: The paper identifies a sharp qualitative difference between two practically motivated sampling schemes:
- Posterior Sampling: Requires a hybrid regime where both communication and search are jointly optimized.
- Tilted Sampling: Leads to a pure regime where the system relies entirely on either communication or search, depending on which is cheaper.

Key Results

Under Posterior Sampling (Standard Gen AI)

Hybrid Regime: When communication and search costs are of comparable magnitude, the optimal policy is a "hybrid" one. The user provides partial but informative communication (non-zero precision), and the agent provides a recommendation set of size $n > 1$ (exponential in $d$ ).
Search-Only Regime: If communication costs become sufficiently high relative to search costs, the optimal policy collapses to "pure search." The user provides no information ( $\kappa = 0$ ), and the agent relies entirely on a large recommendation set to cover the preference space.
Absence of Pure Communication: Unlike the search-only regime, a "pure communication" regime (relying solely on a single recommendation with high precision) does not emerge as an interior solution in the high-dimensional limit. The user always benefits from some level of search ( $n > 1$ ) unless search costs are prohibitively high.

Under Tilted Sampling (Optimized Agent)

Phase Transition: When the agent can optimally "tilt" the distribution (adjusting the weight placed on the user's message), the optimal policy exhibits a sharp phase transition.
Pure Strategies: The system favors a single mode of interaction:
- If communication is cheaper ( $\lambda_c < \lambda_s$ ), the policy is pure communication ( $n=1$ , high precision).
- If search is cheaper ( $\lambda_s < \lambda_c$ ), the policy is pure search ( $\kappa=0$ , large set).
No Hybrid Regime: The hybrid regime disappears under tilted sampling. The ability to tune the distribution allows the agent to fully exploit the cheaper resource, making joint optimization unnecessary.
Performance Gains: Tilted sampling outperforms posterior sampling, particularly in the hybrid region of the posterior regime, by effectively restoring the marginal parity between communication and search.

Finite Dimensionality

For finite $d$ , the paper notes that the "pure communication" regime can emerge due to the discretization gap. Moving from a single recommendation ( $n=1$ ) to multiple ( $n=2$ ) incurs a discrete jump in search cost ( $\lambda_s \log 2$ ). If this jump outweighs the marginal benefit of diversity, the system may stick to a pure communication policy even when communication costs are not zero.

Significance and Claims

The paper claims to advance the theoretical understanding of AI-powered recommendation systems by:

Formalizing the Trade-off: Providing a rigorous framework for the interplay between user cognitive effort (communication) and system-generated effort (search).
Guiding System Design: Offering explicit guidelines for how AI assistants should be tuned based on the relative costs of user interaction. For standard Gen AI agents (posterior sampling), the authors suggest that a mix of user input and diverse recommendations is often optimal. However, for more sophisticated, tuned agents (tilted sampling), the system should dynamically switch to a single, most cost-effective mode.
Bridging Theory and Practice: The high-dimensional approximation mirrors modern embedding-based architectures (e.g., LLMs, vector databases), suggesting that the derived scaling laws are relevant for real-world systems where feature dimensions are large.

The authors emphasize that their findings are theoretical and derived under asymptotic assumptions, though they provide numerical evidence that the asymptotic approximations hold well for finite dimensions relevant to practical applications (e.g., $d=15$ ). They do not propose specific new algorithms for implementation but rather offer a theoretical lens to evaluate existing and future agent architectures.