Sequential computation increasingly produces long traces containing nested branches, status transitions, textual payloads, and compact summaries of earlier execution. This paper introduces budgeted dynamic trace structures (BDTS), a data-structural framework for maintaining rooted trace graphs and append-only histories under an explicit byte or token budget. BDTS combines status-filtered reachability, cursor pagination, soft-capped recency logs, reference-counted observation keys, delta overlays, bounded cost caches, and summary-plus-suffix compaction. We give formal invariants, asymptotic bounds, and an ancillary Rust implementation with reproducible benchmarks. Across synthetic traces with 10,000-40,000 vertices, the prototype builds graphs in 0.58-2.72 ms, enumerates all descendants in 0.24-1.42 ms, and compacts histories of 350k-2.71M approximate tokens to 1,048-4,120 approximate tokens. Tokenizer and forward measurements with three public model targets reduce 3,359-3,360 trace tokens to 432-433 tokens.