# NBQ: Next-Best-Question for Dynamic Profiling

arXiv: https://arxiv.org/abs/2606.00809 · HTML: https://mlsanity.com/paper/2606.00809/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 16 of 16)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback](https://mlsanity.com/paper/2305.14975/) (2023)
- [MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedback](https://mlsanity.com/paper/2309.10691/) (2023)
- [Large language models can accurately predict searcher preferences](https://mlsanity.com/paper/2309.10621/) (2023)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Probing the Multi-turn Planning Capabilities of LLMs via 20 Question Games](https://mlsanity.com/paper/2310.01468/) (2023)
- [On Symmetric and Asymmetric LSHs for Inner Product Search](https://mlsanity.com/paper/1410.5518/) (2014)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Retrieval-Augmented Conversational Recommendation with Prompt-based Semi-Structured Natural Language State Tracking](https://mlsanity.com/paper/2406.00033/) (2024)
- [MockLLM: A Multi-Agent Behavior Collaboration Framework for Online Job Seeking and Recruiting](https://mlsanity.com/paper/2405.18113/) (2024)
- [Enhancing User Personalization in Conversational Recommenders](https://mlsanity.com/paper/2302.06656/) (2023)
- [Criteria-Based LLM Relevance Judgments](https://mlsanity.com/paper/2507.09488/) (2025)
- [Reciprocal Sequential Recommendation](https://mlsanity.com/paper/2306.14712/) (2023)

## Abstract (arXiv)

Many real-world conversational settings for knowledge discovery, including podcasts, hiring screens, and marketplaces, require a purpose-driven understanding of a person. We study the Next-Best-Question (NBQ) problem: at each turn, an interviewer should ask the question with the highest expected information gain given what has already been learned and the conversation goal. We propose NBQ, a plug-and-play framework that seeds a diverse pool of candidate questions, maintains a compact and continuously updated user state, adaptively selects the next question within a turn budget, and distills the resulting free-form dialogue into a structured vector-based user profile. As a demanding application, we instantiate NBQ for reciprocal matchmaking, where compatibility must be mutual and each person is modeled by both self-description and counterpart-preference representations. To support large-scale matching, we further introduce QuickMatch, an efficient retrieval layer that recasts reciprocal matching from quadratic pairwise scoring to approximate vector search. Experiments show that NBQ improves user profiling quality by up to 13.6% and 14.0% in AC@T and AR@T, respectively, while QuickMatch accelerates retrieval by up to 22.9x with recall up to 0.989.