BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning

2025/07/31 by Zhou, Jinan, Ghosh, Rajat, Bhargava, Vaishnavi +2
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2507.23170

Abstract

When designing LLM services, practitioners care about three key properties: inference-time budget, factual authenticity, and reasoning capacity. However, our analysis shows that no model can simultaneously optimize for all three. We formally prove this trade-off and propose a principled framework named The BAR Theorem for LLM-application design.

Citations

• Hierarchical Reasoning Model
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
• Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Models
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
• Towards Understanding Systems Trade-offs in Retrieval-Augmented Generation Model Inference
• FrontierMath: A Benchmark for Evaluating Advanced Mathematical Reasoning in AI
• Omni-MATH: A Universal Olympiad Level Mathematic Benchmark For Large Language Models
• AIME: AI System Optimization via Multiple LLM Evaluators
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
• GPQA: A Graduate-Level Google-Proof Q&A Benchmark
• Persistent memory for AI coding agents: a pre-registered SWE-bench Verified benchmark
• Large Language Models as Analogical Reasoners
• Efficient Memory Management for Large Language Model Serving with PagedAttention
• Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
• MME: A Comprehensive Evaluation Benchmark for Multimodal Large Language Models
• Direct Preference Optimization: Your Language Model is Secretly a Reward Model
• HaluEval: A Large-Scale Hallucination Evaluation Benchmark for Large Language Models
• Efficiently Scaling Transformer Inference
• ReAct: Synergizing Reasoning and Acting in Language Models
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
• Least-to-Most Prompting Enables Complex Reasoning in Large Language Models
• PaLM: Scaling Language Modeling with Pathways
• Self-Consistency Improves Chain of Thought Reasoning in Language Models
• Training language models to follow instructions with human feedback
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• WebGPT: Browser-assisted question-answering with human feedback
• Show Your Work: Scratchpads for Intermediate Computation with Language Models
• Training Verifiers to Solve Math Word Problems
• TruthfulQA: Measuring How Models Mimic Human Falsehoods
• Saturated Transformers are Constant-Depth Threshold Circuits
• LoRA: Low-Rank Adaptation of Large Language Models
• Measuring Mathematical Problem Solving With the MATH Dataset
• Language Models are Few-Shot Learners
• Fast Transformer Decoding: One Write-Head is All You Need
• ZeRO: Memory Optimizations Toward Training Trillion Parameter Models
• Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
• HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering
• Attention Is All You Need
• TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for\n Reading Comprehension
• CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge

Related

• Finding the Sweet Spot: Trading Quality, Cost, and Speed During Inference-Time LLM Reflection
• Bridging the Reasoning Gap: Small LLMs Can Plan with Generalised Strategies
• Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights
• Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategies
• Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs