CS Paper Radar

Protocol Compression Changes Which Party Pays: Bilateral Cost in Cross-Organization LLM Agent Communication

Janghoon Lee

cs.CL ·submitted 2026-09-05 14:54 UTC · v1

Abstract

Agents that talk across organizations exchange long messages billed by the token. A shorter notation therefore looks like a saving that costs nothing but an agreement to use it. Recent work reports the saving is conditional. Compressed notation can instead raise total tokens by 8% to 11% over a JSON baseline, when parsing failures force extra model calls. That is measured for one payer. Between two organizations neither side can install a decoder at the other end, and each pays under its own tokenizer, price, and cache state. We measure both sides. A preregistered token-level study covered 198 content-matched item pairs across six vendors, for 2,376 native-usage cells. We then overlay an English baseline, runtime schema negotiation followed by compression, and injected-schema compression on a two-party procurement bargain with an exactly enumerated feasible set. The overlay covers 1,053 completed dialogues of a 1,215-cell grid across 3 model pairs, plus a 405-dialogue rerun of the negotiated condition. Compression amplifies cross-vendor cost dispersion by a factor of 1.078, with a 95% CI of [1.066, 1.091], and two vendor pairs reverse which endpoint is cheaper. Runtime negotiation succeeds as a protocol and fails as a bargain. The parties agree a schema in 121 of 135 headline dialogues, none of them the schema we would have supplied. They settle the task in only 9 of those dialogues, and they reach impasse in 106 of them. The negotiated sessions average 10.8 turns against 17.6, and cost 52% of the English total because sessions end sooner, not because the handshake is repaid. Break-even horizons run from 20 to 70 turns, the low end only under the conditional accounting, and all of them lie above every observed English session. On one cross-vendor pair both parties keep about half their cost. On the other the receiving party pays more at a high cache-hit rate.

Comment
30 pages, 3 figures, 27 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond Token Savings: A Systematic Study of Context Compression in LLM Agents

cs.LG cs.AI ·2026-09-26 ·Ritul Satish, Prasoon Sinha, Akiho Kawada, Neeraja J. Yadwadkar
highly cited similarity 0.66
Abstract

As LLM agents tackle longer tasks, they increasingly compress growing histories of reasoning, actions, and tool outputs. Compression can reduce token use, but it also changes the information available for later decisions. Existing agentic harnesses bundle decisions about what to compress, when to compress, and how much to remove into fixed policies. A systematic characterization is needed to disentangle these decisions and reveal how each affects task success and execution cost. We systematically vary these decisions across three open-weight models on SWE-bench Verified and Terminal-Bench 1.0. Across nearly 35,000 agent runs, we measure task success, token use, end-to-end latency, and estimated cost. We find that fewer tokens need not mean faster or cheaper execution: on Terminal-Bench with Qwen, policies using roughly one-third as many tokens can take 20-80% longer than the uncompressed agent. Policies with similar overall success can solve different tasks, while the same policy can perform quite differently across models. Our results motivate evaluating compression by its effects on agent execution and tailoring policies to the task, model, and workload.

0.41

An Empirical Cost Attribution of Context-Compression Gateways in Multi-Turn Coding Agents

cs.CL cs.PFcs.SE ·2026-08-19 ·Luzhuo Chen, Jiayu Shi
benchmarkhot direction similarity 0.65
Abstract · 10 pages, 1 figure, 4 tables

Context compression is widely proposed as a way to cut the token bill of LLM coding agents, and public benchmarks report that aggressive compression preserves task-solving quality. These two facts do not imply the third one commonly assumed: that compressing file reads saves money in a real multi-turn agent. We instrument a production compression gateway (Paritok) between coding agents (Claude Code, Codex) and frontier LLMs (Claude Sonnet, GPT-5), and decompose the token bill of real sessions into three independent levers: tool-schema filtering, content compression of file reads and tool output, and history summarization. Measured in isolation under controlled A/B runs, the three save at fundamentally different rates. Tool-schema filtering removes a fixed block every turn, roughly 21K-57K tokens on a typical turn; it is linear in the turn count N and the only unambiguously and reproducibly positive lever. Content compression saves only about 2% of the cache-priced prefix per turn, but compressed reads accumulate in history and are re-sent on every later turn, so its cumulative saving grows quadratically, about 3350*N^2 tokens (measured), overtaking the fixed tool-filter saving within roughly 6 turns until the context window caps it. A non-destructive gateway lets the agent pull original bytes back on demand; each recall re-sends exactly the one segment just compressed away, so its cost is fixed and bounded rather than a multiplicative blowup, and heavy recall spends the accumulated saving back one segment at a time. Finally, a strong single-shot compression benchmark - 86.5% of SWE-bench quality retained at a 25.7% compression rate, achieved by the model this gateway deploys (Paritok-4B, reported separately) - is orthogonal to multi-turn agent cost and must not be cited as a cost-saving argument. We distill the results into an actionable recipe for where token-saving effort pays off.

0.39

Total Cost of Agency: Exact Attribution of Memory Injection Cost in Multi-Agent LLM Workflows

cs.AI cs.CLcs.MAcs.PF ·2026-09-20 ·Vivek Kumar Singh, Preeti Priyam, Gautam Bhowmick
benchmarkcode/data similarity 0.63
Abstract · 8 pages, 3 figures, 6 tables. Code, data, and evaluation harness in github: https://github.com/vsingh45/tca-compiler

Every node in a multi-agent large language model (LLM) workflow retrieves context from memory and injects it into its prompt, where those injected tokens are billed as input tokens at the same per-token price as the system prompt and the user query. Production observability tools report total token cost but do not separate the tokens a node generates from the tokens it is handed, so this component of the bill is invisible to the teams paying it. We introduce the Total Cost of Agency (TCA), a decomposition of multi-agent workflow cost into base prompt, inference, memory injection, miss penalty and context-accumulation components, and an exact attribution method: a two-pass, non-billable token count that measures injected tokens directly rather than estimating them from word-count proxies. On a 200-task enterprise benchmark executed against real model APIs, memory injection accounts for 13.6 percent of the variable cost a compile-time optimizer can act on, about 12 percent of the full billed cost, and its share rises from a structural zero at workflow depth one to 27.6 percent at depth six. Injected tokens grow linearly with depth over the measured range (R^2 = 0.9974, depths two through six); a quadratic fit yields a negative leading coefficient, so the data do not exhibit convex growth at these depths. We show the component is controllable at fixed model tier: reducing the retrieval window capacity from 32 to 2 entries lowers injected tokens by 28.7 percent with an accuracy change within seed-level variation. We report in full that our graph-rewriting transforms are approximately cost-neutral in isolation, that two of the five decomposition terms are zero by construction in this harness, and that total workflow cost is dominated by model tier assignment, which we hold fixed and treat as prior work. Prompt caching is not evaluated; all figures are for the uncached case.

0.43

What the Middleman Delivers: Answer Behavior, Tool Permissions, and Billed Usage in LLM API Relays

cs.SE cs.AI ·2026-11-05 ·Xiaodong Wu, Zhimin Zhao, Qi Li, Chaklam Cheong, Xiangman Li +1 more
similarity 0.61
Abstract

Third-party application programming interface (API) relays offer access to large language models (LLMs), often at lower prices. Users depend on these services for model quality, instruction compliance, and accurate billing. However, existing studies leave unclear whether relays meet these expectations together. We test 20 relays offering GPT-6 Astra and Claude Opus 5. First, we compare answers to knowledge questions with batch-matched official responses. In our first-round sample, the analysis flags 7/10 low-price and 2/10 same- or higher-price relays for behavioral differences. On retesting 35 pairs, seven gain or lose a flag under the original rules, and six under matched correction families. Because answer comparisons cannot reveal every delivery problem, we examine returned content and tool permissions. No injection is confirmed in 3,332 screened responses to a fixed, non-adversarial code and setup workload, yet four relays return tool calls despite instructions disabling them in the first round. Finally, to connect reported usage to actual costs, we compare input-token counts with official references and check balances. For identical requests, five relays report 4,200 to 60,000 more input tokens than the official API. Where balances are available (six services), charges follow reported usage at listed prices, including extra reported input tokens at one service. Our study shows that advertised models and prices are insufficient to judge relay reliability. It identifies unexplained billed token quantities and tool-permission violations as risks and shows why service evaluations need repeated measurements.

0.16

Token Counts Are Not Model Lineage: A Frozen-Threshold Holdout Study of Black-Box LLM API Fingerprinting

cs.CL ·2026-08-30 ·Bo Chen
similarity 0.60
Abstract · 10 pages, 2 figures

Black-box model attribution is increasingly relevant when large language models (LLMs) are served through relay and reseller APIs. A tempting low-cost signal is the prompt-token count returned by an OpenAI-compatible endpoint: two models that share a tokenizer and chat template may produce the same count sequence up to a fixed offset. Yet the validity of this signal for broader \emph{model-family} attribution has received little direct holdout testing. We conduct a frozen-threshold study over 24 labeled endpoint pairs, split evenly into a development set and an untouched holdout set, with three temporal repeats and 30 controlled texts per pair. We introduce a validity-gated result contract that distinguishes an observed dissimilarity from an uninformative measurement caused by missing usage data, rate limits, or endpoint policy. The resulting shift-invariant exact-match score perfectly separates the 12 development pairs, yielding a frozen threshold of 0.725. On holdout, however, only 6 of 12 pairs are eligible under the pre-specified three-repeat rule. Among eligible pairs, balanced accuracy is 0.75, sensitivity is 0.50 (95\% Wilson interval 0.15--0.85), and specificity is 1.00 (0.342--1.00). Two same-family pairs---Qwen 3.8 and DeepSeek V4 variants---fall below the frozen threshold. Across 4,320 formal API calls, every log is replayable, while holdout contains 189 non-200 responses and 157 successful responses without prompt-token usage. The study therefore validates token-count consistency as a fingerprint of a shared \emph{tokenization stack}, but rejects its use as a standalone necessary test for model-family lineage.

0.23

Learning the Cost of Reliable Inference

cs.AI cs.GTcs.LG ·2026-09-23 ·Dimitrios Rontogiannis, Ander Artola Velasco, Manuel Gomez Rodriguez
similarity 0.60
Abstract

Benchmarking and routing platforms increasingly act as intermediaries connecting large language model providers with end-users. However, providers on these platforms typically use a fixed price per token, preventing users from achieving the most competitive price for their tasks. In this work, we design a procurement platform where token prices for each task are driven by provider competition, enabling users to secure competitive pricing for guaranteed quality levels. To this end, the platform sequentially routes queries via a reverse second-price auction that incentivizes model providers to truthfully bid their best estimate of the average cost to serve a user's query. As it routes queries, the platform learns the quality offered by each provider and progressively routes queries to the most cost-competitive provider among those meeting a desired quality threshold. To validate our design, we conduct experiments with multiple LLMs from the Llama and Qwen families on popular mathematical reasoning and question-answering benchmarks. The results show that the pricing margin of the most cost-competitive provider on our platform varies significantly---from $10\%$ to $71\%$---depending on the task and quality threshold. This suggests a substantial inefficiency in the current fixed-price market, and it demonstrates that our platform may enable users to capture maximum savings whenever competitive market conditions permit.

0.20

Who Pays for Thinking? Billing Hidden Reasoning Tokens in Model Cloud Contracts

cs.GT ·2026-10-26 ·Chao Feng, Burkhard Stiller
similarity 0.59
Abstract

In token-priced language model services, users can see the prompts they submit and the answers they receive, but may also pay for internal reasoning and candidate answers that are not shown in the final response. This paper develops a three-party service model to study how charging for this intermediate computation shapes providers' decisions and social welfare. Users purchase answers from a model firm that pays an execution cloud, with either supplier controlling the computation budget. The model separates user billing from upstream payments and identifies when metered pricing encourages excessive generation, when fixed service prices restrict valuable computation, and how responsibility for execution costs changes these choices. A LiveCodeBench study measures answer quality, latency, token use, and resource consumption across five model deployments, with numerical billing comparisons for the three covered by archived tariffs. At equal average charges on the reference workload, the calibrated comparisons show that billing structure changes both service participation and the computation budgets suppliers select. For accepted services with different budgets, the measured outcomes define the user-value thresholds at which their welfare ranking reverses. Metered pricing yields higher welfare when the additional inference it induces creates net social value, whereas fixed service pricing is preferable when the costs of that computation outweigh its benefits.

0.17

Context Has a Price: Adding and Removing Context for LLM Coding Agents under Prefix Caching

cs.AI ·2026-11-17 ·Zerui Yang, Miaomiao Dong, Quan Xue, Chaorui Zhang, Xuanyu Zheng +7 more
similarity 0.59
Abstract

Coding agents repeatedly send their conversation history to a language model. Adding useful code may reduce search, while removing old tool outputs may shorten later prompts. But do these changes reduce the cost of solving a task? We study this as a measurement problem in more than 20,000 runs of open models on SWE-bench Verified, SWE-bench and Loc-Bench. We account separately for uncached input, cached input and output tokens. Three findings emerge. First, in our main evidence-package experiments, retrieved code reduces read and search commands by 18--34%, but increases cost by 33--42% when cached input costs one tenth of uncached input, without a measurable improvement in resolution. Second, removing old observations can either save money or increase cost: the same approach saves 19--36% without a cache discount but increases cost by 38--116% with a tenth-price cache. Third, shorter prompts do not guarantee cheaper runs because agents may respond by taking more steps. We also find that concurrent experiments can share cached prefixes and distort cost comparisons. These results show why context-management methods should be evaluated using both token prices and the agent's subsequent behavior.

0.24