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

Jinan Zhou, Rajat Ghosh, Vaishnavi Bhargava, Debojyoti Dutta, Aryan Singhal · 2025

Read BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning by Jinan Zhou, Rajat Ghosh, Vaishnavi Bhargava, Debojyoti Dutta, Aryan Singhal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-23170.txt.

Introduction

Jinan Zhou and co-authors ask whether a language model service can be cheap, truthful, and smart at once, in a short 2025 paper. The three goals are a tight cost budget for each answer, facts that hold up, and strong reasoning. The authors claim no model can top all three at the same time. They state that claim as a proved result named the BAR result. Builders must pick which goals to favor, since gains in one force losses in another.

Catalog record

CREATORJinan Zhou, Rajat Ghosh, Vaishnavi Bhargava, Debojyoti Dutta, Aryan Singhal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-23170

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

BAR Conjecture: the Feasibility of Inference Budget-Constrained LLM Services with Authenticity and Reasoning Jinan Zhou, Rajat Ghosh, Vaishnavi Bhargava, Debojyoti Dutta, Aryan Singhal 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. 1 Introduction Large language models (LLMs) with the Transformer architecture ( Vaswani et al. 2017 ) are pre-trained with a massive number of tokens to be auto-regressive next token predictors, \prod_{t=1}^{T}P(x_{t}\mid x_{<t}) . An LLM parameter space, \theta , is split in the following way: \theta:(\theta_{\text{PE}},\theta_{\text{TE}},\{\theta^{(l)}_{\text{ATTN}},\theta^{(l)}_{\text{FF}}\}_{l=0}^{L-1},\theta_{\text{OUTPUT}}) . LLMs learn instruction-following during post-training phase using RL-based techniques such as RLHF ( Ouyang et al. 2022 ) , GRPO ( DeepSeek-AI et al. 2025 ) ; preference optimization techniques such as DPO ( Rafailov et al. 2024 ) , KTO ( Ethayarajh et al. 2024 ) ; and supervised techniques such as LoRA ( Hu et al. 2021 ) . The instruction-following, \prod_{t=1}^{T}P(y_{t}\mid y_{<t},x;\theta) , means the model, \theta , learning to steer its generation trajectories \prod_{t=1}^{T}P(y_{t}\mid y_{<t}) based on the instruction prompt, x . Two key benchmarking attributes for a large language model (LLM) are: first, authenticity or faithfulness — its ability to remain grounded in factual information ( Lin et al. 2022 ; Yang et al. 2018 ) , avoid hallucination ( Li et al. 2023a ; Joshi et al. 2017 ) , and resist sycophancy ( Sharma et al. 2025 ) ; second, reasoning — its capability to perform logical tasks such as mathematical reasoning ( Cobbe et al. 2021 ; et al. 2021 ; et al. 2025 ; et al. 2024a ; et al. 2024c ; et al. 2024b ) , logical reasoning ( Wang et al. 2024c ; Yao et al. 2024 ; Wang et al. 2024b ) , commonsense reasoning ( Talmor et al. 2019 ) , STEM question answering ( Rein et al. 2023 ) , scientific research ( Gottweis et al. 2025 ) , cross-domain problem solving ( Wang et al. 2024a ) , and coding ( Patel et al. 2024 ; Zheng et al. 2023 ; Gauthier 2024 ; Li et al. 2023b ; Novikov et al. 2025 ) . While authenticity and reasoning are qualitative measures evaluating the capabilities of LLMs, inference overhead is a budget metric that measures the operational cost of deploying LLMs. Inference for large language models (LLMs) is primarily a memory-bound process due to several factors: these models typically contain billions or even trillions of parameters, requiring constant memory accesses during inference ( Brown et al. 2020 ; Chowdhery et al. 2022 ) . The arithmetic operations per memory access are relatively simple and sparse, causing inference performance to become constrained primarily by memory bandwidth rather than compute throughput ( Pope & Gray 2022 ; Dao et al. 2022 ) . Additionally, transformer-based LLMs frequently access attention-related caches (KV-caches), increasing memory traffic significantly ( Vaswani et al. 2017 ; Shazeer 2019 ) . Large model sizes often approach or exceed GPU memory capacity, necessitating frequent memory transfers or sophisticated memory management strategies ( Kwon et al. 2023 ) , further exacerbating memory bottlenecks ( Rajbhandari et al. 2020 ; Shoeybi et al. 2019 ) . Consequently, memory operations dominate, making inference predominantly memory-bound. 1.1 Empirical Observation on LLM App Design Trade-offs We have empirically observed that, for any given LLM application, satisfying all three key design criteria—budget, authenticity, and reasoning—is practically infeasible. Typically, only two of these criteria can be simultaneously met, leading to inherent trade-offs. Below we discuss these trade-offs explicitly: • Budget vs. Authenticity: Enhancing authenticity often necessitates retrieval-augmented generation increasing latency through additional steps such as document retrieval and reranking. Techniques like model ensembles or chain-of-verification further extend latency due to multiple inference steps. Consequently, many real-time applications (e.g., voice assistants) choose to forgo retrieval augmentation, accepting a higher risk of hallucinations to maintain budget constraints. • Authenticity vs. Reasoning: Improving reasoning capabilities frequently exacerbates the risk of hallucinations, especially when models attempt inference beyond their training data. Methods such as chain-of-thought and zero-shot reasoning amplify rationalized hallucinations if models lack sufficient grounding in specific domains. For instance, GPT-4 can accurately follow logical steps to solve math problems but may hallucinate incorrect final answers if grounding in units or boundary conditions is missing. • Reasoning vs. Budget: Achieving complex reasoning typically requires additional computational resources, such as multi-hop retrieval, deeper context windows, and frameworks like Chain-of-Thought ( Wei et al. 2022 ) prompting or scratchpad reasoning ( Nye et al. 2021b ) . Advanced models (e.g., GPT-4-Turbo, Claude 3 Opus, Gemini 2.5) often employ longer contexts or iterative inference strategies, directly increasing latency and computational overhead. For example, frameworks such as Tree-of-Thoughts ( Yao et al. 2023b ) , ReAct ( Yao et al. 2023c ) , Least-to-Most prompting ( Zhou et al. 2022 ) , Self-Consistency ( Wang et al. 2022 ) , and analogical reasoning ( Yao et al. 2023a ) explicitly trade increased latency for improved reasoning performance. 1.2 Research Question The key research question explored in this paper is whether we can design an LLM app that can simultaneously satisfy a fixed inference budget, concurrently maintaining both authenticity and reasoning. 2 Methodology 2.1 Preliminaries Let an LLM be a stochastic algorithm M with parameters \theta\in\Theta . \mathcal{L}_{\mathrm{budget}}(\theta) , \mathcal{L}_{\mathrm{auth}}(\theta) , and \mathcal{L}_{\mathrm{reason}}(\theta) denote loss functions for inference budget , authenticity , and reasoning , respectively. The inference budget is measured in the end-to-end wall‑clock time and is the sum of compute latency (forward passes and intermediate decoding steps) and retrieval latency (e.g. external API or vector‐DB look‑ups). Premise A1 (Reasoning needs inference-time budget). Given input length n , it have been shown that constant-depth transformers with finite precision poly(n) embedding size can only solve problems in TC^{0} without CoT Merrill et al. 2022 ; Strobl 2023 ; Merrill & Sabharwal 2025 . CoT and other inference-time intermediate steps enhance reasoning by forcing the model to emit an explicit sequence of intermediate tokens that decomposes the original problem; these “scratch‑pad” tokens effectively deepen the computation, letting later self‑attention layers attend to and refine partial conclusions, which empirically improves multi‑step logical and arithmetic accuracy without modifying model weights ( Li et al. 2024 ; Nye et al. 2021a ) . For a family of length‑parameterised reasoning tasks \{T_{n}\}_{n\in\mathbb{N}} (e.g. Parity, Multiplication), any transformer solving T_{n} with \mathcal{L}_{\mathrm{reason}}\leq\varepsilon_{r} requires at least \Omega(n) chain‑of‑thought (CoT) tokens ( scratchpad steps ) ( Amiri et al. 2025 ) . Premise A2 (Factuality needs support from retrieval and tool-calling). Achieving \mathcal{L}_{\text{auth}}\leq\varepsilon_{h} on non‑synthetic queries typically requires at least k\!\geq\!1 external retrieval or verification calls—e.g., ANN search over a vector store, web‑API look‑ups, or fact‑checking tools—each incurring a fixed latency of at least \rho>0 . Empirical studies show that retrieval dominates inference latency: it constitutes roughly 41\% of end‑to‑end wall‑time in a production RAG pipeline ( Shen et al. 2024 ) , accounts for 30 – 60\% of total energy consumption during inference ( Iskander et al. 2023 ) , and adds 30 – 50 ms per query

Read the complete text