PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Junjie Yao, Zhangchen Zhou, Zhi-Qin John Xu

arXiv:2609.37012v1cs.AI

TL;DR

Long-horizon agents resend history with every request, but context limits task length and long histories challenge effective use of relevant information. CADOC replaces structured objects with compact Cards while preserving exact retrieval, scheduling batches to balance waiting costs against shared cache-reconstruction costs. Across evaluations, it achieves the lowest aggregate input cost among compared configurations while maintaining task performance close to full context.

  • Problem

    Long-horizon agents resend history with every request, while context limits task length and models struggle to use relevant information in long histories.

    Source: §1 · p. 1

  • Method

    CADOC is an online scheduler that replaces structured objects with retrievable Cards and batches edits by balancing accumulated waiting cost against shared cache-reconstruction cost.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Approximately 40% lower input costs while maintaining comparable task performance; CADOC also achieves the lowest cost among compared commit policies across diverse workloads and settings.

    Source: §1 · p. 2

  • Takeaways & Limitations

    CADOC provides a cost-derived approach to recoverable, cache-aware context management, with the scheduling rule recovering the optimal integer batch under stationary assumptions.

    Source: §7 · p. 9

    The stationary-model optimality analysis assumes fixed-length blocks, stable prefix caching, no retrieval, and an indefinitely continuing stream.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

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.

1 INTRODUCTION

Long-horizon agents resend their histories, while context limits and difficulty using long histories make context management affect both cost and performance. CADOC batches reversible object replacements to balance shared cache-reconstruction costs against the cost of waiting; evaluations report lower input costs with task performance close to full context.

1 INTRODUCTION

  • Context is a bottleneck because each request resends history, retained tokens incur costs even on cache hits, and long histories challenge relevant-information use.The context window also limits task length, so context management affects both cost and performance.Source: §1 · p. 1
  • Structured objects such as code, files, logs, and tool outputs can be replaced by compact Cards while their exact originals remain retrievable.This contrasts with lossy compression methods that discard details a later step may need.Source: §1 · p. 1
  • Immediate replacement cuts cumulative input tokens by 55.93% but raises input cost by 3.67% versus Full Context.Editing an earlier object can invalidate the cached suffix, while waiting keeps payloads in intervening requests.Source: §1 · p. 1, Figure 1 · p. 2
  • CADOC dynamically batches object replacements by balancing shared cache-reconstruction cost against the accumulated cost of delaying compression.Its scheduling decisions use current shortening and cache estimates rather than forecasts or a preset batching interval.Source: §1 · p. 2
  • Approximately 40% lower input cost while maintaining comparable task performance; CADOC also achieves the lowest cost among compared commit policies across diverse workloads and settings.The evaluation uses continuing task chains and fixed-history replays; CADOC adapts timing without future information, extra scheduling calls, or per-setting batch-size tuning.Source: §1 · p. 2

2 OBJECTS, CARDS, AND THE HOT TAIL

CADOC shortens visible context by replacing structured objects with Cards while preserving exact retrieval of their original contents. It protects recent raw history and commits eligible replacements in batches.

2 OBJECTS, CARDS, AND THE HOT TAIL

  • Cards replace structured objects in their original history positions, while Working Memory retains the original bytes for exact retrieval.Retrieval returns the immutable version observed at that point, even if the file later changes.Source: §2 · p. 2
  • A Card records an object’s identity, version, source, and structural metadata rather than an LLM-generated synopsis.The model can retrieve the original through an ordinary function tool using the object reference and a reason.Source: §2 · pp. 2–3
  • Batching lets replacements share cache-reconstruction cost, while waiting to form a batch keeps removable payloads in intervening inputs.The scheduling rule balances these costs and is summarized by the cached interval and batch-commit figure.Source: Figure 2 · p. 3, §2 · p. 3
  • A recent raw suffix is protected by a maximum block count and token budget; objects that leave it remain raw until a batch commit replaces them with Cards.The protected suffix is the hot tail; objects outside it form the pending sequence.Source: §2 · p. 3

3 CACHE-AWARE BATCH SCHEDULING

CADOC batches object replacements to share cache-reconstruction costs while limiting the cost of leaving removable payloads in intervening requests. Its online rule balances these costs using current estimates, matching the optimal integer batch under stationary assumptions.

3 CACHE-AWARE BATCH SCHEDULING

  • Batching shares hot-tail reconstruction costs, while waiting keeps removable payloads in every intervening input.The stationary trade-off is between a shared per-object cost that falls with batch size and waiting loss that rises with batch size.Source: §3 · p. 3, §3.2 · p. 4

3.1 REPLACEMENT CHANGES BOTH PROMPT LENGTH AND CACHE REUSE

  • A replacement changes both prompt length and cache reuse: editing an otherwise reusable prefix requires fresh processing of the remaining interval.The comparison accounts for cached-token cost when keeping the interval and fresh processing of the shortened interval when replacing it; auxiliary commit cost is optional, and the input-token accounting sets it to zero.Source: §3.1 · pp. 3–4

3.2 STATIONARY MODEL AND THE EOQ CORRESPONDENCE

  • Under stationary assumptions, the EOQ trade-off yields a continuous batch-size minimizer, and the discrete cost differences identify an optimal integer batch.Larger shared reconstruction costs favor larger batches, while larger per-request savings favor earlier commits.Source: §3.2 · pp. 4–5

3.3 FROM THE STATIONARY OPTIMUM TO AN ONLINE RULE

  • CADOC applies a first-crossing rule to current shortening, accumulated waiting loss, and estimated shared reconstruction cost; it commits the pending sequence when waiting no longer pays.The crossing recovers the stationary optimum exactly; in changing histories, timing adapts to observed estimates, with hard capacity limits able to force an earlier commit.Source: §3.3 · p. 5

4 FIXED-HISTORY EVALUATION OF COMMIT SCHEDULING

On fixed-history HCE replays, CADOC has the lowest aggregate input cost across tested hot-tail settings without per-setting batch-size tuning. Fixed-batch performance varies with the hot-tail setting, while CADOC adjusts its batch sizes.

4.1 PROTOCOL AND COMPARED POLICIES

  • HCE replay compares commit policies on identical source histories, with model outputs, object versions, and Card contents frozen and costs computed at wr = 0.1.The replay tests h ∈ {2, 4, 8, 16}; the compared policies include Full Context, Immediate, fixed batches, token thresholds, and CADOC.Source: §4.1 · p. 6

4.2 AGGREGATE COST AND SENSITIVITY TO BATCH SIZE

  • CADOC saves 30.65%, 20.61%, 15.14%, and 11.56% relative to Full Context at h = 2, 4, 8, and 16, respectively, and has the lowest aggregate input cost at each setting.The comparison covers all evaluated configurations and requires no per-setting batch-size tuning.Source: §4.2 · p. 6, Figure 3 · p. 6
  • Fixed batches can lose their benefit or increase cost as the hot-tail setting changes, whereas CADOC’s mean batch size rises from 1.50 to 3.25, 4.75, and 5.00 blocks as h increases.CADOC’s total commit count falls from 20 to 3; the reported trend agrees with the stationary prediction that a larger hot tail raises shared reconstruction cost and favors larger batches.Source: §4.2 · p. 6, Figure 4 · p. 7

5 SYSTEM-LEVEL EVALUATION ON BENCHMARK CHAINS

Across benchmark chains, CADOC lowers input costs relative to FULL while keeping task completion close; offline replay also finds the lowest aggregate cost across all three benchmark histories.

5 SYSTEM-LEVEL EVALUATION ON BENCHMARK CHAINS

  • Benchmark chains retain history across fixed task lists; each arm follows its own trajectory, and costs include retrieved payloads and later retrieval receipts.Costs cover every evaluated input request under Equation (1) with wr = 0.1.Source: §5 · p. 7

5.1 TASK PERFORMANCE AND LONG-HORIZON COST SAVINGS

  • 34.12–47.13% input-cost reductions relative to FULL accompany task-completion decreases of at most four percentage points.Table 1 reports the complete benchmark-chain results.Source: §5.1 · p. 7, Table 1 · p. 7
  • As tasks accumulate, CADOC’s cumulative input cost grows more slowly than FULL’s, and the gap widens.Figure 5 plots cumulative input cost against completed tasks.Source: §5.1 · p. 7, Figure 5 · p. 8
  • On LongMemEval-V2, CADOC preserves every task-level outcome across 40 retrieval events in 146 requests while reducing input cost by 42.40%.Reported costs include retrieval requests; a recorded case also verifies byte-exact recovery and successful downstream use.Source: §5.1 · pp. 7–8

5.2 REPLAY ON BENCHMARK HISTORIES

  • CADOC achieves the lowest aggregate input cost among evaluated configurations on all three benchmark histories.Replay reconstructs successive inference boundaries chronologically and holds recorded agent behavior fixed.Source: §5.2 · p. 8

6 RELATED WORK

Prior context-management systems compress, consolidate, or externalize history, while CADOC distinguishes itself through cost-derived commit scheduling for deterministic object replacements.

6 RELATED WORK

  • Prior systems span lossy compression, compact memory, external memory, and cache-aware editing; Self-GC forecasts reuse while TokenPilot uses an empirically chosen check interval (Hao et al., 2026; Xu et al., 2026).The cited approaches include ReSum, MEM1, ACON, Context-Folding, AgentFold, ContextBudget, MemGPT, Pichay, and LCM.Source: §6 · p. 8
  • Figure 6 covers input-cost savings from offline replay of FULL’s retained conversation histories on three benchmarks.The caption identifies the replay scope, not a specific policy outcome.Source: Figure 6 · p. 9
  • CADOC separates replacement eligibility from commit timing and triggers batches using waiting cost, token shortening, and shared cache-reconstruction cost.This supports online adaptation without future-reuse forecasts or LLM calls.Source: §6 · p. 9

7 CONCLUSION

CADOC combines recoverable Cards with online, cost-derived scheduling, achieving low input cost while keeping task performance close to FULL.

7 CONCLUSION

  • CADOC replaces structured objects with retrievable Cards and balances accumulated waiting loss against shared reconstruction cost to schedule commits.Scheduling needs no future information, scheduling LLM calls, or per-setting batch-size tuning.Source: §7 · p. 9
  • Under stationary assumptions, CADOC’s scheduling rule recovers the optimal integer batch.The conclusion presents this as a cost-derived commit rule.Source: §7 · p. 9
  • Across three continuing benchmark chains, CADOC reduces input cost by 34.12–47.13% while maintaining task performance close to FULL.Benchmark-history replays also yielded the lowest aggregate input cost among evaluated policies.Source: §7 · p. 9

AI USE STATEMENT

The statement reports that ChatGPT with gpt-5.6-sol assisted with manuscript drafting and writing improvement.

AI USE STATEMENT

  • ChatGPT with gpt-5.6-sol assisted with drafting the manuscript and improving the writing.The statement identifies writing assistance.Source: AI USE STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

The section identifies supplementary materials and formalizes the cost decomposition, stationary batch optimum, and online quantities used to schedule commits.

REPRODUCIBILITY STATEMENT

  • The supplement provides derivations, configurations, aggregate results, a retrieval case, and runtime diagnostics, with proofs in Section A.Configuration details are in Section B.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 A COMMON REFERENCE FOR COMPARING SCHEDULES

  • An ideal first-eligible replacement schedule provides a batch-independent reference, separating excess cost into delayed shortening and cache reconstruction.The cost difference is tracked through pending removable tokens and additional uncached tokens under stable prefix reuse.Source: §A.1 · p. 12

A.2 STATIONARY OPTIMUM AND FIRST CROSSING

  • Under stationary assumptions, the optimal batch is the smallest positive integer whose accumulated waiting cost reaches the shared reconstruction cost.Ties select the smaller adjacent batch; a fixed cap truncates the selected size.Source: §A.2 · pp. 12–13

A.3 ONLINE QUANTITIES AND LEDGER UPDATES

  • For heterogeneous blocks or nonlinear overhead, pending-region cost can vary, so runtime applies the shared-cost crossing using current estimates.The online ledger accumulates cached-retention cost for raw pending contents and clears entries after a confirmed commit.Source: §A.3 · pp. 13–14

A.4 A COMPETITIVE BOUND FOR THE WAITING–SETUP OBJECTIVE

The section models online batching as a trade-off between retaining eligible objects raw and paying shared setup costs, then bounds the threshold rule against an offline schedule.

A.4 A COMPETITIVE BOUND FOR THE WAITING–SETUP OBJECTIVE

  • The objective sums per-request costs for objects left pending and setup costs at commit boundaries, with objects allowed to remain raw at the horizon.Eligibility, object gains, and setup costs are schedule-independent, and either action is feasible at every boundary.Source: §A.4 · p. 14
  • The rule commits a nonempty pending batch when accumulated waiting cost plus its current retention cost reaches the setup cost.For positive setup costs bounded between Qmin and Qmax, the rule is 2Qmax/Qmin-competitive; for constant positive setup cost, it is 2-competitive.Source: §A.4 · p. 14
  • Each completed phase costs at most 2Qmax, and phase costs can be assigned to offline setup or waiting costs to establish the competitive bound.The same bound holds after adding a nonnegative pending-region cost shared by every feasible schedule.Source: §A.4 · pp. 14–15

B EXPERIMENTAL CONFIGURATION AND EVALUATION PROTOCOLS

This section specifies replay protocols and reports benchmark, retrieval, continuation-quality, scheduling-decision, and cache-read-weight evaluations.

B EXPERIMENTAL CONFIGURATION AND EVALUATION PROTOCOLS

  • Benchmark chains retain history across 89 Terminal-Bench, 18 LongMemEval-V2, and 50 SWE-bench tasks; HCE costs aggregate three frozen histories across four hot-tail settings.The continuation comparison pools 93 evaluations across 31 probes and averages scores by probe, history, and repeats.Source: B EXPERIMENTAL CONFIGURATION AND… · p. 15

B.1 FIXED-HISTORY REPLAY OF BENCHMARK TRACES

  • The benchmark replay replays 1,801 recorded FULL request boundaries with fixed outputs and Cards, continuing context and cache state across tasks without model calls.It uses h = 8 and wr = 0.1.Source: §B.1 · p. 15

C OBJECT IMPLEMENTATION AND RECORDED RETRIEVAL

  • 9,925 UTF-8 bytes are identical by recomputed SHA-256 before and after retrieval; the task completes correctly with a 2,473-token object and 174-token Card.The retrieved content supplies the trajectory and state location used by the next action.Source: C OBJECT IMPLEMENTATION AND RECORDED… · p. 16

D AGGREGATE HCE CONTINUATION QUALITY

E RECORDED SCHEDULING DECISIONS

  • Across 184 nonempty-pending boundaries, W + 0.1G − Q reproduces every recorded decision, and 172 decisions withstand independent ±5% perturbations.At one recorded crossing, five objects totaling 15,006 raw tokens become 764 Card tokens, a 94.91% reduction.Source: E RECORDED SCHEDULING DECISIONS · pp. 16–17

F SENSITIVITY TO CACHE-READ WEIGHT

Related papers

Loading 2609.37012v1…