{"id":"e9134bf4-d317-4d58-b64e-9867605f930d","arxiv_id":"2502.04358","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proposes that asymptotic analysis with LLM primitives, treating one forward pass as the cost unit, is the right framework for scaling multi-agent LLM systems.","lead":"Scaling systems of LLM agents, the paper argues, needs a new kind of cost analysis that counts each LLM forward pass as the atomic unit of work. The authors illustrate how such asymptotic analysis can expose large efficiency gaps between intuitive agent designs and carefully decomposed ones.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Oracle decomposition assumption is load-bearing; the headline Θ(2^k k) speed-up depends on free, exact block boundaries/specifications that Section 5.4 leaves as open.","rationale":"The reader's weakest_assumption identifies the same point I would stress: the costless, perfect decomposition (oracle) is doing the heavy lifting in two of the three examples. I agree. I do not see a more fundamental flaw: the cost model in Definition 2.2 is internally consistent for compute-style per-token costs, and the paper is explicit that error rates (§5.2) and automatic decomposition costs (§5.4) are open. Those caveats do not invalidate the position—they are exactly the territory AALPs should grow into—but they mean the current examples are existence proofs under strong assumptions, not evidence that such decompositions are achievable. The proposed test would supply the missing empirical evidence: if the Θ(2^k k) advantage survives the addition of an LLM-based boundary locator and realistic error rates, the oracle assumption is benign; if not, the paper's headline example is an artifact. Either way, the verdict of CONDITIONAL remains appropriate: accept the research agenda but require this validation before taking the efficiency claims at face value.","tokens_in":17704,"tokens_out":11989,"duration_ms":116249,"concrete_test":"Benchmark the evolutionary example on an ONEMAX-style problem with k text blocks. Implement the local-mutation variant exactly as in §3.3.2, except replace the 'programmatic way of determining block boundaries' with an LLM-based segmenter that reads the whole solution and outputs per-block boundaries. Also implement the global variant of §3.3.1. For k ∈ {4, 8, 16, 32} (with l fixed so n = kl), measure total LLM token cost (segmenter + mutator + any fitness-related calls) to reach f(x) = k, over multiple runs. If the empirical ratio cost_local / cost_global does not show exponential decay consistent with Θ(2^k k), then the free-oracle assumption, not AALPs, is driving the headline separation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central demonstration that intuitive agent designs miss massive asymptotic separations rests on the availability of free, exact decompositions. Definition 2.4 (oracle decomposition) permits an 'assumed non-LLM operation' with no cost, and the examples use it twice: debugging assumes every function has a 'completely correct, precise and constant size specification' (§3.2.2), and evolution assumes a programmatic way to locate block boundaries (§3.3.2). If these decompositions are unavailable, approximate, or themselves require LLM calls (as §5.4 anticipates), the separations shrink or vanish. In the debugging case, an imperfect specification forces the QA engineer to consider cross-function context, reintroducing Θ(n) dependence and replacing the Θ(b k^2) improvement with something polynomial of lower degree or even Θ(1). In the evolution case, an LLM-based boundary locator costs Θ(m n) per scan; if its output is noisy, local mutations may cross blocks, degrading the expected hitting time from Θ(k) to something closer to Θ(2^k). The paper flags these issues in §5.4 but does not analyze whether the framework's headline results survive their inclusion. Since the strongest claim explicitly cites the Θ(2^k k) improvement, the free-oracle assumption is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This position paper argues that scaling LLM-based agentic systems requires asymptotic analysis that treats a single LLM forward pass as the atomic unit of cost, an abstraction the authors call the LLM primitive. The paper defines a minimal framework (LLM primitives, capabilities sets, oracle decomposition), then presents three worked examples—k-task routing, iterative code debugging, and evolutionary optimization—in which a carefully decomposed agent design is compared with a more intuitive, role-based design. The claimed gains are Θ(k), Θ(bk²), and Θ(2^k·k) respectively. The paper also discusses alternative views (e.g., that people would do this anyway, or that direct cost optimization suffices) and lists open research directions, including automatic decomposition, stochasticity, error correction, and parallelization.","tokens_in":17952,"tokens_out":9523,"duration_ms":94531,"significance":"If the position is accepted, the paper supplies a useful and much-needed notation for reasoning about the orchestration-level efficiency of LLM-agent systems, independent of any particular model implementation. The worked examples are transparent, the assumptions are mostly stated explicitly, and the arithmetic is straightforward to verify; this makes the paper a good starting point for a formal theory of LLM-agent algorithms. The paper is appropriately modest in presenting itself as a call to action rather than a complete framework. Its main limitation—that the headline separations depend on oracle decompositions and on reliability assumptions—is real, but it is explicitly acknowledged in Sections 5.1, 5.2, and 5.4, and for a position paper this is an acceptable research-direction rather than a fatal flaw.","major_comments":[],"minor_comments":[{"comment":"The definition says a single application of M to a string of length n costs mn, but the examples in Section 3 count cost as m·n² when the model produces n output tokens (e.g., Equations (5), (7), and (12)). Please clarify that the primitive is a single forward pass per output token, with cost m times the current context length, or define a separate cost rule for generation, so that the definitions match the example derivations.","section":"Definition 2.2"},{"comment":"The improvement values in Table 1, especially Θ(2^k·k), are conditional on the oracle-decomposition assumption and on zero cost for decomposition, but Table 1 presents them without qualification. Please add an explicit footnote or phrase in the table caption and in the conclusion noting that these gains assume the oracle-decomposition setting described in Sections 2 and 3, and that LLM-based decomposition costs are not yet incorporated into the examples.","section":"Table 1 / Section 3.3.3"},{"comment":"The assumption that 'the required size of the LLM scales linearly with the number of required capabilities' is presented in the text as following from neural scaling laws, but this is a modeling choice rather than a standard scaling-law statement. Please mark it explicitly as an assumption at the point of use, in addition to the later mention in Section 5.1.","section":"Section 3.1.3, Eq. (3)"},{"comment":"The notation m_d(in + (in + 1) + ... + (in + n)) is ambiguous; it should be clear that the cost of generating the n output tokens accumulates the growing context length at each output-token step, and the line 'm_d(in + (in + 1) + ... + (in + n)) = Θ(m_d·i·n²)' would benefit from an explicit intermediate expression.","section":"Section 3.2.1, Eq. (5)"},{"comment":"The statement that the expected number of applications of the global mutator is 2^k assumes that each of the k blocks is sampled independently with probability 1/2 of being correct on every application, and that the initial state does not affect the expected hitting time. Please state this independence assumption explicitly, since the later local-mutation comparison depends on it.","section":"Section 3.3.1"},{"comment":"The discussion of machine sentience and suffering is speculative and tangential to the technical position of the paper. Consider shortening it to a brief note or moving it to the impact statement, so that the main argument about asymptotic analysis remains focused.","section":"Section 5.7"},{"comment":"There is a typo: 'aymptotic' should be 'asymptotic'.","section":"Section 4, Alternative View 2"}],"recommendation":"minor_revision","confidential_remarks":"This is a position paper, so I evaluated it on the quality and transparency of its argument rather than on empirical validation or formal theorem-proving. The oracle-decomposition concern raised by the stress-test is valid as a limitation, but the paper already acknowledges it in multiple places and treats it as an open research direction; I therefore do not consider it a blocking issue. I have no concerns about overlap or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: This is a clear, honest position paper, but its central claim—that AALPs is required—is stronger than the evidence supports. The framework itself is not new: the authors cite Chen et al. (2024) as the first formal treatment. What this paper adds is a plain-language argument, three simple worked examples, and a research agenda.\n\nThe examples are simple arithmetic, but they serve a real purpose. They show how counting LLM forward passes as the cost unit separates orchestration efficiency from model internals, and the Θ(2^k k) separation in the evolutionary example is genuinely striking. The paper is also unusually candid. It flags its own assumptions—the oracle decomposition, linear cost, no stochastic errors—and lists them as open directions in Section 5. That honesty is valuable and makes the paper a good discussion piece.\n\nThe soft spot is exactly where the stress-test note lands. The headline separations in Sections 3.2 and 3.3 depend on free, exact decompositions: perfect function specifications and programmatic block boundaries. Section 5.4 acknowledges that automatic decomposition will likely require LLM calls whose cost must be counted, but the paper never re-runs its examples with that cost included. If decomposition is imperfect or itself costs Θ(mn) per scan, the Θ(bk²) and Θ(2^k k) improvements shrink or vanish. For a position paper, flagging these assumptions is acceptable, but it means 'required' is not supported. The argument would be on much firmer ground if framed as 'promising and worth developing.'\n\nThe capability-scaling rule in Section 3.1 (mg = Θ(k·ms)) is also just assumed, not argued from data. That is fine as an illustration, but it should be labeled as an assumption. The linear input-cost model is similarly approximate, and the authors do note this.\n\nWho is this for? Researchers designing multi-agent LLM systems and anyone thinking about a complexity theory for LLM-based algorithms. It deserves a serious referee—I would send it out. The main revision I would ask for is to soften the central claim and add a short discussion of how the examples change when decomposition costs are included. With that change, the paper is a solid call to action.","headline":"A clear, honest position paper on LLM-agent complexity analysis, but the 'required' claim is stronger than the evidence and the headline gains depend on free, exact decompositions that the paper itself leaves open.","tokens_in":18444,"tokens_out":3567,"would_cite":false,"duration_ms":30919,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Counting LLM forward passes as the atomic cost unit exposes asymptotic separations in multi-agent systems that role-based design misses.","keywords":["LLM agents","asymptotic analysis","LLM primitives","oracle decomposition","multi-agent orchestration","problem decomposition","evolutionary optimization","agent scaling"],"falsifier":"Run the evolutionary example with real LLMs on a family of block-fitness functions where each of $k$ blocks is either correct or incorrect, count forward passes for whole-string mutation versus per-block mutation with known boundaries, and check whether the measured ratio of total calls grows roughly as $2^k k$ as $k$ increases; if it does not, the paper's central separation fails to appear in practice.","tokens_in":17458,"feed_emoji":"🧩","tokens_out":11022,"duration_ms":91552,"temperature":0.7,"pith_summary":"The paper's position is that scaling LLM-based agentic systems to large, many-task workloads will require asymptotic analysis in which the LLM forward pass is the atomic unit of cost. It introduces a minimal framework built on language-based algorithms, capabilities sets, and oracle decompositions, then uses three worked examples to argue that this analysis exposes efficiency separations that intuitive, human-team-inspired designs miss. If the position holds, multi-agent system builders should invest in complexity analysis of orchestration rather than treating role assignment as the main design decision, and the largest gains should come from decomposing problems into independently solvable, precisely specified pieces.","feed_headline":"Counting LLM calls exposes exponential agent speed-ups","feed_subtitle":"A position paper argues that role-based agent design misses large asymptotic wins from problem decomposition.","key_machinery":"The central object is the LLM primitive, a single forward pass of a model of size $m$ over an input of length $n$, counted as cost $mn$; each model also carries a capabilities set describing what it can reliably do. The frameworks around it are the language-based algorithm, an algorithm whose steps include LLM calls, and the oracle decomposition, an assumed zero-cost, non-LLM operation that splits a problem in a specified way. The argument's engine is the asymptotic comparison of orchestration schemes that differ only in how they route, focus, and decompose LLM calls; the oracle decomposition is what lets a proposed decomposition be turned into a calculable separation.","core_discovery":"On its own terms, the central claim is that asymptotic analysis with LLM primitives (AALPs) is critical to scaling LLM agents, and the evidence is a set of derived cost separations. An LLM primitive costs $mn$ for a model of size $m$ applied to a string of length $n$, and counting these primitives isolates orchestration efficiency from any particular model's internals. In the three examples, the optimized scheme beats the intuitive one by $\\Theta(k)$ for $k$-task routing, by $\\Theta(bk^2)$ for debugging a $k$-function codebase with $b$ bugs, and by $\\Theta(2^k k)$ for evolutionary optimization on a block-structured fitness landscape. The largest separation is presented as evidence that intuitive designs can be extraordinarily far from optimal and as motivation to develop AALPs into a practical engineering tool.","pith_inferences":["One consequence the paper leaves implicit: the oracle-decomposition assumption in Sections 3.2 and 3.3 means all separations are upper bounds on what a free decomposition can buy; counting the LLM calls spent to find and verify decompositions would shrink the gap, so a natural next step is to derive closed-form costs for LLM-based decomposers.","The same accounting extends by analogy to non-text modalities: a compact vision-only model is the asymptotically right engine for high-volume visual subtasks, with multi-modal foundation models reserved for cases that genuinely need them, a direction the paper touches on but does not quantify.","A quantitative falsification target follows from the evolutionary example: if per-block mutation's success probability decays with $k$, the $\\Theta(2^k k)$ separation in expected calls may not hold for real LLMs; an empirical measurement of per-block success as a function of $k$ would test the position's most extreme claim.","The debugging example's assumption of perfect constant-size specifications could be relaxed by letting the specification itself be generated by an LLM; the position would be more robust if the separation persisted after subtracting the cost of generating and checking specifications."],"forward_implications":["Routing increases the value of specialization linearly in the number of tasks: a delegator plus $k$ specialists costs $\\Theta(m_s n)$ versus $\\Theta(k m_s n)$ for a generalist of the same per-task size, so large many-task systems should be built from many small specialists rather than one large model.","For iterative debugging, the analysis says focusing each QA and fixing call on a single function, rather than on the whole accumulating code, yields a speed-up of $\\Theta(bk^2)$ in the dominant term, making extreme decomposition the target design for scaling coding agents.","For evolutionary optimization, local block-wise mutation has expected LLM-primitive cost $\\Theta(m_u k l^2)$ versus $\\Theta(m_u 2^k k^2 l^2)$ for whole-string mutation, a separation of $\\Theta(2^k k)$ that makes block-structured solution representations a primary design choice.","Because the delegator and QA costs are asymptotically small relative to specialists and debuggers, research and development effort on model-size reduction should be concentrated on the agents that are executed most and process the largest inputs.","AALPs lets designers compare orchestration schemes before the required capabilities exist, so insights about decomposition can guide development of future LLMs rather than only analyzing current ones."],"supporting_citations":[{"why":"This citation supplies the prior formal treatment of LLM-based algorithms, including the 'LLM-based algorithm' definition that the authors adopt and extend.","marker":"Chen et al., 2024"},{"why":"This citation provides the scaling-law evidence used to assume that required model size grows with the number of capabilities, which drives the $\\Theta(k)$ routing separation.","marker":"Kaplan et al., 2020"},{"why":"This citation grounds the linear cost model in Definition 2.2 by showing that API pricing scales linearly with input tokens.","marker":"OpenAI, 2025"},{"why":"This citation independently grounds the linear cost model in Definition 2.2 by showing that API pricing scales linearly with input tokens.","marker":"Anthropic, 2025"},{"why":"This citation supplies the $(1+\\lambda)$-EA framework that the evolutionary example instantiates with an LLM mutator.","marker":"Droste et al., 2002"},{"why":"This citation provides the ONEMAX-style fitness function and the probabilistic tools used to compute the expected $2^k$ calls of global mutation.","marker":"Doerr, 2020"},{"why":"This citation justifies ignoring training cost on the grounds that long-run inference cost dominates, a premise for counting forward passes as the primitive.","marker":"Sardana et al., 2024"},{"why":"This citation describes AutoGen-style multi-agent conversation, the accumulation-of-context baseline that the focused debugging analysis is contrasted with.","marker":"Wu et al."},{"why":"This citation represents the anthropomorphic team-role approach to coding agents that the paper uses as the naive baseline in the debugging example.","marker":"Qian et al., 2024"}],"fun_headline_variants":["Asymptotic analysis with LLM calls exposes exponential agent wins","Role-based agent design misses exponential asymptotic gains","LLM primitives expose exponential speed-ups in agent decomposition","Intuitive agent roles can be exponentially far from optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a problem can be split, at no cost, into independent, precisely specified subproblems—as when debugging assumes a completely correct constant-size specification for every function and evolution assumes programmatic block boundaries—so if that decomposition is unreliable or itself needs LLM calls, the promised speed-ups collapse.","fun_headline_variants_meta":{"raw":{"variants":["Asymptotic analysis with LLM calls exposes exponential agent wins","Role-based agent design misses exponential asymptotic gains","LLM primitives expose exponential speed-ups in agent decomposition","Intuitive agent roles can be exponentially far from optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000754,"raw_usage":{"total_tokens":3348,"prompt_tokens":931,"completion_tokens":2417,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2353}},"tokens_in":547,"tokens_out":2417,"duration_ms":17205,"temperature":1.0,"reasoning_tokens":2353,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:22:35.192243+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the evolutionary example with real LLMs on a family of block-fitness functions where each of $k$ blocks is either correct or incorrect, count forward passes for whole-string mutation versus per-block mutation with known boundaries, and check whether the measured ratio of total calls grows roughly as $2^k k$ as $k$ increases; if it does not, the paper's central separation fails to appear in practice.","supporting_citations":[{"cited_title":"OpenAI API Pricing , 2025","cited_arxiv_id":null,"evidence_quote":"This citation grounds the linear cost model in Definition 2.2 by showing that API pricing scales linearly with input tokens."},{"cited_title":"On the analysis of the (1+ 1) evolutionary algorithm","cited_arxiv_id":null,"evidence_quote":"This citation supplies the $(1+\\lambda)$-EA framework that the evolutionary example instantiates with an LLM mutator."},{"cited_title":"Beyond chinchilla-optimal: Accounting for inference in language model scaling laws","cited_arxiv_id":null,"evidence_quote":"This citation justifies ignoring training cost on the grounds that long-run inference cost dominates, a premise for counting forward passes as the primitive."},{"cited_title":"Chatdev: Communicative agents for software development","cited_arxiv_id":null,"evidence_quote":"This citation represents the anthropomorphic team-role approach to coding agents that the paper uses as the naive baseline in the debugging example."}],"review_version":1}