mlsanityData to 14 Oct 2026

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

arXiv 2507.23170 ↗First posted 31 Jul 2025cs.LGcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 37 of its 55 references that are in the map. First posted on arXiv 31 Jul 2025.

Builds on

37 of 55 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Hierarchical Reasoning Model26 Jun
  2. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May

Other references · 35

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  4. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  5. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  6. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  7. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  8. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  9. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  10. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  11. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  12. 2021TruthfulQA: Measuring How Models Mimic Human Falsehoodscited by 2,975
23 more
  1. 2017TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehensioncited by 2,955
  2. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,879
  3. 2019Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelismcited by 1,868
  4. 2021WebGPT: Browser-assisted question-answering with human feedbackcited by 1,745
  5. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,407
  6. 2023Towards Understanding Sycophancy in Language Modelscited by 1,040
  7. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  8. 2025AlphaEvolve: A coding agent for scientific and algorithmic discoverycited by 867
  9. 2019Fast Transformer Decoding: One Write-Head is All You Needcited by 717
  10. 2025Accelerating scientific discovery with Co-Scientistcited by 401
  11. 2023HaluEval: A Large-Scale Hallucination Evaluation Benchmark for Large Language Modelscited by 341
  12. 2024KTO: Model Alignment as Prospect Theoretic Optimizationcited by 264
  13. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  14. 2023Large Language Models as Analogical Reasonerscited by 107
  15. 2024LogicBench: Towards Systematic Evaluation of Logical Reasoning Ability of Large Language Modelscited by 68
  16. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 53
  17. 2024Multi-LogiEval: Towards Evaluating Multi-Step Logical Reasoning Ability of Large Language Modelscited by 39
  18. 2025MME-Reasoning: A Comprehensive Benchmark for Logical Reasoning in MLLMscited by 33
  19. 2024Code Comprehension then Auditing for Unsupervised LLM Evaluationcited by 32
  20. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  21. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  22. 2024Towards Understanding Systems Trade-offs in Retrieval-Augmented Generation Model Inferencecited by 15
  23. 2023Back to Basics: A Simple Recipe for Improving Out-of-Domain Retrieval in Dense Encoderscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Keep, Customize, or Exit: Default Design and Token Pricing in LLM Reasoning Services
  2. 2025An Empirical Study of LLM Reasoning Ability Under Strict Output Length Constraint
  3. 2026ReFlect: An Effective Harness System for Complex Long-Horizon LLM Reasoning
  4. 2025Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs
  5. 2024Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategies
  6. 2024Token-Budget-Aware LLM Reasoning
  7. 2025Thinking Short and Right Over Thinking Long: Serving LLM Reasoning Efficiently and Accurately
  8. 2025Intra-request branch orchestration for efficient LLM reasoning