Source-linked AI summary
TrajectoryDB: A New Database for Agent Trajectories
Yunjia Zheng, Juncheng Yang
TL;DR
Agent trajectories are valuable for downstream tasks, but existing systems fragment their data and do not jointly support their structure, semantics, and lineage. The paper envisions TrajectoryDB, which co-designs ingestion, storage, and query processing for trajectories. Its conclusion is that trajectories warrant treatment as a distinct data type and a trajectory-native management system.
Problem
Existing systems fragment raw trajectories, derived state, telemetry, and processing, while trajectory queries combine structural traversal, semantic predicates, temporal order, and provenance.
Source: §1 · pp. 1–2Method
TrajectoryDB treats raw trajectories and derived data as first-class and co-designs ingestion, storage, and query processing around trajectory-specific patterns.
Source: §1 · p. 2Results
The paper concludes that trajectories are a distinct data type whose combined structure, text, and lineage properties are not supported together by existing database systems.
Source: §6 · p. 6Takeaways & Limitations
TrajectoryDB aims to make agent trajectories as natural to store, query, and optimize as documents are in document databases or time-series data are in time-series databases.
Source: §1 · p. 2
Abstract
from arXiv · showhide
AI agents generate rich execution trajectories that capture their interactions with large language models, tools, and external environments. These trajectories are increasingly valuable for downstream tasks such as memory extraction, model fine-tuning, runtime optimization, and security and cost monitoring. Yet trajectory data today is fragmented across files, databases, and observability systems, with no persistent data management system designed around its unique structure and access patterns. We argue that trajectories should be treated as a distinct data type. A trajectory combines hierarchical execution structure, large volumes of text whose analysis often requires semantic reasoning, and rich dependencies and lineage among events, intermediate states, and derived artifacts. These properties introduce new requirements throughout the data lifecycle. Ingestion must reconstruct and preserve execution structure and lineage; storage must efficiently organize large but highly redundant contexts while maintaining relationships among records; and query processing must jointly reason over structure, temporal order, semantics, and lineage. We therefore envision TrajectoryDB, a trajectory-native data management system that co-designs ingestion, storage, and query processing to efficiently manage and analyze agent execution trajectories.
1 INTRODUCTION
Agent trajectories are valuable records for learning, behavior analysis, and runtime optimization, but existing tools manage only fragments of their lifecycle. TrajectoryDB is envisioned as a trajectory-native system that co-designs ingestion, storage, and query processing.
1 INTRODUCTION
- Trajectories support memory extraction, fine-tuning, failure diagnosis, safety control, performance diagnosis, cost attribution, and resource-aware scheduling.Source: §1 · p. 1
- Existing approaches split raw trajectories, derived state, telemetry, and processing logic across files, databases, and scripts.File pipelines preserve raw data but offer little reusable derived state or declarative querying; memory systems persist task-specific state, while log stores focus on individual events.Source: §1 · p. 1
- Trajectories combine nested execution structure, semantic text, repeated context, and derived state with lineage requirements.Queries may need to jointly consider structure, order, semantics, redundancy, and provenance.Source: §1 · p. 1
- TrajectoryDB treats raw trajectories and derived data as first-class citizens in a trajectory-native data management system.Source: §1 · p. 2
- Its unified data model and query operators jointly represent and reason over execution structure, temporal relationships, semantic annotations, and derived state.Source: §1 · p. 2
- TrajectoryDB co-designs ingestion, storage, and query processing around trajectory-specific access patterns and redundancies.Source: §1 · p. 2
2 TRAJECTORY AS A NEW DATA TYPE
An agent trajectory records model and environment interactions in a hierarchy of sessions, turns, steps, and messages, with branches and associated execution metadata. Such records support learning from experience, behavior analysis, and runtime monitoring and optimization.
2.1 Agent Trajectory
- A trajectory consists of requests, messages, and tool executions produced while completing a task, organized into steps, turns, and sessions.Execution configuration and operational telemetry are queried alongside the trajectory.Source: §2.1 · p. 2
- Trajectories can branch into a tree of sessions, while each session follows a session-turn-step-message hierarchy.They also contain semantic content, repeated context, and derived data whose provenance matters.Source: Figure 1 · p. 2
- Runtime telemetry includes latency, token counts, cache-hit ratios, retries, timeouts, and tool-call resource usage.These measures support service-level and user-experience monitoring, cost and resource optimization, and failure diagnosis.Source: §2.1 · p. 2
2.2 Diverse Use Cases
- Trajectory use cases include extracting reusable memories and fine-tuning from successful trajectories.Other uses include diagnosing failures, enforcing safety, monitoring runtime health, and optimizing system resource use and scheduling.Source: §2.2 · pp. 2–3
3 TRAJECTORY-DB REQUIREMENTS
Trajectory workloads repeatedly access, filter, and aggregate overlapping trajectory data. Database support should expose its hierarchy and preserve ordered event patterns across heterogeneous records.
3 TRAJECTORY-DB REQUIREMENTS
- Trajectory workloads repeatedly access, filter, and aggregate overlapping parts of a trajectory, motivating common database requirements.Source: §3 · p. 3
3.1.1 Session-structure retrieval.
- Explicit session, turn, step, and message structure supports retrieval at different granularities and preserves subagent parent-child branches.Role attributes also allow fine-tuning workloads to select assistant messages efficiently.Source: §3.1.1 · p. 3
- Trajectory workloads detect patterns over ordered, heterogeneous events, including tool-use sequences, role-spanning safety checks, and operational recovery behavior.These queries depend on preserving execution order.Source: §3.1.2 · p. 3
3.2 LLMs as UDFs
LLM-based semantic evaluation can serve as a reusable query primitive over free-form text. Its results must compose with relational and order-sensitive operations and update as trajectories accumulate evidence.
3.2 LLMs as UDFs
- An LLM-based semantic-analysis UDF can express predicates over free-form text and compose with other query operators.Source: §3.2 · p. 3
3.2.1 Composing semantic and relational operators.
- Semantic judgments can be embedded in relational plans, where assembled context is evaluated and results feed joins, ordering, or aggregation.For example, a query can identify the first violating step or join semantic failure judgments with runtime measurements.Source: §3.2.1 · p. 3
- As new evidence arrives, stateful semantic evaluation updates prior judgments and may revise or invalidate accumulated assessments.Examples include memory validation, safety monitoring, and comparing new failures with recent ones.Source: §3.2.2 · p. 3
3.2.2 Incremental semantic evaluation over growing trajectories.
- The listed system challenges include reconstructing request hierarchies, supporting graph structures over relational data, and storing large text payloads efficiently.They also include reconciling physical layouts, order-sensitive processing, co-optimizing relational and semantic operators, and caching semantic judgments.Source: §3.2.2 · p. 4
3.3 Lineage Query
Lineage queries must recover pre-compaction history and preserve how semantic results were derived. TrajectoryDB’s proposed provenance supports both reevaluation when sources or criteria change and queries about a result’s origins.
3.3 Lineage Query
- Reconstructing pre-compaction context supports diagnosing lost constraints, verifying memory evidence, and replaying alternative compaction strategies [33] [46].The original history identifies which compaction removed relevant information and enables construction of alternative compacted contexts.Source: §3.3.1 · p. 4
3.3.1 Context reconstruction.
- TrajectoryDB should retain each semantic result’s evaluated input, supporting records, judge model, and evaluation criterion to make its derivation reconstructable.Finer-grained lineage can link each extracted memory or failure judgment to its supporting trajectory evidence [13] [46].Source: §3.3.2 · p. 4
- Provenance enables invalidating and reevaluating judgments when source trajectories, judge models, or criteria change, and querying what produced a judgment.This makes semantic judgments reusable derived data rather than outputs of one-time LLM calls.Source: §3.3.2 · p. 4
4 CHALLENGES AND OPPORTUNITIES
This section maps trajectory requirements to key challenges and examines gaps in existing database systems, using a one-month production trace to characterize agent trajectories.
4 CHALLENGES AND OPPORTUNITIES
- The section maps requirements to challenges and discusses where existing database systems fall short.Its characterization uses a one-month trace from the production system.Source: §4 · p. 4
- The production trace is used to characterize agent trajectory behavior.The section presents this characterization alongside its discussion of database-system gaps.Source: §4 · p. 4
- Table 1 presents the mapping from requirements to key challenges.The section uses this mapping to organize its discussion of existing systems.Source: §4 · p. 4
4.1 Structure Reconstruction and Maintenance
TrajectoryDB must reconstruct execution hierarchy from timestamped requests and maintain graph relationships alongside relational and ordered access. The design choices balance ingestion work, long-lived state, and efficient traversal.
4.1 Structure Reconstruction and Maintenance
- TrajectoryDB should reconstruct trajectory structure and organize it logically and physically rather than leave it scattered across timestamped requests.Source: §4.1 · p. 4
4.1.1 Reconstructing Request Hierarchy.
- Generic records leave session, turn, and step relationships implicit, so eager reconstruction simplifies queries but adds ingestion work, while lazy reconstruction shifts cost to queries.The design question is which structural relationships to materialize during ingestion and which to derive lazily.Source: §4.1.1 · p. 4
- Requests from one workflow may be hours or days apart, and sessions can last weeks, so ingestion must retain per-session state without a natural safe cutoff.Short inactivity bounds risk splitting trajectories; long bounds increase the overhead of inactive sessions, while existing stream processors rely on watermarks or grace periods.Source: §4.1.1 · p. 4
4.1.2 Maintaining Graph Structure over Relational Data.
- Subagent branches and lineage create DAGs over trajectory records, making efficient graph traversal and relational analytics a joint design challenge.Relational recursive queries can be costly for deep or branching graphs and may not preserve traversal order; graph-native traversal can add payload I/O, deserialization, or cross-system coordination costs [21]. Trajectories are append-only, mostly forest-shaped, and clustered by session.Source: §4.1.2 · p. 5
4.2 Data Layout and Storage
Trajectory storage must reconcile session-oriented scans, columnar analytics, and graph-linked lineage. It must also manage large cumulative contexts whose sharing is disrupted by mutations, while balancing payload layout and compression.
4.2.1 Reconciling Conflicting Physical Layouts.
- Replay and context reconstruction favor session-contiguous layouts, field-oriented analytics favor columnar layouts, and lineage queries follow graph links; no single layout naturally serves all three.Transactional stores can fit alongside application state, but growing trajectory volumes make large analytical scans expensive.Source: §4.2.1 · p. 5
4.2.2 Storing Large but Redundant Text Payload.
- Storing full cumulative contexts can generate about 35 PB/day under the passage’s 1 GW facility assumptions, while inline payloads risk I/O and cache pollution and separate payloads break session-contiguous scans.The estimate assumes 1,000,000 fully utilized H100s, 2,000 output tokens/s per H100, a 50:1 input-to-output ratio, and approximately four bytes per token. PostgreSQL’s TOAST stores oversized values in chunks accessed through pointers.Source: §4.2.2 · p. 5
- 80% of production sessions mutate their prefix, through compaction, tool-result truncation, or edits to earlier context, disrupting clean prefix sharing.In a sample of 5,951 sessions, 3,794 never forked; the remaining sessions forked into multiple instances and accounted for over 80% of instances, with forks occurring throughout sessions.Source: §4.2.2 · p. 5, Figure 2 · p. 5
- Zstandard compresses exported production PostgreSQL data 20×, versus less than 2× with built-in compression, but block compression and dictionary encoding do not exploit request-level context sharing.TrajectoryDB should exploit known sharing between requests directly rather than rediscovering redundancy from raw bytes or literals within physical blocks [15, 44, 45, 7].Source: §4.2.2 · p. 6
4.3 Query Language and Optimization
Trajectory queries require order-aware execution, joint planning of relational and semantic operators, and safe reuse of semantic results. The section frames these as query-language and optimization challenges for trajectories.
4.3.1 Enabling Order-Sensitive Query Processing.
- Trajectory engines must preserve branch-local order and represent partial order across concurrent branches, while tracking order through operators and lineage traversal.Sequence matching and rolling reward deltas illustrate why order can change query results.Source: §4.3.1 · p. 6
4.3.2 Co-optimization Across Relational and Semantic Operators.
- Relational and semantic operators need joint planning because their execution order trades off cheaper filtering against costly LLM calls.Trajectory queries may pass dynamically constructed subsequences, lineage neighborhoods, or session context to semantic operators; LOTUS defines operators over declared relational inputs.Source: §4.3.2 · p. 6
4.3.3 Caching Semantic Results.
- Trajectory semantic caches must track query semantics, trajectory state, and model configuration to identify stale judgments and refresh only affected results.Input similarity alone is insufficient as new trajectory steps may invalidate cached results; GPTCache and MeanCache are cited as existing semantic caches.Source: §4.3.3 · p. 6
5 RELATED WORK
Related work covers semantic operators, LLM-based document discovery and preprocessing, and data-lineage systems. The cited approaches vary in optimization, operator placement, candidate selection, and lineage capture.
Semantic operators
- LOTUS and Palimpzest provide declarative frameworks for LLM-powered operators over relational data.Abacus formalizes cost-based optimization, PLOP [37] optimizes semantic-operator placement, and UQE screens candidate rows before LLM evaluation.Source: §5 · p. 6
- DocETL uses LLM operators to discover schemas and structure documents into tables, while EVAPORATE generates extraction code for document processing.Source: §5 · p. 6
Data lineage
- Titian captures record-level lineage in distributed dataflows, while Smoke co-designs lineage capture with physical operators for low overhead and interactive queries.Source: §5 · p. 6
- GProM rewrites queries to compute provenance on demand, trading query-time cost for zero capture overhead.Source: §5 · p. 6
6 CONCLUSION
The conclusion presents agent trajectories as a distinct data type whose properties are not jointly supported by existing database systems. It envisions TrajectoryDB co-designing the full data lifecycle.
6 CONCLUSION
- Agent trajectories combine hierarchical execution structure, large volumes of text, and complex lineage among records and derived state.Source: §6 · p. 6
- Existing database systems are not designed to support trajectory structure, text, and lineage together.Source: §6 · p. 6
- TrajectoryDB is envisioned to co-design ingestion, storage, and query processing for managing and analyzing agent trajectories.Source: §6 · p. 6