Query–service matching in customer service systems faces a critical challenge of accurately aligning user queries expressed in colloquial language with formally defined services while balancing business objectives. Traditional keyword-based and embedding approaches fail to capture complex semantic nuances and cannot provide interpretable explanations. We address this problem by proposing a novel reasoning-enhanced framework that leverages large language models (LLMs) for structured multi-criteria evaluation. Our key innovation is a reasoning-first scoring architecture where the model generates detailed explanations before numerical scores, reducing score variance by 18% through conditional mutual information. We introduce a controlled stochastic perturbation mechanism with theoretically derived optimal parameters that balance diversity and relevance, alongside a knowledge distillation pipeline enabling 960× model compression (480B→0.5B parameters) while retaining 94% performance. Rigorous theoretical analysis establishes Pareto optimality guarantees for multi-criteria evaluation, information-theoretic entropy reduction bounds, and PAC learning guarantees for distillation. Experimental validation on real-world telecommunications data demonstrates 89% Precision@1 (15.3% improvement over baselines), 23% diversity enhancement, and 96× latency reduction, with deployment cost decreasing 1200× compared to direct LLM inference. This work bridges the gap between LLM capabilities and production deployment requirements through principled mathematical foundations and practical system design.