acceptodds
Under review as a conference paper at ICLR 2027

CADOC: Cache-Aware Dynamic Object Context for Long-Horizon Agents

Abstract

For a long-horizon agent, context is the bottleneck: the history is resent with every request, the window caps task length, and reasoning degrades as the history grows. Replacing structured objects with compact retrieval Cards shortens the prompt and keeps the exact originals retrievable, but editing the history can break prefix-cache reuse, and prior recoverable methods time their edits by forecasts of future reuse or by preset intervals. We propose CADOC (Cache-Aware Dynamic Object Context), an online algorithm that replaces structured objects with compact Cards while preserving exact, on-demand retrieval of their original contents. CADOC schedules replacements in batches by balancing accumulated waiting cost against shared cache-reconstruction cost. Its scheduling rule follows from an economic order quantity trade-off, recovers the optimal integer batch under stationary assumptions. Across evaluation, CADOC consistently achieves the lowest aggregate input cost among the compared configurations, which reduces input cost by approximately 40% on average while maintaining task performance close to full context. CADOC thus provides a cost-derived approach to compressible context management, demonstrating that efficient compression depends not only on shortening prompts but also on scheduling edits to preserve cache reuse.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
language agent, context management, prompt cache

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_buZ1OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses context management for long-horizon agents and argues that shortening the prompt does not by itself reduce cost, because edits to the history break prefix-cache reuse. It can even raise cost: on an HCE history, immediate replacement removes 55.93% of cumulative input tokens yet increases input cost by 3.67%. The question therefore becomes when to reduce input tokens so that the agent benefits without paying for cache reconstruction. The authors propose CADOC, a scheduler for input-token reduction whose commit rule follows from the economic-order-quantity (EOQ) model of operations research, which gives the timing and condition under which a batch of reductions should be committed. The reduction itself moves structured spans, such as file contents and tool outputs, to a working memory and leaves compact Cards in the prompt, with byte-exact retrieval on demand. Validation consists of frozen-history replays against Immediate, fixed-batch and token-threshold policies, and live runs on Terminal-Bench 2.1, LongMemEval-V2 and SWE-bench Verified. In the live runs, input cost falls by 34.12–47.13% versus full context, and task completion drops by at most two tasks per benchmark.

Critical strengths

The commit rule is derived rather than tuned, and its predictions hold. The EOQ argument gives a closed-form commit condition from observable quantities and also yields a 2-competitive online bound for constant reconstruction cost. The replays behave as the theory predicts: the best fixed batch size shifts across hot-tail settings (b = 2 at h = 2, b = 8 at h = 4, 8, 16), while CADOC adapts without manual adjustment. The rule also recovers a known special case: at w_r = 1, where cached tokens get no discount, CADOC reduces to Immediate, as Eq. 32 shows. I found no prior work that derives commit timing from observed cache cost with a competitive guarantee. This matters because it lets the method carry over to new workloads without per-setting tuning.

The replay experiment is carefully controlled. Model outputs, object versions and Card contents are frozen; only commit timing varies, and every policy sees the same histories. Under this control, CADOC has the lowest input cost in every setting, tying Immediate only where the cache discount vanishes (w_r = 1).

Critical weaknesses

The live evidence has no error bars, so randomness cannot be ruled out as the source of the cost reduction or the completion drop. Table 1 comes from one chain per arm, so the 34.12–47.13% cost reductions and the completion changes (38→36 of 89, 10→10 of 18, 31→29 of 50) have no variance estimate, and LongMemEval-V2 has only 18 tasks. Because FULL and CADOC generate separate stochastic trajectories, the cost difference can also reflect changes in model calls, output lengths, tool use and retries rather than the commit policy alone.

The reported savings are model input-cost savings, not end-to-end agent-system cost. Input tokens are a useful proxy when inference dominates and behavior is comparable, but practitioners benefit from the overall end-to-end cost, which is not measured. For example, Figure 5 shows only cumulative input cost, not end-to-end cost, latency or throughput.

Questions for authors

Could you add variance or error bars to the Table 1 cost reductions (for example, repeated chains or bootstrap over tasks), and report output tokens, tool calls and retries per arm, so that the policy effect can be separated from trajectory variation?

Could you report CADOC's end-to-end monetary cost, wall-clock latency and throughput compared with FULL and Immediate?

3 comments

We thank the reviewer for the positive assessment of the derived commit rule and the controlled replay design. We address both points below.

W1 / Q1: Variance and separating the policy effect from trajectory variation

Repeated chains. To assess run-to-run variation, we repeated the benchmark evaluations using gpt-5.6-terra, with identical task lists and configurations across runs. We conducted 3 runs per arm for Terminal-Bench 2.1 and SWE-bench , and 5 runs per arm for LongMemEval-v2, as the former two benchmarks incur substantially higher evaluation costs. We report the mean and standard deviation of solved tasks across runs.

BenchmarkRuns per armFULL solvedCADOC solvedInput-cost reduction
Terminal-Bench 2.1342.00 ± 6.0839.00 ± 6.0871.14 ± 6.44%
LongMemEval-v2511.00 ± 0.0010.60 ± 0.8976.98 ± 6.55%
SWE-bench333.00 ± 1.0032.33 ± 1.5359.73 ± 7.66%

Difference from the original results. The reruns were conducted approximately four months after the original experiments, using the same task lists, CADOC scheduling configuration, and cost accounting. However, both FULL and CADOC exhibited substantial changes in their execution trajectories, suggesting that changes in the API serving stack or underlying model backend may have contributed to the differences. For example, on LongMemEval, FULL's model requests increased about 42% on average, while its average input length decreased 38% on average. CADOC's requests decreased about 48%, with average input length decreasing about 34%. These changes in both arms suggest that the execution environment may have shifted between evaluations. A concrete example is LongMemEval task 3a7a7880. In the original CADOC run, the agent made 55 model requests before failing. In the five reruns, it averaged only 8.2 requests, but still failed the task. This single task illustrates how changes in execution trajectories can substantially affect measured costs even when task outcomes remain unchanged.

With agent actions held fixed, CADOC still reduces input cost by 49.83% on Terminal-Bench, 46.75% on SWE-bench, and 75.57% on LongMemEval-V2 (Section 6.1, Figure 7).

Per-arm trajectory statistics. As suggested, we report per arm the quantities that could differ between trajectories:

BenchmarkArmModel requestsTool callsRetrieval calls
Terminal-Bench 2.1FULL1,108.00 ± 14.111,214.00 ± 29.100
CADOC773.33 ± 95.30824.00 ± 125.155.00 ± 3.61
LongMemEval-V2FULL137.60 ± 32.2779.00 ± 33.590
CADOC76.00 ± 12.8398.80 ± 34.9512.00 ± 5.70
SWE-benchFULL637.33 ± 57.84984.67 ± 37.000
CADOC590.33 ± 59.34910.67 ± 89.500.33 ± 0.58

Output tokens per arm are reported in the cost table under W2/Q2 below. Agent-level retries, such as re-running a tool or revising a step after an error, are already counted in the model requests and tool calls above; API-level retries mainly reflect the stability of the provider's service rather than the context policy.

W2 / Q2: End-to-end monetary cost, latency, and throughput

We agree that the overall cost is what matters most to practitioners. The table below reports the token usage and billed cost returned by the provider. Billing records cover over 90% of inference requests but are not available for every request.

BenchmarkArmTotal input tokensCache-hit tokensUncached tokensOutput tokensTotal billed cost
Terminal-Bench 2.1FULL / Immediate / CADOC400.158 M / 128.401 M / 107.619 M329.581 M / 92.531 M / 77.576 M70.578 M / 35.870 M / 30.043 M297.773 K / 248.557 K / 203.925 K523.6560 PU / 142.6354 PU / 97.3151 PU
LongMemEval-V2FULL / Immediate / CADOC18.427 M / 2.722 M / 2.217 M12.162 M / 0.611 M / 0.660 M6.265 M / 2.111 M / 1.557 M11.546 K / 15.538 K / 11.247 K30.5180 PU / 5.3648 PU / 4.1495 PU
SWE-bench VerifiedFULL / Immediate / CADOC228.384 M / 72.011 M / 72.946 M192.275 M / 34.255 M / 43.832 M36.110 M / 37.756 M / 29.115 M129.756 K / 112.471 K / 109.142 K296.0961 PU / 99.0102 PU / 87.3930 PU

Latency and throughput. Our primary objective is cost reduction rather than latency or throughput optimization. Moreover, substantial fluctuations in API serving conditions make wall-clock comparisons difficult. Nevertheless, CADOC requires fewer model requests than FULL across all three benchmarks, and fewer tool calls on Terminal-Bench and SWE-bench (Appendix C.2). These reductions suggest that CADOC may also achieve lower latency and higher throughput under stable serving conditions.

We thank the reviewer for the valuable comments and hope that our responses have addressed your concerns.

Thank you for the additional experiments. The repeated runs substantially address my concern about variance: CADOC continues to show large input-cost reductions across all three benchmarks, and the frozen-action replay provides stronger evidence that the reduction comes from the context policy rather than trajectory variation. The provider-billing results also strengthen the practical cost claim, with CADOC costing less than both FULL and Immediate in every benchmark. I will therefore keep my rating at 3 (weak acceptance).

We sincerely thank the reviewer for the recognition and constructive suggestions. We are glad that our responses have addressed your concerns, and we truly appreciate your valuable feedback. We wish you all the best and continued success in your work!

Reviewer_JJraOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CADOC schedules recoverable context edits to reduce input costs for long-horizon agents while accounting for prefix-cache reuse. It replaces structured objects with compact Cards that retain access to the originals, batching replacements by balancing accumulated waiting loss against shared cache-reconstruction cost. Under stationary assumptions, the scheduling rule recovers the optimal integer batch size. Fixed-history replay shows the lowest aggregate input cost among the tested configurations. Across three closed-loop task chains, CADOC reduces input cost by 34.12–47.13% relative to FULL, with task completion remaining close to FULL on these runs.

Critical strengths
  1. The cost decomposition turns the timing of context edits into an explicit scheduling decision. Equation 5 separates the replaceable region, shared reconstruction, and waiting costs. First threshold crossing recovers the optimal integer batch under equal-length, equal-benefit, stable-cache assumptions. This gives the online rule a clear economic interpretation and a precise stationary reference point.

  2. The hot-tail sweep demonstrates practical adaptation without manually tuning the batch size. As HCE's h increases from 2 to 16, the average batch size grows from 1.50 to 5.00. This avoids the reversal where fixed b=2 costs 35.01% more than Full at h=16.

Critical weaknesses
  1. The correspondence of non-trigger rules across replay paths would benefit from clearer reporting. The fixed-history comparisons hold recorded agent behavior constant and already support CADOC's cost advantage. To interpret the contribution of commit timing, please clarify how object eligibility, hot-tail protection, and charging conventions correspond across policies for the same input state. Pending sets and cache frontiers may legitimately differ because of commit history; the current evidence does not establish a comparison error.

  2. Per-task failure diagnosis would improve interpretation of the closed-loop results. Table 1 shows SWE decreasing from 31/50 to 29/50 and Terminal-Bench from 38/89 to 36/89, while LongMemEval's task outcomes are unchanged. This supports a descriptive "close to FULL" characterization on the evaluated chains. Because the arms develop their own trajectories, these net differences do not establish that externalization causes quality degradation. This diagnostic suggestion is not an independent acceptance condition.

Questions for authors
  1. Please briefly explain how object eligibility, protection budgets, and charging conventions correspond across the replay policies. One configuration example or existing object-event record for a shared input state would suffice. Different commit histories need not produce identical pending sets or cache frontiers. This addresses the same reporting clarification as weakness 1 and does not request a new experiment.

  2. For alignable tasks, please report the success/failure cross-tabulation between FULL and CADOC and any observable restoration-related failure patterns. A net loss of two completions does not determine the total number of discordant tasks. Please state the coverage denominator and provide an existing example where FULL succeeds and CADOC fails, if available. The example may leave the cause unresolved; a single trajectory need not establish restoration's causal responsibility.

1 comment

We thank the reviewer for the careful reading of the cost decomposition and the hot-tail sweep, and for the constructive framing of both suggestions. We address them below.

W1 / Q1: Correspondence of non-trigger rules across replay policies

Thank you for this suggestion. In our controlled replay experiments, all policies process identical recorded agent trajectories and share the same object-selection rules, Card representations, and eligibility requirements, including at least one raw exposure before compression. They also use identical protection budgets (h=8h=8, 12,800 tokens), with capacity overrides and emergency compression disabled. Only the compression scheduling rule differs.

Matched object-level example. We track the same object across four policies on a recorded Terminal-Bench trajectory. The following table reports its commit boundary and the cached/uncached input tokens at the shared replay boundary 30.

PolicyCommit boundaryCached tokensUncached tokens
Immediate1421,510200
CADOC3010,08011,630
Fixed-206826,474200
Tokens-327688026,474200

CADOC and Immediate produce identical rendered prompts at boundary 30 but have different cache frontiers due to their earlier commit histories. This illustrates why identical object-selection rules need not produce identical cache states.

Cost accounting. All policies use the same logical-prompt-json-v1 serialization, o200k_base tokenizer, and prefix-cache accounting. Cached tokens RtR_t are determined by the longest common token prefix with the preceding request, while the remaining tokens are counted as uncached NtN_t. Costs follow Equation (1), C=∑t(Nt+0.1Rt)C=\sum_t(N_t+0.1R_t), including Card tokens and cache reconstruction. CADOC's internal WW, GG, and QQ estimates are not charged separately.

The matched object-level example is now included in Appendix B.1 (Table 2).

W2 / Q2: Task-level success/failure cross-tabulation

We agree that, since each arm follows its own trajectory, the net differences in Table 1 do not by themselves indicate that externalization degrades quality. We report the requested diagnosis on our new repeated runs with gpt-5.6-terra (3 runs per arm on Terminal-Bench and SWE-bench, 5 on LongMemEval), where all 89, 50, and 18 tasks can be aligned between FULL and CADOC. A task is counted as succeeded if it is solved in at least one run.

BenchmarkBoth succeedFULL onlyCADOC onlyBoth fail
Terminal-Bench 2.1524231
SWE-bench351212
LongMemEval-V211016

Restoration-related failure patterns. For each FULL-only task, we checked whether the failure involved content replaced by a Card:

PatternCount
Needed content was replaced by a Card and not retrieved0
Content was retrieved but not used correctly0
No involvement of replaced content (e.g., environment error, timeout, reasoning error)5

Example where FULL succeeds and CADOC fails. In Terminal-Bench's count-dataset-tokens task, FULL correctly counted both the DeepSeek reasoning and solution text, returning 79,586 tokens. CADOC instead submitted 63,841, the reasoning-only count, even though its tool output also reported the correct combined total. The relevant counts were still present in uncompressed tool output when CADOC wrote its answer. The observed failure was therefore a field-selection error, with no evidence that compression removed the information needed to answer.

We have included the cross-tabulation, failure patterns, and a representative failure case in Appendix C.3 (Tables 5–6).

We greatly appreciate the reviewer's insightful suggestions and hope that our clarifications and additional analyses have satisfactorily addressed your questions.

Reviewer_tEKUOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces CADOC, a cache-aware online scheduler for reducing the active context of long-horizon agents without permanently discarding structured content. CADOC replaces eligible objects (e.g., file contents, logs, or tool outputs) with compact retrieval Cards while storing the exact originals for on-demand recovery. Its main contribution is a commit-timing rule that balances the cost of carrying raw objects for additional requests against the shared prefix-cache reconstruction cost caused by editing earlier context. Under a stationary model, the rule corresponds to an economic-order-quantity trade-off and recovers an optimal integer batch size; online, it uses observed shortening and cache estimates rather than future-workload forecasts. In fixed-history replays, CADOC has the lowest aggregate input cost among the compared policies across tested settings. In benchmark chains, it reduces input cost by 34.12–47.13% and cumulative input tokens by 44.72–80.60%, while task completion is close to the full-context baseline.

Critical strengths
  1. The paper focuses on a real systems-level issue that simple token-count comparisons can miss. Editing an earlier part of a prompt can invalidate prefix-cache reuse for the suffix. The paper makes a useful distinction between shortening context and reducing actual input cost.
  2. The reversible object representation is practically appealing. Cards shorten the active prompt while retaining byte-exact access to the original payload. This avoids the irreversible information loss associated with lossy summarization, provided that the relevant object can be identified and retrieved when needed.
  3. The scheduling rule has a clear economic interpretation. The trade-off between accumulated waiting cost and shared reconstruction cost is intuitive, and the stationary analysis yields an explicit optimal integer batch condition. The online rule does not require an LLM call or a forecast of future reuse.
  4. The evaluation includes both scheduling replays and complete task chains. Comparisons against immediate replacement, fixed-size batching, and token-threshold policies across multiple hot-tail settings are useful. The sensitivity analysis over cache-read weights also helps show that the scheduling result is not tied to only one accounting parameter.
  5. The end-to-end results show meaningful potential savings. The benchmark-chain results report sizeable input-cost reductions with relatively small observed differences in completion rates, including a case where retrieval events are included in the cost accounting.
Critical weaknesses
  1. The cost model may not accurately capture real serving economics. The reported cost uses a weighted accounting of input tokens and cache reads (with a default cache-read weight of 0.1). Actual costs and latency depend on provider-specific cache behavior, cache-hit granularity, request routing, cache retention, and the implementation of object retrieval. The paper acknowledges that cache-hit effects require measurement under the actual serving configuration, but the headline efficiency claim would be stronger with measurements from a real inference endpoint.
  2. The fixed-history replay and online benchmark-chain evaluations answer different questions. Replays freeze model outputs and object/Card contents, which is appropriate for isolating scheduling cost but cannot capture how a changed context alters subsequent reasoning, retrieval choices, or task trajectories. The end-to-end chain evaluation addresses this partially, but it is relatively limited in task count and has small completion differences that may be noisy.
  3. The complete benchmark-chain evidence is narrow. The reported chains use Terminal-Bench 2.1, LongMemEval-V2, and SWE-bench. This is a useful spread, but it is not clear how well the method applies to unstructured conversational histories or agent workloads whose context is not naturally partitioned into retrievable objects. The core method depends on identifying structured, versioned payloads that can be externalized.
  4. Some assumptions behind the optimality result are restrictive. The exact stationary optimum assumes stable prefix caching, no retrieval, and a regular stream of eligible objects with fixed-size blocks. The dynamic rule is reasonable as a heuristic extension, but the paper should more clearly separate guarantees under the stationary model from empirical behavior under nonstationary, heterogeneous workloads.
  5. The baseline comparison could better separate scheduling from object externalization. CADOC combines reversible Cards with cache-aware batching. The reported results suggest the scheduler is effective, but a more complete factorial comparison—same Card mechanism with different schedulers, and alternative object-selection policies—would clarify which component contributes most to the gains.
  6. Task performance is close to, but not identical to, full context. For example, CADOC solves 36/89 versus 38/89 tasks on Terminal-Bench and 29/50 versus 31/50 on SWE-bench. These are modest differences, but without repeated runs or uncertainty estimates it is difficult to tell whether the method preserves performance reliably across stochastic agent execution.
Questions for authors
  1. Have you evaluated CADOC against an actual serving stack with prefix caching enabled? How do measured cost and latency compare with the proposed token/cache accounting?
  2. How sensitive are the results to deviations from the assumed cache behavior, including cache expiration, request routing, partial-prefix hits, and retrieval overhead?
  3. Can you report repeated runs or uncertainty estimates for the benchmark-chain task completion results?
  4. Can you isolate the benefit of the batching scheduler from the benefit of reversible object externalization, using matched Cards and object-selection policies?
  5. What happens when object sizes, shortening ratios, and eligibility times vary substantially, or when objects are retrieved repeatedly? Does the online crossing rule remain competitive in these cases?
  6. What classes of agent histories can be converted reliably into structured objects and Cards, and what is the expected performance on histories that are mostly natural-language reasoning rather than tool payloads?
7 comments

We thank the reviewer for the careful reading and for recognizing the distinction between shortening context and reducing actual input cost, the reversible object representation, and the economic interpretation of the commit rule. We address each point below.

W1 / Q1 / Q2: Real serving economics, cache behavior, and retrieval overhead

We agree that measuring cost on a real serving endpoint is important. CADOC is a context-compression method for running agents: it decides when to compress the context during execution, by identifying structured content such as file contents and tool outputs and replacing it with Cards. It aims to reduce cost rather than latency, and it does not model the provider's internal serving mechanisms (e.g., cache expiration, request routing, and cache-hit granularity). Their effect on cost is reflected in the measurements on the actual endpoint below. It's noted that provider billing records are not available for every inference request, although they cover over 90% of all requests.

Measured cost on the actual endpoint. To evaluate the actual endpoint cost, we reran the benchmark chains under FULL and CADOC. The table below reports the token usage returned by the provider and the billed cost for each benchmark, averaged across runs (the repeated runs are detailed in the next point).

BenchmarkArmTotal input tokensCache-hit tokensUncached tokensOutput tokensTotal billed cost
Terminal-Bench 2.1FULL / CADOC400.158 M / 107.619 M329.581 M / 77.576 M70.578 M / 30.043 M297.773 K / 203.925 K523.6560 PU / 97.3151 PU
LongMemEval-V2FULL / CADOC18.427 M / 2.217 M12.162 M / 0.660 M6.265 M / 1.557 M11.546 K / 11.247 K30.5180 PU / 4.1495 PU
SWE-bench VerifiedFULL / CADOC228.384 M / 72.946 M192.275 M / 43.832 M36.110 M / 29.115 M129.756 K / 109.142 K296.0961 PU / 87.3930 PU

These entries use gpt-5.6-terra accessed through an API gateway, and PU denotes the gateway's billing units. On the actual endpoint, CADOC reduces the observed billed cost by 81.4%, 86.4%, and 70.5% on Terminal-Bench 2.1, LongMemEval-V2, and SWE-bench, respectively.

Sensitivity to the accounting assumptions. CADOC remains the lowest-cost policy at every cache-read weight we tested (Appendix H), and 172 of 184 decisions are unchanged under ±5% perturbation of its runtime estimates (Appendix G). The measured costs in the table above further show substantial savings under real caching conditions.

Retrieval overhead. Looking up an object in Working Memory is a local operation that requires no additional LLM call (Section 2), and all reported costs already include the agent requests that carry retrieved payloads and their later replacement by retrieval receipts (Section 6). In the new runs, CADOC makes 5.00 ± 3.61, 12.00 ± 5.70, and 0.33 ± 0.58 retrieve_object calls per run on Terminal-Bench, LongMemEval, and SWE-bench, respectively. With these retrievals included, CADOC's billed cost remains well below that of FULL.

Revision. We have added the measured-cost table and the retrieval counts to Appendix C.1-C.2.

W4: Scope of the optimality guarantees

Thank you for this helpful suggestion, and we agree that the paper would benefit from making this distinction clearer. Our intention with Proposition 1 is to characterize the optimal batch in the stationary setting, which serves as a useful reference point for the online rule. For more general settings, Proposition 2 (Appendix A.4) offers a competitive bound for the online rule, and Sections 4–5 complement this with evaluations on nonstationary, heterogeneous agent histories. In revision, we clarify these assumptions at the end of Appendix A. Section 4 and Appendix D evaluate the rule empirically on heterogeneous workloads.

W2 (first part): Replay and closed-loop evaluations answer different questions

We agree that replay cannot capture how a changed context alters later reasoning, retrieval, or task trajectories. This is why we pair it with closed-loop benchmark chains (Section 6), in which each arm develops its own trajectory, so any change in model behavior is reflected in both cost and task completion. To account for run-to-run variation in closed-loop execution, we have repeated the benchmark chains across multiple runs, as reported in the previous point.

W2 (second part) / W6 / Q3: Repeated runs and uncertainty

To assess run-to-run variation, we repeated the benchmark evaluations using gpt-5.6-terra, with identical task lists and configurations across runs. We conducted 3 runs per arm for Terminal-Bench 2.1 and SWE-bench , and 5 runs per arm for LongMemEval-v2, as the former two benchmarks incur substantially higher evaluation costs. We report the mean and standard deviation of solved tasks across runs.

BenchmarkRuns per armFULL solvedCADOC solvedInput-cost reduction
Terminal-Bench 2.1342.00 ± 6.0839.00 ± 6.0871.14 ± 6.44%
LongMemEval-v2511.00 ± 0.0010.60 ± 0.8976.98 ± 6.55%
SWE-bench333.00 ± 1.0032.33 ± 1.5359.73 ± 7.66%

The repeated experiments demonstrate that CADOC robustly preserves task performance while achieving substantial cost reductions across all three benchmarks. The relatively high variance on Terminal-Bench 2.1 is not specific to CADOC, as the FULL baseline exhibits similarly large standard deviations, suggesting that the variability primarily stems from the benchmark itself rather than CADOC.

Difference from the original results. The reruns were conducted approximately four months after the original experiments, using the same task lists, CADOC scheduling configuration, and cost accounting. However, both FULL and CADOC exhibited substantial changes in their execution trajectories, suggesting that changes in the API serving stack or underlying model backend may have contributed to the differences.

For example, on LongMemEval, FULL's model requests increased about 42% on average, while its average input length decreased 38% on average. CADOC's requests decreased about 48%, with average input length decreasing about 34%. These changes in both arms suggest that the execution environment may have shifted between evaluations.

A concrete example is LongMemEval task 3a7a7880. In the original CADOC run, the agent made 55 model requests before failing. In the five reruns, it averaged only 8.2 requests, but still failed the task. This single task illustrates how changes in execution trajectories can substantially affect measured costs even when task outcomes remain unchanged.

We therefore report repeated evaluations to account for execution variability and use fixed-trajectory replay to independently verify the effectiveness of CADOC's compression scheduling.

W3 / Q6: Applicability to unstructured histories

Which histories can be converted. Because eligible objects include file contents, code, tool results, logs, tables, and generated artifacts (Section 2), CADOC applies directly to tool- and artifact-heavy agent workloads, such as software engineering, command-line tasks, and search or memory tasks over tool outputs.

As quantified in Appendix C.4 (Table 7), eligible structured objects account for 60.81%, 95.50%, and 68.62% of input tokens on Terminal-Bench 2.1, LongMemEval-V2, and SWE-bench Verified, respectively. For dialogue-dominated histories with few eligible objects, CADOC performs fewer replacements and its potential savings are correspondingly limited.

Extending the compression target to whole conversations. We conducted a stratified replay pilot on 27 trajectories from three additional agent benchmarks, MemoryArena, EvoMemBench, and AgencyBench, covering nine task types (three per type). Each compression replaces the entire history prefix, including user and assistant dialogue and tool calls/results, with a semantic summary, while retaining fixed system/developer instructions, tool definitions, and the protected recent history. All strategies use the same summarizer, DeepSeek-v4.1-flash. Each summary is generated from the archived original prefix, and the cost of rereading that prefix is included. The table reports savings relative to FULL.

StrategyNet cost saving
Dynamic-Summary (CADOC)6.82%
Immediate−468.88%
Fixed-10−42.25%
Fixed-20−13.58%
Tokens-32768−8.00%

We provide detailed results and experimental settings in the appendix. This shows that CADOC's dynamic commit scheduling also works when the compression target extends beyond structured objects.

W5 / Q4: Separating scheduling from object externalization

Matched Cards and object-selection policy. Thank you for this suggestion. We would like to clarify that our primary contribution is the dynamic compression scheduling mechanism, rather than object externalization itself.

1. Isolating the scheduling benefit. In our controlled replay experiments, all policies use identical object-selection rules and Card representations, differing only in compression timing (Sections 5 and 6.1). We further evaluate this comparison on 254 test segments (Appendix D):

PolicyInput-token reductionInput-cost saving
FULL0.00%0.00%
Immediate32.15%−11.30%
CADOC27.83%7.42%

Despite removing fewer tokens, CADOC reduces input cost by 16.82% relative to Immediate, demonstrating the independent benefit of compression scheduling. Additional decision-rule ablations are provided in Appendix D.4.

2. Validation across different settings. Our new Monte Carlo simulations (Section 4, Figure 3) confirm the theoretically predicted square-root scaling law and show that CADOC achieves near-optimal costs even when the optimal fixed batch size varies substantially. Large-scale trajectory replay (Appendix D.2) further shows that CADOC matches or outperforms the best hindsight-selected fixed strategy in 7 of 8 settings, without per-setting tuning.

3. Generalization to other compression methods. We also extend CADOC's scheduling rule to LLM-based conversation summarization, without structured-object identification. The results, including summary-generation costs, are:

StrategyNet cost saving
Dynamic-Summary (CADOC)6.82%
Immediate−468.88%
Fixed-10−42.25%
Fixed-20−13.58%
Tokens-32768−8.00%

Detailed settings and results are provided in Appendix D.5 (Table 9).

Together, these results demonstrate that dynamic scheduling independently improves compression efficiency and generalizes beyond structured Cards.

Q5: Heterogeneous Contexts and Repeated Retrieval

Thank you for this question. We further evaluate the robustness of CADOC's online scheduling rule under heterogeneous context dynamics through Monte Carlo simulations and large-scale trajectory replay.

Monte Carlo simulations. In Section 4 (Figure 3), we consider two block-length distributions with different means and variances, three compression ratios, and eight hot-tail settings. CADOC consistently achieves near-optimal costs even when the optimal fixed batch size varies substantially across configurations. The observed batch sizes also follow the square-root scaling predicted by Proposition 1.

Large-scale trajectory replay. We further evaluate CADOC on 353 trajectory segments covering nine task types with heterogeneous object sizes, shortening ratios, and eligibility patterns. We compare CADOC against six fixed-batch sizes, six token thresholds, and Immediate. The following table compares CADOC with the best fixed-rule strategy selected in hindsight on the 254 test segments:

Hot-tail hhBest fixed-rule savingCADOC saving
119.43%19.43%
212.50%12.29%
48.08%9.26%
84.88%7.42%
16, 32, 64, 1284.45%6.80%

CADOC matches or outperforms the best hindsight-selected baseline in most settings. Detailed experiments and sensitivity analyses are provided in Appendix D.2–D.3.

Repeated retrieval. Retrieved objects re-enter the context as new occurrences and follow the same compression lifecycle (Appendix A.3 and E). In our repeated LongMemEval-V2 evaluations, CADOC performs 12.00±5.7012.00 \pm 5.70 retrievals per run while achieving 76.98±6.5576.98 \pm 6.55% input-cost savings, including the costs of restored content.

Together, these results demonstrate that CADOC remains highly competitive across heterogeneous workloads and retrieval-intensive executions, without requiring workload-specific batch-size tuning.

We sincerely thank the reviewer for the constructive feedback and hope that our responses and additional experiments have adequately addressed your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Additional Experiments

We thank the Area Chair and the reviewers for their constructive feedback. We added three sets of experiments and clarified the scope of our theoretical results.

1. Monte Carlo simulations (Section 4, Figure 3, and Appendix I). We varied inference-block lengths, retention ratios, and hot-tail lengths. The results support the predicted square-root relationship between mean compression batch size and hot-tail length. Across these settings, CADOC’s cost stayed close to that of the best tested fixed batch size, even as that batch size varied substantially.

2. Large-scale trajectory replay (Appendix D). We collected 353 trajectory segments covering 8,617 inference calls across nine task types from three additional benchmarks. On the 254 held-out segments, CADOC matched or outperformed the best fixed rule selected in hindsight in most hot-tail settings. At h=8h=8, with identical Cards and object-selection rules, CADOC reduced input cost by 16.82% relative to Immediate, isolating the benefit of scheduling.

3. Repeated benchmark evaluations (Section 6, Table 1, and Appendix C). We ran FULL and CADOC three times each on Terminal-Bench 2.1 and SWE-bench Verified, and five times each on LongMemEval-V2. Relative to mean FULL cost, CADOC reduced modeled input cost by 71.14 ± 6.44% on Terminal-Bench, 76.98 ± 6.55% on LongMemEval, and 59.73 ± 7.66% on SWE-bench (mean ± SD). Mean task completion rates were within 3.4 percentage points of FULL on all three benchmarks.

4. Theoretical scope and additional evidence (Appendices A–D). At the end of Appendix A, we distinguish the stationary optimum, the competitive bound for the reduced waiting–setup objective, and the settings evaluated empirically. We also added an object-level replay example, structured-object coverage statistics, task-level failure analyses, and scheduling-rule ablations. In a 27-segment pilot using LLM-generated conversation summaries (Appendix D.5, Table 9), CADOC saved 6.82% relative to uncompressed replay after accounting for summary generation. All four alternative schedules increased cost.

We appreciate the reviewers’ suggestions and hope that our responses and revisions address their questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.